灰狼優(yōu)化算法的改進(jìn)及其應(yīng)用

鄧 飛，魏祎璇，劉奕巧，王統(tǒng)照

（1.華北科技學(xué)院 經(jīng)濟(jì)管理學(xué)院，河北 廊坊 065201；2.北京科技大學(xué) 大安全科學(xué)研究院，北京 100083；3.馬來(lái)亞大學(xué) 機(jī)械工程學(xué)院，馬來(lái)西亞 吉隆坡50603；4.寧波諾丁漢大學(xué) 流體與熱工程研究中心，浙江 寧波 315100）

0 引言

求解復(fù)雜問(wèn)題的經(jīng)典群體智能優(yōu)化算法有遺傳算法（Genetic Algorithm,GA）[1]、模擬退火算法（Simulated Annealing,SA）[2]、粒子群優(yōu)化算法（Particle Swarm Optimization,PSO）[3]、蟻群優(yōu)化算法（Ant Colony Optimization,ACO）[4]等。Mirjalili 等（2014）[5]提出的灰狼優(yōu)化算法（Grey Wolf Optimization，GWO）雖然較其他群體智能算法具有調(diào)節(jié)參數(shù)少、結(jié)構(gòu)簡(jiǎn)化易于程序?qū)崿F(xiàn)、求解精度高等優(yōu)點(diǎn),但也存在一定的缺陷，例如：不能直接對(duì)離散組合問(wèn)題進(jìn)行求解[5]；存在著群體進(jìn)化迭代中全局尋優(yōu)能力欠缺，容易陷入局部最優(yōu)的問(wèn)題；不能直接用于解決多目標(biāo)優(yōu)化復(fù)雜問(wèn)題。針對(duì)上述問(wèn)題，本文在GWO算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出離散編碼、解碼策略以適配優(yōu)化離散組合問(wèn)題；引入GA 算法中的交叉操作和大規(guī)模鄰域搜索算法（Large Neighborhood Search，LNS）中的破壞修復(fù)操作，在彌補(bǔ)全局搜索能力不足的同時(shí)，進(jìn)一步提高局部搜索能力；融入NSGA-Ⅱ框架，實(shí)現(xiàn)多目標(biāo)優(yōu)化復(fù)雜問(wèn)題的求解。

1 問(wèn)題描述

旅行商問(wèn)題（Travelling Salesman Problem,TSP）和多旅行商問(wèn)題（Multiple Traveling Salesman Problem，MTSP）屬于典型的離散組合優(yōu)化問(wèn)題[6]，在TSP和MTSP的基礎(chǔ)上添加不同約束條件后可以得到不同形式的泛化多旅行商問(wèn)題（General Multiple Traveling Salesman Problem，GMTSP）[7]。本文以洪澇災(zāi)害中的無(wú)人機(jī)應(yīng)急救援任務(wù)為應(yīng)用場(chǎng)景來(lái)驗(yàn)證所提出的改進(jìn)的GWO算法的有效性。為盡快了解整體災(zāi)情，單架無(wú)人機(jī)在執(zhí)行空中巡航任務(wù)時(shí)從中心出發(fā)，訪問(wèn)受災(zāi)需求點(diǎn)后再返回中心，僅需在TSP中考慮整個(gè)飛行距離最短，因此屬于單目標(biāo)優(yōu)化問(wèn)題。若單架無(wú)人機(jī)在執(zhí)行應(yīng)急物資配送任務(wù)時(shí)從中心出發(fā)，各自訪問(wèn)不同需求點(diǎn)后返回中心，則在MTSP中需考慮最小化無(wú)人機(jī)使用數(shù)量，以便節(jié)約出來(lái)后用于執(zhí)行其他受災(zāi)片區(qū)的救援任務(wù)。此外，為使最長(zhǎng)救援路徑中的最后一個(gè)需求點(diǎn)盡快收到應(yīng)急物資，還需要考慮最小化最長(zhǎng)飛行路徑距離，該情形屬于多目標(biāo)優(yōu)化問(wèn)題。

