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

Improved simulated annealing algorithm and genetic algorithm for TSP

作　　者：姚明海[1,2] 王娜 赵连朋[1] 

机构地区：[1]渤海大学信息科学与技术学院,辽宁锦州121013 [2]东北师范大学数学与统计学院,长春130117 [3]锦州师范高等专科学校计算机系,辽宁锦州121013

出　　处：《计算机工程与应用》2013年第14期60-65,共6页Computer Engineering and Applications

基　　金：吉林省科技发展计划项目青年科研基金(No.201201070)

摘　　要：对遗传算法和模拟退火算法的特点进行了比较,阐述了遗传算法与模拟退火算法集合的必要性。提出了一个用于求解TSP问题的改进的模拟退火和遗传算法。利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题。在遗传算法中改进了传统的交叉机制,利用父代染色体与子代染色体进行交叉,解决了传统遗传算法中存在的"早熟"问题。针对模拟退火算法收敛速度慢等问题,提出了新的解生成机制和改良算法,提高了算法的收敛速度。实验测试的结果表明,该方法具有较好的收敛效果和更高的稳定性。The characteristics of genetic algorithm and simulated annealing algorithm are compared, it elaborates the necessity of the combination of genetic algorithm and simulated annealing algorithm. An improved simulated annealing and genetic algo- rithm for solving TSP is proposed. The global random searching ability of genetic algorithm makes up the question of the simu- lated annealing algorithm that easy to fall into the local optimal solution. The crossover method of genetic algorithm is changed, the parent chromosomes and offspring chromosomes are crossed, it solves the problems of traditional genetic algorithm ＂prema- ture＂. It proposes new solution generation mechanisms and improved algorithm for that the simulated annealing algorithm con- verges slowly, the method improves the speed of convergence of the algorithm. Experimental test results show that the new algo- rithm has faster convergence and better stability.

关 键 词：遗传算法 模拟退火算法 旅行商问题(TSP) 优化算法 最优解 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]