求解TSP问题的改进模拟退火遗传算法

Improved simulated annealing genetic algorithm for solving TSP problem

巡回旅行商问题(TSP)是最典型的NP的难题,遗传算法(GA)是解决这类问题的有效方法之一。由于该问题的解是一种特殊的序列,一般的交叉算子在该问题的求解效果方面并不理想,提出了贪心的3PM交叉算子,同时又引入退火选择方法,形成一种新的模拟退火遗传算法GCBSAGA(Greed Cross-3PM Basedon Simulated Annealing Genetic Algorithms)。该算法还将模拟退火算法与遗传算法相结合,使得遗传算法在前期发挥着全局搜索的强大功能,很容易收敛到全局较优解;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能,最终收敛到全局最优解。经过国际公认的TSPLIB提供的实验数据的验证,GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解。

The Traveling Salesman Problem（TSP） is a well-known NP complete problem,while the Genetic Algorithm（GA） is one of the ideal methods in solving it.Because the problem is a special sequence,the general cross-operator in the problem solving effect is not ideal.The greedy cross-3PM operator is proposed,while the annealing selection method is introduced,and a new simulated annealing genetic algorithm GCBSAGA（Greed Cross-3PM Based on Simulated Annealing Genetic Algorithms） is formed.The algorithm combines simulated annealing and genetic algorithm together,making genetic algorithm in the early stage play a powerful global search function.It is easy to converge to the global optimum solution;In the later stage,the simulated annealing genetic algorithms are used to deal with the overall situation of pre-optimum solution.And it makes full use of simulated annealing＇s latter part of the power of local search and eventually converges to the global optimal solution.After the experimental data verification provided by the internationally recognized TSPLIB,GCBSABA in the case eil76,eil101,pr144,st70 are found to provide better optimal path solution than TSPLIB.