將上述GMTSP 定義為有向圖G=(V，E)，V={v1，v2，…，vn}為n個(gè)節(jié)點(diǎn)的集合，v1表示應(yīng)急指揮中心，v2至vn表示受災(zāi)需求點(diǎn)，共有m個(gè)無(wú)人機(jī)從應(yīng)急指揮中心出發(fā)；為節(jié)點(diǎn)之間的可行邊集合，eij表示受災(zāi)需求點(diǎn)i和j之間的飛行路線，根據(jù)其可行邊的賦值可以表示該飛行路線是否有旅行商選擇，如果被選擇，則eij=1；否則eij=0。有向圖G對(duì)應(yīng)一個(gè)頂點(diǎn)距離矩陣C=(cij)n×n，cij表示受災(zāi)需求點(diǎn)i和j之間的歐氏距離，且cij=cji，即受災(zāi)需求點(diǎn)i與j的往返距離是相等的；μi表示受災(zāi)需求點(diǎn)i在當(dāng)前路徑中的位置序號(hào)，即一架無(wú)人機(jī)前往受災(zāi)需求點(diǎn)i時(shí)已經(jīng)經(jīng)過(guò)的受災(zāi)需求點(diǎn)數(shù)目。數(shù)學(xué)模型如下：

只有對(duì)灰狼個(gè)體進(jìn)行合適的評(píng)價(jià)，才能保證灰狼群體在位置更新過(guò)程中方向“不偏離”，從而選出近似最佳位置。式（1）和式（2）分別表示兩個(gè)不同的目標(biāo)函數(shù)，式（3）至式（11）表示約束條件。其中，式（1）確保了需要最小化最長(zhǎng)飛行路徑距離，式（2）確保了需要最小化無(wú)人機(jī)使用數(shù)量，單目標(biāo)情形下只需要考慮以式（1）為優(yōu)化目標(biāo)，多目標(biāo)情形下需要同時(shí)考慮以式（1）和式（2）為優(yōu)化目標(biāo)；式（3）限定了無(wú)人機(jī)數(shù)量范圍；式（4）表示第k個(gè)飛行路徑的長(zhǎng)度；式（5）和式（6）確保了所有無(wú)人機(jī)的出發(fā)和返回地點(diǎn)都為應(yīng)急指揮中心；式（7）和式（8）確保了每一個(gè)受災(zāi)需求點(diǎn)（節(jié)點(diǎn)2 到節(jié)點(diǎn)n）只能被一架無(wú)人機(jī)執(zhí)行應(yīng)急救援任務(wù)；式（9）消除了形成子支路回路的可能性；式（10）和式（11）對(duì)變量eij進(jìn)行了取值約束。

2 單一目標(biāo)優(yōu)化問(wèn)題情形下的改進(jìn)離散灰狼優(yōu)化算法

灰狼群體有著非常嚴(yán)格的等級(jí)制度，灰狼α是群體領(lǐng)導(dǎo)者，灰狼β和灰狼δ處于群體中間層級(jí)，灰狼ω處于底層。本文在GWO算法的基礎(chǔ)上提出改進(jìn)離散灰狼優(yōu)化算法（Improved Discrete Grey Wolf Optimizer,IDGWO），其核心思想為：提出離散編碼、解碼策略以適配TSP問(wèn)題；借鑒GA 算法中的交叉操作以彌補(bǔ)全局搜索能力不足；引入LNS 算法中的破壞修復(fù)操作，進(jìn)一步提高局部搜索能力。IDGWO算法的整體設(shè)計(jì)流程如圖1所示。

圖1 單一目標(biāo)情形下的IDGWO算法設(shè)計(jì)流程

2.1 離散編碼、解碼策略

要實(shí)現(xiàn)受災(zāi)需求點(diǎn)的路徑分組，需要先確定每一架無(wú)人機(jī)飛行路徑上的需求點(diǎn)次序，這顯然是一個(gè)離散組合優(yōu)化問(wèn)題。雖然GWO 算法能解決群體連續(xù)行為的優(yōu)化問(wèn)題，但是GMTSP中路徑上的節(jié)點(diǎn)分配問(wèn)題是離散的，因此需要在編碼和解碼上對(duì)GWO算法的位置編碼進(jìn)行離散化改良[8]，具體做法如下：

