貪婪隨機自適應灰狼優化算法求解TSP問題

高珊 孟亮

關鍵詞： GRAGWO算法; 貪婪隨機自適應算法; 灰狼優化算法; 群體智能; 旅行商問題; 組合優化

中圖分類號： TN911?34; TP393 ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）14?0046?05

Greedy randomized adaptive grey wolf optimization algorithm for solving TSP difficulty

GAO Shan， MENG Liang

（College of Information and Computer， Taiyuan University of Technology， Taiyuan 030024， China）

Abstract： A greedy randomized adaptive grey wolf optimization （GRAGWO） algorithm is proposed to solve TSP difficulty. GRAGWO algorithm is based on the greedy randomized adaptive search procedures （GRASP）， which adopts construction phase of GRASP to generate the initial solution and the grey wolf optimization （GWO） algorithm is used in the local search phase to optimize its searched result. GWO algorithm cannot be directly used to solve discrete problems because it is easy to fall into local optimum， resulting in lower convergence rate in the later period. According to the characteristics of TSP， the grey wolf coding mode is redefined to solve the TSP problem， which is easy to form a local optimal path and leads to the decline of population diversity with the increase of iterations. Several groups of TSP problems in different scales in TSPLIB database were used as experimental cases. The GRAGWO algorithm is compared with other bionic algorithms in this paper. The results show that GRAGWO algorithm has relative advantages in the aspects of solving accuracy， stability and large?scale urban problems.

Keywords： GRAGWO algorithm; greedy randomized adaptive search procedure; grey wolf optimization algorithm; swarm intelligence; traveling salesman problem; combination optimization

0 ?引 ?言

旅行商問題是一個典型的組合優化問題，該問題假設一位旅行商需訪問n個城市，城市之間的間距是固定的，旅行商從一指定的城市出發，且不重復的訪問剩余城市，最后回到起始城市，在所有的回路中求出最短路徑[1?2]。TSP問題應用非常廣泛，例如繪制基因組圖譜、望遠鏡、X射線、操控工業機械、安排生產作業任務等。TSP問題是著名的NP完全問題，求解TSP問題有精確算法和啟發式算法兩種。精確算法能保證在指數級次數中找到最好結果，但其本身非常復雜，且對計算機要求較高;啟發式算法普遍簡單，運行時間短，例如模擬退火算法、遺傳算法、局部搜索算法等，但易陷入局部最優。

貪婪隨機自適應搜索算法（Greedy Randomized Adaptive Search Procedures，GRASP）是一種求解組合優化問題的啟發式算法[3]?；依莾灮惴ㄊ?014年由Mirjalili等人提出的啟發式智能算法。該算法模擬自然界灰狼等級制度和狼群搜索獵物過程，利用灰狼種群內部等級制度，實現對目標獵物函數的優化過程[4]。該算法具有優良的收斂穩定性與較強的全局探索能力。本文利用GRASP算法尋求初始解，從而加速灰狼算法的收斂速度，且提高其局部搜索能力。實驗表明，兩種算法的結合可以高效提高求解速度與解的質量。

1 ?算法原理

1.1 貪婪隨機自適應搜索算法

GRASP算法分兩個階段，構造階段和局部搜索階段[3]。在構造階段，初始化可行解S和候選集C，并對候選集的每一個元素進行評估，判斷是否可加入限制候選列表（Restricted Candidate List，RCL）。每次從RCL中隨機選取一個值與可行解S進行比對，更新RCL的元素，并對包含的所有元素進行再次評估，直到滿足條件時結束。

RCL規模大小也會影響此算法性能，規模過大會生成很多差別的解。RCL通常采用靜態固定法和動態調整法來調整列表規模，體現了GRASP算法自適應功能。

在第一階段會得到質量不高的可行解，因此在第二階段，可行解需要以持續不斷的迭代方式進行局部搜索，以求得最優解。若局部新優解S比目前的優解S*更優的話，就更換S*，直到找到最優解。選擇相鄰解在局部搜索階段有兩種方法：最優適應和首次適應。最優適應在所有相鄰解被搜尋后，將更優相鄰解替換為可行解;首次適應是當搜索到比可行解更優相鄰解時進行替換后再次局部搜索，當循環達到滿足給定的迭代次數時終止。

1.2 ?灰狼優化算法

GWO算法模仿灰狼的社會等級制度和獵食行為，并控制搜索方位?；依莾灮惴ㄒ驯粡V泛應用并不斷改進，主要體現在約束函數優化、多級閾值圖像分割、路徑優化等領域[4]?；依堑燃墢母叩降蜑棣?，β，δ，ω這四種等級，每一個等級表示一個可能解。α狼是狼群頭領，擁有最高決策權，代表最優解;β，δ，ω狼分別代表優解、次優解、候選解。狼群每次捕獵過程是由各等級的相互協作完成，由搜尋、包圍、攻擊3個步驟組成。

1.2.1 ?搜尋過程

