文献类型：期刊文章

作　　者：王宇平[1] 李英华[1]

机构地区：[1]西安电子科技大学计算机学院,西安710071

出　　处：《计算机学报》

基　　金：国家自然科学基金(60374063)资助

年　　份：2007

卷　　号：30

期　　号：5

起止页码：748-755

语　　种：中文

收录情况：BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI(收录号：20072510663256)、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

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

关 键 词：量子遗传算法 量子比特 TSP 组合优化

分 类 号：TP18]