求解TSP的量子遗传算法

• 作者: 李英华 王宇平
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 量子遗传算法 量子比特 TSP 组合优化
• 年，卷（期）: 2007,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 748-755
• 页数: 8页
• 分类号: TP18
• 字数: 8249字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.05.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王宇平	西安电子科技大学计算机学院	128	1633	22.0	34.0
2	李英华	西安电子科技大学计算机学院	10	225	7.0	10.0