计算机科学 ›› 2013, Vol. 40 ›› Issue (Z6): 67-69.
郭晶,陈贤富
GUO Jing and CHEN Xian-fu
摘要： 针对遗传算法系统的维持能力问题,提出一种量子演化算法(a Quantum-Inspired Evolutionary Algorithm)用于解决装箱问题的布局与优化。算法中采用量子比特编码、量子延伸变异操作。同时根据装箱问题具体情况,设计相应的量子旋转门更新策略,并在此基础上引入遗传操作,同时提出MCBF算法修复策略。最后,对8个测试数据集进行测试。实验测试结果显示,算法在维持遗传基因种群多样性与提高优化质量等方面效果明显。
| [1] 实例数目总和HGGAMGGAQIEA 最优值运行时间最优值运行时间最优值运行时间 u12020181．701292180．635905200．958405 u250201739．6108231813．803196．937677 u5002018752．0479418108．8121957371164 u100020166572．956217588．8807518585．845125 T6020620．789710．6953181．216115 T120200053．76911222．20842 Total120757387．10583726．5961106684．5369 测试硬件条件为:3.10GHz,3.49G的内存,WIN-XP操作系统,VC＋＋环境。 表4中“最优值”表示该算法成功解决的实例数目,“运行时间”为每个实例每次的平均运行时间。 表4的实验数据显示,QIEA算法在解决数据集u120,u250,u500,u1000时,数据集中每个实例的平均运行时间都小于HGGA算法的平均运行时间,特别是当解决数据集u1000时,QIEA的平均运行时间更是远远小于HGGA算法。 MGGA算法有两个数据集的运行时间要优于QIEA算法,分析可能原因如下:由于QIEA算法引入了量子旋转门更新操作,提高了算法的空间复杂性和计算复杂性,特别是计算时涉及到了浮点运算,因此可能延长算法的执行时间。 由于QIEA算法利用了量子比特编码,因此提高了种群的多样性和系统维持能力,克服了遗传算法的早熟收敛的情况。同时,QIEA算法与HGGA算法相比较,其不需要提前计算所使用箱子数目的上限值,使算法更加简洁。 在解决数据集T60和T120时,QIEA算法的效果更加明显,不仅能成功解决更多的实例数目,而且运行时间更短。 结束语 理论分析与部分实验结果显示,在系统维持能力和种群多样性方面,QIEA算法优于HGGA算法和MGGA算法,面向特种装箱的实验应用方面可以显示良好的优化效果。需要指出的是装箱问题是一个强约束多目标优化经典NP难题,有关一般三维强约束装箱应用问题有待进一步扩展研究。 Beasley J E．OR-Library:Distributing test problems by electronicmail [J]．Journal of Operational Research Society,1990,41(11):1069-1072 (下转第102页)(上接第69页) [2] Singh A,Gupta A K．Two heuristics for the one-dimensionalbin-packing problem [J].OR Spectrum,2007,29(4):765-781 [3] Kuk-Hyun,Kim J-H．Quantum-Inspired Evolutionary Algo-rithm for a Class of Combinatorial Optimization [J].Evolutionary Computation,2002,6(6):580-593 [4] Gu Jin-wei,Gu Man-zhan．Anovel competitive co-evolutionaryquantum genetic algorithm for stochastic job shop scheduling problem[J].Computers and Operations Research,2010,7(5):927-937 [5] Conffman E G,Galambos J G．Bin packing approximation algorithms:combinatorial analysis [M].the Netherlands:Kluwer Academic Publishers,1998:151-207 [6] 杨俊安,庄镇全.量子遗传算法研究现状[J].计算机科学,2003,0(11):13-15 [7] Galinier P,Hao J K.Hybrid evolutionary algorithms for graph coloring[J].Journal of Combinatorial Optimization,1999,3(4):381-383 [8] Han K-H,Kim J-H．Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem [J].Evolutionary Computation,2000,2:1354-1360 [9] 。 表3 修复策略算法结果比较(使用箱子数目的平均值) u120u250u500u1000T60T120T249T502 NFD68．6142．6282．4562．724．648．6100．1201．2 FFD49．8103．1203．9405．423．245．895190．1 BFD49．8103．1203．9405．423．245．895190．1 MFFD49．7103203．6404．923．245．895190．1 CBF49．8103．1203．5405．12345．794．9190．4 MCBF50．8103．4204．5404．421．842．387．2173．9 表3的实验结果显示,MCBF算法除了数据集u120,u500以外,都能得到比其他算法更优的解,且在数据集T60,T120,T249,T501上,解的质量有优。所以本文采用MCBF算法作为QIEA算法的修复策略。 表4是HGGA算法和MGGA算法与本文提出的QIEA算法的实验结果比较。表中HGGA算法和MGGA算法分别运行100次。QIEA算法运行1次,且交叉概率pcross=0.8,量子变异概率pmutation=0.1。 表4 QIEA算法、MGGA算法和HGGA算法的测试比较结果表 数据 集[1]实例数目总和HGGAMGGAQIEA 最优值运行时间最优值运行时间最优值运行时间 u12020181．701292180．635905200．958405 u250201739．6108231813．803196．937677 u5002018752．0479418108．8121957371164 u100020166572．956217588．8807518585．845125 T6020620．789710．6953181．216115 T120200053．76911222．20842 Total120757387．10583726．5961106684．5369 测试硬件条件为:3.10GHz,3.49G的内存,WIN-XP操作系统,VC＋＋环境。 表4中“最优值”表示该算法成功解决的实例数目,“运行时间”为每个实例每次的平均运行时间。 表4的实验数据显示,QIEA算法在解决数据集u120,u250,u500,u1000时,数据集中每个实例的平均运行时间都小于HGGA算法的平均运行时间,特别是当解决数据集u1000时,QIEA的平均运行时间更是远远小于HGGA算法。 MGGA算法有两个数据集的运行时间要优于QIEA算法,分析可能原因如下:由于QIEA算法引入了量子旋转门更新操作,提高了算法的空间复杂性和计算复杂性,特别是计算时涉及到了浮点运算,因此可能延长算法的执行时间。 由于QIEA算法利用了量子比特编码,因此提高了种群的多样性和系统维持能力,克服了遗传算法的早熟收敛的情况。同时,QIEA算法与HGGA算法相比较,其不需要提前计算所使用箱子数目的上限值,使算法更加简洁。 在解决数据集T60和T120时,QIEA算法的效果更加明显,不仅能成功解决更多的实例数目,而且运行时间更短。 结束语 理论分析与部分实验结果显示,在系统维持能力和种群多样性方面,QIEA算法优于HGGA算法和MGGA算法,面向特种装箱的实验应用方面可以显示良好的优化效果。需要指出的是装箱问题是一个强约束多目标优化经典NP难题,有关一般三维强约束装箱应用问题有待进一步扩展研究。 Beasley J E．OR-Library:Distributing test problems by electronicmail [J]．Journal of Operational Research Society,1990,41(11):1069-1072 (下转第102页)(上接第69页)[2]Singh A,Gupta A K．Two heuristics for the one-dimensionalbin-packing problem [J].OR Spectrum,2007,29(4):765-781[3]Kuk-Hyun,Kim J-H．Quantum-Inspired Evolutionary Algo-rithm for a Class of Combinatorial Optimization [J].Evolutionary Computation,2002,6(6):580-593[4]Gu Jin-wei,Gu Man-zhan．Anovel competitive co-evolutionaryquantum genetic algorithm for stochastic job shop scheduling problem[J].Computers and Operations Research,2010,7(5):927-937[5]Conffman E G,Galambos J G．Bin packing approximation algorithms:combinatorial analysis [M].the Netherlands:Kluwer Academic Publishers,1998:151-207[6]杨俊安,庄镇全.量子遗传算法研究现状[J].计算机科学,2003,0(11):13-15[7]Galinier P,Hao J K.Hybrid evolutionary algorithms for graph coloring[J].Journal of Combinatorial Optimization,1999,3(4):381-383[8]Han K-H,Kim J-H．Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem [J].Evolutionary Computation,2000,2:1354-1360[9]Kim B-I,Wy J．Last two fit augmentation to the well-knownconstruction heuristics for one-dimensional bin-packing problem:an empirical study [J]．The International Journal of Advanced Manufacturing Technology,2010,50(9-12):1145-1152 [10] Stawowy A.Evolutionary based heuristic for bin packing problem[J].Computer and Industrial Engineering,2008,5(2):465-474 [11] Bhatia A K,Basu S K．Packing Bins Using Multi-chromosomal Genetic Representation and Better-Fit Heuristic [J].Computer Science,2004,3316:181-186 [12] Chan F T S,Au K C,Chan L Y,et al.Using genetic algorithms to solve quality-related bin packing problem[J].Robotics and Computer-Integrated Manufacturing,2007,3(1):71-72 [13] 陈国良,等.遗传算法及其应用[M]．北京:人民邮电出版社,2001:101-161 [14] Gupta J N D,Ho J C.A new heuristic algorithm for the one-dimensional bin-packing problem[J].Production planning & control,1999,0(6):598-603 |
| No related articles found! |
|
||
首页