高珊 孟亮

關(guān)鍵詞： GRAGWO算法; 貪婪隨機自適應(yīng)算法; 灰狼優(yōu)化算法; 群體智能; 旅行商問題; 組合優(yōu)化

中圖分類號： TN911?34; TP393 ? ? ? ? ? ? ? ? 文獻標(biāo)識碼： 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 ?引 ?言

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

貪婪隨機自適應(yīng)搜索算法（Greedy Randomized Adaptive Search Procedures，GRASP）是一種求解組合優(yōu)化問題的啟發(fā)式算法[3]?；依莾?yōu)化算法是2014年由Mirjalili等人提出的啟發(fā)式智能算法。該算法模擬自然界灰狼等級制度和狼群搜索獵物過程，利用灰狼種群內(nèi)部等級制度，實現(xiàn)對目標(biāo)獵物函數(shù)的優(yōu)化過程[4]。該算法具有優(yōu)良的收斂穩(wěn)定性與較強的全局探索能力。本文利用GRASP算法尋求初始解，從而加速灰狼算法的收斂速度，且提高其局部搜索能力。實驗表明，兩種算法的結(jié)合可以高效提高求解速度與解的質(zhì)量。

1 ?算法原理

1.1 貪婪隨機自適應(yīng)搜索算法

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

RCL規(guī)模大小也會影響此算法性能，規(guī)模過大會生成很多差別的解。RCL通常采用靜態(tài)固定法和動態(tài)調(diào)整法來調(diào)整列表規(guī)模，體現(xiàn)了GRASP算法自適應(yīng)功能。

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

1.2 ?灰狼優(yōu)化算法

GWO算法模仿灰狼的社會等級制度和獵食行為，并控制搜索方位?；依莾?yōu)化算法已被廣泛應(yīng)用并不斷改進，主要體現(xiàn)在約束函數(shù)優(yōu)化、多級閾值圖像分割、路徑優(yōu)化等領(lǐng)域[4]。灰狼等級從高到低為α，β，δ，ω這四種等級，每一個等級表示一個可能解。α狼是狼群頭領(lǐng)，擁有最高決策權(quán)，代表最優(yōu)解;β，δ，ω狼分別代表優(yōu)解、次優(yōu)解、候選解。狼群每次捕獵過程是由各等級的相互協(xié)作完成，由搜尋、包圍、攻擊3個步驟組成。

1.2.1 ?搜尋過程

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

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

[C=2r] （2）

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

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

1.2.2 ?包圍過程

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

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

[A=2ar-a] （5）

[a=2-ttmax] （6）

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

1.2.3 ?位置更新（攻擊）

通過α，β，δ，ω更新位置信息，判斷目標(biāo)獵物位置并對獵物攻擊。產(chǎn)生新位置關(guān)系后，對狼群中的元素進行邊界控制，完成一次迭代。此階段狼群位置更新如圖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個隨機數(shù);X表示灰狼攻擊獵物的最終位置?；依峭ㄟ^速度變異、搜索半徑變化、位置更新等策略，并借助參數(shù)A和C的隨機變化、較強的全局能力，使得灰狼在全局范圍亦可搜尋到最優(yōu)解或次最優(yōu)解。重復(fù)進行上述步驟，直到達到終止條件輸出最優(yōu)解。綜述，灰狼捕食過程是可以抽象成連續(xù)空間上的組合優(yōu)化模型。

2 ?改進策略

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

2.1 GRASP算法初始化種群

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

2.2 目標(biāo)函數(shù)構(gòu)造

作為改進算法的第二階段，灰狼優(yōu)化算法的求解范圍是一個二維的連續(xù)空間，需界定自變量的取值范圍與目標(biāo)函數(shù)表達式。TSP問題引入灰狼優(yōu)化算法后，假設(shè)灰狼的種群規(guī)模為N，城市個數(shù)為D。在D維的城市搜尋空間中，第i（i∈N）只灰狼的位置[Xi]被定義為一組正整數(shù)序列，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指城市數(shù)量;[d（i，j）]指第i個到第j個城市之間的距離，其中[d（i，i）]（1≤i≤N）均為0。

當(dāng)求解城市數(shù)量為D，狼群數(shù)量為N時，TSP問題求解目的為求取一個最優(yōu)狼群位置P，使得目標(biāo)數(shù)值f最?。?/p>

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

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

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

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

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

隨后保存所有行中目標(biāo)函數(shù)值最小值，此為一次完整循環(huán)，當(dāng)所有完成循環(huán)次數(shù)，即可輸出所有循環(huán)之后的最優(yōu)解。

3 ?實驗結(jié)果

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

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

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

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

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

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

4 ?結(jié) ?語

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

參考文獻

[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.