改進(jìn)混合粒子群算法求解旅行商問題

徐福強(qiáng)，鄒德旋，章猛，羅鴻赟

（江蘇師范大學(xué) 電氣工程及自動化學(xué)院，江蘇 徐州 221116）

0 引言

旅行商問題（TSP）是典型的NP-難問題［1］，也是經(jīng)典的組合優(yōu)化問題，故具有廣泛的應(yīng)用背景，如計算機(jī)聯(lián)網(wǎng)、交通運(yùn)輸、電氣布線、路線規(guī)劃等［2］。獲得高效的TSP 求解算法是組合優(yōu)化領(lǐng)域的一個研究熱點，目前求解TSP 的方法主要分為兩大類。第一類是傳統(tǒng)的精確算法，主要有分支定界法、線性規(guī)劃法、動態(tài)規(guī)劃法等［3］。但是隨著TSP 中城市規(guī)模的增大，該類算法的求解能力顯著下降。第二類是近些年來隨著人工智能的發(fā)展而興起的智能優(yōu)化算法，主要有遺傳算法（GA）［4］、蟻群算法（ACO）［5］、粒子群算法（PSO）［6］、模擬退火算法（SA）［7］等，現(xiàn)已廣泛地應(yīng)用于TSP 求解，并且取得了很好的效果。

由于PSO 具有搜索迅速、容易實現(xiàn)、參數(shù)設(shè)置簡單等優(yōu)點［8］，故對利用PSO 來解決TSP 的研究有著重要意義。但考慮到PSO 最初是用于連續(xù)型問題求解，而TSP 是離散型的組合優(yōu)化問題。針對這個問題，近年來不斷有學(xué)者提出了適用于解決TSP的改進(jìn)PSO。例如，高尚等學(xué)者［6］結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想，提出用混合粒子群算法來求解TSP，并且在遺傳算法的交叉和變異的策略選擇上進(jìn)行了詳細(xì)的介紹，但其解決TSP 的問題規(guī)模太小，并未驗證該算法在大規(guī)模TSP 上的實用性。鄧偉林等學(xué)者［9］提出一種離散粒子群算法來解決TSP，重新定義了速度及其粒子位置的相關(guān)算子，并設(shè)計距離排序矩陣來指導(dǎo)粒子進(jìn)行高效的全局搜索，但是其參數(shù)設(shè)置較為復(fù)雜，算法收斂速度較慢。裴皓晨等學(xué)者［10］提出一種引入混沌算子的改進(jìn)混合粒子群算法優(yōu)化來解決TSP，可使搜索的范圍擴(kuò)大，提高了搜索到更高質(zhì)量解的概率，但在求解規(guī)模稍大的TSP時，解的質(zhì)量明顯下降。Wei等學(xué)者［11］將概率初始化策略和遺傳算子引入到粒子群優(yōu)化算法中，提出一種解決TSP 的改進(jìn)混合粒子群算法，在算法迭代過程中節(jié)省了更多計算資源，增加了種群的多樣性并提高了算法的收斂精度，但在解的質(zhì)量和求解穩(wěn)定性上還有不足。

針對以上所述的解決TSP 的各種改進(jìn)粒子群算法的優(yōu)缺點，本文提出了結(jié)合貪心策略［12］、動態(tài)學(xué)習(xí)概率、Metropolis 準(zhǔn)則［13］和2-opt 局部優(yōu)化［14］的改進(jìn)混合粒子群算法。依據(jù)貪心策略對種群進(jìn)行初始化可以得到更高質(zhì)量的搜索空間，一定程度上保證了解的質(zhì)量；加入動態(tài)學(xué)習(xí)概率來平衡粒子群算法中的個體學(xué)習(xí)和群體學(xué)習(xí)；在個體學(xué)習(xí)和群體學(xué)習(xí)的過程中采用Metropolis 準(zhǔn)則來依一定概率接受劣解，不僅增加了種群多樣性也提高了算法在搜索過程中跳出局部最優(yōu)的能力；變異的部分采用2-opt 局部優(yōu)化的策略可以消除路徑中出現(xiàn)交叉的現(xiàn)象，增強(qiáng)局部搜索能力，并進(jìn)一步提高全局解的質(zhì)量。最后，通過Matlab 將本文改進(jìn)算法和其他4 種智能優(yōu)化算法在TSPLIP 中的8 個實例上進(jìn)行了仿真測試，證明了本文改進(jìn)算法在求解精度、解的穩(wěn)定性上具有更好的表現(xiàn)，并且對大規(guī)模的TSP 也具有較好的求解能力。

1 旅行商問題描述