本算法使用整數(shù)編碼來(lái)定義體現(xiàn)灰狼位置特征的個(gè)體，灰狼個(gè)體包括part1 部分和part2 部分，即所有需求點(diǎn)編號(hào)次序部分和各支路徑上需求點(diǎn)數(shù)量統(tǒng)計(jì)部分。若有1 個(gè)應(yīng)急指揮中心和n-1 個(gè)受災(zāi)需求點(diǎn)，無(wú)人機(jī)的數(shù)量為m，結(jié)合MTSP 的特征，一個(gè)灰狼個(gè)體就是n-1+m維的行向量，Xi=(xi，1，xi，2，…，xi，n-1+m)，其中，part1 長(zhǎng)度為n-1，即所有受災(zāi)需求點(diǎn)的數(shù)量；part2 長(zhǎng)度為m，即所有無(wú)人機(jī)數(shù)量。例如，假設(shè)應(yīng)急指揮中心的編號(hào)為1，受災(zāi)需求點(diǎn)的編號(hào)為2 至9，無(wú)人機(jī)數(shù)量為3，則IDGWO算法求解問(wèn)題所采用編碼向量為Xi=(5，4，8，7，6，3，2，9，2，3，3)。從圖2 可以看出，該向量（即灰狼個(gè)體）被豎線分成了兩個(gè)部分，豎線左邊的part1 中共有8 個(gè)數(shù)值，右側(cè)part2 中共有3 個(gè)數(shù)值。part1 中，無(wú)人機(jī)1 依次訪問(wèn)需求點(diǎn)5 和4；無(wú)人機(jī)2 依次訪問(wèn)需求點(diǎn)8、7、6；無(wú)人機(jī)3依次訪問(wèn)需求點(diǎn)3、2、9。由part1 中的數(shù)值可以算出part2 中的數(shù)值，三架無(wú)人機(jī)途徑需求點(diǎn)的數(shù)量分別為2、3、3。

圖2 IDGWO算法求解GMTSP采用的編碼

IDGOW算法解碼是將上述灰狼個(gè)體位置編碼解碼為無(wú)人機(jī)飛行路線的方案，具體為：通過(guò)識(shí)別灰狼個(gè)體Xi=(xi，1，xi，2，…，xi，n-1+m)中part2 各路徑的長(zhǎng)度來(lái)截取part1中受災(zāi)需求點(diǎn)編號(hào)向量；在每個(gè)路線向量起始位置加上應(yīng)急指揮中心編號(hào)形成新路徑向量。解碼后的路線如下：

（1）飛行路徑1：1→5→4。

（2）飛行路徑2：1→8→7→6。

（3）飛行路徑3：1→3→2→9。

2.2 種群初始化

IDGWO算法采用隨機(jī)排列方式對(duì)灰狼種群進(jìn)行初始化。種群中有NIND個(gè)灰狼個(gè)體，初始化灰狼群體中任意灰狼個(gè)體的步驟如下：（1）對(duì)受災(zāi)需求點(diǎn)編號(hào)進(jìn)行隨機(jī)排序，將其作為灰狼個(gè)體編碼中的part1。（2）隨機(jī)生成m個(gè)數(shù)字作為part2，且須符合兩個(gè)條件：每個(gè)數(shù)字須大于等于1，m個(gè)數(shù)字之和為n-1。（3）將part1和part2合并，生成一個(gè)完整的灰狼個(gè)體。（4）重復(fù)前3個(gè)步驟NIND次，最終生成一個(gè)NIND行、n-1+m列的矩陣作為初始化灰狼種群。

2.3 全局搜索操作

全局搜索操作實(shí)際上是灰狼位置更新操作，為使灰狼個(gè)體能夠最大可能地尋找到最優(yōu)位置，結(jié)合GMTSP 的離散型特點(diǎn)，同時(shí)借鑒遺傳算法的交叉操作[1]，對(duì)灰狼位置進(jìn)行更新，具體計(jì)算公式如下：

式（12）中，t表示當(dāng)前時(shí)刻，Xt+1為下一時(shí)刻灰狼個(gè)體的離散位置向量，灰狼α、β和δ當(dāng)前時(shí)刻的灰狼個(gè)體分別記為Xα，t、Xβ，t和Xγ，t，Cross[]表示個(gè)體間的交叉操作函數(shù)，rand是一個(gè)0到1之間的隨機(jī)變量。

在對(duì)灰狼個(gè)體進(jìn)行更新時(shí)，有1/3 的概率分別與灰狼α、β和δ進(jìn)行兩兩個(gè)體間就某一段基因序列進(jìn)行交換，從而使自身個(gè)體發(fā)生變化，最終使灰狼種群向著適應(yīng)度值減小的方向進(jìn)化。

如果存在灰狼個(gè)體向量ind1=(4,7,5,6,3,2,8,9,2,5,1)和ind2=(6,3,7,8,5,2,4,9,3,3,2)，交叉位置r1 和r2 是需要隨機(jī)產(chǎn)生的，為了方便說(shuō)明，這里將其初始化為6 和7，則ind1 和ind2 的交叉片段分別為s1=(2,4)和s2=(2,8)；將s1放置到ind1前，將s2放置到ind2前，此時(shí)ind1=(2,4,4,7,5,6,3,2,8,9,2,5,1)，ind2=(2,8,6,3,7,8,5,2,4,9,3,3,2)；分別對(duì)ind1 和ind2 進(jìn)行逐個(gè)遍歷，查找重復(fù)值的第二個(gè)位置，并將其刪除，此時(shí)ind1=(2,4,7,5,6,3,8,9,2,5,1)，ind2=(2,8,6,3,7,5,4,9,3,3,2)。具體的灰狼位置更新步驟如圖3所示。

