改進(jìn)遺傳模擬退火算法求解TSP

張雁翔　祁育仙

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

關(guān)鍵詞：遺傳算法；模擬退火算法；旅行商問(wèn)題（TSP）