旅行商問題最早由Flood［15］在1956 年提出，是一個具有代表性的離散組合優(yōu)化問題?？梢悦枋鰹橐粋€商品的推銷員要去若干城市推銷商品，隨機(jī)選擇某一個城市作為起點，從該城市出發(fā)，要求經(jīng)過所有的城市并且只經(jīng)過一次，最后再回到起點城市。也就是構(gòu)成一個哈密頓回路［16］，關(guān)鍵在于找到一條滿足條件的行進(jìn)路線使得整個回路的路徑長度最短。

從圖論的角度來描述TSP［17］如下：設(shè)圖G＝（V，E），這里V表示所有城市組成的頂點集，E是集合V中元素（城市）兩兩相連組成的邊集，設(shè)每2個城市之間的距離記為則求解TSP 的數(shù)學(xué)模型可表示為：

式（1）中的第一項是對從1到n個城市計算最短的路徑距離和，式（1）中的第二項是計算第n個城市回到第一個城市的距離，這2 項相加構(gòu)成一個完整的回路路徑長度。

2 算法分析

2.1 粒子群算法

PSO 是一個由Kennedy 和Eberhart 在1995 年提出的群體智能優(yōu)化算法［18］。其基本思想是先隨機(jī)初始化一群粒子，每個粒子都具有速度和位置以及由目標(biāo)函數(shù)決定的適應(yīng)度值這3 個屬性，再引入個體極值和群體極值的2 個概念。在每次迭代過程中，根據(jù)式（2）和式（3）來更新每個粒子的速度和位置，然后計算適應(yīng)度值，并根據(jù)目前的適應(yīng)度值來更新個體極值和群體極值，再經(jīng)多次迭代，搜索到目標(biāo)函數(shù)的最優(yōu)解。標(biāo)準(zhǔn)PSO 的速度與位置的更新公式如下：

2.2 遺傳算法

遺傳算法是由Holland 教授［19］在所著的《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的。是一種受到生物界自然選擇和自然遺傳現(xiàn)象啟發(fā)的隨機(jī)搜索算法。算法模仿自然遺傳現(xiàn)象中的繁殖、交叉和基因突變的情況［20］，根據(jù)一定的標(biāo)準(zhǔn)來進(jìn)行選擇和保留較好的候選解，此后再經(jīng)過不斷地重復(fù)迭代，直至找到最優(yōu)解或者滿足終止條件為止。

2.3 解決TSP 的混合粒子群算法

混合粒子群算法就是把遺傳算法和粒子群算法進(jìn)行了融合，通過遺傳算法的交叉操作和粒子群算法中的個體學(xué)習(xí)和群體學(xué)習(xí)來對每代粒子個體進(jìn)行優(yōu)秀子代的產(chǎn)生和遴選；在此基礎(chǔ)上將通過遺傳算法的變異來替代實現(xiàn)粒子群算法中的位置更新操作，經(jīng)多次迭代后找到TSP 的最優(yōu)解。近年來，經(jīng)過較多學(xué)者研究和大量的實驗仿真結(jié)果充分地證明了混合粒子群算法的有效性和先進(jìn)性。但是其在求解TSP 的精度和穩(wěn)定性方面還有一定的提升空間，并且對大規(guī)模TSP 的求解能力較差。

3 算法改進(jìn)

3.1 基于貪心策略的種群初始化

智能群體優(yōu)化算法一般是隨機(jī)生成初始種群，這樣容易使初始種群個體的適應(yīng)度值與研究需要的最優(yōu)解的適應(yīng)度值出現(xiàn)很大的偏差。造成算法收斂速度的降低和運(yùn)行耗時的增加，還會導(dǎo)致解的質(zhì)量下降、甚至增加了算法陷入局部最優(yōu)的可能。

本文采用基于貪心策略的種群初始化來有效地保證初始搜索空間的質(zhì)量。具體方法是按照在TSP中兩城市間距離最短的思想來依次選定一個起始城市，然后在剩余城市中選取與上個選定城市距離最近的城市作為下一個城市，循序重復(fù)操作直至最后一個城市。這樣得到的城市序列作為改進(jìn)混合粒子群算法的初始解，在一開始迭代的時候就具有較好的適應(yīng)度值，有利于加快算法的收斂速度，提高算法求解精度。

3.2 加入動態(tài)學(xué)習(xí)概率

