求解TSP的量子遗传算法

被引：75

作者：

王宇平

李英华

机构：

[1] 西安电子科技大学计算机学院

来源：

计算机学报 | 2007年 / 05期

关键词：

量子遗传算法; 量子比特; TSP; 组合优化;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

引用

页码：5748 / 5755

页数：8

共 4 条

[1]

Han K-H.Genetic quantum algorithm and its application tocombinatorial optimization problem//Proceedings of IEEEthe 2000 Congress on Evolutionary Computation. . 2000

[2]

Wang Yu-Ping,Li Ying-Hua,Dang Chuang-Ying.A novelglobally convergent hybrid evolutionary algorithm for trave-ling salesman problems//Proceedings of the 3rd InternationalConference on Machine Learning and Cybernetics,ICMLC2004. . 2004

[3]

Narayanan A,Moore M.Quantum inspired genetic algo-rithms//Proceedings of the 1996 IEEE International Confer-ence on Evolutionary Computation(ICEC96). . 1996

[4]

Back T.Evolutionary Algorithms in Theory and Practice. . 1996

← 1 →