面向装箱问题的量子遗传优化算法  

Quantum Genetic Evolutionary Algorithm for Bin Packing Problem

作　　者：郭晶[1] 陈贤富[1] 

机构地区：[1]中国科学技术大学电子科学与技术系,合肥230027

出　　处：《计算机科学》2013年第06A期67-69,102,共4页Computer Science

摘　　要：针对遗传算法系统的维持能力问题,提出一种量子演化算法(a Quantum-Inspired Evolutionary Algorithm)用于解决装箱问题的布局与优化。算法中采用量子比特编码、量子延伸变异操作。同时根据装箱问题具体情况,设计相应的量子旋转门更新策略,并在此基础上引入遗传操作,同时提出MCBF算法修复策略。最后,对8个测试数据集进行测试。实验测试结果显示,算法在维持遗传基因种群多样性与提高优化质量等方面效果明显。Aiming at the problem of the genetic algorithm＇s system maintenance ability, the paper presented a quantum- inspired evolutionary algorithm for layout and optimization of bin packing problem. This algorithm adopts quantum bit coding and quantum improving mutation. According to the specific situation of bin packing problem, the corresponding rotation gate updating strategy was devised and genetic operation was introduced. Furthermore a new repair strategy called modified complete and best fit algorithm were proposed. Finally, the eight testing sets were tested. The experimental results show this algorithm has a higher performance in maintaining the population diversity of genetic gene and improving the quality of optimization.

关 键 词：量子演化 遗传操作 装箱问题 种群多样性 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]