摘要
多尺度量子谐振子算法(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.
出处
《电子科技大学学报》
EI
CAS
CSCD
北大核心
2016年第3期469-474,共6页
Journal of University of Electronic Science and Technology of China
基金
国家自然科学基金(60702075)
国家社会科学基金(12XSH019)
中国博士后科学基金(20090451420)
广东省科技厅高新技术产业化科技攻关项目(2011B010200007)
四川省青年科学基金(09ZQ026-068)
关键词
组合优化
多尺度量子谐振子算法
优化算法
旅行商问题
combinatorial optimization
multi-scale quantum harmonic oscillator algorithm
optimizationalgorithm
traveling
salesman problem
