求解TSP的離散野馬優化算法

蔡延光，方春城，2，吳艷林，陳華君

1.廣東工業大學 自動化學院，廣州 510006

2.揭陽職業技術學院 機電工程系，廣東 揭陽 522051

旅行商問題（traveling salesman problem，TSP）是組合優化領域一個著名問題，該問題已被證明是NPhard問題[1]，很難精確求解，目前常見的主要解法有線性規劃法、啟發式算法、元啟發式算法等方法。元啟發式算法求解方法先后出現遺傳算法（genetic algorithm，GA）、蟻群算法（ant colony optimization，ACO）、粒子群算法（particle swarm optimization，PSO）、灰狼算法（gray wolf algorithm，GWA）、蝙蝠算法（bat algorithm，BA）等。近幾年以來，更是出現各種新的搜索策略或者新的群體智能優化算法求解TSP問題，如林敏等[2]提出基因-表現型的布谷鳥算法，基因由小數和整數兩部分組成，小數部分決定訪問順序，整數部分代表城市編碼，兩部分的信息組成鄰域空間，布谷鳥在該空間進行Levy 飛行更新，該算法對大規模算例效果較好。孫鑒等[3]提出一種基于大規模鄰域搜索的模擬退火算法求解TSP。在模擬退火算法中引入大規模鄰域搜索策略和2-Opt（2-optimization）策略，實現對TSP問題的求解。文獻[4]提出一種基于粒子群優化改進蟻群算法的TSP 解法。文獻[5]結合2-Opt 策略提出一種新的離散灰狼算法求解TSP 問題。文獻[6]用麻雀搜索算法（sparrow search algorithm，SSA）求解TSP 問題，該方法容易陷入局部最優，且沒有足夠的停滯。蟻群算法[7]為經典求解方法，但該算法容易陷入局部最優，隨著城市數量的增加，其求解結果的劣勢較為明顯。文獻[8]提出了一種改進的樹種子算法（tree seed algorithm，TSA）求解TSP 問題，實驗結果表明，該算法是一種相對較好的求解方法。文獻[9]和文獻[10]分別提出了一種離散蜘蛛猴優化算法（discrete spider monkey optimization，DSMO）和暫定速度粒子群算法（velocity tentative particle swarm optimization，VTPSO），結合序列交換策略，實現求解TSP問題。暫定速度粒子群算法[11]在粒子群算法的基礎上增加序列變換策略，實現對TSP 的求解。文獻[12]結合序列交換策略和3-Op（t3-optimization）搜索策略，提出一種交換序列人工蜂群算法（swap sequence based artificial bee colony algorithm，ABCSS）求解TSP 問題。文獻[13]提出一種基于啟發式信息的離散混合式蛙跳算法（discrete shuffled frog-leaping algorithm，DSFLA）求解TSP問題。盡管很多學者做出了大量的探索，取得一定效果，但仍存在一些不足。本文提出一種離散野馬優化算法（discrete wild horse optimizer，DWHO）對TSP 進行求解，具有良好的求解能力、更高精度和收斂速度。

野馬優化算法（wild horse optimizer，WHO）是由Naruei 和Keynia[14]于2021 年提出的一種新的元啟發式算法，用于求解連續系統的尋優問題；其靈感來自于野馬的放牧、交配和群體領導行為。目前野馬優化算法的研究主要集中在工程問題和能耗預測。文獻[15]應用野馬優化算法研究了輻射狀配電網分布式電源優化規劃問題；文獻[16]應用野馬優化算法研究混合多區域電力系統頻率調節的控制問題；文獻[17]在研究住宅建筑的能耗時，引入野馬優化算法對能源消耗進行預測。野馬優化算法的初衷是為求解工程連續問題而提出的；因此，為了使該算法能用于求解離散問題，需要對求解結果進行離散化解碼。本文提出一種映射方法實現對野馬優化算法求解結果進行離散化解碼，命名為最小位置匹配值法（min-position matched value，MPMV）。只有離散化解碼之后的解才能表示TSP 問題的解，離散化解碼后的每一匹野馬代表TSP 的一個解。本文應用最小位置匹配值法提出一種離散野馬優化算法求解旅行商問題，引入變鄰域策略，提高算法的搜索能力；選取TSPLIB標準庫33個標準算例進行大量實驗，并與交換序列人工蜂群算法（ABCSS）[12]、離散蜘蛛猴優化算法（DSMO）[9]等算法的求解結果進行比較。實驗表明，離散野馬優化算法的求解結果優于以上兩種算法的求解結果，尋優能力也比較強；與以上兩種算法相比較，最優解改進率最大值分別達到4.52%和3.41%；實驗表明離散野馬優化算法的收斂速度較好，精度也處于最高。

