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

张雁翔　祁育仙

摘要：遗传算法和模拟退火算法均是解决TSP的有效方法，分析2种算法各自的优缺点，在已有遗传模拟退火算法的基础上进行改進并用于求解TSP。引用部分最近插入法、部分随机产生初始种群，减小了群体多样性与收敛速度的矛盾。在遗传算法中，使用精英保留策略对选择操作进行改进，保证种群的质量；引入进化逆转算子，使子代继承亲代的较多信息，增强搜索能力。经过国际公认的TSPLIB实验数据仿真验证，改进后的遗传模拟退火算法搜索最优能力提高。

关键词：遗传算法；模拟退火算法；旅行商问题（TSP）