圖3 灰狼位置更新步驟

2.4 局部搜索操作

IDGWO 算法的局部?jī)?yōu)化操作借鑒了LNS 算法[9]中的核心思想：破壞和修復(fù)，即先按照規(guī)則對(duì)灰狼個(gè)體α、β和δ所在路徑上的受災(zāi)需求點(diǎn)進(jìn)行破壞以縮短路徑長(zhǎng)度，再將破壞移除出來(lái)的受災(zāi)需求點(diǎn)重新按照某種規(guī)則插入路徑中。

破壞操作的具體步驟如下：（1）將被移除受災(zāi)需求點(diǎn)集合R和被破壞路徑集合T初始化為空集；（2）在當(dāng)前灰狼個(gè)體中確定被移除的路徑數(shù)目k，初始化k值為2與m之間的隨機(jī)數(shù)；（3）從受災(zāi)需求點(diǎn)中隨機(jī)選出一個(gè)iseed作為被移除的初始節(jié)點(diǎn)，以到iseed點(diǎn)的距離大小為依據(jù)，將所有受災(zāi)需求點(diǎn)進(jìn)行升序排列得到集合lst，且初始化i的值為0；（4）如果i不大于集合lst的長(zhǎng)度并且集合T的長(zhǎng)度小于k，則繼續(xù)執(zhí)行，否則轉(zhuǎn)至步驟（7）；（5）在k的每條路徑中分別移除l個(gè)受災(zāi)需求點(diǎn)，l的值為1 與Lmax之間的隨機(jī)數(shù)，Lmax取num(r)和avgt中的最小值，num(r)表示當(dāng)前路徑中的受災(zāi)需求點(diǎn)數(shù)量，avgt表示當(dāng)前灰狼個(gè)體中每條路徑上受災(zāi)需求點(diǎn)數(shù)量的均值；（6）更新R和T，將i值增加1，轉(zhuǎn)至步驟（4）；（7）破壞操作結(jié)束，將集合R中的節(jié)點(diǎn)從初始路徑集合中移除，形成破壞后的路徑集合sdestroy。

修復(fù)操作的具體步驟如下：（1）將sdestroy的值賦值給修復(fù)后的路徑集合srepair以完成初始化操作；（2）如果被移除的受災(zāi)需求點(diǎn)集合R是非空集，則繼續(xù)執(zhí)行，否則轉(zhuǎn)至步驟（6）；（3）將R集合中各個(gè)元素放回srepair中并拿出，在此過(guò)程中計(jì)算出每次放回后得到的遺憾值集合regret；（4）找出最終放回的受災(zāi)需求點(diǎn)，即regret集合中的最大值在R中所對(duì)應(yīng)的受災(zāi)需求點(diǎn)rIns，并且將該受災(zāi)需求點(diǎn)放回srepair中“插入成本”最小的路徑位置；（5）更新R，即將受災(zāi)需求點(diǎn)rIns從R中刪除，轉(zhuǎn)至步驟（2）；（6）修復(fù)操作結(jié)束，形成修復(fù)后路徑集合srepair。

3 多目標(biāo)情形下的改進(jìn)離散灰狼優(yōu)化算法

鑒于IDGWO算法無(wú)法對(duì)最小化最長(zhǎng)路徑距離以及最小化無(wú)人機(jī)數(shù)量?jī)蓚€(gè)目標(biāo)的MTSP進(jìn)行求解，本文在IDGWO 算法的基礎(chǔ)上融合NSGA-Ⅱ框架[10]，提出多目標(biāo)改進(jìn)離散灰狼優(yōu)化算法（Multi-target Improved Discrete Grey Wolf Optimizer,MIDGWO）。MIDGWO 算法求解MTSP 的基本流程如下頁(yè)圖4所示。該算法的基本思想是：隨機(jī)生成一個(gè)父代灰狼種群；通過(guò)基于IDGWO 算法中的更新操作優(yōu)化每一個(gè)灰狼個(gè)體位置；基于IDGWO 算法中的局部搜索操作優(yōu)化三個(gè)頭狼個(gè)體位置產(chǎn)生出子代種群；將父代和子代種群合并后進(jìn)行快速非支配排序，形成不同序值級(jí)別的個(gè)體集合；計(jì)算所有個(gè)體擁擠度；根據(jù)序值和擁擠度進(jìn)行截取，修剪成新父代種群；依此類推，直到滿足循環(huán)結(jié)束條件后得到帕累托最優(yōu)解集。

