第1期 李波，等：基于单亲遗传算法的动态设备布局仿真研究 ·79 6000 lems and the location of economic activities [J ]Econo- 34000 ◆PGA metrica,1957(25):53.76. 2000 SA [2]ROSENBLATT M J.The dynamics of plant layout [J ] 6 0 合5期 30台10期 /5a Management Science,1986(37):272-286. [3]KUSIA K A,HERA GU S S.The facility layout problem 问题规 [J ]European Journal of Operational Research,1987 (29):229.251. 图13PGA、SA运行时间比较 [4]CONWA Y D G,VEN KATARAMANAN M A.Genetic Fig 13 Time comparison of PGA and SA search and the dynamic facility layout problem[J].Com- A=(C_PGA_c_SA)/c-PGA.(6) puters and Operations Research,1994,21(8):955- 式中：cPGA和cSA分别代表PGA和SA得到的 960. [5]BALA KRISHNAN J,CHEN G C H.Genetic search and 最优成本.△在相同规模问题时的平均值如图14所 the dynamic layout problem:an improved algorithm [J]. 示 Computers and Operations Research,2000(27):587- 593. [6]KA KU B,MAZZOLA J B,A tabur search heuristic for ◆一相对成本增长率 the plant layout problem [J ]INFORMS Journal on Computing,1997,9(4):374-384. 10期 5期 15 30台5期 5台1 30台10期 [7]BA YKASOGU A,NABIL N Z,GIND Y.A simulated 2 6 annealing algorithm for the dynamic layout problem [J]. 问题规模 Computers and Operations Research,2001(28):1403- 1426. 图14相同规模问题的相对成本增长率 [8]BALA KRISHNAN J,CHENG,C H.A hybrid genetic Fig 14 Relative cost growth rate algorithm for the dynamic plant layout problem [J ]In 从图13、14可以看到PGA运行时间随问题规 ternational Journal of Production Economics,2003(86): 模增大而增加的程度远小于SA.在大多数情况下 107.120 PGA能在可以接受的时间内得到更好的优化解.虽 [9]李茂军，童调生.单亲遗传算法及其应用研究U].湖南 然PGA在大规模设备布置问题中的优化解质量不 大学学报，1998,25(6)：56·59. 如SA,但PGA的时间成本随着问题规模的增加， LI Maojun,TONG Tiaosheng.Partheno-genetic algo- rithm and its application [J ]Journal of Hunan Universi- 时间增长率远远小于SA,在30台5期的8个问题 ty,1998,25(6):56.59. 中，PGA花费的平均时间仅仅是SA的19.66%；而 [10]BA YKASOGU A,NABIL N Z.GINDY.Erratum to 在30台10期的8个问题中也只有22.87%，得到 A simulated annealing algorithm for dynamic layout 的最优成本只增加了不到4%.因此，在解决具体问 problem[J ]Computers Operation Research,2004, 题时，还要综合考虑时间成本和优化结果的质量，来 (31):313.315. 对算法进行选择」 作者简介： 李波，女，1967年生，教授，主要 4结束语 研究方向为物流系统规划、物流系统调 通过PGA算法对算例问题的实验运行，可以 度、智能计算与建模.发表学术论文30 看出PGA用于顺序编码的组合优化问题比较一般 多篇，EI检索论文9篇，参与编写教材 GA还是有一定优势的，其时间增加程度一般小于 3部. 其他算法.但在实验中发现，PGA随着编码长度的 Email libo0410 @yahoo.com.cn. 增加（问题规模的扩大）性能下降，所以对大规模设 备布局问题的布置计算，从种群多样性和时间代价 方面来看，应该进一步考虑降低时间复杂度并且增 邱枫，男，1979年生，硕士研究 大搜索空间的算法，这将是下一步研究的目标， 生，主要研究方向为物流与供应链管理、 物流系统规划」 参考文献 E mail qf ll @126.com [1]KOOPMANS T C,BECKMAN M.Assignment prob- 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图 13 PGA、SA 运行时间比较 Fig113 Time comparison of PGA and SA Δ = ( C PGA c S A ) / c PGA . (6) 式中 :c_PGA 和 c_SA 分别代表 PGA 和 SA 得到的 最优成本.Δ在相同规模问题时的平均值如图 14 所 示. 图 14 相同规模问题的相对成本增长率 Fig114 Relative cost growth rate 从图 13、14 可以看到 PGA 运行时间随问题规 模增大而增加的程度远小于 SA. 在大多数情况下 PGA 能在可以接受的时间内得到更好的优化解. 虽 然 PGA 在大规模设备布置问题中的优化解质量不 如 SA ,但 PGA 的时间成本随着问题规模的增加 , 时间增长率远远小于 SA ,在 30 台 5 期的 8 个问题 中 ,PGA 花费的平均时间仅仅是 SA 的 19166 % ;而 在 30 台 10 期的 8 个问题中也只有 22187 % ,得到 的最优成本只增加了不到 4 %. 因此 ,在解决具体问 题时 ,还要综合考虑时间成本和优化结果的质量 ,来 对算法进行选择. 4 结束语 通过 PGA 算法对算例问题的实验运行 ,可以 看出 PGA 用于顺序编码的组合优化问题比较一般 GA 还是有一定优势的 ,其时间增加程度一般小于 其他算法. 但在实验中发现 ,PGA 随着编码长度的 增加(问题规模的扩大) 性能下降 ,所以对大规模设 备布局问题的布置计算 ,从种群多样性和时间代价 方面来看 ,应该进一步考虑降低时间复杂度并且增 大搜索空间的算法 ,这将是下一步研究的目标. 参考文献 : [1 ] KOOPMANS T C , BECKMAN M. Assignment prob2 lems and the location of economic activities [J ]. Econo2 metrica , 1957 (25) :53 - 76. [2 ]ROSENBLA TT M J. The dynamics of plant layout [J ]. Management Science , 1986 (37) :272 - 286. [3 ] KUSIA K A , HERA GU S S. The facility layout problem [J ]. European Journal of Operational Research , 1987 (29) :229 - 251. [4 ]CONWA Y D G, VEN KA TARAMANAN M A. Genetic search and the dynamic facility layout problem[J ]. Com2 puters and Operations Research , 1994 , 21 ( 8) : 955 - 960. [5 ]BALA KRISHNAN J , CHEN G C H. Genetic search and the dynamic layout problem : an improved algorithm [J ]. Computers and Operations Research , 2000 (27) : 587 - 593. [6 ] KA KU B , MAZZOLA J B , A tabu2search heuristic for the plant layout problem [J ]. INFORMS Journal on Computing , 1997 ,9 (4) :374 - 384. [7 ]BA YKASO GLU A , NABIL N Z , GIND Y. A simulated annealing algorithm for the dynamic layout problem [J ]. Computers and Operations Research , 2001 (28) : 1403 - 1426. [8 ]BALA KRISHNAN J , CHEN G, C H. A hybrid genetic algorithm for the dynamic plant layout problem[J ]. In2 ternational Journal of Production Economics , 2003 (86) : 107 - 120. [9 ]李茂军 ,童调生. 单亲遗传算法及其应用研究[J ]. 湖南 大学学报 ,1998 ,25 (6) : 56 - 59. L I Maojun , TON G Tiaosheng. Partheno2genetic algo2 rithm and its application [J ]. Journal of Hunan Universi2 ty , 1998 , 25 (6) : 56 - 59. [10 ]BA YKASO GLU A , NABIL N Z. GIND Y. Erratum to A simulated annealing algorithm for dynamic layout problem[J ]. Computers & Operation Research , 2004 , (31) :313 - 315. 作者简介 : 李 波 ,女 ,1967 年生 ,教授 ,主要 研究方向为物流系统规划、物流系统调 度、智能计算与建模. 发表学术论文 30 多篇 , EI 检索论文 9 篇 ,参与编写教材 3 部. E2mail : libo0410 @yahoo. com. cn. 邱 枫 ,男 , 1979 年生 ,硕士研究 生 ,主要研究方向为物流与供应链管理、 物流系统规划. E2mail : qf_ll @126. com. 第 1 期 李 波 ,等 :基于单亲遗传算法的动态设备布局仿真研究 · 97 ·