Computer Science ›› 2013, Vol. 40 ›› Issue (Z6): 67-69.
Previous Articles Next Articles
GUO Jing and CHEN Xian-fu
[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! |
|