张雁翔，祁育仙

(太原理工大学信息化管理与建设中心，山西太原 030024)



改进遗传算法求解TSP

张雁翔，祁育仙

(太原理工大学信息化管理与建设中心，山西太原 030024)

摘要：针对遗传算法收敛速度慢、易陷入早熟的问题提出一种改进的遗传算法。在传统遗传算法基础上，引入最近插入法产生高性能的初始种群；选择操作中加入精英保留策略，保证收敛到全局最优；根据种群进化状况自适应调整交叉概率、变异概率，克服过早收敛并加快收敛速度；在选择、交叉、变异之后加入进化逆转操作，保留亲代较多信息，增强搜索能力；提出一种新的遗传终止规则，提高遗传算法的有效性。经过国际公认的TSPLIB实验数据仿真验证，改进后的遗传算法精确性、有效性和收敛速度均有明显提高。

关键词：旅行商问题；遗传算法；最近插入法

旅行商问题(traveling salesman problem，TSP)又称为旅行推销员问题、货郎担问题，是最著名的NP完全问题。TSP并不仅仅是旅行商问题，且涉足众多领域，应用十分广泛，如邮路问题、基因组图谱绘制问题和产品的生产安排问题等，因此TSP的有效求解具有重要的意义。

目前，人工智能发展迅速，出现了许多独立于问题的智能优化算法。文献[1]讨论了蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、粒子群优化算法等求解TSP的优缺点及研究进程；文献[2]利用贪心策略指导遗传操作，提出了贪心遗传算法，保证算法的有效性；文献[3]将单亲遗传算法与模拟退火算法相结合，提高全局寻优能力。……