一種求解TSP問題的改進遺傳蟻群算法

徐練淞　潘大志

摘要：旅行商問題（TSP）是一種經典的組合優化問題。傳統的蟻群算法運用正反饋和分布式計算機制，具有較強的魯棒性。但是該算法搜索時間長、易出現早熟停滯現象。因此本文根據旅行商問題的模型特點，在蟻群算法的基礎上針對TSP問題提出了一種新型的改進蟻群算法：即變參數選擇城市策略，并且在交叉策略中選擇PMX（Partially Matched Crossover）交叉策略。實驗結果表明，與傳統基本蟻群算法和遺傳算法相比，能夠較快地找到最優解，解的質量也相對較好，因此提高了蟻群算法對TSP問題的求解-效率。

關鍵詞：蟻群算法；群體智能；旅行商問題；遺傳算法