求解旅行商问题的混合量子算法  

Hybrid quantum algorithm for solving traveling salesman problems

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

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

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

基　　金：高等学校博士点基金资助项目(20093120110008);上海市重点学科资助项目(S30504)

摘　　要：提出了求解旅行商问题的混合量子算法(HQA).HQA以量子计算为基础,设计了移位解码,解决了构造路径难的问题.并采用微粒群算法的进化模式和跟踪保优模式,构造了动态惯性权重使量子角更新、更有效,增加了局部优化进行精细搜索.对多个算例的测试结果表明,HQA具备了求解旅行商问题的能力.Hybrid quantum algorithm（HQA） was put forward to solve traveling salesman problems.On the basis of quantum computing,displacement decoding was designed which enables the algorithm to overcome the difficulties in route configuration.Evolutionary mode and best tracing and keeping mode,derived from particle swarm optimization algorithm,were adopted,dynamic inertia weight was configured to update quantum angles effectively,and local optimization was taken to carry out lean search.The capability of HQA to solve traveling salesman problems was demonstrated by the results of several examples.

关 键 词：混合量子算法 旅行商问题 优化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.4[自动化与计算机技术—控制科学与工程]