該算法通過隨機數擾亂判斷與獵物之間的距離，以此初始化種群。

[D=C?Xp（t）-X（t）] （1）

[C=2r] （2）

[r=rand（0，1）] （3）

式中：t為當下迭代次數;X（t）為灰狼的位置;[Xp]（t）為第t次迭代中獵物位置;D為灰狼與獵物的間距;r為0～1之間的任意隨機數。

1.2.2 ?包圍過程

在灰狼包圍獵物的過程中，通過狼之間不同距離和獵物距離，建立灰狼與獵物的關系模型。

[X（t+1）=Xp（t）-AiDi] （4）

[A=2ar-a] （5）

[a=2-ttmax] （6）

式中：A表示包圍步長;[tmax]表示最大迭代次數，控制參數a隨著算法迭代次數的增加而線性遞減。其中，當[A]≥1時，表示灰狼會進行全局搜索;而[A]<1時，意味灰狼將在附近搜索。A，C的隨機初始化保證了灰狼在搜索過程中易達到全局最優位置。

1.2.3 ?位置更新（攻擊）

通過α，β，δ，ω更新位置信息，判斷目標獵物位置并對獵物攻擊。產生新位置關系后，對狼群中的元素進行邊界控制，完成一次迭代。此階段狼群位置更新如圖1所示。

[Dα=C1Xα-XDβ=C2Xβ-XDδ=C3Xδ-X] （7）

[X1=Xα-A1DαX2=Xβ-A2DβX3=Xδ-A3Dδ] （8）

[X（t+1）=（X1+X2+X3）3] （9）

式中：[X1]，[X2]，[X3]表示α，β，δ狼的位置;[A1]，[A2]，[A3]表示3個隨機數;X表示灰狼攻擊獵物的最終位置?；依峭ㄟ^速度變異、搜索半徑變化、位置更新等策略，并借助參數A和C的隨機變化、較強的全局能力，使得灰狼在全局范圍亦可搜尋到最優解或次最優解。重復進行上述步驟，直到達到終止條件輸出最優解。綜述，灰狼捕食過程是可以抽象成連續空間上的組合優化模型。

2 ?改進策略

GWO循環初期具有較快的收斂速度，狼群位置變化較大，全局搜索能力較強，但隨迭代次數的增多后，位置變化波動漸少，易導致局部最優。本文提出的改進算法是將GRASP和GWO相結合，通過GRASP算法中構造階段的貪婪性與隨機性得到初始解來得到GWO中質量較高的初始群體，再通過GWO對其進行第二階段操作，搜索并逐步替換最優解。

2.1 GRASP算法初始化種群

作為改進算法的第一階段，隨機貪婪方法能夠得出可行初始解。在構造階段的每一次迭代生成的RCL大小和表內元素分別被參數α和貪婪函數決定，其中α∈{0，1}。參數α決定算法的貪婪程度，當α=0時是完全貪婪搜索過程，而α=1時是簡單的隨機過程。在貪婪隨機構造階段每一次迭代過程中，從RCL列表中隨機選擇一個元素加入當前局部解中，隨后更新RCL列表，重復該過程，直到滿足貪婪隨機構造階段可行解的值，該值為改進算法初始解。隨著構造階段的迭代，所有元素之間的關系結構不斷優化，得到更優解。

2.2 目標函數構造

作為改進算法的第二階段，灰狼優化算法的求解范圍是一個二維的連續空間，需界定自變量的取值范圍與目標函數表達式。TSP問題引入灰狼優化算法后，假設灰狼的種群規模為N，城市個數為D。在D維的城市搜尋空間中，第i（i∈N）只灰狼的位置[Xi]被定義為一組正整數序列，N只灰狼在D維空間中搜尋獵物，即搜索空間域P是一個矩陣：

[P=X11 ? ?X21 ? ?… ? ?Xj1 ? ?… ? ?XD1X12 ? ?X22 ? ?… ? ?Xj2 ? ?… ? ?XD2? ? ?? ? ? ? ? ? ? ? ? ? ??X1i ? ?X2i ? ?… ? ?Xji ? ?… ? ?XDi? ? ? ?? ? ? ? ? ? ?? ? ? ?? ? ?X1N ? ?X2N ? ?… ? ?XjN ? ?… ? ?XDN] （10）

式中，[Xji]（i≤N，j≤D）指在搜索空間P中，第i只灰狼在第j維度上的位置，矩陣首行為第一只灰狼在搜索空間中的位置序列，尾行表示第N只灰狼的位置序列。

TSP問題中實際距離矩陣W可表示為：

[W=d（1，1）…d（1，N）???d（N，1）…d（N，N）] （11）

式中：N指城市數量;[d（i，j）]指第i個到第j個城市之間的距離，其中[d（i，i）]（1≤i≤N）均為0。

當求解城市數量為D，狼群數量為N時，TSP問題求解目的為求取一個最優狼群位置P，使得目標數值f最?。?/p>

