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

Application study on hybrid quantum algorithm in traveling salesman problem

针对旅行商问题(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.