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

劉樹趙 鄒德旋 羅鴻赟 張慧峰 李夢迪

摘? 要： 針對傳統遺傳算法求解旅行商問題收斂速度慢且不穩定的問題，提出了一種改進遺傳算法（Improved genetic algorithms， IGA）。通過鄰域搜索算法對初始化種群進行優化；設計了一種自適應調節的交叉和變異概率；加入了Metropolis準則，以一定概率接受劣解，提高跳出局部最優的能力；加入了逆轉操作加強局部搜索能力，加快種群收斂。利用Matlab將IGA和其他五種算法在TSPLIB數據庫中進行試驗，結果表明，該算法在中小型TSP問題上的收斂速度和求解精度都有一定的優勢。

關鍵詞： 遺傳算法； 旅行商問題； 領域搜索算法； 自適應調節

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）05-66-06

Improved genetic algorithm to solve traveling salesman problem

Liu Shuzhao， Zou Dexuan， Luo Hongyun， Zhang Huifeng， Li Mengdi

（School of Electrical Engineering and automation， Jiangsu Normal University， Xuzhou， Jiangsu 221116， China）

Abstract： Aiming at the slow and unstable convergence of the traditional genetic algorithm for solving the travelling salesman problem （TSP）， an improved genetic algorithm （IGA） is proposed. The initialized population is optimized by the neighborhood search algorithm. An adaptive adjustment of crossover and variation probability is designed. The Metropolis criterion is added to accept inferior solutions with a certain probability， which improves the ability to jump out of the local optimum. The reversal operation is added to strengthen local search capabilities and accelerate population convergence. The IGA and other five algorithms are tested in the TSPLIB database using Matlab， and the results show that the convergence speed and solution accuracy of the algorithm have certain advantages in small and medium-sized TSP problems.

Key words： genetic algorithm; the travelling salesman problem （TSP）; domain search algorithm; adaptive adjustment

0 引言

旅行商問題（TSP）是組合優化領域很經典的一個NP-Hard問題[1]，可以簡單描述為一個商人在已知的城市中不重復的訪問每一個城市，最后回到出發的城市，商人的路線便是旅行商問題的解。該問題具有廣泛的工程應用背景，如網絡通信接點的設置、物流路徑規劃、飛機航線的安排等[2]。目前，很多智能優化算法應用于求解TSP問題，主要有遺傳算法（GA）[3]、粒子群算法（PSO）[4]、蟻群算法（ACO）[5]、模擬退火算法（SA）[6]以及人工螢火蟲優化算法（AGSO）[7]等，并且都取得了不錯的效果。

Holland教授于1975年首先提出了遺傳算法[8]。遺傳算法作為一種啟發式隨機搜索算法，通用性強，目前已經有很多學者從不同方面對遺傳算法進行改進，來解決TSP問題，并取得了不錯的效果。如劉艷琪等人[9]提出了基于病毒侵染的改進遺傳算法，通過加入病毒種群來感染初始種群，加快了算法的收斂速度；徐佳等人[10]提出了一種生物信息啟發式遺傳算法，引入生物學中的基因序列對比手法改進交叉操作，獲得較為穩定的求解結果；于瑩瑩等人[11]提出了基于貪婪操作的啟發式交叉算子，使算法具有更可靠的尋有能力；王震等人[12]通過貪婪算法初始化種群，變異算子采用2-opt局部優化算法，可以使算法在較小的迭代次數內得到質量更高的全局最優解；姚宇威等人[13]將雜草算法和遺傳算法混合，在解決算法易陷入局部最優這一缺陷上有明顯的改善；李慶等人[14]通過設計了一個動態適應度函數以及引入了相似度概念，使得遺傳算法在優化性能上獲得了較大提升。

基于以上分析，本文提出了一種改進遺傳算法（IGA），在種群初始化的過程中引入了鄰域搜索算法優化種群，使得算法在迭代初期就有較好的種群；設計了自適應調節的交叉和變異概率，平衡了算法的全局和局部搜索能力；引入了Metropolis準則，以一定概率接受劣解，提高跳出局部最優的能力；最后通過加入逆轉操作，加快算法的收斂。

1 TSP問題

TSP問題可以抽象描述為在一個帶權重的完全無向圖中，找到一個權值總和最小的哈密頓回路。其數學模型為，要在給出的城市中找到一條最優路徑：[V=v1，v2，…vn]，并滿足提下目標函數：

[LV=mini=1n-1d（vi，vi+1）+dvn，v1]? ⑴

