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

Genetic-simulated Annealing-based Ant Colony Algorithm for Traveling Salesman Problem

摘要:

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

Abstract:

The traditional ant colony algorithm has the advantages of good convergence and robustness, but has a long convergence time in solving the problem of TSP. In order to improve the quality of the solution of the traditional ant colony algorithm, G-SAACO is proposed,the genetic algorithm and simulated annealing algorithm are introduced into the ant colony algorithm.. The idea of the algorithm was to introduce the variation and crossover strategy of genetic algorithm into the traditional ant colony algorithm to get the candidate solutions, which increased the diversity of the solution. And introduction of simulated annealing algorithm mechanism made the algorithm have higher probability of selecting poor solutions in a candidate set into the latest set. Besides,In the mechanism of controlling the temperature, the quality of the solutions was improved through backfire strategy. In order to test the improved ant colony algorithm, randomly selected parts of the city of the TSPLIB to simulate.Compared with the standard GA,simulated annealing algorithm and the traditional ant colony algorithm for traveling salesman problem(TSP).The results show that the algorithm has a strong ability to find good solutions, and the stability of the average value is enhanced.