圖4 多目標(biāo)情形下的MIDGWO算法設(shè)計(jì)流程

3.1 快速非支配排序

假定F1表示最小化無(wú)人機(jī)數(shù)量目標(biāo)，F(xiàn)2表示最小化最長(zhǎng)飛行路徑距離目標(biāo)，若灰狼群體中有個(gè)體p和個(gè)體q存在如式（13）中的關(guān)系，則p支配q。

快速非支配排序的步驟如下：（1）將灰狼種群中所有不能被任何其他個(gè)體支配的個(gè)體集合選擇出來(lái)，其序值等級(jí)設(shè)置為1；（2）找出剔除種群中序值等級(jí)為1 的個(gè)體后剩下的個(gè)體集合，將其序值等級(jí)設(shè)置為2；（3）對(duì)序值等級(jí)為2 的個(gè)體集合繼續(xù)按照支配關(guān)系，賦予支配個(gè)體集合序值等級(jí)為2，賦予被支配個(gè)體集合序值等級(jí)為3；（4）依此類推，得到所有個(gè)體序值等級(jí)，將個(gè)體按照序值等級(jí)標(biāo)號(hào)num的取值放置到相應(yīng)集合Ranknum中。

3.2 擁擠度計(jì)算和修剪操作

同一序值等級(jí)的不同灰狼個(gè)體是無(wú)法進(jìn)行比較的，因此需要將擁擠度作為評(píng)價(jià)指標(biāo)，該指標(biāo)越大表明種群多樣性越好。擁擠度的計(jì)算公式如式（14）所示：

其中，某一序值等級(jí)集合中個(gè)體數(shù)目為n；Ci表示第i個(gè)個(gè)體的擁擠度；Fi+1，1和Fi-1，1分別表示第i+1 和第i-1 個(gè)個(gè)體的第1 個(gè)目標(biāo)函數(shù)值；Fi+1，2和Fi-1，2分別表示第i+1 和第i-1 個(gè)個(gè)體的第2 個(gè)目標(biāo)函數(shù)值。當(dāng)個(gè)體不處于序值集合兩端的時(shí)候，擁擠度為與其相鄰的兩個(gè)個(gè)體在每個(gè)目標(biāo)函數(shù)上的距離差之和，否則擁擠度為無(wú)窮大。

由于子代和父代灰狼種群合并后的個(gè)體數(shù)是初始種群的2 倍，因此為了接下來(lái)的迭代進(jìn)化，需要對(duì)其進(jìn)行修剪操作，使個(gè)體數(shù)減少為初始種群大小（假設(shè)為N）。具體的步驟如下：（1）若Rank1集合中的個(gè)體數(shù)目小于等于N，則將Rank1集合中的所有個(gè)體形成新父代種群，直接執(zhí)行步驟（3）；（2）若Rank1集合中的個(gè)體數(shù)目大于N，則對(duì)其個(gè)體按照擁擠度大小進(jìn)行降序排序，只取前N個(gè)放到新父代種群中，執(zhí)行步驟（3）；（3）將Ranki集合中的個(gè)體按照上述規(guī)則逐個(gè)放入新父代種群，直至個(gè)體數(shù)量為N，最終形成新父代種群。

4 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 單目標(biāo)情形下的實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證IDGWO算法對(duì)最小化最長(zhǎng)飛行路徑距離為單一目標(biāo)問(wèn)題的求解性能，本文從精確度角度出發(fā)，采用TSPLIB數(shù)據(jù)集中的不同標(biāo)準(zhǔn)算例對(duì)該算法和其他算法進(jìn)行對(duì)比測(cè)試。由于TSPLIB數(shù)據(jù)庫(kù)中僅為每個(gè)算例提供了目前旅行商數(shù)目為1的優(yōu)化仿真路徑長(zhǎng)度最優(yōu)值，因此優(yōu)化對(duì)象為單旅行商問(wèn)題。考慮到IDGWO算法中全局優(yōu)化和局部?jī)?yōu)化操作分別借鑒了GA算法中的交叉操作和LNS算法中的破壞修復(fù)操作，對(duì)比實(shí)驗(yàn)算法選定為GA算法、基于IDGWO算法但剔除交叉操作的算法（記為IDGWO-NGO）、LNS 算法、基于IDGWO 算法但剔除破壞修復(fù)操作的算法（記為IDGWO-NLO）。此外，為對(duì)比傳統(tǒng)群體智能算法，增加SA 算法和ACO 算法。為保證算法運(yùn)行對(duì)比實(shí)驗(yàn)的公平性，所有算法種群規(guī)模都設(shè)置為50，最大迭代次數(shù)為1000，無(wú)人機(jī)數(shù)量為1。所有算法分別針對(duì)TSPLIB標(biāo)準(zhǔn)庫(kù)中的chn31、att48、eil76和ch150四個(gè)算例連續(xù)進(jìn)行15次仿真，仿真結(jié)果見(jiàn)表1。

