求解ＴＳＰ問題的改進遺傳算法

摘要：旅行商問題(TSP)是遺傳算法得以成功應用的典型問題。文章對遺傳算法加以改進，提出了新的選擇策略和交叉算子，并且引入了兄弟競爭的策略來加快收斂速度和全局搜索能力。把該算法應用在不同類型的TSP問題的求解上，表現出了比傳統遺傳算法更好的收斂性和計算效率。說明改進算法是有效的。關鍵詞：旅行商問題(TSP)；遺傳算法(GA)；交叉算子；兄弟競爭策略

0 引言

旅行商問題(Traveling salesman Problem，簡記為TSP)自1932年K．Menger提出以來，已引起各個領域許多研究者的興趣。它是一個古老而又困難的問題，是一種典型組合優化問題(combinatorial Optimization Problem)，并且也是一種NP完全問題(Nondeterministic Polynomial Complete Problem)。TSP問題可以描述為：一個推銷員要到n(n>2)個城市推銷貨物，從某個城市出發，經過其余各個城市一次且僅僅一次，然后回到出發點，求其最短行程，即尋找一條巡回路徑。

TSP問題主要有兩類：一類是任兩個城市間的距離都是對稱的，假設點i和點j之間的距離為d_ij則d_ij=d_ji，它對應的是圖論中的無向圖；另一類是兩個城市間的距離是非對稱的，即d_ij≠d_ji它對應的是圖論中的有向圖。

TSP問題中，可能的路徑總數與城市數目n是成指數型增長的，一般很難精確地求出其最優解，因而尋找出有效的近似求解算法就具有重要的意義。很多實際應用問題，如印制電路板的鉆孔路線方案，連鎖店的貨物配送路線，列車編組等，經過簡化處理后，均可建模為TSP問題，因而對TSP問題求解方法的研究具有重要實際價值。另外，所有NP完全問題在數學上都等價于TSP問題，它的研究對于科學和工程技術領域中大量組合優化問題，尤其是其中的NP完全問題的求解有著極為重要的價值。……