其中，[vi]為城市編號，[dvi，vi+1]為城市[vi]到[vi+1]的距離，[n]為城市總數，[1≤i≤n]。

2 傳統遺傳算法

傳統遺傳算法基本步驟：

step 1 確定合適的編碼方式，對種群進行初始化。

step 2 建立合適的適應度函數，并計算生成的種群中個體的適應度值。

step 3 根據個體適應度值進行選擇操作，主要的選擇方式有輪盤賭選擇法和錦標賽選擇法等。

step 4 根據交叉概率進行交叉操作，生成新的種群。

step 5 根據變異概率進行變異操作，生成新的種群。

step 6 判斷是否滿足停止條件，如果滿足，則輸出結果；如果不滿足，則轉到step2。

盡管傳統遺傳算法已經具備不錯的全局尋優能力和全局收斂能力，但在處理復雜問題時，效率較低，為了追求更高的精度以及更快的收斂速度，本文提出一種改進遺傳算法，用于求解TSP問題。

3 改進遺傳算法

3.1 種群初始化

傳統遺傳算法的種群初始化通常是由計算機隨機生成，這樣容易使初始種群的個體適應度與我們想要求得的最優適應度偏差較大，從而使算法收斂速度較慢且運行耗時較高，導致解的質量的下降。因此，IGA中采用鄰域搜索算法生成種群與隨機生成種群相結合，一半種群由鄰域搜索生成，另一半種群由計算機隨機生成，在提高初始種群質量的同時，又保證了初始種群的多樣性，在提高種群初期收斂速度的同時，又防止陷入局部最優。鄰域搜索算法具體方法如下。

對所給的城市進行編碼，得到序號集合[1，2，…，n]。隨機生成起始城市[i]，在剩下的城市中找到一個與城市[i]距離最近的城市，構成路徑，依次在剩下的城市中選擇與上一個被選擇的城市最短距離的城市，直到構成一條完整路徑。這樣得到的城市路徑形成的初始種群，在一開始便有一個良好的適應度，對于算法的收斂和求解精度的提高都有一定的幫助。

3.2 自適應交叉和變異概率

傳統的遺傳算法一般使用固定的交叉和變異概率，這會導致優良個體被破壞以及劣質個體被保留，影響算法的性能。在本文中設計了一種自適應交叉和變異概率，根據當前個體的適應度值以及當前種群個體最大適應度與平均適應度的差值相結合自動調整交叉和變異概率，算法交叉概率[pc]和變異概率[pm]如下：

