改進遺傳模擬退火算法求解TSP

張雁翔　祁育仙

摘要：遺傳算法和模擬退火算法均是解決TSP的有效方法，分析2種算法各自的優缺點，在已有遺傳模擬退火算法的基礎上進行改進并用于求解TSP。引用部分最近插入法、部分隨機產生初始種群，減小了群體多樣性與收斂速度的矛盾。在遺傳算法中，使用精英保留策略對選擇操作進行改進，保證種群的質量；引入進化逆轉算子，使子代繼承親代的較多信息，增強搜索能力。經過國際公認的TSPLIB實驗數據仿真驗證，改進后的遺傳模擬退火算法搜索最優能力提高。

關鍵詞：遺傳算法；模擬退火算法；旅行商問題（TSP）