基于改進的遺傳算法求解旅行商問題

吳軍++嚴麗娜

【摘 要】論文提出了一種改進的遺傳算法求解旅行商問題（TSP）。該算法結合TSP的特點，采用實數編碼方式減少算法計算復雜度；等位交叉方式擴大算法的搜索空間，改善尋優能力；輪盤賭選擇策略加快算法的收斂速度。通過30個城市的benchmark實例進行仿真試驗，試驗結果表明，改進的遺傳算法改善了全局搜索能力，具有較快的收斂速度和較高的收斂精度。

【Abstract】In this paper， an improved genetic algorithm for traveling salesman problem （TSP） is proposed.The algorithm combines the characteristics of TSP， using real number encoding to reduce the computational complexity of the algorithm， a cross way to expand the search space and improve searching ability， roulette selection strategy to accelerate the convergence of the algorithm.In this paper， it has simulated benchmark examples in thirty cities.The simulation results show that the improved genetic algorithm can improve the global search ability， and its convergence speed and the convergence precision is higher.

【關鍵詞】旅行商問題；遺傳算法；收斂速度

【Keywords】traveler problem；genetic algorithm；convergence precision

【中圖分類號】TP18 【文獻標志碼】A 【文章編號】1673-1069（2017）03-0096-03

1 引言

旅行商問題（TSP）也稱貨郎擔問題，它旨在尋求旅行商在遍歷諸多城市一次最后回到起點城市的最短路徑，是數學圖論中的經典問題。在實際生活中，像物流路徑優化、車間調度和網絡路由選址等都可歸結為TSP，因此，TSP的研究具有重要的理論意義和實際價值。

Karp[1]證明了TSP是一個NP難問題，傳統的優化算法在求解TSP問題時往往會陷入局部最優，尤其隨著城市數量的增加，計算量也急劇增加，致使很多算法癱瘓。因此智能優化算法強的搜索效率、快速的收斂速度在求解TSP中得到了廣泛應用。Aziz[2]提出了廣義的蟻群算法，算法中融合了局部和全局兩種信息素更新機制，提高全局迅游能力。何湘竹[3]將混沌搜索機制融入基于教與學的優化算法求解TSP，通過benchmark實例仿真試驗顯示，新算法性能更優越。段艷明[4]將果蠅優化算法的連續空間對應到離散規劃，利用了遺傳算法的交叉、變異操作進行路徑的尋優，加快局部搜索能力和收斂速度。

遺傳算法是一種模擬生物進化過程的隨機搜索優化方法，與其他的局部搜索算法相比，遺傳算法具有更強的魯棒性，隱形的并行搜索機制增強了算法尋優能力，但遺傳算法也存在缺陷，例如： 種群常常會出現早熟收斂、易陷入局部最優的問題，使算法的搜索性能大大降低[5]。針對這些問題，學者提出了許多解決方法，如參數控制、多種群的運用和交配限制[6-8]等。

2 求解TSP的改進遺傳算法

鑒于目前遺傳算法在優化領域的優越性能，論文以TSP為例，提出了改進的遺傳算法。

2.1 實數編碼