在粒子群算法中通過個體學(xué)習(xí)和群體學(xué)習(xí)來更新粒子的速度，個體學(xué)習(xí)有利于拓展粒子的搜索空間，群體學(xué)習(xí)有利于粒子朝全局做最優(yōu)搜索。結(jié)合解決TSP 的具體情況，本文采取加入動態(tài)學(xué)習(xí)概率的方法調(diào)節(jié)與個體最優(yōu)交叉及與群體最優(yōu)交叉的進(jìn)行，來更好地平衡個體學(xué)習(xí)與群體學(xué)習(xí)。動態(tài)學(xué)習(xí)概率的數(shù)學(xué)定義式如下：

其中，iter表示目前的迭代次數(shù)，itermax表示算法設(shè)定的最大迭代次數(shù)。

通過式（4）可知，隨著迭代的不斷進(jìn)行，p1會不斷變大，當(dāng)取一個0～1 之間的隨機(jī)數(shù)大于p1時，與個體最優(yōu)交叉，即個體學(xué)習(xí)；否則，與群體最優(yōu)交叉，即群體學(xué)習(xí)。所以，算法迭代搜索的前期個體學(xué)習(xí)的概率更高，增加了種群的多樣性；到了算法迭代的后期，群體學(xué)習(xí)的概率更高，傾向于和群體最優(yōu)進(jìn)行交叉，利于算法的全局收斂。

3.3 采用Metropolis 準(zhǔn)則接受劣解

由于混合粒子群算法在解決TSP時，容易陷入局部最優(yōu)而導(dǎo)致算法收斂不到最優(yōu)解。所以本文改進(jìn)算法在個體學(xué)習(xí)和群體學(xué)習(xí)中采用Metropolis 準(zhǔn)則來依概率p2接受劣解，從而在一定程度上豐富了種群粒子的多樣性，提高了算法跳出局部最優(yōu)的能力。概率p2的數(shù)學(xué)表達(dá)式如下：

其中，distnew表示經(jīng)過個體學(xué)習(xí)或群體學(xué)習(xí)產(chǎn)生的新城市序列對應(yīng)的路徑長度；distpast表示之前的舊城市序列對應(yīng)的路徑距離；隨著迭代的進(jìn)行，itermax-0.95× iter的值在不斷減小，根據(jù)指數(shù)函數(shù)的特點，p2的值在逐漸減小，所以迭代到后期，接受劣解的可能性就不斷降低，保證了算法的收斂性。當(dāng)distnew ＜distpast時，直接用新城市序列替換舊城市序列，實現(xiàn)算法朝距離最短的城市序列方向搜索。否則，在個體學(xué)習(xí)和群體學(xué)習(xí)中依據(jù)rand ＜p2的概率來接受distnew ＞distpast的城市序列。并且如果distnew -distpast的值較小，也就意味著新解和舊解對應(yīng)路徑距離相差得小，p2值反而越大，則rand ＜p2的概率越大，接受該劣解的可能性就更大，并且該劣解經(jīng)過此后的2-opt 局部優(yōu)化得到更短路徑的可能性也越大。

3.4 2-opt 局部優(yōu)化

TSP 中很容易出現(xiàn)路徑交叉的現(xiàn)象，并且路徑一旦有交叉勢必會導(dǎo)致整個路徑距離的增加，故而消除交叉現(xiàn)象的發(fā)生也是解決TSP 的重要一步。考慮到2-opt 局部優(yōu)化的耗時性，本文對個體學(xué)習(xí)和群體學(xué)習(xí)后的粒子適應(yīng)度值進(jìn)行升序排列，取適應(yīng)度值從小到大且20%種群規(guī)模數(shù)量的粒子進(jìn)行2-opt局部優(yōu)化。2-opt 局部優(yōu)化操作示意如圖1 所示。

圖1中，圖1（a）表示原路徑，是經(jīng)過個體學(xué)習(xí)或群體學(xué)習(xí)得到的目前搜索到的最好的城市序列：A→B→C→D→E→F→G→H→A，可以直觀地看出城市B和城市C及城市F和城市G之間有路徑交叉的現(xiàn)象；再觀察圖1（b）中的新路徑，就是把城市B和城市G的位置進(jìn)行了調(diào)換，同時把原來城市B和城市G之間的城市序列順序進(jìn)行了倒置。新的城市序列為：A→G→F→E→D→C→B→H→A。顯而易見，之前的交叉現(xiàn)象被消除了，路徑的長度也縮短了，故證明了2-opt 局部優(yōu)化的有效性。

圖1 2-opt 局部優(yōu)化操作示意圖Fig.1 Schematic diagram of 2-opt local optimization operation

本文采取2-opt 局部優(yōu)化作為本文改進(jìn)算法中的變異操作，同時也實現(xiàn)粒子群算法中綜合個體學(xué)習(xí)和群體學(xué)習(xí)后的位置更新操作。經(jīng)過2-opt 優(yōu)化后，比較選擇更短的城市路徑距離對應(yīng)的城市序列，使得算法朝著全局最優(yōu)搜索。

