基于TSP問題的仿生算法比較

文/劉云飛

1 引言

TSP問題自1759年被歐拉提出來后，一直成為一個困擾著數學界的難題。TSP問題是一個組合優化的問題，本身具有NPC計算復雜性，因為在計算機出現之前的數學計算比較復雜，人們可用于解決TSP問題的工具較為落后，TSP問題的精確結果僅僅局限于小規模數據。隨著計算機計算的發展，計算量已經不再是困擾TSP問題求解難度的主要因素，可用于求解TSP問題的算法增速劇烈，但是每種算法的精確度都具有一定的差別。參考文獻[1]中作者對現今求解TSP問題的算法進行分類，分為仿生算法和非仿生算法，并通過實驗比較兩種算法的求解精確度，最終發現對規模不大的TSP問題，仿生算法和非仿生算法的計算準確度相差不大，但是在問題規模很大時，非仿生算法求解準確度與仿生算法相去較大。本文將針對不同規模的TSP問題，對常見的仿生算法進行尋優對比，尋找對TSP問題求解較為敏感的仿生優化算法。

2 TSP問題簡介

TSP問題可以這樣描述：已知n 個城市各城市間的距離, 某一旅行商從某個城市出發訪問每個城市一次且僅一次, 最后回到出發城市,怎樣安排才使其所走路線最短。

其數學模型可以表示為：

對于T個城市問題，為每個城市進行編號，假設m、n為任意兩個城市編號，0≤m≤T，0≤n≤T。kmn為城市m到城市n的距離，TSP問題的實質就是尋找一條最優路徑，使得該路徑中每個城市遍歷一次，且路徑長度最短。

目標函數：minS=∑m≠nkmnxmn

3 TSP問題求解算法簡介-仿生算法

雖然仿生算法對求解TSP問題結果較好，但是不同的仿生算法之間也有差別。在用仿生算法解決TSP問題時，遺傳算法、免疫算法和蟻群算法是經常被選用的，這三種智能算法在求解尋優過程中分別具備各自的特點：

3.1 遺傳算法

遺傳算法（genetic algorithm GA）是模擬生物在自然環境中的遺傳和進化過程而形成的自適應全局優化搜索算法，它最早是由美國的J.H.Holland教授提出，該算法起始于20世紀60年代對自然和人工自適應系統方面的研究。遺傳算法借鑒了達爾文的進化論和孟德爾的遺傳學說，通過模擬自然界物種的進化機制，在算法運行過程中自動獲取和積累有關搜索空間的數據，并自適應的控制搜索過程以求得最優解。

表1：burmal14（已知最優路徑距離：30.8785）

表2：att48（已知最優路徑距離：33522）

表3：kroA100（已知最優路徑距離：21282）

遺傳算法是一種常用的優化算法，編碼技術簡單，遺傳操作易于理解，使用“適者生存”的原則，采用選擇、交叉和變異等操作，通過模擬自然界物種進化原理，一代代的把“最優個體”遺傳下去。該算法從種群中進行選擇，搜索過程不受函數約束條件的限制，可以避免陷入局部次優解以及保證算法的簡易性。但是當解決結構復雜和搜索空間較大的優化問題時，該算法搜索時間比較長，易出現早熟問題。而且對初始種群的選擇很敏感，不同的初始種群的選取會直接影響解的質量和算法效率。

3.2 免疫算法

最早的免疫系統模型是由Jerne于1973年提出的，他依據Burnet的克隆選擇學說，開創了獨特型網絡理論，給出了免疫系統的數學框架，并利用微分方程模型模擬了淋巴細胞的動態變化。現實的生物免疫系統是一種復雜的自適應系統，免疫系統能夠在病原體入侵人體時識別出病原體，并且產生針對該病原體的抗體，抗體可以將病原體消滅，并在消滅病原體后依然殘存在人體內，當同一種病原體再次入侵人體時，病原體會被體內存留的抗體消滅，免疫系統的這種學習、記憶和模式識別的能力可用于解決科學和工程問題。

與其它算法相比，免疫算法具有利用自身產生多樣性和維持機制的能力，可以確保種群的多樣性，這解決了一般尋優過程中經常出現的 “早熟”問題，利于獲取全局最優解。

3.3 蟻群算法

蟻群算法(Ant Colony Optimization, ACO)是由意大利學者M.Dorigo.V.Maniezzo和A.Colorni于20世紀90年代初通過模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發式隨機搜索算法，該算法在智能理論研究領域具有重要地位。

螞蟻可以在沒有任何參照的情況下找到從巢到食物的最短路徑，并且可以在路徑被阻擋時自適應地搜索到新的最短路徑。根本原因是螞蟻在尋找食物時可以在它們尋找的路徑上釋放一種特殊的分泌物——信息素。隨著時間的推移，信息素蒸發導致濃度降低，而在最短路徑上的螞蟻可以比其它路徑上的螞蟻更快地返回，提升路徑上的信息素濃度，從而形成一種正反饋機制。蟻群算法易于與其它算法相結合，具備求解復雜問題的能力，但是由于前期解過多，造成蟻群算法搜索算法較慢。

4 實驗結果對比

為了比較不同的仿生算法對TSP問題求解的精確度，本文使用burmal14、att48和kroA100對不同的仿生算法進行了實驗，這三組實驗數據來源TSPLIB[7]。實驗環境 為：pc機 -intel(R) Core(TM) i5-2450M CPU@2.50GHz，Windows7 64旗艦版。實驗軟件為：MATLAB R2014b。實驗結果如表1所示。

通過表2、表3分析實驗結果，我們得出如下結論：

（1）對于小規模TSP問題，如14個城市最短路徑問題，遺傳算法、免疫算法和蟻群算法的尋優能力都很強，幾乎每一次運行都可尋找到最優路徑。

（2）對于規模較大的TSP問題，三種仿生算法的尋優能力是有所差異的。由于遺傳算法全局搜索能力較強，因此在解決48個和100個城市最短路徑的問題時，同樣10次的運行結果，遺傳算法總是可以尋找到比其他兩種算法距離更短的路徑。但由于遺傳算法的每次尋優具有一定的概率性，尋優穩定性的能力不如蟻群算法，這也導致它的平均路徑長度與蟻群算法在相差不大情況下，標準誤差卻遠遠大于蟻群算法。

（3）通過實驗數據對比，我們不難發現免疫算法在尋優的過程中具有記憶性，每代的最短路徑會記錄下來，與下一代隨機生成的個體。

5 結語

通過本次實驗，我們不難發現遺傳算法、免疫算法和蟻群算法在TSP問題中各有優缺點，遺傳算法的全局性保證了它尋優結果的準確性，蟻群算法的魯棒性保證了它尋優結果的穩定性。因此在大規模TSP問題的尋優中，我們應該優先考慮采用遺傳算法和蟻群算法的聯合尋優，利用遺傳算法的隨機搜索、快速性和全局性產生TSP問題所需的初始種群，然后，充分利用蟻群算法的并行性和正反饋機制來修正尋優算法，提升尋優算法的求解效率和求解精度，這種聯合尋優算法不僅適用于TSP問題，也可推廣至求解其它NP問題。