對包含n個城市的TSP問題，我們提出一種新的有效編碼方法——實數編碼。它是指整數1到的一個全排列所構成的實數序列a1，a2，…，an，其中a∈[1，n）之間的整數，編碼中ai表示編號為的城市排在路徑上的第ai個位置。

2.2 輪盤賭選擇

輪盤賭選擇法是遺傳算法中常用的選擇方式，首先計算每個個體的適應度值fi，i∈[1，ps），ps為種群規模。這里fi的值越大，說明這個個體越優秀；其次，計算每個個體的選擇概率pi=fi/（∑fi）和累積概率Pi=∑■■pi；最后，隨機產生一個實數num∈[0，1]，選取滿足num

2.3 等位交叉

交叉算子是遺傳算法中關鍵的操作，它涉及種群的多樣性和算法的搜索效率等，論文基于等位交叉來改變兩個交叉個體的局部基因片段，使每個個體都能遺傳到對方的基因。具體操作如圖1所示。

■

圖1 等位交叉具體操作圖

2.4 改進的遺傳算法

基于以上操作算子，求解 TSP的改進遺傳算法步驟如下：

步驟1 初始化遺傳算法種群個數ps、最大迭代次數inmax、交叉概率pc和變異概率pm等；

步驟2 根據各城市的坐標計算各個城市之間的距離，記作Cij，i，j∈[1，n]，代表第i個城市到第j個城市的距離，初始生成ps個個體，即ps個城市路線；

步驟3 計算每條路線的距離Si，計算適應度值根據公式fi=1/Si，計算選擇概率pi=fi/（∑fi）和累積概率Pi=∑■■pi；

步驟4 根據選擇概率和累積概率采用輪盤賭選擇法選擇要交叉的兩個個體；

步驟5 根據交叉概率判斷是否交叉，交叉采用等位交叉法，產生兩個等位基因互換的兩個交叉個體；

步驟6 根據變異概率判斷是否變異，選擇變異基因位置，隨機產生基因片段，替換要變異的基因片段，產生新個體；

步驟7 計算新個體的適應度值，依據適應度值判斷保留新個體還是原個體。循環迭代，返回步驟3，當迭代次數達到最大結束算法；

步驟8 輸出最優解，畫出路線圖。

3 仿真試驗及分析

為了驗證該算法的正確性和有效性，選用30個城市的benchmark實例進行仿真實驗。

3.1 實驗測試環境與參數設置

實驗測試環境為：操作系統Windows 7，處理器為Intel（R） Core（TM）i3-2350，CPU@2.30GHz，內存6GB，編程軟件MATLAB R2010a。種群設置為100，對于算例Oliver30最大迭代次數設置為200，交叉概率pc=0.8，變異概率pm=0.4。

3.2 試驗結果及分析

通過遺傳算法對30個城市的benchmark實例進行20次測試得到其最優解，數據結果如表1所示。表1列舉了該算法20次獨立運行結果，最優值表示20次獨立運行中最好結果，最差值表示20次獨立運行中最差結果，平均值表示20次獨立運行結果的平均值，已知最優值表示目前TSPLB標準庫收錄的最優結果。

表1 TSP測試結果

■

由表1試驗結果可以看出，該算法在求解TSP中有較好的效果，20次獨立運行結果中最好值423.949與標準數據庫中最好值423.7406相差0.2084，誤差結果在可以接受的范圍，平均值424.4247與最優值423.949相差0.4757，表明該算法對求解TSP具有較高的穩定性。

圖2中給出了算法迭代200次的部分路線圖，分別是第50、第100和第200代結果，由圖可以看出，算法在運行至第100次時，結果430.8781已經接近最優值，表明算法有較強的收斂能力，第200次結果423.949非常接近已知最優值，表明了算法具有較強的全局搜索能力。圖3給出了該算法是以寧都值變化圖，也可直觀地看出該算法具有較強的收斂性能。

【參考文獻】

【1】Karp R.M. Reducibility Among Combinatorial Problems. Plenum Press. 1972：85-103.

【2】Zalilah Abd Aziz. Ant Colony Hyper-heuristics for Travelling Salesman[J]. Procedia Computer Science.2015，76：534-538.

【3】何湘竹.一種改進的基于教與學的優化算法求解旅行商問題[J].中南民族大學學報（自然科學版）.2015，34（4）：89-93.

【4】段艷明，肖輝輝.求解TSP問題的改進果蠅優化算法[J].計算機工程與應用，2016，52（6）：144-149.

【5】Park T，Ryu K R. A dual population genetic algorithm with evolving diversity[C]. IEEE Congress on Evolutionary Computation. 2007： 3516-3522.

【6】黃江波，付志紅.基于自適應遺傳算法函數優化與仿真[J].計算機仿真，2011，28（5）：237-240.

【7】鞏敦衛，孫曉燕.變搜索區域多種群遺傳算法[J].控制理論與應.2006，23（2）：256-260.

【8】徐曉艷.基于聚類思想的改進混合遺傳算法[D].北京：北京工業大學計算機學院，2013.