多尺度量子谐振子算法在组合优化问题中的性能分析  

Performance Analysis of Multi-Scale Quantum Harmonic Oscillator Global Optimization Algorithm in Combinatorial Optimization Problems

作　　者：王鹏[1] 黄焱[2,3] 安俊秀[4] 李建平[5] 

机构地区：[1]西南民族大学计算机科学与技术学院,成都610041 [2]中国科学院成都计算机应用研究所,成都610041 [3]中国科学院大学,北京石景山区100049 [4]成都信息工程大学并行计算实验室,成都610225 [5]电子科技大学计算机科学与工程学院,成都611731

出　　处：《电子科技大学学报》2016年第3期469-474,共6页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(60702075);国家社会科学基金(12XSH019);中国博士后科学基金(20090451420);广东省科技厅高新技术产业化科技攻关项目(2011B010200007);四川省青年科学基金(09ZQ026-068)

摘　　要：多尺度量子谐振子算法(MQHOA)是一种基于一维量子谐振子波函数原理提出的新优化算法,该文在MQHOA框架下构建了旅行商问题(TSP)的求解流程和方法,研究了算法的物理意义和理论收敛过程。通过对12组TSP标准测试数据集的实验表明,根据算法物理模型要求的高斯邻域生成方法优于随机邻域生成方法,而且MQHOA算法对TSP问题的求解结果在获得最优解的概率和多次实验的平均最小距离两个指标上都要优于模拟退火算法,与其他算法对比也证明了该算法具有较好的性能。同时还研究了在规则城市数据集条件下算法的性能和收敛情况。这些结果证明MQHOA算法可以较好地被应用于组合优化问题。The multi-scale quantum harmonic oscillator algorithm （MQHOA） is a novel optimization algorithm based on the wave function of one-dimensional quantum harmonic oscillator. The process for solving traveling salesman problem （TSP） using MQHOA is proposed, and the physical meanings and theoretical convergence process of MQHOA are analyzed. The experiments for 12 groups of typical TSP data show that the neighborhoods generated on Gaussian distribution are better than those on random distribution. MQHOA for TSP is better than simulated annealing algorithm on the ratio of getting precise route and the average shortest distance. The comparison with other algorithms also proves the good performance of MQHOA. The performance about regular city data set has also been researched. The experiments results prove that MQHOA is an excellent algorithm to solve combinatorial optimization problems.

关 键 词：组合优化 多尺度量子谐振子算法 优化算法 旅行商问题 

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