表1 算法仿真實(shí)驗(yàn)結(jié)果對(duì)比

表1中的仿真均值是指15次仿真結(jié)果的平均值，仿真最小值是15次仿真結(jié)果中最好的優(yōu)化結(jié)果。仿真運(yùn)算結(jié)果的精確度可以用相對(duì)錯(cuò)誤值（Relative Error，RE）[11]來(lái)度量，具體計(jì)算公式如式（15）所示：

其中，Save表示仿真均值，Sopt表示TSPLIB 數(shù)據(jù)庫(kù)提供的算例最優(yōu)解。隨著RE數(shù)值的升高，算法仿真結(jié)果精確度會(huì)降低。

在chn31 算例下，IDGWO 算法的精確度表現(xiàn)較好，仿真最小值幾乎接近于TSPLIB最優(yōu)解，RE值控制在0.05以內(nèi)，GA 和IDGWO-NGO 算法的RE值分別為3.5562 和4.0588，LNS和IDGWO-NLO算法的RE值分別為0.1214和6.4028，SA和ACO算法的RE值分別為10.2598和1.5610；在att48 算例下，GA 和IDGWO-NGO 算法的RE值分別是IDGWO 算法的46 倍和83 倍，LNS 和IDGWO-NLO 算法的RE值分別近乎是IDGWO算法的7倍和172倍，SA和ACO算法的RE值則分別是IDGWO 算法的226 倍和46 倍；在eil76 和ch150 算例下，IDGWO 算法比其他6 種算法的RE值都要低，RE值的最大差值分別達(dá)到35.26 和143.20。由于IDGWO-NGO 算法和IDGWO-NLO 算法分別是在IDGWO 算法的基礎(chǔ)之上剔除了交叉操作和破壞修復(fù)操作，因此聚焦于這3種算法可以發(fā)現(xiàn)：無(wú)論在何種算例下，IDGWO-NGO 和IDGWO-NLO 算法的RE值都明顯比IDGWO算法更高。尤其是在chn31算例下，IDGWO-NGO的RE值比IDGWO 算法增大了近98 倍；在att48 算例下，IDGWO-NGO 算法的RE值比IDGWO 算法增大了近171倍。這3 種算法在同等算例下，IDGWO-NLO 算法的RE值最高，IDGWO-NGO算法次之。這從側(cè)面驗(yàn)證了交叉操作和破壞修復(fù)操作可以提升IDGWO 算法的精確度，而且后者的操作是精確度提升的關(guān)鍵因素。不可否認(rèn)的是，隨著算例節(jié)點(diǎn)數(shù)目增大（節(jié)點(diǎn)數(shù)目從31 個(gè)增大到150 個(gè)），IDGWO 算法的RE值基本上也在增大（從0.0451 增大到1.2813），這說(shuō)明算法的求解精確度在持續(xù)下降。綜合上述對(duì)比實(shí)驗(yàn)結(jié)果可知，IDGWO算法和其他6種優(yōu)化算法相比，可以更有效地提高對(duì)TSP問(wèn)題的求解精確度。

4.2 多目標(biāo)情形下的實(shí)驗(yàn)結(jié)果分析

梁星星等（2017）[12]以最小化旅行商數(shù)量和最小化最長(zhǎng)路徑距離為多目標(biāo)，分別采用多目標(biāo)模擬退火算法和多目標(biāo)遺傳算法來(lái)求解MTSP，測(cè)試發(fā)現(xiàn)，前者算法的計(jì)算結(jié)果優(yōu)于后者。由于上述文獻(xiàn)采用的算例中存在多個(gè)孤立點(diǎn)，使得求解的帕累托最優(yōu)解數(shù)量較少，直接影響后續(xù)算法性能指標(biāo)的對(duì)比計(jì)算，因此本文在原算例的基礎(chǔ)上進(jìn)行修改，將其作為多目標(biāo)情況下的測(cè)試集①由于篇幅限制，多目標(biāo)情形下的測(cè)試集具體數(shù)據(jù)未列出。。

