基于一种改进遗传模拟退火算法的TSP求解  

Traveling Salesman Problem Solving Based on an Improved Genetic Simulated Annealing Algorithm

作　　者：乔彦平[1] 张骏[1] 

机构地区：[1]西北工业大学自动化学院,陕西西安710072

出　　处：《计算机仿真》2009年第5期205-208,共4页Computer Simulation

摘　　要：快速收敛于全局最优解是遗传算法的一个研究重点。在对遗传算法和模拟退火算法研究的基础上,分析了两种算法各自的优缺点,对已有的遗传模拟退火算法进行了改进。结合遗传算法和模拟退火算法的优点,给出了一种并行的多层搜索结构,提高了算法的效率;同时,在此基础上,提出一种种群早熟评价指标。最后,将此改进算法应用到旅行商问题中,并分别对10个城市和30个城市的旅行商问题进行了仿真,用于验证算法的可行性和快速性。仿真结果表明。改进的遗传模拟退火算法能够较快的收敛于全局最优解。Rapid convergence in the global optimal solution is a focus of genetic algorithm. Based on the study of genetic algorithm and simulated annealing algorithm, the paper analyses the major merits and shortcomings of the two algorithms, and gives an improved genetic simulated annealing algorithm, which combines the major merits of the two algorithms. Especially, it gives a parallel searching structure of multi layers, and gives a new criterion for judging the premature convergence in this improved algorithm. At last, the algorithm is applied in the traveling salesman problem （ TSP）, and it is simulated with both of 10 - city TSP and 30 - city TSP to prove the algorithm＇ s feasibility and efficiency. The results of the simulation indicate that the improved algorithm has a rapid convergence in the global optimal solution.

关 键 词：遗传算法 模拟退火算法 旅行商问题 过早收敛 

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