首页 | 本学科首页   官方微博 | 高级检索  
     

求解TSP的量子遗传算法
引用本文:王宇平,李英华.求解TSP的量子遗传算法[J].计算机学报,2007,30(5):748-755.
作者姓名:王宇平  李英华
作者单位:1. 西安电子科技大学计算机学院,西安,710071
2. 西安电子科技大学计算机学院,西安,710071;大连理工大学数学系,辽宁,大连,116024
摘    要:量子遗传算法(QGA)在求解数值和组合优化问题时效率明显优于传统进化算法,但目前较多被用于求解组合优化的背包问题,为了充分发挥QGA的优点,文中用其求解TSP这一经典的NP难问题.首先,文中设计了一种利用几率幅值编码的新的编码方式,即利用几率幅值编码的量子个体与一组向量对应,而此向量又与一条可行路径一一对应.这样的编码方式不仅缩小了种群规模,占用较少内存,所得的解均可行,而且有效地增强了种群的多样性;其次,在量子个体上实施量子杂交,这一操作有利于保留相对较好的基因段;最后,为了加快算法的收敛速度,引入两阶段局部搜索,第一阶段主要针对实例中排列稀疏处的城市进行优化,第二阶段在第一阶段的基础上着重对排列密集处的城市优化.据此,设计了解TSP的一个新的高效的QGA,并证明了其以概率1收敛到全局最优解;测定算法性能的数值实验数据表明,该算法在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.

关 键 词:量子遗传算法  量子比特  TSP  组合优化  求解  量子遗传算法  Quantum  Genetic  Algorithm  全局最优解  情况  迭代次数  数据表  数值实验  算法性能  测定  收敛速度  以概率  二阶  优化  城市  搜索  局部  两阶段  基因  操作
修稿时间:2004-08-102006-07-05

A Novel Quantum Genetic Algorithm for TSP
WANG Yu-Ping,LI Ying-Hua.A Novel Quantum Genetic Algorithm for TSP[J].Chinese Journal of Computers,2007,30(5):748-755.
Authors:WANG Yu-Ping  LI Ying-Hua
Abstract:Quantum genetic algorithm(QGA) was proved to be better than the conventional genetic algorithms on numerical and combinational optimization problems,but it is usually used to solve the knapsack problems of the combinational optimization.It is also possible to use its strong ability of exploitation and exploration to other difficult problems,for example,the TSP,a class of NP-hard combinatorial optimization problems.First,a new encoding scheme with pairs of amplitudes is designed.A quantum individual is corresponding to a vector,and the vector is corresponding to the unique valid tour,and vice versa.The advantages of the encoding scheme are that it always generates feasible solution,uses less population size and storage,and can effectively enhance the diversity of the population.Second,the quantum crossover can maintain the relatively good gene blocks.Third,the two-phase local search for edge evolving is integrated into QGA to accelerate its convergent speed.The first phase is used to optimize the sparsely located cities,and the second phase is used to optimize densely located cities.Based on these,a novel and efficient QGA for TSP is proposed,and its convergence to global optimal solution with probability one is proved.The numerical experiments show that the proposed algorithm can find the global optimal solution with less computation and evolving time.
Keywords:quantum genetic algorithm  qubit  TSP  combinatorial optimization
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号