3.5 改進(jìn)混合粒子群優(yōu)化算法解決TSP 的步驟

步驟1加載TSP 實例和計算城市間距離。

步驟2算法初始化，包括種群的初始化，結(jié)合城市間的距離來基于貪心策略得到較高質(zhì)量的初始種群，同時設(shè)置本文改進(jìn)算法的最大迭代次數(shù)，作為算法結(jié)束的標(biāo)志條件。

步驟3計算粒子適應(yīng)度值，并確定個體最優(yōu)和群體最優(yōu)。

步驟4根據(jù)動態(tài)學(xué)習(xí)概率p1來進(jìn)行學(xué)習(xí)策略的選擇，如果隨機(jī)數(shù)大于p1，則選擇個體學(xué)習(xí)，與粒子個體最優(yōu)進(jìn)行交叉，否則選擇群體學(xué)習(xí)，與群體最優(yōu)進(jìn)行交叉，并且在個體學(xué)習(xí)和群體學(xué)習(xí)中加入了Metropolis 準(zhǔn)則，依概率p2來接受劣解。

步驟5對經(jīng)過個體學(xué)習(xí)和群體學(xué)習(xí)的種群進(jìn)行2-opt 局部優(yōu)化操作，消除路徑交叉的情況，搜索更優(yōu)解。

步驟6判斷是否達(dá)到算法終止條件，本文為設(shè)定的最大迭代次數(shù)，如果達(dá)到，輸出最優(yōu)解及對應(yīng)的最短路徑長度，否則返回步驟3，重復(fù)執(zhí)行，直至滿足算法終止條件。

本文改進(jìn)混合粒子群算法流程如圖2 所示。

圖2 改進(jìn)混合粒子群算法流程圖Fig.2 Flow chart of improved hybrid particle swarm optimization

4 仿真實驗及分析

4.1 仿真實驗基礎(chǔ)

根據(jù)以上分析，為了驗證本文改進(jìn)混合粒子群算法解決TSP 的可行性與有效性，將混合粒子群算法、GA、ACO、SA 及本文改進(jìn)混合粒子群算法在Matlab 仿真軟件上對TSPLIB 中的8 個不同城市規(guī)模的實例進(jìn)行測試。

本文仿真實驗環(huán)境配置如下：硬件方面使用AMD Ryzen 7 5800H 3.2 GHz CPU，16 G RAM 的計算機(jī)；軟件環(huán)境基于Windows 10，Matlab R2019a。

本文仿真實驗選用了TSPLIB 中8 個不同城市規(guī)模的實例，從小到大分別是Oliver30，eil51，st70，eil76，eil101，ch150，pr226，pcb442?；旌狭Ｗ尤核惴▍?shù)設(shè)置：種群規(guī)模取1 000，最大迭代次數(shù)取200，與個體最優(yōu)交叉的概率取0.5，與群體最優(yōu)交叉的概率取0.5，變異的概率取0.3；GA 參數(shù)設(shè)置：種群規(guī)模取1 000，最大迭代次數(shù)取200，交叉概率取0.7，變異概率取0.2；ACO 參數(shù)設(shè)置：螞蟻數(shù)量等于TSPLIB 實例中的城市個數(shù)，最大迭代次數(shù)取200，信息素重要程度因子取1，啟發(fā)函數(shù)的重要程度因子取5，信息素?fù)]發(fā)因子取0.2；SA 參數(shù)設(shè)置：初始溫度61 ℃，結(jié)束溫度3 ℃，溫度衰減系數(shù)取0.985，馬爾科夫鏈長度取TSPLIB 實例中城市個數(shù)的100倍；本文算法參數(shù)：種群規(guī)模等于TSPLIB 實例中城市個數(shù)，最大迭代次數(shù)取200，動態(tài)學(xué)習(xí)概率為p1，Metropolis 準(zhǔn)則中接受劣解的概率為p2，選取進(jìn)行2-opt局部優(yōu)化的粒子個數(shù)為種群規(guī)模的20%。

4.2 實驗結(jié)果與分析

經(jīng)過以上分析，將5 種算法在8 個TSPLIB 實例上獨(dú)立運(yùn)行30次，記錄每次的運(yùn)行結(jié)果。對各算法在每個TSPLIB 實例上運(yùn)行得到的30 個結(jié)果進(jìn)行處理，找到最優(yōu)解、最差解，計算出平均解，再結(jié)合TSPLIB 實例的已知最優(yōu)解［21］，根據(jù)式（6）計算出平均偏差率。具體見如下：