1 TSP問題的數學模型

有n個城市，已知任兩個城市之間的距離，求一條路徑恰好經過每個城市且每個城市只經過一次的回路，使得路徑總長度最小。該問題的數學模型為[18-19]：目標函數：

決策變量：

其中，L(c)表示路徑的長度，c∈(c1,c2,…,cn)為訪問的城市，1,2,…,n表示城市的編號，V為城市集合，S為子回路。cij表示從城市i到城市j的距離，決策變量xij表示從i到j則取1，其他情況取0。式（3）和（4）為平衡約束，表示從上一個節點出發去訪問當前節點，并從當前節點出發去訪問下一個節點。式（5）表示不能出現子回路。

2 野馬優化算法原理

野馬優化算法，其靈感來自野馬的社會生活行為。野馬群是由穩定的家庭群體組成的馬群，其中包括一匹種馬，一匹或若干匹母馬及其后代，種馬是種群的領導者，領導者（種馬）帶領組內成員尋找棲息地。野馬優化算法是根據野馬群體的行為，放牧、交配、支配和領導而設計的智能算法并對連續系統問題進行優化。

野馬優化算法基本原理包括以下五部分內容：

（1）創建初始種群、組建馬群分組和挑選領導者。隨機產生一個初始種群，將種群進行分組，每個小組由一匹種馬擔任領導者，并由一匹或若干匹母馬及后代組成。

（2）野馬的放牧和交配。小馬通常大部分時間都在群體周圍吃草。為了實施放牧行為，將種馬視為放牧區的中心，小組成員在具有不同半徑的領導者周圍移動和搜索，這就是野馬的放牧行為。一匹小馬離開組i并加入臨時組，另一匹小馬離開組j并加入臨時組。假設這兩匹小馬分別是雄性和雌性，由于這兩匹小馬沒有家庭關系，它們可以進行交配。由此產生的后代必須離開臨時組，加入另一個組，如k組。這就構成了野馬的交配行為，形成新一代的小馬。所有不同的野馬都會重復這種離開、交配和繁殖的循環。

（3）由組長（種馬）領導小組。領導者帶領組成員前往更合適的棲息地，如果當前組占主導地位，那么就使用這個地區；如果另一個小組占主導地位，它們必須離開該地。棲息地代表當前最優解。

（4）領導者的交流與選拔。根據適應度選擇領導者，如果小組內部中存在組員的適應度優于組長，則組長和相應組員的位置進行對換，小組長的位置代表本小組的最優解。

（5）保存最優解。比較各個小組組長的適應度，適應度最優的小組長代表全局最優解，將其保存。

3 離散野馬優化算法求解TSP問題

3.1 編碼解碼策略

為了更好遵循野馬優化算法的基本原理，采用實數編碼代表野馬各維數值。TSP問題屬于離散問題，為使野馬優化算法適應于求解TSP問題，需將求解結果進行離散化解碼，解碼后的每個個體就代表TSP 的一個解。Ali 等[20]提出BMV（best-matched value）解碼方法，將向量中的連續值轉化為索引值，最后隨機選取若干個體，根據某一概率將其部分基因按另一概率與上一代獲得的最優解的相應基因進行匹配。Li 等[21]提出LRV（largest ranked value），主要應用在車間作業調度的作業順序，基于隨機鍵的最大排序值，實現離散化解碼。Ai 等[22]提出SR-1（solution representation-1）和SR-2（solution representation-2）解碼方法，這種解碼方法首先應用在車輛路徑規劃問題中，SR-1采用2 m維度進行編碼，SR-2采用3 m維度進行編碼，將路徑進行分割，雖然能實現將實數編碼轉化為整數解碼，但采用對路徑的分割，增加了解碼的計算量和難度。Prins[23]提出PRINS解碼方法，也是這一種針對求解車輛路徑問題的解碼方法，同樣存在計算量大的缺點。本文提出一種映射方法實現對野馬優化算法求解結果的離散化解碼，命名為最小位置匹配值法（MPMV）。離散解碼策略的主要原理如下：野馬每個個體各個維度的數值都用實數表示，代表各個個體的位置，將這些實數映射到整數域，個體中各維度的最小值對應整數1、其次對應整數2、依次類推。解碼后每匹野馬個體各維度的數值對應城市的編號。MPMV 解碼方法與上述幾種解碼方法相比，解碼過程簡單容易實現。