[f=min Pd（i，j）， （i，j）≤D，（i，j）∈N，i≠j]

式中：i和j表示城市序號;[min P]表示最優的種群位置;[d（i，j）]表示距離矩陣和。

該函數讀取每個灰狼位置矩陣P中，對位置序列與相對應距離矩陣W的距離累加求和。例如，從第1個城市前往第6個城市，假設位置為P=[1，4，6，2，3，5]，則表示為從1號城市出發，依次經過4，6，2，3，5號城市，最終回到1號城市。此時灰狼種群從距離矩陣W讀取距離進行目標函數值的計算，在距離矩陣W中對應的距離分別為[d1，4]，[d4，6]，[d6，2]，[d2，3]，[d3，5，d（5，1）]，對于P=[1，4，6，2，3，5]順序下的目標函數值f的計算方法為：

[f=sumd1，4，d4，6，d6，2，d2，3，d3，5，d5，1]

不同的灰狼隨機初始化會產生不同的解向量，通過函數判定其目標函數優化狀況，若解比之前解更優則替換為更優解，并作為本只灰狼當前迭代最優解;反之保持不變，繼續進行下一行判斷，直到所有灰狼解向量優化全部完成。

隨后保存所有行中目標函數值最小值，此為一次完整循環，當所有完成循環次數，即可輸出所有循環之后的最優解。

3 ?實驗結果

本算法在TSPLIB中38個歐幾里得樣本問題上進行測試，問題范圍內擁有大量城市節點（16～2 392個），例如表1中的第2個實例為Eil51，表示有51個節點。將RCL的長度設置為30，50，100，150，且灰狼的個數根據城市數變化。

例如：當城市數量小于100，那灰狼個數需設置為城市數量的[12];當城市數量在100～1 000，灰狼個數設置為城市數量的[13];當城市規模大于1 000，將灰狼個數設置為城市數量的[14]。當城市節點數少于1 000，迭代次數根據城市數設置在10～100之間;當城市節點數超過1 000的實例，該算法只測試100次迭代;當城市節點數大于1 200的實例，該算法運行200次迭代。

表1第4列表示修改過的GRASP算法所找到的最佳解決方案，第5列顯示了本文算法產生解的偏差，第6列顯示本文算法所得到解的平均值。相對偏差，即p=100[c-coptcopt]，其中c表示通過本文算法找到最優解路徑長度，[copt]是已知最優解。

對表1分析，在大多數情況下，當該算法節點數量達到299個時即可獲得已知最優解;當實例在節點數量為299～2 392個之間時，解決方案的偏差在0.01%～1.0%之間。根據這38個實例測試，得出已知最優解共有22個，其中14個解的偏差在0.01%～0.65%之間（占總測試數比的36.8%），實例中只有一個產生解的偏差為1.00%。

表2顯示了在RCL不同長度（30，50，100，150）從51～442個節點的10個實例實驗中，分別得出的最優解。不同長度的RCL會影響結果，在Rand75實例中全為最優解。在D198實例中，不同長度的RCL生成了不同最終解。當RCL長度為30時，所求得最優解與已知的最優解的差距隨著節點數增大而增大，當節點數小于100情況下均找到最優值。隨著節點數增大，RCL長度在100和150找到最優解;當RCL長度為100時，其中40%達到已知最優解;其余與已知最優解最大偏差為2.7%;當RCL長度為150時，其中也有40%能達到已知最優解，與已知最優最大解偏差為2.6%。隨著節點數的增多，總體上RCL的長度較長易找到最優路徑;而節點數較少，RCL的長度較短時，更易在更短的時間與更少的迭代內找到最優路徑。

表3顯示了TSPLIB中的實例在4種不同算法下的求解結果：蟻群算法（Ant Colony Optimization，ACO）[5]，自適應離散型布谷鳥算法（Adaptive Discrete Cuckoo Search，ADCS）[6]，遺傳算法（Genetic Algorithm，GA）[7]，以及本文所改進的算法對節點數量在51～150之間的實例進行實驗。通過對結果分析，正如預期，相較于另外3種啟發式算法，所得的結果仍存在一定差距，但運用本文改進算法能得到更好的最優解。

4 ?結 ?語

本文改進算法是利用GRASP與GWO相結合的一種相對其他算法精度更高、搜索性能更好、更易克服陷入局部優化的求解TSP的新算法。在多數情況下，利用本文改進算法通過對TSPLIB數據庫中多個實例研究，證明其結果等同于已知最優解;有時所得解不是最優解，但相對同條件下其他算法所得到的解更近乎為最優解。雖然本文改進算法在一定條件下顯得相對高效，但還存在許多問題，尤其在處理大型TSP問題時，會出現運行效率較低的情況。今后將繼續改進算法以解決以上問題。

參考文獻

[1] NENAD M， RACA T， DRAGAN U. An efficient general variable neighborhood search for large travelling salesman problem with time windows [J]. Yugoslav journal of operations research， 2013， 1（23）： 19?30.