5 種算法的實驗結(jié)果見表1。表1中，測試實例下面的括號中數(shù)值就是目前對應(yīng)TSPLIB 實例的已知最優(yōu)解。由表1 可以發(fā)現(xiàn)在解決實例Oliver30時，各算法搜索到的最優(yōu)解都很接近已知最優(yōu)解，并且平均偏差率都很小，說明各算法搜索的穩(wěn)定性都還不錯，其中SA 的效果最好，略優(yōu)于本文改進(jìn)算法；而隨著TSP 規(guī)模的增加，各算法搜索到的最優(yōu)解開始慢慢與已知最優(yōu)解的偏差增大，其中混合粒子群算法和GA 體現(xiàn)得尤為明顯，當(dāng)TSP 規(guī)模到100 及以上時，求解的質(zhì)量很差，故而混合粒子群算法和GA 對ch150、pr226、pcb442 這3 個實例的實驗結(jié)果直接舍棄；雖然在本文仿真實驗中ACO 和SA求解了大規(guī)模TSP 的解，但是觀察表1 可知，ACO和SA 的最優(yōu)解和偏差率都比本文改進(jìn)算法的結(jié)果大，表明了本文改進(jìn)算法對于解決大規(guī)模的TSP 具有更好的適應(yīng)性和明顯優(yōu)勢。

表1 算法實驗結(jié)果Tab.1 Experimental results of the algorithm

為了更加直觀地了解5 種算法解決TSPLIP 實例的過程情況，本文繪制出了5 種算法解決eil51、st70、ch150、pcb442 這4 個具有代表性的實例上的迭代曲線，如圖3～圖6 所示。觀察圖3 和圖4 可以發(fā)現(xiàn)，本文改進(jìn)混合PSO 的初始解就具有很大優(yōu)勢，并且收斂的速度要比其他4 種算法明顯更快，搜索到最優(yōu)解的迭代次數(shù)更少，凸顯出算法的尋優(yōu)能力較強(qiáng)。觀察圖5 和圖6 可知，當(dāng)TSP 的規(guī)模較大時，本文提出的改進(jìn)混合PSO 仍然具有很強(qiáng)的尋優(yōu)能力。與ACO 和SA 相比，求解TSP 的質(zhì)量更高，并且較少的迭代次數(shù)就可以搜索到最優(yōu)解，表明了本文改進(jìn)算法的適應(yīng)能力強(qiáng)和求解精度高。為了直觀地考察本文改進(jìn)算法的求解效果，根據(jù)上述分析做出對應(yīng)的求解到的最優(yōu)路徑圖如圖7～圖10所示。

圖3 eil51 迭代曲線圖Fig.3 Iteration curve of eil51

圖4 st70 迭代曲線圖Fig.4 Iteration curve of st70

圖5 ch150 迭代曲線圖Fig.5 Iteration curve of ch150

圖6 pcb442 迭代曲線圖Fig.6 Iteration curve of pcb442

圖7 eil51 最優(yōu)路徑圖Fig.7 Optimal path of eil51

圖8 st70 最優(yōu)路徑圖Fig.8 Optimal path of st70

圖9 ch150 最優(yōu)路徑圖Fig.9 Optimal path of ch150

圖10 pcb442 最優(yōu)路徑圖Fig.10 Optimal path of pcb442

5 結(jié)束語

本文提出了一種改進(jìn)混合粒子群算法來解決旅行商問題，利用基于貪心策略的種群初始化很好地保證了算法搜索空間的質(zhì)量；在算法的搜索過程中加入動態(tài)學(xué)習(xí)概率來選擇個體學(xué)習(xí)或群體學(xué)習(xí)，并在每個學(xué)習(xí)中引入Metropolis 準(zhǔn)則來依一定概率接受劣解，既能增加種群粒子的多樣性，也能提高算法跳出局部最優(yōu)的能力；再將經(jīng)過個體學(xué)習(xí)和群體學(xué)習(xí)得到的城市序列進(jìn)行2-opt 局部優(yōu)化，有效地消除了城市路徑間出現(xiàn)交叉的現(xiàn)象，并且較好地保留更短的路徑及對應(yīng)的城市序列，保證了算法朝著全局最優(yōu)的方向進(jìn)行收斂，提高了算法求解的精度。最后和其他4 種智能優(yōu)化算法在Matlab 軟件上對TSPLIB 的8 個不同規(guī)模的實例進(jìn)行了測試，仿真結(jié)果表明了本文改進(jìn)算法的求解精度更高，算法的穩(wěn)定性更好，并且更加適應(yīng)于大規(guī)模TSP 的求解。