在應用野馬優化算法過程中，只有將實數編碼的個體數據離散解碼后才能表示路徑編號。設有一個7 維度的個體，其各維度的值為[3.2，-0.6，4.8，-3.7，5.8，1.5，6.3]，經過MPMV離散化解碼后，其值變為[4，2，5，1，6，3，7]。離散解碼方案見圖1所示。

圖1 最小位置匹配值法離散化方案Fig.1 Minimum position matching value method discretization scheme

3.2 算法設計

野馬優化算法首先須定義種群規模popN，種馬比例PS，交配概率PC。種馬、小馬的位置定義為Xi=(Xi1,Xi2,…,Xin)，i∈(1,2,…,popN)，Xi表示第i個個體，popN∈(N+)為種群的規模；n為城市個數。種馬數量NStallion=popN×PS，小馬的數量Nfoal=popN×(1-PS)；第i匹野馬遍歷的城市路徑為：Xi1?Xi2?…?Xin?Xi1。

小馬放牧行為按式（6）進行：

Stallion是領導者（種馬）的位置，R為[－2，2]內的隨機數，主要控制個體與領導者間的角度；自適應機制Z的計算方式由式（7）～（9）表示：

其中，P是由0和1組成的向量，R1，R3均為[0，1]范圍內均勻分布的隨機向量，R2為[0，1]內一隨機數。IDX為滿足條件P==0 的隨機向量R1返回的索引值，Θ為點乘。TDR表示從1線性遞減到0的系數，iter為迭代次數，maxiter為最大迭代數。

小馬的交配行為，如式（11）表示：

領導者帶領小組成員前往更合適的棲息地，如果當前組占主導地位，那么就使用這個地區；如果另一個小組占主導地位，它們必須離開該地，用式（12）來表示該操作。

領導者的交流與選拔。首先，隨機選擇領導者以保持算法的多樣性。在算法的后期階段，根據適應度選擇領導者。如果組內一名組員個體的適應度優于組長，則組長和相應組員的位置將根據式（13）進行更改。

最后比較各組組長的適應度，適應度最優者代表本輪的最優解。適應度函數如式（14），fitness為個體適應度，L(c)表示路徑長度。

3.3 局部搜索策略

為使算法具有良好的局部搜索能力，引入變鄰域搜索策略，采用三種鄰域搜索策略，分別是交換操作、逆轉操作、插入操作。

3.3.1 交換操作

以路徑為7 個城市為例，假設當前路徑為1?2?3?4?5?6?7，任意選取兩個位置，這里選取第2個位置和第6個位置的城市進行交換操作，操作后的路徑變為1?6?3?4?5?2?7。交換操作示意圖如圖2。

圖2 交換操作示意圖Fig.2 Swap operation diagram

3.3.2 逆操作

繼續以7 個城市為例，假設當前路徑為1?2?3?4?5?6?7，任意選取兩個位置，選取第2個位置和第6個位置之間的城市進行逆操作，操作后的路徑變為1?6?5?4?3?2?7。逆操作示意圖如圖3。

圖3 逆操作示意圖Fig.3 Reverse operation diagram

3.3.3 插入操作

以7 個城市為例，假設當前路徑為1?2?3?4?5?6?7，任意選取兩個位置，將選取的第一個城市插入到第二個被選取的城市后面。繼續用第2個位置和第6個位置為例進行插入操作。操作后的路徑變為1?3?4?5?6?2?7。插入操作示意圖如圖4。

圖4 插入操作示意圖Fig.4 Insertion operation diagram

3.4 算法步驟

因本文算法是為求解離散化問題而提出，故命名為離散野馬優化算法（discrete wild horse optimizer，DWHO）。

步驟1初始化。定義種群規模popN，種馬比例PS，交配概率PC，迭代次數iter；

步驟2創建分組并選擇各組領導；

步驟3離散化種群個體；

步驟4計算領導（種馬）適應度fitness；

步驟5按式（10）計算參數TDR；

步驟6按式（9）計算自適應參數Z；

