混合量子算法在旅行商问题中的应用研究  

Application study on hybrid quantum algorithm in traveling salesman problem

作　　者：傅家旗[1] 叶春明[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《上海理工大学学报》2009年第2期160-164,共5页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(70672110);上海市重点学科建设资助项目(S30504)

摘　　要：针对旅行商问题(TSP)的特点提出了一种新的解码方式,结合了进化计算(EA)和微粒群算法(PSO)的思想,构造了独特的混合量子算法(HQA).为进一步提高算法的性能,构造了改进混合量子算法(IHQA).IHQA在更新个体时能够指导惯性权重进行动态变化,决定个体在下一代被吸引或扩散.经测试证明,两种混合算法均表现出强大的寻优能力,IHQA效率更高.A novel method of coding was brought forward and the essence of evolutionary algo rithm （EA） and particle swarm optimization algorithm （PSO） was put into consideration in terms of the characteristics of Traveling Salesman Problem （TSP）, and a distinctive hybrid quantum algorithm （HQA） was constructed. The breakthrough was taken as the means of updating the individual to improve the capability of HQA. Still further, the updating of inertial weight was guided dynamically, and the decision that individual would turn out to be attractive or repulsive in the next iteration was made. This new algorithm is called improved hybrid quantum algorithm（IHQA）. The result of the test manifests that both two algorithms are of strong capability in optimum-searching, and IAQA performs better.

关 键 词：量子比特 量子进化算法 混合量子算法 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]