改進(jìn)遺傳算法求解旅行商問題

劉樹趙 鄒德旋 羅鴻赟 張慧峰 李夢(mèng)迪

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

關(guān)鍵詞： 遺傳算法； 旅行商問題； 領(lǐng)域搜索算法； 自適應(yīng)調(diào)節(jié)

中圖分類號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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）是組合優(yōu)化領(lǐng)域很經(jīng)典的一個(gè)NP-Hard問題[1]，可以簡(jiǎn)單描述為一個(gè)商人在已知的城市中不重復(fù)的訪問每一個(gè)城市，最后回到出發(fā)的城市，商人的路線便是旅行商問題的解。該問題具有廣泛的工程應(yīng)用背景，如網(wǎng)絡(luò)通信接點(diǎn)的設(shè)置、物流路徑規(guī)劃、飛機(jī)航線的安排等[2]。目前，很多智能優(yōu)化算法應(yīng)用于求解TSP問題，主要有遺傳算法（GA）[3]、粒子群算法（PSO）[4]、蟻群算法（ACO）[5]、模擬退火算法（SA）[6]以及人工螢火蟲優(yōu)化算法（AGSO）[7]等，并且都取得了不錯(cuò)的效果。

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

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

1 TSP問題

TSP問題可以抽象描述為在一個(gè)帶權(quán)重的完全無向圖中，找到一個(gè)權(quán)值總和最小的哈密頓回路。其數(shù)學(xué)模型為，要在給出的城市中找到一條最優(yōu)路徑：[V=v1，v2，…vn]，并滿足提下目標(biāo)函數(shù)：

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

其中，[vi]為城市編號(hào)，[dvi，vi+1]為城市[vi]到[vi+1]的距離，[n]為城市總數(shù)，[1≤i≤n]。

2 傳統(tǒng)遺傳算法

傳統(tǒng)遺傳算法基本步驟：

step 1 確定合適的編碼方式，對(duì)種群進(jìn)行初始化。

step 2 建立合適的適應(yīng)度函數(shù)，并計(jì)算生成的種群中個(gè)體的適應(yīng)度值。

step 3 根據(jù)個(gè)體適應(yīng)度值進(jìn)行選擇操作，主要的選擇方式有輪盤賭選擇法和錦標(biāo)賽選擇法等。

step 4 根據(jù)交叉概率進(jìn)行交叉操作，生成新的種群。

step 5 根據(jù)變異概率進(jìn)行變異操作，生成新的種群。

step 6 判斷是否滿足停止條件，如果滿足，則輸出結(jié)果；如果不滿足，則轉(zhuǎn)到step2。

盡管傳統(tǒng)遺傳算法已經(jīng)具備不錯(cuò)的全局尋優(yōu)能力和全局收斂能力，但在處理復(fù)雜問題時(shí)，效率較低，為了追求更高的精度以及更快的收斂速度，本文提出一種改進(jìn)遺傳算法，用于求解TSP問題。

3 改進(jìn)遺傳算法

3.1 種群初始化

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

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

3.2 自適應(yīng)交叉和變異概率

傳統(tǒng)的遺傳算法一般使用固定的交叉和變異概率，這會(huì)導(dǎo)致優(yōu)良個(gè)體被破壞以及劣質(zhì)個(gè)體被保留，影響算法的性能。在本文中設(shè)計(jì)了一種自適應(yīng)交叉和變異概率，根據(jù)當(dāng)前個(gè)體的適應(yīng)度值以及當(dāng)前種群個(gè)體最大適應(yīng)度與平均適應(yīng)度的差值相結(jié)合自動(dòng)調(diào)整交叉和變異概率，算法交叉概率[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]為當(dāng)前種群中個(gè)體適應(yīng)度最大值，[f]為當(dāng)前種群個(gè)體適應(yīng)度平均值，[f']為待交叉的兩個(gè)個(gè)體中適應(yīng)度大的值，[f]為待變異個(gè)體適應(yīng)度值。

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

3.3 加入Metropolis準(zhǔn)則

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

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

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

隨機(jī)選中的城市為C和F，那么打亂之后的順序?yàn)椋?/p>

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

計(jì)算原來路徑長度的大小[distpast]以及新生成路徑適應(yīng)度值[distnew]的大小，比較[distnew]和[dist]的大小，如果[distnew]小于[distpast]，則用新路徑代替原來的路徑，如果[distnew]大于[distpast]，則以概率[p1]接收新路徑。概率[p1]的數(shù)學(xué)表達(dá)式如下所示：

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

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

3.4 逆轉(zhuǎn)操作

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

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

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

隨機(jī)選中的城市為C和F，那么打亂之后的順序?yàn)椋?/p>

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

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

3.5 改進(jìn)自適應(yīng)遺傳算法求解TSP問題具體步驟

step 1 鄰域搜索算法與隨機(jī)生成相結(jié)合，初始化種群。

step 2 計(jì)算適應(yīng)度函數(shù)。

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

step 4 改進(jìn)OX交叉操作。操作如下：

父代1：

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

父代2：

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

隨機(jī)選擇起點(diǎn)和終點(diǎn)，如第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

根據(jù)映射關(guān)系消去路徑中相同的城市;

父代1：

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

父代2：

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

改進(jìn)的OX交叉算子，即使在要交叉的兩個(gè)父代相同的情況下，也會(huì)生成不同的子代。

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

在生成的路徑中隨機(jī)選兩個(gè)城市，交換兩個(gè)城市的位置，如當(dāng)前城市為：

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

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

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

step 6 加入Metropolis準(zhǔn)則，以一定概率接受劣解。

step 7 逆轉(zhuǎn)操作。

step 8 判斷是否滿足停止條件，滿足，則輸出結(jié)果；不滿足，則跳轉(zhuǎn)到step 2。

本文改進(jìn)遺傳算法流程圖如圖1所示。

圖1? 改進(jìn)遺傳算法流程圖

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

為了測(cè)試改進(jìn)遺傳算法的性能，將IGA與另外5種算法在Matlab仿真軟件上對(duì)TSPLIB數(shù)據(jù)集不同城市規(guī)模的實(shí)例進(jìn)行測(cè)試，5種算法分別為傳統(tǒng)遺傳算法（GA）、粒子群算法（PSO）、蟻群算法（ACO）、模擬退火算法（SA）以及結(jié)合2-opt局部尋優(yōu)操作的混合遺傳算法（HGA）。

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

4.2 仿真結(jié)果分析

按照上述實(shí)驗(yàn)前的準(zhǔn)備，將六個(gè)算法在六個(gè)TSPLIB實(shí)例上獨(dú)立運(yùn)行20次，記錄每次的運(yùn)行結(jié)果。找出最優(yōu)解，并結(jié)合TSPLIB實(shí)例的已知最優(yōu)解[15]，根據(jù)公式計(jì)算偏差率，具體公式如下：

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

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

5 結(jié)束語

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

參考文獻(xiàn)（References）：

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

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

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

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

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

[6] 郭樂新.基于模擬退火算法的旅行商問題的實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2012（3）：3-5，18

[7] 周永權(quán)，黃正新.求解TSP的人工螢火蟲群優(yōu)化算法[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] 劉艷琪，劉一杰.基于病毒侵染和逆轉(zhuǎn)操作的改進(jìn)遺傳算法[J].湖南文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2022，34（3）：23-29

[10] 徐佳，韓逢慶，劉奇鑫，等.一種求解TSP的生物信息啟發(fā)式遺傳算法[J].系統(tǒng)仿真學(xué)報(bào)，2022，34（8）：1811-1819

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

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

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

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

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