步驟7取隨機數Rand并判斷是否大于交配概率PC，如果滿足轉到步驟8，否則轉到步驟9；

步驟8按式（6）更新小馬位置；

步驟9小馬按式（11）交配產生新一代小馬并更新位置；

步驟10離散化小馬個體并計算適應度fitness；

步驟11按式（12）更新領導（種馬）位置；

步驟12離散化種馬個體并計算適應度fitness；

步驟13按式（13）選擇領導（種馬）；

步驟14判斷是否所有分組都已完成更新，如果滿足就暫存最優解并轉入步驟15，否則轉入步驟6；

步驟15進行變鄰域搜索，更新最優解；

步驟16判斷是否滿足結束條件，如果滿足轉入步驟17，否則轉入步驟5；

步驟17結束迭代并輸出最優解。

4 實驗仿真與分析

4.1 實驗環境及參數設置

實驗操作系統為Win7，CPU為Intel Core i55200-U，2.20 GHz，內存為8 GB，實驗軟件用MATLAB 2016B。

實驗中，令種群規模popN=50，為確保各組小馬數量一致，PS可以取0.2 或0.5，當種馬比例PS=0.2，各組的小馬數量大于種馬數量，能確保小組內小馬的多樣性，因此，實驗中取PS=0.2。通過大量實驗發現，當PC=0.13 實驗效果較好，故交配概率PC取0.13。最大迭代次數maxiter=1 000。初始種群采用隨機種群，編碼采用實數編碼，解碼應用最小位置匹配值法。采用TSPLIB 標準庫提供的標準算例進行實驗，每個算例分別單獨運行20次。

定義誤差率（Gap）等于所得最優解（best solution，BS）與已知最優解（best known solution，BKS）的差值除以已知最優解再乘以100%，如式（15）所示。同時定義算法最優解改進率（best solution improvement rate，BSIR），BS1表示第一個算法的最優解，BS2表示第二個算法的最優解，BSIR 表示的就是第二個算法的求解結果與第一個算法的求解結果相比較的改進程度，如式（16）所示。

4.2 TSP實驗分析

4.2.1 DWHO算法求TSP問題的求解能力

選取TSPLIB標準庫33個算例進行實驗，將DWHO的實驗結果和ABCSS[12]、DSMO[9]兩種算法的實驗結果進行比較，比較結果如表1所示。

表1 DWHO最優解與其他算法實驗結果比較Table 1 Best solution of DWHO compared with other algorithms

由表1 可以看出，在小規模TSP 算例中，離散野馬優化算法的計算結果比較理想，大部分算例求出的最優解與已知最優解一致或非常接近。算例burma14、ulysses16、ulysses22、pr76、pr124求得的最優解等于已知最優解，gr96 優于已知最優解。33 個算例中共有27 個算例求出的最優解等于或優于其他兩種算法的最優解，即表1中第6列的數據加粗并加下劃線標出部分。

從表1中可以看出，針對大規模TSP算例，離散野馬優化算法的尋優能力比其他兩種算法強，算例kroC100的最優解非常接近已知最優解，其誤差率為0.01%，算例rd100、pr152、pr226、gr229 的誤差率分別只有0.09%、0.19%、0.45%、0.17%。圖5是離散野馬優化算法分別求解算例kroC100、pr124、pr152、pr226 的最優路徑圖。同時，對各種算法的Wilcoxon 秩和檢驗如表2 所示。33個算例中，本文算法比被比較的兩種算法的求解結果普遍好，實驗結果顯示本文所提算法的求解能力的優越性。

圖5 DWHO求解算例kroC100、pr124、pr152、pr226的最優路徑Fig.5 Best routing of kroC100，pr124，pr152 and pr226 by DWHO

離散野馬優化算法的求解結果與其他兩種算法的求解結果的精確度進行比較，結果如表3 所示。表3 數據帶負號表明離散野馬優化算法的求解結果比被比較的算法更優，正的則表示相反。表明離散野馬優化算法比其他兩種算法的求解結果有著明顯的改善；與ABCSS、DSMO兩種算法相比較，最優解的改進率最大值分別達到4.52%和3.41%，即帶下劃線并加粗的數據。進一步比較表1～表3 可以發現，DWHO 在求解中小規模算例時，能很好地求出已知最優解或者是非常接近已知最優解，在三個算法中的求解能力最強；對于大規模算例，隨著求解問題維度的增加，本文算法的求解能力略微下降，導致在個別算例的求解表現不一定完全優于被比較的算法。一方面是因為受到變鄰域搜索策略的影響。采用鄰域搜索策略會使算法在搜索的過程中偶爾出現跳不出局部最優，使本文算法在個別算例的求解結果不一定能比被比較算法表現好；另一方面，因本文算法屬元啟發式算法，算法在初始化及迭代過程中的隨機參數也會影響算法的求解能力，這也是元啟發式算法的普遍缺陷。