將MIDGWO算法和上述文獻(xiàn)提出的多目標(biāo)模擬退火算法（Multi-objective Simulated Annealing，MSA）進(jìn)行對(duì)比，以檢驗(yàn)所提出算法的有效性。將兩種算法初始種群規(guī)模均設(shè)置為200，最大迭代次數(shù)為2000，無(wú)人機(jī)數(shù)量范圍為1～29，后者算法中變異、交叉等參數(shù)和原文獻(xiàn)一致。為避免求解的偶然性，兩種算法均獨(dú)立重復(fù)運(yùn)行15次，將每次運(yùn)行后的解集作為下一次運(yùn)行的初始種群，這樣得到帕累托前沿對(duì)比結(jié)果，如圖5所示②由于篇幅限制，MIDGWO和MSA算法的帕累托最優(yōu)解集的具體數(shù)據(jù)未列出。。從圖5中的變化趨勢(shì)可以看出以下特征：兩種算法的最長(zhǎng)路徑距離和無(wú)人機(jī)數(shù)量變化呈現(xiàn)負(fù)相關(guān)關(guān)系。兩種算法的最長(zhǎng)路徑距離最小值都能達(dá)到136.8941，但MIDGWO 算法只需要無(wú)人機(jī)數(shù)量為11，而MSA算法卻需要無(wú)人機(jī)數(shù)量為25。圖6可以更形象地展現(xiàn)其區(qū)別。兩種算法的帕累托最優(yōu)解數(shù)量不同，MINDGWO算法的最優(yōu)解數(shù)量要比MSA算法少。

圖5 帕累托前沿對(duì)比圖

圖6 最優(yōu)路徑對(duì)比圖

為進(jìn)一步量化兩種多目標(biāo)優(yōu)化算法的解集質(zhì)量，本文將從優(yōu)劣程度和多樣性兩個(gè)維度來(lái)進(jìn)行測(cè)評(píng)。

Zitzler和Thiele（1998）[13]認(rèn)為，受制于傳統(tǒng)一元多目標(biāo)優(yōu)化指標(biāo)或一元指標(biāo)組合，無(wú)法清晰比較兩個(gè)帕累托最優(yōu)解集的優(yōu)劣，因此本文使用覆蓋率來(lái)反映兩個(gè)解集相互支配的情況。覆蓋率的具體計(jì)算如式（16）所示：

其中，C(MIDGWO，MSA) 表示MIDGWO算法對(duì)MSA算法的覆蓋率，其取值范圍在0 到1 之間；|· |表示算法的帕累托最優(yōu)解個(gè)數(shù)；e1和e2分別表示兩種算法中某一帕累托最優(yōu)解；e1?e2ore1～e2表示帕累托最優(yōu)解e1支配或等價(jià)于e2。

解集多樣性一般用分布性和延展性這兩個(gè)指標(biāo)來(lái)衡量，兩個(gè)指標(biāo)數(shù)值越大表示算法解集越具有豐富的多樣性。分布性指標(biāo)的計(jì)算有很多種方法，如指標(biāo)Δ'[14]、指標(biāo)SP[15]、指標(biāo)χ2[16]等，由于指標(biāo)Δ'在計(jì)算解集中函數(shù)值的距離時(shí)采用更為簡(jiǎn)單的歐氏距離，且更適用于兩個(gè)優(yōu)化目標(biāo)優(yōu)化問(wèn)題，因此本文選其作為衡量MIDGWO和MSA算法帕累托最優(yōu)解集的分布性指標(biāo)，具體計(jì)算如式（17）和式（18）所示：

其中，di表示解集中第i個(gè)解與其他解歐氏距離的最小值；表示di的均值，當(dāng)di=時(shí)，Δ'=0，此時(shí)解集的分布性最佳。

延展性的衡量標(biāo)準(zhǔn)使用Zitzler（1999）[17]提出的指標(biāo)，該指標(biāo)通過(guò)計(jì)算解集中每個(gè)目標(biāo)函數(shù)數(shù)值差距最大元素之間的歐氏距離來(lái)展現(xiàn)解集寬廣程度，具體計(jì)算公式如式（19）所示：

根據(jù)上述多目標(biāo)優(yōu)化算法的解集質(zhì)量指標(biāo)計(jì)算公式，可以得到MIDGWO和MSA算法的帕累托最優(yōu)解集的相關(guān)指標(biāo)數(shù)值，如表2所示。由于MIDGWO算法的帕累托最優(yōu)解集中所有元素均能支配或等價(jià)于MSA 算法的解集元素，因此C(MIDGWO，MSA)=1，這代表著前者帕累托最優(yōu)解集要遠(yuǎn)比后者優(yōu)秀。在多樣性方面，MIDGWO 算法的分布性指標(biāo)Δ'要比MSA 算法小得多，這說(shuō)明在帕累托最優(yōu)解的分布程度上，前者要比后者均勻得多；延展性方面正好相反，MSA 算法的數(shù)值要比MIDGWO 算法大得多，這說(shuō)明前者算法的帕累托最優(yōu)解集比后者要窄一些。雖然MSA 算法的延展性更好一些，但考慮到覆蓋率情況，后者所有帕累托最優(yōu)解完全都被前者所支配，因此MIDGWO 算法比MSA 算法在多目標(biāo)MTSP 上的解集質(zhì)量更加優(yōu)異。

