采用基于模拟退火的蚁群算法求解旅行商问题  

Simulated annealing-based ant colony algorithm for traveling salesman problems

作　　者：刘波[1] 蒙培生[1] 

机构地区：[1]华中科技大学土木工程与力学学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2009年第11期26-30,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家高技术研究发展计划资助项目(2005AA642010)

摘　　要：针对蚁群算法加速收敛和停滞现象的矛盾,提出一种基于模拟退火机制的蚁群算法.在高温阶段以高的概率接收候选集内较差的解加入更新集,随着温度的降低,路径上的信息素分布趋于集中,可以使算法快速收敛.在温度控制机制上采用回火策略,可以使解的质量进一步提高.在算法中结合3opt局部优化算法可进一步提高算法效率,并证明了该算法以概率1收敛到最优解.数值实验表明:相对于基本蚁群算法,该算法的迭代次数可以节省99%左右,且准确性提高接近1%.To solve the contradiction between convergence speed and precocity in the ant colony algo rithm, ant algorithm based on simulated annealing method was introduced. In the stage with high temperature, the inferior solutions were adopted to the updated collection with high probability. It made the trail information accumulate on the road and results converge rapidly with drop in temperature. In the mechanism of controlling the temperature, the quality of the solutions was improved through backfire strategy. Meanwhile, the 3opt scheme was used to optimize solution in each step. The algorithm was proved to be convergent with probability one. Results demonstrate that the algo-rithm can reduce the number of iterations over 99% and increase accuracy about 1% compared with basic ant colony algorithm.

关 键 词：混合算法 蚁群算法 模拟退火 收敛性 旅行商问题 

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