表3 DWHO最優解對比其他算法的改進率Table 3 Improvement rate of DWHO best solution compared with other algorithms

4.2.2 DWHO算法時間復雜度分析

假設城市的個數為n，算法最大迭代次數為maxiter，DWHO種群規模為m，種群初始化時間復雜度為O(n)，馬群放牧與交配時間復雜度為O(n)，計算適應度值時間復雜度為O(n2)，變領域操作時間復雜度為O(3×n)，計算全局最優值時間復雜度為O(n)，離散野馬優化算法總的時間復雜度為O(maxiter×m×n2)。

同樣，進一步分析ABCSS、DSMO兩種算法的時間復雜度。假設ABCSS 算法的蜜源為SN個，算法初始化的時間復雜度為O(SN×n)，算法在雇傭蜂階段產生了三個新種群，時間復雜度為O(3×SN×n)，序列交換操作時間復雜度為O(n2)，因此ABCSS算法總的時間復雜度為O(maxiter×SN×n)。設DSMO種群規模為m，DSMO 算法初始化種群時間復雜度為O(n)，蜘蛛猴位置更新的時間復雜度為O(n)，蜘蛛猴被選中的時間復雜度為O(n)，則選取全局領導者時間復雜度為O(m×lbn)，本地領導者決策階段蜘蛛猴位置更新的時間復雜度為O(n)，全局領導者決策階段決定種群分組或者融合為一個組，時間復雜度為O(m×lbn)，序列交換操作時間復雜度為O(n2)，因此DSMO算法總的時間復雜度為O(maxiter×(m×lbn+n2))。

通過比較，可以發現DWHO 與其他兩種比較算法相比，并沒有增加時間復雜度，證明本文算法的有效性。

4.2.3 交叉概率PC對算法求解能力的影響

進一步分析交配概率PC對算法求解能力的影響。選取TSPLIB數據集的ulysses16、pr76、kroA100、lin318四個算例進行比較。PC分別取0.05、0.13、0.45、0.8 進行實驗，比較算法在不同PC取值情況下的求解能力，結果如圖6 所示。為方便比較，迭代次數取200 次。實驗表明，當PC在0.13附近取值時，算法的求解能力較好。

圖6 不同PC對算法求解能力的影響Fig.6 Influence of different PC on solving ability of algorithm

5 結語

本文提出離散野馬優化算法求解TSP 問題。應用最小位置匹配值法對求解結果進行離散化解碼，使野馬優化算法能應用于求解TSP 問題，引入變鄰域搜索策略，增強算法的局部搜索能力，提升算法的收斂速度。通過大量實驗，并將離散野馬優化算法的求解結果和ABCSS、DSMO 兩種算法的求解結果進行比較，從比較的結果可以看出，離散野馬優化算法的尋優能力明顯優于另外兩種算法。在求解大規模TSP問題，除極個別算例外，求出的最優解的誤差率都比較小。大量實驗表明離散野馬優化算法求解TSP 效果較好，比ABCSS、DSMO 兩種算法的求解結果有著較明顯的改善。與ABCSS、DSMO 兩種算法比較，離散野馬優化算法的最優解的改進率最大值分別達到4.52%和3.41%，可見本文提出的離散野馬優化算法求解精度比較高，求解能力較強；因此，可以得出結論，通過離散化解碼并引入適當的搜索策略，野馬優化算法可以成功地應用于求解離散問題。同時，本文所提算法也存在一定的不足，比如在求解大規模算例時，因采用鄰域局部搜索策略，隨著求解問題維度的增加，算法求解能力略微下降，導致個別算例的求解結果未能完全優于被比較算法。在今后的工作中，將進一步探索引入其他局部搜索策略進行改進，也可以混合其他優化算法進行改進，使離散野馬優化算法能更好地應用于求解離散化問題。