表2 多目標(biāo)優(yōu)化算法性能指標(biāo)對(duì)比

5 結(jié)論

本文針對(duì)GWO 算法中表現(xiàn)出來(lái)的缺陷進(jìn)行改進(jìn)，提出IDGWO和MIDGWO算法，并以洪澇災(zāi)害中的無(wú)人機(jī)應(yīng)急救援任務(wù)為應(yīng)用場(chǎng)景對(duì)算法的有效性進(jìn)行驗(yàn)證。經(jīng)過(guò)分析，得到如下結(jié)論：

（1）IDGWO 和MIDGWO 算法均能夠適配離散組合問(wèn)題。IDGWO算法對(duì)以最小化最長(zhǎng)飛行路徑距離為單一目標(biāo)的GMTSP 進(jìn)行求解，使用TSPLIB 標(biāo)準(zhǔn)庫(kù)中的chn31、att48、eil76 和ch150 四個(gè)算例連續(xù)進(jìn)行15 次實(shí)驗(yàn)仿真，能得到最優(yōu)解；MIDGWO 算法對(duì)以最小化最長(zhǎng)飛行路徑距離和最小化無(wú)人機(jī)使用數(shù)量為多目標(biāo)的GMTSP 進(jìn)行求解，使用某一測(cè)試集為算例進(jìn)行15次實(shí)驗(yàn)仿真，也能得到最優(yōu)解集。

（2）為驗(yàn)證求解單目標(biāo)GMTSP 時(shí)IDGWO 算法的性能，從求解精確性維度出發(fā)，采用TSPLIB數(shù)據(jù)集中的四個(gè)算例對(duì)該算法與GA、IDGWO-NGO、LNS、IDGWO-NLO、SA和ACO這6種智能優(yōu)化算法進(jìn)行對(duì)比評(píng)測(cè)。實(shí)驗(yàn)結(jié)果顯示，在不同算例下，IDGWO算法的RE值最小為0.04，最大為1.28；在同樣算例下，其RE值都要比其他算法?。ㄅc其他算法RE值的最小差值分別為0.08、0.62、0.86 和0.94），因此IDGWO 算法的求解精確度最高；在同等算例下，按算法的RE值從小到大排列，分別為IDGWO、IDGWO-NGO 和IDGWO-NLO 算法，IDGWO 算法中的交叉操作和破壞修復(fù)操作分別通過(guò)彌補(bǔ)全局搜索能力和提高局部搜索能力來(lái)提升算法求解的精確度，特別是后者的操作是關(guān)鍵。

（3）為驗(yàn)證MIDGWO 算法求解多目標(biāo)GMTSP 時(shí)的性能，從解集的優(yōu)劣程度和多樣性兩個(gè)維度出發(fā)，使用同一測(cè)試集對(duì)比MSA 算法進(jìn)行評(píng)測(cè)。實(shí)驗(yàn)結(jié)果顯示，衡量?jī)?yōu)劣程度的覆蓋率的數(shù)值為1，這說(shuō)明MIDGWO算法的帕累托最優(yōu)解集中所有元素均能支配或等價(jià)于MSA算法的解集元素；衡量多樣性程度一般使用分布性指標(biāo)和延展性指標(biāo)，MIDGWO 算法的分布性指標(biāo)數(shù)值要比MSA 算法小得多，說(shuō)明MIDGWO 算法的帕累托最優(yōu)解分布程度要比MSA 算法更加均勻；雖然延展性指標(biāo)結(jié)果表明MSA 算法要比MIDGWO 算法更為寬廣，但綜合考慮覆蓋率情況，MIDGWO算法在處理多目標(biāo)GMTSP上的求解質(zhì)量更好。

本文對(duì)GWO算法進(jìn)行改進(jìn)，提出的IDGWO和MIDGWO 算法得到了很好的算法性能驗(yàn)證，但分析結(jié)果顯示，隨著算例節(jié)點(diǎn)數(shù)目增大，算法求解性能也在下降，未來(lái)將探索結(jié)合機(jī)器學(xué)習(xí)算法進(jìn)行進(jìn)一步改進(jìn)。