徐 胜，马小军，钱 海，王震宇

(南京工业大学 电气工程与控制科学学院，南京 211800)



基于遗传-模拟退火的蚁群算法求解TSP问题

徐 胜，马小军，钱 海，王震宇

(南京工业大学 电气工程与控制科学学院，南京 211800)

传统的蚁群算法具有收敛性好、鲁棒性强等优点，但在解决旅行商(TSP)问题方面存在收敛时间长，容易出现停滞等问题;为了提高传统蚁群算法的解的质量，本文提出了基于遗传-模拟退火的蚁群算法(G-SAACO)，将遗传算法和模拟退火算法引入蚁群算法中;其方法是在传统蚁群算法中引入遗传算法的变异与交叉策略来得到候选解，增加解的多样性;同时引进模拟退火算法机制，使得在高温时以较高概率选择候选集中比较差的解加入最新集，温度控制上加入了回火机制，进一步提高解的质量;为了检验改进的蚁群算法，随机选用了TSPLIB中的部分城市进行仿真，结果与传统蚁群算法、模拟退火蚁群算法、遗传蚁群算法相比，算法具有较强的发现较好解的能力，同时增强了平均值的稳定性。

传统蚁群算法；遗传算法；模拟退火；旅行商问题

0 引言

在20世纪50年代中期，人们从生物行为和生物进化的机理中获得启发，提出了各种用来解决优化问题的方法，如遗传算法、禁忌搜索、模拟退火、进化策略等。20世纪90年代，意大利学者Dorigo等人通过观察蚂蚁觅食的行为提出了蚁群算法(ACO)[1]。蚁群算法利用了蚁群觅食的正反馈原理，具有收敛性好、鲁棒性强、并行性好等优点，使得其在解决TSP问题方面优于模拟退火算法、禁忌算法、遗传算法等智能算法[2-3]。……