[pc=k1sin（fmax-f'fmax-f），? ?f'≥fk3? ? ? ? ? ? ? ? ? ? ? ? ? ? ?，? ? ? ? ? f'

[pm=k2sin（fmax-ffmax-f），? ? ? ? ? ? f≥fk4? ? ? ? ? ? ? ? ? ? ? ? ? ? ，? ? ? ? ? ? f

其中，[k1]，[k2]，[k3]，[k4≤]1.0，[fmax]為當前種群中個體適應度最大值，[f]為當前種群個體適應度平均值，[f']為待交叉的兩個個體中適應度大的值，[f]為待變異個體適應度值。

分析式⑵和式⑶，當[fmax-f]變小時，也就是說種群中個體適應度值最大值接近種群個體適應度平均值，這時候算法可能收斂到了全局最優解，也可能陷入了局部最優解，因此它的交叉概率[pc]和變異概率[pm]增大，增加種群的多樣性；當[fmax-f]變大時，則相反。在某一代的種群中，不同的個體應該對應不同的[pc]和[pm]，做到盡可能的保留優質個體，淘汰劣質個體，因此，當個體適應度值大，降低該個體的[pc]和[pm]，當個體適應度值小，增大該個體的[pc]和[pm]。在公式中加入了三角函數，使交叉概率和變異概率呈非線性變化，易于算法跳出局部最優解。

3.3 加入Metropolis準則

傳統遺傳算法隨機性強，但在算法進化的后期，仍然存在容易陷入局部最優導致算法收斂，所求解與最優解相差較大。而模擬退火算法具有良好的局部尋優能力，并且可以概率性的跳出局部最優并最終趨向于全局最優。Metropolis準則就是幫助模擬退火算法跳出局部最優的重要部分，因此，本文在傳統遺傳算法中加入了Metropolis準則幫助算法在迭代過程中跳出局部最優。具體方法如下。

當算法在變異操作后生成新的種群，對所生成的種群中每個解進行操作。隨機選取解中的兩個城市，并將這兩個城市之間（包含這兩個城市）所有的城市順序隨機打亂，如當前城市為：

A→B→C→D→E→F→G→H

隨機選中的城市為C和F，那么打亂之后的順序為：

A→B→E→C→F→D→G→H

計算原來路徑長度的大小[distpast]以及新生成路徑適應度值[distnew]的大小，比較[distnew]和[dist]的大小，如果[distnew]小于[distpast]，則用新路徑代替原來的路徑，如果[distnew]大于[distpast]，則以概率[p1]接收新路徑。概率[p1]的數學表達式如下所示：

[p1=e-distnew-distpastmaxgen-0.9×gen]? ⑷

其中，[maxgen]為算法最大迭代次數，[gen]為算法當前迭代次數。隨著算法迭代的進行，[maxgen-0.9×gen]在不斷的減小，根據指數函數的特點，[p1]的值也在不斷減小，算法接受劣解的概率減小，有助于算法整體收斂。并且當[distnew-distpast]的值較大時，也就是新解和舊解相差較大，[p1]的概率也在變小，接受劣解的概率減小，相反，當[distnew-distpast]的值較小時，接受劣解的概率增大，在不影響算法收斂能力的同時保留了跳出局部最優的能力。

3.4 逆轉操作

傳統遺傳算法適應性強，適用于各種組合優化的問題，但在解決復雜問題時，收斂速度較慢，往往需要多次迭代才能尋得全局最優。為了解決這一缺陷，根據局部尋優的思想在算法中加入逆轉操作，加快種群收斂，逆轉操作具體方法如下所示：

經過上述操作后，在生成的種群中隨機選取解的兩個城市，并將這兩個城市之間的順序倒換，如當前城市為：

A→B→C→D→E→F→G→H

隨機選中的城市為C和F，那么打亂之后的順序為：

A→B→F→E→D→C→G→H

然后將路徑距離更小的解保留。

3.5 改進自適應遺傳算法求解TSP問題具體步驟

step 1 鄰域搜索算法與隨機生成相結合，初始化種群。

step 2 計算適應度函數。

step 3 采用輪盤賭選擇法與精英保留策略結合，精英保留比為0.9。

step 4 改進OX交叉操作。操作如下：

父代1：

A→B→C→D→E→F→G→H

父代2：

B→A→E→F→C→H→G→D

隨機選擇起點和終點，如第3位和第5位;

父代1：

E→F→C→A→B→C→D→E→F→G→H

父代2：

B→A→E→F→C→H→G→D→C→D→E

根據映射關系消去路徑中相同的城市;

父代1：

E→F→C→A→B→D→G→H

父代2：

B→A→F→H→G→C→D→E

改進的OX交叉算子，即使在要交叉的兩個父代相同的情況下，也會生成不同的子代。

step 5 交換變異，操作如下：

在生成的路徑中隨機選兩個城市，交換兩個城市的位置，如當前城市為：

A→B→C→D→E→F→G→H

選擇的城市為B和E，那么新路徑為：

A→E→C→D→B→F→G→H

step 6 加入Metropolis準則，以一定概率接受劣解。

step 7 逆轉操作。

step 8 判斷是否滿足停止條件，滿足，則輸出結果；不滿足，則跳轉到step 2。

本文改進遺傳算法流程圖如圖1所示。

圖1? 改進遺傳算法流程圖

4 仿真實驗

4.1 實驗環境與參數設置

為了測試改進遺傳算法的性能，將IGA與另外5種算法在Matlab仿真軟件上對TSPLIB數據集不同城市規模的實例進行測試，5種算法分別為傳統遺傳算法（GA）、粒子群算法（PSO）、蟻群算法（ACO）、模擬退火算法（SA）以及結合2-opt局部尋優操作的混合遺傳算法（HGA）。

所有的實驗均處于同一環境下，即操作系統為Windows10，處理器為Intel?Core（TM）i5-7300HQ，8GRAM，運行環境為Matlab 2019a。傳統遺傳算法（GA）種群規模為100，最大迭代次數為1000，交叉概率為0.9，變異概率為0.05；粒子群算法（PSO）粒子數量為100，最大迭代次數為1000；蟻群算法（ACO）螞蟻數量取100，信息素重要程度因子取1，啟發函數重要因子取5，信息素揮發因子取0.1，最大迭代次數取500；模擬退火算法（SA）初始溫度為100攝氏度，結束溫度為0.66攝氏度，溫度衰減系數為0.99，馬爾科夫鏈長度為500；混合遺傳算法（HGA）種群規模為100，最大迭代次數為1000，交叉概率為0.9，變異概率為0.05；本文算法種群規模為100，最大迭代次數為500，[k1=k3=1.0]，[k2=k4=0.5]。

4.2 仿真結果分析

按照上述實驗前的準備，將六個算法在六個TSPLIB實例上獨立運行20次，記錄每次的運行結果。找出最優解，并結合TSPLIB實例的已知最優解[15]，根據公式計算偏差率，具體公式如下：

六種算法具體實驗結果見表1。由于傳統遺傳算法（GA）和粒子群算法（PSO）在求解規模稍大的TSP問題時偏差較大，求解的質量很差，所以舍棄一部分實驗結果。從表1可知，相對于本文涉及到的其他幾種算法，改進遺傳算法（IGA）在中小型TSP問題的求解精度上更高，對于TSP問題的求解具有一定優勢。

為了更加直觀的了解上述算法求解TSP問題的具體過程，以IGA、HGA、ACO、SA為例，設置最大迭代次數都為500代，本文繪制了eil51、st70、eil76和eil101這四個具有代表性實例的迭代曲線，如圖2～圖5所示。通過觀察這四分迭代曲線我們可以發現，本文的改進遺傳算法（IGA）初始化種群采用了鄰域搜索算法和隨機生成相結合的方法，初始解便具有很大優勢；采用了自適應交叉和變異概率以及加入了逆轉操作，加快了算法的收斂；加入了Metropolis準則，以一定概率接受劣解，提高了跳出局部最優的能力，對算法的求解精度也有一定的提高。圖6～圖9給出了本文算法求解到的最優路徑圖。

5 結束語

本文提出了一種改進遺傳算法（Improvegenetic algorithms，IGA）來解決旅行商問題。通過鄰域搜索算法對初始化種群進行優化，也保留了隨機生成種群策略，在提高初始種群質量的同時保證了種群多樣性；設計了一種自適應調節的交叉和變異概率，提高算法尋優效率；加入了Metropolis準則，以一定概率接受劣解，提高跳出局部最優的能力；加入了逆轉操作加強局部搜索能力，加快種群收斂。利用Matlab對IGA和其他五種算法對TSPLIB數據庫中進行試驗，實驗結果表明，該算法在中小型TSP問題上的收斂速度、求解精度都有一定的優勢。

參考文獻（References）：

[1] 程榮.遺傳算法求解旅行商問題[J].科技風，2017，（16）：40，51

[2] 高海昌，馮博琴，朱利.智能優化算法求解TSP問題[J].控制與決策，2006（3）：241-247，252

[3] 張占云，宗曉萍，王培光.基于旅行商問題的改進遺傳算法研究[J].電子世界，2017（7）：19-21

[4] 羅金炎.一種求解旅行商問題的改進粒子群算法[J].沈陽化工大學學報，2017，31（4）：377-384

[5] 賈燕花.蟻群算法在旅行商問題（TSP）中的應用研究[J].計算機與數字工程，2016，44（9）：1664-1667

[6] 郭樂新.基于模擬退火算法的旅行商問題的實現[J].現代計算機（專業版），2012（3）：3-5，18

[7] 周永權，黃正新.求解TSP的人工螢火蟲群優化算法[J].控制與決策，2012，27（12）：1816-1821

[8] HOLLAND J H. Adaptationin natural and artificialsystems：an introductory analysis with applications to biologycontrolandartificial intelligence[M].Massachusetts，USA：MIT press，1992

[9] 劉艷琪，劉一杰.基于病毒侵染和逆轉操作的改進遺傳算法[J].湖南文理學院學報（自然科學版），2022，34（3）：23-29

[10] 徐佳，韓逢慶，劉奇鑫，等.一種求解TSP的生物信息啟發式遺傳算法[J].系統仿真學報，2022，34（8）：1811-1819

[11] 于瑩瑩，陳燕，李桃迎.改進的遺傳算法求解旅行商問題[J].控制與決策，2014，29（8）：1483-1488

[12] 王震，劉瑞敏，朱陽光，等.一種求解TSP問題的改進遺傳算法[J].電子測量技術，2019，42（23）：91-96

[13] 姚宇威，鄧燕妮.混合雜草遺傳算法求解旅行商問題[J].科學技術創新，2020（11）：40-41

[14] 李慶，魏光村，高蘭，等.用于求解TSP問題的遺傳算法改進[J].?軟件導刊，2020，19（3）：116-119

[15] REINELT G.TSPLIB-A traveling salesman problemlibrary[J].OSRA Journal on Computing，1991，3（4）：376-384