余澤泰 余盟 肖人彬 鐘衛(wèi)衛(wèi) 王玉梅

摘要 為了提高狼群算法的適應(yīng)能力，使其能在復(fù)雜環(huán)境下具有較高的尋優(yōu)精度與速度，提出一種具有動(dòng)態(tài)適應(yīng)性的狼群算法。首先，提出一種動(dòng)態(tài)分群算法，增強(qiáng)狼群算法的全局適應(yīng)性;其次，定義一種差異度擬熵，構(gòu)造自適應(yīng)步長(zhǎng)，提高算法在復(fù)雜環(huán)境下的精度與收斂速度;使用隨機(jī)游走環(huán)節(jié)，增強(qiáng)算法的適應(yīng)性，縮短計(jì)算耗時(shí)。在17種測(cè)試函數(shù)上與其他幾種算法進(jìn)行對(duì)比，顯示所提出算法具有較好的精度與收斂速度。在三維無(wú)人機(jī)航線規(guī)劃問(wèn)題上驗(yàn)證了該算法的有效性與實(shí)用性。

關(guān) 鍵 詞 狼群算法;動(dòng)態(tài)適應(yīng)性;分群;差異度擬熵

中圖分類號(hào) TP18? ? ?文獻(xiàn)標(biāo)志碼 A

Dynamical adaptive wolf pack algorithm and its application

YU Zetai， YU Meng， XIAO Renbin， ZHONG Weiwei， WANG Yumei

（Artificial Intelligence and Automation， Huazhong University of Science and Technology， Wuhan， Hubei 430074， China）

Abstract In order to improve the adaptability of the wolf pack algorithm， and provide it with good performance of search accuracy and speed under complex environment， a dynamical adaptive wolf pack algorithm （DAWPA） is proposed. Firstly， a dynamic clustering algorithm is proposed to enhance the global adaptability. Secondly， a difference pseudo entropy is defined to construct self-adaptive variable step-size， which improves the search accuracy and convergence speed. Random scout method is used to enhance the adaptability and shorten the computing time. Then， DAWPA is applied on 17 benchmarks. Compared with several other algorithms， DAWPA has shown better performance on accuracy and speed. Finally， application of DAWPA on 3D UAV route planning problem has demonstrated its validation and utility.

Key words wolf pack algorithm; dynamical adaptability; clustering; difference pseudo entropy

群智能優(yōu)化算法是通過(guò)模擬自然界中生物種群的行為方式，來(lái)求解復(fù)雜優(yōu)化問(wèn)題的智能算法。相比于傳統(tǒng)的優(yōu)化算法，群智能優(yōu)化算法在解決一部分NP難問(wèn)題上展現(xiàn)了良好的效果，得到了大量研究，在解決優(yōu)化問(wèn)題上得到了廣泛應(yīng)用。

國(guó)內(nèi)外學(xué)者已經(jīng)提出了多種群智能算法，如粒子群算法（Particle Swarm Optimization， PSO）和人工蜂群算法（Artificial Bee Colony， ABC）。這兩種算法得到廣泛應(yīng)用，在優(yōu)化中展現(xiàn)了獨(dú)特的優(yōu)勢(shì)[1]。然而，面對(duì)復(fù)雜問(wèn)題時(shí)，它們出現(xiàn)了較嚴(yán)重的早熟現(xiàn)象[2-3]。

為了解決復(fù)雜情況下的尋優(yōu)問(wèn)題，在狼群捕獵方式的啟發(fā)下，吳虎勝等[4]提出了一種新的群智能優(yōu)化算法——狼群算法（Wolf Pack Algorithm， WPA），并基于馬爾科夫鏈證明了該算法的收斂性。由于WPA具有較好的全局搜索能力，自提出就引起國(guó)內(nèi)外學(xué)者關(guān)注，并被應(yīng)用于生產(chǎn)調(diào)度、圖像處理、路徑規(guī)劃、云計(jì)算等問(wèn)題[5]，在高維問(wèn)題上具有較好的收斂與魯棒性[6]。同時(shí)，針對(duì)一些特殊的問(wèn)題，一系列衍生的應(yīng)用算法也被開(kāi)發(fā)出來(lái)。例如，應(yīng)用于0-1背包問(wèn)題的二進(jìn)制狼群算法（BWPA）[7];應(yīng)用于TSP問(wèn)題的離散狼群算法（DWPA）[8];應(yīng)用于多目標(biāo)0-1規(guī)劃問(wèn)題的元胞狼群算法[9];應(yīng)用于模糊雙層背包問(wèn)題的改進(jìn)二進(jìn)制狼群算法（IBWPA）[10]等。此外，結(jié)合BWPA與柔性種群更新策略的柔性二進(jìn)制狼群算法（FWPA）被應(yīng)用于解決一系列靜態(tài)多維背包問(wèn)題，展現(xiàn)了優(yōu)秀的性能[11]。

WPA對(duì)高維復(fù)雜函數(shù)的尋優(yōu)效果較好，可以有效避免早熟現(xiàn)象。然而，基本狼群算法還存在一些不足。面對(duì)問(wèn)題特征較復(fù)雜，如當(dāng)優(yōu)化目標(biāo)為兼具高維、耦合特征、多峰等復(fù)雜性質(zhì)的場(chǎng)景，如具有復(fù)雜環(huán)境的水下三維路徑規(guī)劃問(wèn)題、高維度多約束的水電站廠內(nèi)優(yōu)化運(yùn)行問(wèn)題[12-13]，基本狼群算法的適應(yīng)能力不夠強(qiáng)，較易早熟，因此影響了收斂速度與尋優(yōu)精度[14]，出現(xiàn)了收斂速度慢、求解精度不夠高和容易陷入局部最優(yōu)等問(wèn)題。為了提高其適應(yīng)性，文獻(xiàn)[15]通過(guò)引入精英集策略（Elite Set Strategy）和差分進(jìn)化改進(jìn)了WPA的初始解生成方式，提高了面對(duì)不同優(yōu)化問(wèn)題時(shí)的適應(yīng)能力。文獻(xiàn)[6]給出了基于對(duì)立學(xué)習(xí)的初始解優(yōu)化方案，提出了對(duì)立狼群算法（OWPA），既提高了正常情況下狼群算法的局部搜索能力，又提高了復(fù)雜情況下種群分布的多樣性，具有更好的魯棒性。文獻(xiàn)[16]使用Tent混沌映射初始化狼群，在圍攻過(guò)程中加入levy飛行方法，提出了一種混沌狼群圍捕算法，提高了算法的實(shí)時(shí)性。文獻(xiàn)[17]將混沌理論和反向?qū)W習(xí)結(jié)合起來(lái)實(shí)現(xiàn)狼群算法的優(yōu)化，通過(guò)優(yōu)化初始解的方式，提高了面對(duì)復(fù)雜問(wèn)題時(shí)的全局自適應(yīng)性。文獻(xiàn)[18]基于適應(yīng)度將狼群分為子群，提出了自適應(yīng)狼群分組策略，使狼群算法在復(fù)雜環(huán)境下具有更好的適應(yīng)能力。針對(duì)原始狼群算法游走步長(zhǎng)與圍攻步長(zhǎng)固定、缺乏局部自適應(yīng)能力的問(wèn)題，出現(xiàn)了多種基于迭代次數(shù)[19]、歐氏距離[20-21]、適應(yīng)度函數(shù)[22]的自適應(yīng)步長(zhǎng)狼群算法，且得到了較充分的研究。文獻(xiàn)[23]使用基于迭代次數(shù)的自適應(yīng)圍攻步長(zhǎng)，將PSO算法中求解當(dāng)前局部最優(yōu)的思想引入到游走、召喚行為中，提出一種改進(jìn)狼群算法，并將其運(yùn)用于Otsu圖像分割中，提高了分割精度且縮短了分割時(shí)間。文獻(xiàn)[24]在游走行為中加入隨機(jī)擾動(dòng)算子，借鑒模擬退火方法改進(jìn)了圍攻過(guò)程，提高了算法的全局搜索能力。文獻(xiàn)[25]在基本狼群算法的基礎(chǔ)上，增加了二次游走與人工狼變異的環(huán)節(jié)，在應(yīng)用問(wèn)題上獲得了較高精度。

本文在以往研究的基礎(chǔ)上，提出一種具有動(dòng)態(tài)適應(yīng)性的狼群算法（Dynamical Adaptive Wolf Pack Algorithm， DAWPA）。在狼群的群體分工上，通過(guò)使用一種動(dòng)態(tài)分群算法，根據(jù)環(huán)境與狼群分布動(dòng)態(tài)調(diào)整子群數(shù)量，使算法的全局搜索更充分。在圍攻環(huán)節(jié)中，定義一種差異度擬熵，構(gòu)造自適應(yīng)的圍攻步長(zhǎng)。對(duì)游走環(huán)節(jié)，使用隨機(jī)游走策略代替貪婪策略，從而增強(qiáng)算法的適應(yīng)性。使用17種測(cè)試函數(shù)，通過(guò)與其他6種群體智能算法進(jìn)行對(duì)比，顯示DAWPA具有較好的收斂精度與速度。最后，將DAWPA算法應(yīng)用到復(fù)雜三維環(huán)境的無(wú)人機(jī)航路規(guī)劃問(wèn)題上，驗(yàn)證了該算法的有效性與實(shí)用性。

1 基本狼群算法

狼群算法（WPA）通過(guò)模擬狼群捕食行為及其獵物分配方式，抽象出游走、召喚、圍攻3種智能行為以及“勝者為王”的頭狼產(chǎn)生規(guī)則和“強(qiáng)者生存”的狼群更新機(jī)制。其中，游走行為對(duì)應(yīng)于探狼的貪婪搜索，在游走方向中挑選獵物氣味最濃的方向前進(jìn)。探狼的位置更新規(guī)則如下式：

[xpid=xid+sin2π×p/h×stepa]， （1）

式中：[xid]為探狼i在第d維的當(dāng)前位置; [xpid]為探狼i向第p個(gè)方向前進(jìn)后在第d維所處的位置;h為最大前進(jìn)方向;[stepa]為游走步長(zhǎng)。

召喚行為是頭狼發(fā)起召喚，人工狼向頭狼靠近的過(guò)程，人工狼的位置更新方式遵從以下公式：

[xi′=xi+stepb?xlead-xi/xlead-xi]， （2）

式中：[xi]為人工狼i更新前的位置;[xlead]為頭狼位置;[stepb]為圍攻步長(zhǎng);[xi′]為人工狼i更新后的位置。當(dāng)人工狼與頭狼距離小于給定閾值時(shí)，人工狼以頭狼位置作為獵物位置，向其發(fā)起圍攻。每次人工狼的位置發(fā)生變動(dòng)后，若適應(yīng)度高于頭狼，位置更新的人工狼將會(huì)成為新的頭狼。通過(guò)人工狼與頭狼之間的互動(dòng)，不斷更新狼群的位置，從而逼近最優(yōu)解。圍攻行為根據(jù)下式調(diào)整人工狼位置：

[xi′=xi+λ?stepc?xlead-xi]， （3）

式中：[λ]為[-1，1]之間均勻分布的隨機(jī)數(shù);[stepc]為人工狼的圍攻步長(zhǎng)。

模擬自然界弱肉強(qiáng)食的環(huán)境，WPA設(shè)置了淘汰弱者的狼群更新機(jī)制，并隨機(jī)生成新的人工狼進(jìn)行補(bǔ)充，以保持狼群數(shù)量的穩(wěn)定。

2 具有動(dòng)態(tài)適應(yīng)性的狼群算法

為了提高基本狼群算法的適應(yīng)能力，DAWPA首先對(duì)狼群群體的分工方式進(jìn)行調(diào)整。WPA采取單一頭狼產(chǎn)生規(guī)則，當(dāng)應(yīng)用環(huán)境復(fù)雜時(shí)，單頭狼模式難以有效搜索多個(gè)局部最優(yōu)解。文獻(xiàn)[18]采取的分群方法，雖然增強(qiáng)了算法的適應(yīng)性，但該算法僅根據(jù)適應(yīng)度進(jìn)行分群，沒(méi)有考慮狼群在解空間中的分布情況。為了使子群的劃分合理，除了以適應(yīng)度的大小挑選子群頭狼外，還需根據(jù)頭狼間的距離進(jìn)行篩選，使分群后子群間距離最大化。此外，還需根據(jù)環(huán)境不同與狼群分布的變化，動(dòng)態(tài)調(diào)整子群劃分，以提高算法的動(dòng)態(tài)適應(yīng)性。

在基本狼群算法中，圍攻行為的步長(zhǎng)是固定值，不具有自適應(yīng)能力。在局部開(kāi)發(fā)上，自適應(yīng)步長(zhǎng)可以增強(qiáng)算法局部的自適應(yīng)能力。目前，有基于算法迭代次數(shù)與以歐式距離為參數(shù)的自適應(yīng)步長(zhǎng)方法?；诘螖?shù)的自適應(yīng)步長(zhǎng)具有動(dòng)態(tài)的自適應(yīng)能力，隨著迭代次數(shù)的增加，步長(zhǎng)逐漸減小。但該方法不具有環(huán)境自適應(yīng)性，對(duì)于不同的解空間情況采取的是相同的步長(zhǎng)大小，削弱了算法的適應(yīng)能力。以歐式距離為參數(shù)的自適應(yīng)步長(zhǎng)在特征可分時(shí)具有環(huán)境自適應(yīng)性，但在實(shí)際應(yīng)用中，問(wèn)題特征的各個(gè)維度之間存在相關(guān)性時(shí)，歐氏距離就不再適用。

為了增加自適應(yīng)步長(zhǎng)的適用范圍，必須使用一種能處理耦合特征的步長(zhǎng)調(diào)節(jié)參數(shù)。圍攻過(guò)程反映了頭狼將獵物信息傳遞給人工狼，細(xì)化指導(dǎo)其捕獵的過(guò)程，可以考慮用熵對(duì)頭狼與人工狼之間的信息差進(jìn)行衡量，隨信息差的減小而逐漸減小圍攻步長(zhǎng)。然而，Shannon定義的熵不能衡量序列信息。因此，DAWPA設(shè)計(jì)了一種差異度擬熵，其具有區(qū)分序列的能力。通過(guò)對(duì)頭狼和人工狼的差異度進(jìn)行擬熵計(jì)算，衡量其信息差，進(jìn)而構(gòu)造出自適應(yīng)步長(zhǎng)。

最后，為了增強(qiáng)算法的全局搜索能力，DAWPA對(duì)WPA的游走策略進(jìn)行了調(diào)整。WPA的游走環(huán)節(jié)采取的是貪婪策略，探狼向獵物氣味濃度最高的方向前進(jìn)。為了增強(qiáng)算法避開(kāi)局部最優(yōu)的能力，DAWPA使用隨機(jī)游走環(huán)節(jié)以增強(qiáng)其隨機(jī)性，當(dāng)應(yīng)用環(huán)境的適應(yīng)度函數(shù)計(jì)算復(fù)雜時(shí)，可以有效提高算法的全局搜索能力。

2.1 動(dòng)態(tài)分群策略

在自然界中，狼群具有領(lǐng)域性。在環(huán)境復(fù)雜的情況下，分布較廣的狼群往往會(huì)被環(huán)境分割成數(shù)個(gè)子群。被環(huán)境分隔的每個(gè)狼群的活動(dòng)范圍較為固定，且遵循各自頭狼的領(lǐng)導(dǎo)。模擬自然界中狼群的領(lǐng)域性，針對(duì)復(fù)雜的解空間環(huán)境，提出如下的動(dòng)態(tài)分群策略。

Step 1：完成狼群的初始化后，設(shè)狼群中共有m只狼，計(jì)算m只狼對(duì)應(yīng)的適應(yīng)度，取適應(yīng)度最高的個(gè)體作為子群1的頭狼。為了獲得子群的頭狼，取適應(yīng)度前5%的狼個(gè)體組成頭狼候選集。除了考慮適應(yīng)度外，新的子群頭狼應(yīng)與原來(lái)的各個(gè)頭狼具有較遠(yuǎn)的距離，使各子群對(duì)解空間的探索更充分。由于各個(gè)頭狼之間距離之和隨頭狼數(shù)量增加而增加，因此選取新頭狼的距離閾值應(yīng)與頭狼數(shù)量有關(guān)。具體來(lái)說(shuō)，從頭狼候選集中選取滿足的人工狼，將其作為新子群的頭狼。

[i=1udi≥23udmax]， （4）

式中：u為現(xiàn)有子群數(shù);[di] 指當(dāng)前人工狼與現(xiàn)有的第i個(gè)子群頭狼的歐式距離;[dmax]指子群1的頭狼到解空間邊界距離的最大值，代表了解空間中相對(duì)大的距離，從而可以將其作為距離閾值。

Step 2：由式（4）可以獲得u個(gè)子群頭狼，使用kmeans聚類方法，將m只狼劃分為u個(gè)子群。

Step 3：對(duì)u個(gè)子群的人工狼分別進(jìn)行游走、召喚、圍攻操作。

Step 4：對(duì)Tmax次迭代的狼群算法，則在尋優(yōu)過(guò)程中間隔Tmax/10次迭代完成一次“分裂-合并”的子群動(dòng)態(tài)調(diào)整。

a）子群分裂：將每個(gè)子群適應(yīng)度僅次于頭狼的人工狼作為頭狼候選集，選取滿足式（4）的人工狼作為新子群的頭狼。

b）子群合并：對(duì)每個(gè)子群計(jì)算距離[di]，若其不滿足式（4），則將其與距離最近的子群合并。合并的子群頭狼為原有兩個(gè)子群中適應(yīng)度大的頭狼。

Step 5：完成“分裂-合并”操作后，重新使用kmeans算法進(jìn)行聚類操作。

在簡(jiǎn)單問(wèn)題中，狼群間的適應(yīng)度與在解空間中的分布差異不大，狼群不會(huì)被劃分為多個(gè)子群，整個(gè)狼群一起進(jìn)行捕獵。而在復(fù)雜問(wèn)題中，問(wèn)題的解空間環(huán)境往往呈現(xiàn)出高維、多峰的性質(zhì)，求解過(guò)程中可能出現(xiàn)多個(gè)接近的局部最優(yōu)解，動(dòng)態(tài)分群策略將會(huì)根據(jù)狼群自身的適應(yīng)度與分布情況，動(dòng)態(tài)地調(diào)整子群的數(shù)量，各個(gè)子群可以同時(shí)探索多個(gè)局部最優(yōu)解?；纠侨核惴ㄖ挥袉晤^狼，所有的人工狼都接受其指導(dǎo)，向唯一的局部最優(yōu)解方向探索;DAWPA采取的動(dòng)態(tài)分群策略，不固定子群的數(shù)量與范圍，隨著實(shí)際問(wèn)題與當(dāng)前狀態(tài)的變化進(jìn)行不同的分群，使狼群算法具有了動(dòng)態(tài)的適應(yīng)能力。

2.2 基于差異度擬熵的自適應(yīng)圍攻行為

設(shè)兩頭人工狼的位置向量分別為a， b，則它們的差異度向量定義為：

d={di}={ai-bi}， i=1，…，n.

借鑒文獻(xiàn)[26]定義的擬熵（pseudo entropy），定義一種差異度擬熵如下：

定義1

[PE=-k=1ndkpke1-pk]， （5）

式中， [pk0≤pk≤1] 為k在[dk]中的頻率。式（5）定義的差異度擬熵隨兩個(gè)個(gè)體之間相對(duì)信息差的減小而增大，當(dāng)兩個(gè)個(gè)體完全一致，即信息差為0時(shí)，差異度擬熵取得最大值為0。

差異度擬熵將差異度向量作為系統(tǒng)，通過(guò)衡量差異度的混亂程度，聚合了原個(gè)體向量間各個(gè)維度的綜合信息，從而可以將其作為自適應(yīng)步長(zhǎng)的控制參數(shù)，構(gòu)建自適應(yīng)的圍攻行為。

[xi′=xi+λ×stepc×xlead-xi]， （6）

式中：[stepc=21+ePE-1];[λ]為[-1，1]之間的隨機(jī)數(shù)。使用sigmoid函數(shù)可以使步長(zhǎng)調(diào)節(jié)更為平滑，同時(shí)將差異度擬熵映射為[0，1]的步長(zhǎng)。

通過(guò)式（6），以差異度擬熵為參數(shù)進(jìn)行自適應(yīng)步長(zhǎng)控制，可以將頭狼和人工狼各個(gè)維度的信息差進(jìn)行有效聚合，使人工狼更可能找到最優(yōu)解。由于差異度擬熵統(tǒng)計(jì)了差異度向量的元素，反饋的控制參數(shù)不易受到特征維度與特征關(guān)系的影響，因此在高維、特征存在耦合的情況下精度更高。

2.3 游走環(huán)節(jié)的隨機(jī)化

在基本狼群算法的游走過(guò)程中，探狼分別向h個(gè)方向游走，選擇氣味最濃的方向前進(jìn)。這意味著游走過(guò)程中需要計(jì)算m×h次人工狼的適應(yīng)度。在實(shí)際應(yīng)用問(wèn)題中，多次適應(yīng)度函數(shù)的計(jì)算使游走環(huán)節(jié)耗時(shí)巨大。游走行為本質(zhì)上是一種隨機(jī)搜索過(guò)程，是狼群算法跳出局部最優(yōu)解的重要環(huán)節(jié)。由于探狼主要由上一次迭代過(guò)程中向頭狼發(fā)起圍攻的人工狼組成，距離頭狼較近，選擇適應(yīng)度最高的方向游走，探狼將繼續(xù)靠近頭狼，導(dǎo)致狼群進(jìn)一步陷入局部最優(yōu)解。因此，為了使算法跳出局部最優(yōu)解，設(shè)置隨機(jī)游走環(huán)節(jié)，人工狼按照下式更新位置：

[xi′=xi+sin2π×randi1，hh×stepa] （7）

式中，[randi1，h] 指從1到h之間的一個(gè)隨機(jī)整數(shù)。該游走行為代表在h個(gè)方向中隨機(jī)選取一個(gè)方向前進(jìn)。在隨機(jī)游走中，不進(jìn)行適應(yīng)度的計(jì)算，這意味著在游走過(guò)程中不進(jìn)行頭狼替換的操作，保留原有頭狼進(jìn)入召喚過(guò)程。

隨機(jī)游走策略在一段時(shí)間內(nèi)保留了原有頭狼的指導(dǎo)，避免反復(fù)更換頭狼而帶來(lái)搜索不徹底的問(wèn)題，使人工狼對(duì)解空間的探索更充分，避開(kāi)了局部最優(yōu)，因此具有提高全局搜索的適應(yīng)性的效果。同時(shí)也大大減少了適應(yīng)度計(jì)算的耗時(shí)，加快了算法的效率。

2.4 綜合效果分析

上節(jié)分別介紹了DAWPA所使用的3種技術(shù)的作用。在DAWPA的尋優(yōu)過(guò)程中，3種技術(shù)之間相互作用，其效果互相影響，彌補(bǔ)了部分缺點(diǎn)，增強(qiáng)了算法效果。所提出技術(shù)對(duì)算法性能的作用如圖2所示。其中，紅色實(shí)線代表正面效應(yīng)，綠色虛線代表負(fù)面效應(yīng)。

動(dòng)態(tài)分群策略強(qiáng)了算法的全局搜索能力，通過(guò)將狼群根據(jù)環(huán)境劃分為子群，提高了種群分布的多樣性進(jìn)而增加了覆蓋全局最優(yōu)解的概率，但其精確度不足。

在進(jìn)行粗略的全局搜索后，圍攻過(guò)程可以掃描鄰近區(qū)域，提高算法精度。自適應(yīng)的圍攻進(jìn)一步增強(qiáng)了復(fù)雜函數(shù)環(huán)境下的尋優(yōu)精度。然而，自適應(yīng)步長(zhǎng)的引入增加了計(jì)算耗時(shí)。

隨機(jī)游走環(huán)節(jié)替代了WPA的貪婪游走，減少了重復(fù)計(jì)算適應(yīng)度函數(shù)與頭狼更新的過(guò)程，避免狼群因過(guò)于頻繁地更換頭狼導(dǎo)致搜索不充分。此外，隨機(jī)游走環(huán)節(jié)顯著減少了計(jì)算耗時(shí)，抵消了自適應(yīng)圍攻的負(fù)面效應(yīng)。

3 DAWPA實(shí)現(xiàn)與性能測(cè)試

3.1 DAWPA流程

DAWPA的流程圖如圖3所示，其算法步驟如下。

Step 1： 狼群初始化。在解空間中隨機(jī)初始化狼群的空間坐標(biāo)，計(jì)算適應(yīng)度獲得子群1的頭狼。

Step 2： 動(dòng)態(tài)分群環(huán)節(jié)。根據(jù)適應(yīng)度獲得頭狼候選集，根據(jù)式（4）選出子群頭狼，使用kmeans算法分群。

Step 3： 隨機(jī)游走環(huán)節(jié)。根據(jù)式（7），令人工狼進(jìn)行隨機(jī)游走，更新其坐標(biāo)。

Step 4： 各子群的召喚行為。對(duì)不同的子群分別進(jìn)行圍攻，各子群的人工狼分別向各自的頭狼靠近，若人工狼適應(yīng)度大于頭狼，則其成為新的頭狼。人工狼的位置更新如下式：

[xki′=xki+λbxklead-xki ，]? ? ? ? ? ? ? ? ? ? ? ?（8）

式中：[xki]為第k子群的第i只人工狼; [xki′]為其經(jīng)過(guò)召喚行為后的位置;[λb]為固定召喚步長(zhǎng);[xklead]為第k子群的頭狼。

Step 5： 基于差異度擬熵的自適應(yīng)圍攻過(guò)程。對(duì)于每個(gè)子群的每只狼，根據(jù)式（6）可計(jì)算出自適應(yīng)的圍攻步長(zhǎng)，向獵物發(fā)起圍攻。

Step 6： 子群種群更新。對(duì)種群中適應(yīng)度差的個(gè)體進(jìn)行淘汰，并產(chǎn)生等量的隨機(jī)新個(gè)體。

Step 7： 群體的“分裂-合并”行為。在一定的間隔下，在各子群內(nèi)部挑選頭狼候選，進(jìn)行分裂;對(duì)子群頭狼之間的距離進(jìn)行計(jì)算，根據(jù)結(jié)果進(jìn)行合并。

Step 8： 重復(fù)過(guò)程3-7，直至到達(dá)最大迭代次數(shù)或算法精度滿足閾值。

為了更好地解釋DAWPA算法流程，提供其偽代碼如下。

Algorithm 1. Pseudo code of DAWPA

Input： the parameters of DAWPA including population size n， step coefficient S， distance determinant coefficient dnear.

Output： the best objective value.

1. Generate initial population of wolves Xi = {xi1， xi2， …， xij， …， xin}

2. Evaluate the fitness of whole population o and select the initial lead wolf Ylead = max{Yi}

3. Clustering method

4. Select wolves with top 5% fitness as leader wolf candidates

5. group_number：=1

6. for candidates i=1;i

7.? if candidate i satisfies Eq. （4） then

8.? ?group_number++

9.? endif

10. end for

11. Generate subgroups using k-means（group_number）

12. Set iteration counter for initial population g：=0

13. while g

14.? for i=1;i

15.? ?Scouting behavior

16.? ?Takes a step towards direction p as in Eq. （7） and update positions of subgroup i

17.? ?Summoning behavior

18.? ?if Yij > Yi_lead then

19.? ? renew lead wolf i and restart the summoning behavior

20.? ?else if Yi ≤ Ylead & dis ≤ dnear then/*dis is the distance between Xlead and Xi*/

21.? ? wolves from subgroup i move to lead wolf i with the moving operator

22.? ?else

23.? ? update their positions as in Eq. （8）

24.? ?endif

25.? ?Besieging behavior

22.? ?if Yi > Ylead then

23.? ? renew the lead wolf

24.? ?else if Yi ≤ Ylead

25.? ? wolves move to the lead wolf with the moving operator

26.? ?else

27.? ? update their positions as in Eq. （6）

28.? ?endif

29.? end for

30.? Split and Merge

31.? for i=1;i

32.? ?if wolf x2 satisfy Eq. （4） then/*x2 refers the wolf that has second highest fitness in subgroup i*/

33.? ? divide group i to 2 subgroups using k-means method

33.? ?endif

34.? end for

35.? for i=1;i

36.? ?if xilead does not satisfy Eq. （4） then

37.? ? subgroup i merges with the nearest subgroup

38.? ?endif

39.? end for

40.? g++

41.? Restart the scouting， summoning and besieging behaviors

42. end while

3.2 測(cè)試函數(shù)與參數(shù)設(shè)置

3.2.1 測(cè)試函數(shù)

參考文獻(xiàn)[27-28]，將DAWPA在17個(gè)測(cè)試函數(shù)上進(jìn)行10次重復(fù)測(cè)試。選取的測(cè)試函數(shù)包含了近年來(lái)研究中常用的單峰、多峰、可分、不可分、不同維度等多種類型的函數(shù)，以測(cè)試算法在多種環(huán)境下的表現(xiàn)情況差異[29-32]。

函數(shù)與特性如表1所示，U（unimodal）表示單峰函數(shù)，M（multimodal）表示多峰函數(shù)，S為可分（separable），N為不可分（non-separable）。單峰為在定義域內(nèi)無(wú)局部極值，只有全局最優(yōu)值的函數(shù);多峰為有多個(gè)局部極值的函數(shù)，一般的算法較易陷入局部最優(yōu)值，因此可以用來(lái)檢驗(yàn)算法的全局搜索和避免過(guò)早收斂的能力;含有N維自變量且能表示為N個(gè)單變量函數(shù)之和的函數(shù)為可分函數(shù);反之則為不可分函數(shù)。

3.2.2 比較算法及參數(shù)設(shè)置

本文使用人工蜂群算法（ABC）[33]、布谷鳥(niǎo)搜索算法[34]與4種改進(jìn)狼群算法進(jìn)行比較。3種狼群算法分別為基于歐氏距離的自適應(yīng)改進(jìn)狼群算法（IWPA）[21]、引入趨向游走行為和死亡概率的改進(jìn)狼群算法（Chemotactic behavior and Death probability WPA， CDWPA）[35]和基于levy飛行的動(dòng)態(tài)狼群算法（Dynamic wolf pack algorithm based on Levy Flight， LDWPA）[36]進(jìn)行比較。此外，使用一種較新穎的改進(jìn)PSO算法，prey-predator PSO （PP-PSO）算法進(jìn)行比較，該算法在CEC2017測(cè)試函數(shù)集上展現(xiàn)了比其他10種PSO衍生算法更好的性能[37]。為方便讀者閱讀，將結(jié)果分兩組進(jìn)行展示。其中WPA的改進(jìn)算法（包括DAWPA， IWPA， CDWPA， LDWPA）為一組，其他算法為一組（包括DAWPA， CS， ABC， PP-PSO）。本文統(tǒng)計(jì)4個(gè)尋優(yōu)性能指標(biāo)，分別為最優(yōu)值（best），平均值（mean），標(biāo)準(zhǔn)差（SD）與平均耗時(shí)（average time-cost）。

實(shí)驗(yàn)的最大迭代次數(shù)為2 000次，初始種群數(shù)目都設(shè)為100，精度閾值為1×10-6，即小于1×10-6的精度誤差均可視為0。各算法參數(shù)見(jiàn)表2.測(cè)試環(huán)境為i7-6500U CPU @ 2.50GHz 2.59GHz， Matlab R2018a。測(cè)試結(jié)果見(jiàn)表3和表4。

3.3 結(jié)果分析

本節(jié)將從算法精度（包含3.3.2節(jié)統(tǒng)計(jì)分析）、速度-穩(wěn)定性能與收斂速度比較三方面，對(duì)表3、表4的結(jié)果進(jìn)行分析。

為了方便讀者理解，下面對(duì)性能指標(biāo)的含義進(jìn)行簡(jiǎn)要介紹?！癇est”為尋優(yōu)全程中算法取得的最接近標(biāo)準(zhǔn)值的結(jié)果?！癕ean”為尋優(yōu)過(guò)程中，所有迭代的平均結(jié)果。“SD”為計(jì)算結(jié)果的標(biāo)準(zhǔn)差，其代表了算法的穩(wěn)定性能?！癮verage time-cost”為每次尋優(yōu)（2 000次迭代）的平均耗時(shí)。

3.3.1 算法精度分析

表3、表4中的最優(yōu)值與平均值反映了算法的尋優(yōu)精度。從低維、可分、單峰的函數(shù)，如F1-5的結(jié)果來(lái)看，DAWPA的尋優(yōu)精度與其他算法的結(jié)果接近。對(duì)于低維、不可分、多峰函數(shù)，例如F8-9，DAWPA的算法精度與CS， ABC， PP-PSO， CDWPA， LDWPA算法接近，而IWPA則相對(duì)較低。對(duì)于高維、可分、單峰函數(shù)，包括F6-7，DAWPA，ABC和IWPA算法比CS算法略有優(yōu)勢(shì)，同時(shí)精度遠(yuǎn)高于PP-PSO算法與LDWPA算法。對(duì)高維、可分、多峰函數(shù)，如F11，4種WPA改進(jìn)算法具有明顯優(yōu)勢(shì)，顯示其避免陷入局部最優(yōu)的能力比其他算法強(qiáng)，且DAWPA算法精度優(yōu)于其他3種WPA改進(jìn)算法。CS， ABC和PP-PSO算法的優(yōu)化基于適應(yīng)度，采取貪婪策略進(jìn)行更新。但當(dāng)面對(duì)多峰函數(shù)時(shí)，單純依賴適應(yīng)度的更新機(jī)制極易陷入局部最優(yōu)解，因此其算法精度不佳。而WPA改進(jìn)算法采用了游走-召喚-圍攻的做法，由可變的頭狼對(duì)其他人工狼進(jìn)行指導(dǎo)，對(duì)全局信息與頭狼附近的局部信息都進(jìn)行了探索，因此在多峰高維問(wèn)題上精度較好。相對(duì)于其他WPA改進(jìn)算法，DAWPA加入了分群策略，將解空間中被多個(gè)峰分隔的子群進(jìn)行適當(dāng)?shù)姆秩海謩e由各自的頭狼召喚、圍攻，同時(shí)有間隔的進(jìn)行子群的合并-分裂，使多個(gè)較優(yōu)的解空間領(lǐng)域得到充分探索，獲得了最好的算法精度。

此外，對(duì)多峰不可分的高維函數(shù)，如F16-17，其反映了算法對(duì)不可分的維度信息的處理能力。計(jì)算結(jié)果的比較表明，DAWPA的算法精度高于WPA改進(jìn)算法且遠(yuǎn)高于PP-PSO、ABC和CS算法。這證明采用差異度擬熵的自適應(yīng)圍攻環(huán)節(jié)對(duì)不可分的維度信息處理能力更強(qiáng)，提高了算法的精度。

3.3.2 統(tǒng)計(jì)分析

3.3.1節(jié)中的分析顯示DAWPA相對(duì)于其他算法在復(fù)雜函數(shù)尋優(yōu)上具有更好的性能。為了進(jìn)行進(jìn)一步的統(tǒng)計(jì)分析，本節(jié)采取無(wú)參數(shù)Friedman test分析復(fù)雜函數(shù)上的平均精度，以測(cè)試DAWPA相對(duì)其他算法的精度優(yōu)勢(shì)是否顯著[38]。算法平均精度為算法平均結(jié)果與標(biāo)準(zhǔn)值的差值的絕對(duì)值。原假設(shè)認(rèn)為DAWPA與比較的算法的性能無(wú)顯著差異，當(dāng)p值小于0.05時(shí)拒絕原假設(shè)且置信度為95%。

為了應(yīng)用F-test，首先選取多個(gè)復(fù)雜函數(shù)，并將其劃分為兩類。將函數(shù)維數(shù)大于等于30且小于等于100的函數(shù)劃分為中等維數(shù)函數(shù)（Mid-dimensional），將函數(shù)維數(shù)高于100的劃分為高維函數(shù)（High-dimensional）。函數(shù)的劃分如表5所示。

將表3、表4中的平均結(jié)果（mean）與標(biāo)準(zhǔn)值的差值的絕對(duì)值作為精度指標(biāo)。借鑒文獻(xiàn)[39]，對(duì)每個(gè)算法分別計(jì)算中等維度函數(shù)與高維函數(shù)的精度指標(biāo)的平均值（mean）與中位數(shù)（median）。

基于該平均值與中位數(shù)，使用Matlab進(jìn)行F-test，計(jì)算p值為0.02<0.05，即可以以95%的置信度拒絕原假設(shè)，顯示DAWPA算法對(duì)其他算法的精度優(yōu)勢(shì)具有顯著性。指標(biāo)及計(jì)算結(jié)果如表6所示。

3.3.3 速度-穩(wěn)定性能分析

表3、表4中的標(biāo)準(zhǔn)差與耗時(shí)分別體現(xiàn)了算法的穩(wěn)定性和快速性。對(duì)于智能算法而言，其速度-穩(wěn)定性能之間的平衡對(duì)算法的應(yīng)用影響巨大，因此對(duì)這兩個(gè)指標(biāo)同時(shí)進(jìn)行分析。由于各個(gè)函數(shù)復(fù)雜程度不同，不同函數(shù)的尋優(yōu)標(biāo)準(zhǔn)差之間存在數(shù)量級(jí)的差異。為了直觀展示DAWPA相對(duì)于其他算法的尋優(yōu)標(biāo)準(zhǔn)差的情況，使用對(duì)數(shù)標(biāo)準(zhǔn)差比，即DAWPA的標(biāo)準(zhǔn)差與其他6種算法標(biāo)準(zhǔn)差的比值的對(duì)數(shù)作為特征，與算法耗時(shí)一起展示。對(duì)于標(biāo)準(zhǔn)差比值分母為0的情況，若分子也為0，將比值標(biāo)為1;若分子大于0，將比值標(biāo)為10 000，則取對(duì)數(shù)后為4。結(jié)果如圖4a）和4b）所示。

在穩(wěn)定性方面，對(duì)于低維、單峰函數(shù)， DAWPA的穩(wěn)定性相對(duì)于ABC算法、CS算法較差，與CDWPA和LDWPA互有優(yōu)劣但較為接近，好于IWPA算法。對(duì)于高維、多峰尤其是不可分的復(fù)雜函數(shù)，如F11、F16、F17，比值曲線出現(xiàn)了明顯的下三角，說(shuō)明DAWPA在復(fù)雜函數(shù)上的穩(wěn)定性顯著好于其他算法，不易受到干擾。在7種算法中，對(duì)于高維的復(fù)雜函數(shù)，DAWPA擁有最好的穩(wěn)定性。這是因?yàn)檫@5種算法本質(zhì)上都屬于隨機(jī)搜索算法，而當(dāng)搜索進(jìn)入到局部最優(yōu)解時(shí)，其他算法基于貪婪的更新策略都容易陷入局部最優(yōu)，盡管都加入了一定概率的跳出局部最優(yōu)的操作，但算法穩(wěn)定性仍然會(huì)受到明顯的影響。而DAWPA使用了分群的策略，多個(gè)子群同時(shí)探索，有更大概率求得全局最優(yōu)值，算法穩(wěn)定性得到了提高。從計(jì)算耗時(shí)上看，DAWPA在低維函數(shù)上計(jì)算耗時(shí)較大，但在高維函數(shù)上顯著縮短了耗時(shí)，與其他WPA改進(jìn)算法相比，具有明顯優(yōu)勢(shì)。一方面這是由于分群策略的使用加快了算法求得全局最優(yōu)解的速度，抵消了計(jì)算耗時(shí)，另一方面是因?yàn)殡S機(jī)游走環(huán)節(jié)，相對(duì)于WPA的其他改進(jìn)算法的游走環(huán)節(jié)減少了適應(yīng)度函數(shù)的計(jì)算，因此大幅度減少了計(jì)算耗時(shí)。

3.3.4 算法收斂情況分析

速度-穩(wěn)定性能分析顯示，與非WPA改進(jìn)算法相比，DAWPA具有更好的穩(wěn)定性，但計(jì)算耗時(shí)較多。本節(jié)通過(guò)對(duì)收斂過(guò)程進(jìn)行分析，確定耗時(shí)較多的原因。由于CDWPA與LDWPA算法的耗時(shí)較大，該分析僅涵蓋DAWPA， CS， ABC， IWPA， PP-PSO5種算法。

將尋優(yōu)誤差隨迭代次數(shù)的變化繪制成收斂曲線，選擇一系列高維函數(shù)，包括F6， F7， F11，與F17，繪制5種算法在不同函數(shù)上的收斂曲線，如圖5。

以高維、不可分、多峰函數(shù)F17為例，5種算法的收斂曲線如圖6所示。在100代左右，IWPA算法就基本收斂，其精度停留在1×10-4級(jí)別，顯示其可能陷入了局部最優(yōu)。250代左右，DAWPA算法到達(dá)全局最優(yōu)，達(dá)到了更高的尋優(yōu)精度。2 000代后，ABC與CS算法仍然未能收斂到全局最優(yōu)解。PP-PSO算法在尋優(yōu)初期快速下降，但很快陷入局部最優(yōu)解。

圖5所示其他收斂曲線也顯示DAWPA在速度與精度上具有優(yōu)勢(shì)。IWPA的收斂速度與DAWPA接近，但精確度較差。ABC算法與DAWPA算法在F16上達(dá)到了接近的精度，但在F11， F17上性能較差。

分析結(jié)果說(shuō)明，在復(fù)雜函數(shù)上，DAWPA基于游走-召喚-智能圍攻的尋優(yōu)過(guò)程，相對(duì)于PP-PSO、ABC算法和CS算法，能更好地對(duì)解空間進(jìn)行搜索，在尋優(yōu)能力上有明顯優(yōu)勢(shì)。在多峰不可分函數(shù)上，與IWPA的對(duì)比證明，DAWPA基于差異度擬熵的智能圍攻過(guò)程，對(duì)不可分的函數(shù)特征有更高的尋優(yōu)精度。

綜上所述，DAWPA在高維不可分多峰函數(shù)上，用一定的計(jì)算耗時(shí)，換取了明顯的尋優(yōu)精度、穩(wěn)定性的提升。在圍攻過(guò)程中，DAWPA的動(dòng)態(tài)分群過(guò)程和差異度擬熵的計(jì)算量大于其他改進(jìn)WPA算法，花費(fèi)了較多時(shí)間，因此在簡(jiǎn)單函數(shù)上整體耗時(shí)較長(zhǎng);但在如F17等復(fù)雜函數(shù)上耗時(shí)明顯縮短。原因是DAWPA通過(guò)動(dòng)態(tài)分群，減小了陷入局部最優(yōu)的可能;隨機(jī)游走環(huán)節(jié)減少了適應(yīng)度函數(shù)計(jì)算的大量耗時(shí);使用差異度擬熵，對(duì)頭狼和人工狼的相似度進(jìn)行了更合適的度量，提高尋優(yōu)精度的同時(shí)，在更少的迭代次數(shù)內(nèi)收斂到最優(yōu)值，抵消了計(jì)算的耗時(shí)。測(cè)試結(jié)果證明，DAWPA算法具有更強(qiáng)的適應(yīng)能力，不易陷入局部最優(yōu)解。同時(shí)，動(dòng)態(tài)分群與隨機(jī)游走環(huán)節(jié)加快了算法收斂到全局最優(yōu)值的速度，較PP-PSO、ABC算法、CS算法和其他改進(jìn)WPA算法有明顯的優(yōu)勢(shì)。

4 DAWPA的實(shí)際應(yīng)用

復(fù)雜地形三維航路規(guī)劃是指在復(fù)雜三維地形環(huán)境下，無(wú)人機(jī)自主規(guī)劃一條航線躲避障礙物，同時(shí)盡可能減少航程。相比于二維航路規(guī)劃，三維情況下搜索空間過(guò)大，快速拓展隨機(jī)樹(shù)[40]、A*算法[41]等傳統(tǒng)二維航路規(guī)劃算法的計(jì)算時(shí)間過(guò)長(zhǎng)?；谀M流體流動(dòng)的思想，文獻(xiàn)[42]提出了基于擾動(dòng)流體動(dòng)態(tài)系統(tǒng)（IFDS）的三維航路規(guī)劃方法，該方法具有光滑的航路特性和快速性，但產(chǎn)生的流線存在局部陷阱或可能停留于駐點(diǎn)。為了解決流線缺陷，文獻(xiàn)[43]提出了改進(jìn)擾動(dòng)流體動(dòng)態(tài)系統(tǒng)算法（IIFDS）。在IIFDS算法中，需要對(duì)反應(yīng)系數(shù)進(jìn)行優(yōu)化，以產(chǎn)生最優(yōu)航路。多種群智能優(yōu)化算法在對(duì)反應(yīng)系數(shù)進(jìn)行尋優(yōu)時(shí)，尋優(yōu)效果隨維度增長(zhǎng)而下降，且容易陷入局部最優(yōu)解[42]。為了驗(yàn)證DAWPA具有的動(dòng)態(tài)適應(yīng)性，本文將DAWPA應(yīng)用于無(wú)人機(jī)航路規(guī)劃，對(duì)復(fù)雜三維地形下IIFDS算法的反應(yīng)系數(shù)組進(jìn)行尋優(yōu)，規(guī)劃出較優(yōu)航線。IIFDS模型參見(jiàn)文獻(xiàn)[42]。

4.1 復(fù)雜地形下的三維航路規(guī)劃

在IIFDS模型中，排斥反應(yīng)系數(shù)[ρ]、切向反應(yīng)系數(shù)[σ]與切向方向系數(shù)[θ]的選取影響了最終航線的方向、形狀與長(zhǎng)度。本文使用DAWPA，對(duì)其進(jìn)行優(yōu)化以獲得較優(yōu)航線。首先定義適應(yīng)度函數(shù)J?？紤]航路長(zhǎng)度代價(jià)[J1]與障礙物威脅代價(jià)[J2]。

[J=μ1J1+μ2J2，]

式中，[μ1，μ2∈0，1]為代價(jià)權(quán)重系數(shù)，有[μ1+μ2=1]。

其次，對(duì)于狼群的初始化，設(shè)定參數(shù)范圍[ρ∈0.1，30、σ∈0.1，30、θ∈-π，π]， 初始化狼群規(guī)模N，則[Xi=ρ1，σ1，θ1，...，ρK，σK，θK，i=1，2，...，N]，維度D=3K。

基于3.1節(jié)的算法流程，設(shè)定規(guī)劃空間為[10×10×3]，隨機(jī)產(chǎn)生10個(gè)不同類型的障礙物，如圖7所示。障礙物高度不一，可以測(cè)試算法權(quán)衡左右繞行或拉升避障的能力;有單峰障礙物，也有兩個(gè)障礙物疊加的多峰障礙，更加貼近實(shí)際地形，也增加了難度。

對(duì)圖7的地形，設(shè)定無(wú)人機(jī)起點(diǎn)為（0，0，0），終點(diǎn)為（10，10，0.5）。為了無(wú)人機(jī)的安全，設(shè)置代價(jià)權(quán)重系數(shù)[0.3，0.7]，代表較高的避障權(quán)重。使用DAWPA、CS算法、ABC算法、PP-PSO算法、IWPA算法、CDWPA算法與LDWPA算法進(jìn)行比較，設(shè)置種群規(guī)模N=100，最大迭代次數(shù)t=100，進(jìn)行50次重復(fù)實(shí)驗(yàn)，并選取其中適應(yīng)度最好的航線結(jié)果進(jìn)行比較。

將使用6種算法所得到的航路按照第3節(jié)的分組方式分兩組繪制，如圖8a）、圖b）、圖8c）和圖8d），對(duì)應(yīng)的路徑信息如表7所示。對(duì)于不可行路徑，其代價(jià)記為-。

DAWPA、CS、IWPA和LDWPA算法生成的航線都能在復(fù)雜三維地形中避開(kāi)障礙物到達(dá)終點(diǎn)，但ABC、PP-PSO與CDWPA算法生成的路徑未能避開(kāi)部分障礙物，說(shuō)明這3種算法未能找到合適的排斥反應(yīng)系數(shù)和切向反應(yīng)系數(shù)。在7種算法生成的路徑中，DAWPA生成的路徑的長(zhǎng)度代價(jià)與避障代價(jià)均小于其他算法，路徑也較為平滑，更加適用于無(wú)人機(jī)的飛行。

在復(fù)雜三維地形下的航路規(guī)劃問(wèn)題中，待優(yōu)化個(gè)體為針對(duì)各個(gè)障礙物的排斥反應(yīng)系數(shù)、切向反應(yīng)系數(shù)和切向方向系數(shù)。由于可能的航線不止一條，該問(wèn)題有著多峰函數(shù)性質(zhì)。因此，DAWPA的動(dòng)態(tài)分群策略有助于同時(shí)探索多條較優(yōu)路徑，從而更快地找到最優(yōu)路徑。另外，對(duì)于一條航路，避開(kāi)不同障礙物的角度不是完全獨(dú)立的，例如，航線穿過(guò)兩個(gè)障礙物之間時(shí)，對(duì)其中一個(gè)障礙物避障角度過(guò)大會(huì)導(dǎo)致無(wú)人機(jī)進(jìn)入到另一個(gè)障礙物中，引起避障代價(jià)的提高。在航線規(guī)劃中，各個(gè)維度之間存在一定的聯(lián)系，優(yōu)化目標(biāo)具有不可分函數(shù)的特性。DAWPA的優(yōu)勢(shì)在于，使用差異度擬熵對(duì)所有維度信息進(jìn)行統(tǒng)計(jì)，因此對(duì)不可分函數(shù)的局部信息有更強(qiáng)的感知能力。綜上所述，對(duì)于航路規(guī)劃問(wèn)題，DAWPA擁有更好的優(yōu)化效果。

5 結(jié)論

本文針對(duì)基本狼群算法缺乏適應(yīng)性的問(wèn)題，提出了一種具有動(dòng)態(tài)適應(yīng)性的狼群算法DAWPA，以提高狼群算法在實(shí)際應(yīng)用中的表現(xiàn)。

通過(guò)引入動(dòng)態(tài)分群策略，種群的分布可以根據(jù)優(yōu)化環(huán)境進(jìn)行動(dòng)態(tài)調(diào)整;使用差異度擬熵改進(jìn)的圍攻過(guò)程提高了復(fù)雜環(huán)境下的尋優(yōu)精度;隨機(jī)游走環(huán)節(jié)增強(qiáng)了全局適應(yīng)性，并減少了計(jì)算耗時(shí)，從而抵消了前兩個(gè)技術(shù)帶來(lái)的較高的時(shí)間代價(jià)。在測(cè)試函數(shù)集上與其他6種算法比較的仿真實(shí)驗(yàn)體現(xiàn)了DAWPA在搜索全局最優(yōu)與快速收斂上的能力。此外，在三維無(wú)人機(jī)路徑規(guī)劃問(wèn)題上，DAWPA展現(xiàn)了比其他6種算法更好的優(yōu)化性能，獲得的飛行路徑航程更短且能良好避障，具有實(shí)用性。

本文定義了一種差異度擬熵，具有度量耦合函數(shù)特征的相似度與序列信息的能力，拓展了自適應(yīng)步長(zhǎng)算法，理論上對(duì)優(yōu)化目標(biāo)具有不可分特性的相似性度量具有通用性，可以將其引入其他需要不可分函數(shù)相似性度量的智能算法中。另外，本文提出的動(dòng)態(tài)分群策略提供了一種改進(jìn)的初始解生成方法。由于采取了動(dòng)態(tài)分群的策略，DAWPA在復(fù)雜函數(shù)上較強(qiáng)的處理能力，可以應(yīng)用于其他復(fù)雜結(jié)構(gòu)問(wèn)題的尋優(yōu)，如多水下自主航行器的動(dòng)態(tài)任務(wù)分配問(wèn)題等。下一步可以考慮針對(duì)具體問(wèn)題，進(jìn)一步優(yōu)化分群策略，使其適用于更多應(yīng)用場(chǎng)景。

參考文獻(xiàn)：

[1]? ? GUPTA A，SRIVASTAVA S. Comparative analysis of ant colony and particle swarm optimization algorithms for distance optimization[J]. Procedia Computer Science，2020，173：245-253.

[2]? ? ALFI A，MODARES H. System identification and control using adaptive particle swarm optimization[J]. Applied Mathematical Modelling，2011，35（3）：1210-1221.

[3]? ? SQUILLERO G，TONDA A. Divergence of character and premature convergence：a survey of methodologies for promoting diversity in evolutionary optimization[J]. Information Sciences，2016，329：782-799.

[4]? ? 吳虎勝，張鳳鳴，吳廬山. 一種新的群體智能算法：狼群算法[J]. 系統(tǒng)工程與電子技術(shù)，2013，35（11）：2430-2438.

[5]? ? 劉聰，費(fèi)煒，胡勝. 狼群算法的研究與應(yīng)用綜述[J]. 科學(xué)技術(shù)與工程，2020，20（9）：3378-3386.

[6]? ? LI H，WU H S. An oppositional wolf pack algorithm for Parameter identification of the chaotic systems[J]. Optik，2016，127（20）：9853-9864.

[7]? ? 吳虎勝，張鳳鳴，戰(zhàn)仁軍，等. 求解0-1背包問(wèn)題的二進(jìn)制狼群算法[J]. 系統(tǒng)工程與電子技術(shù)，2014，36（8）：1660-1667.

[8]? ? 吳虎勝，張鳳鳴，李浩，等. 求解TSP問(wèn)題的離散狼群算法[J]. 控制與決策，2015，30（10）：1861-1867.

[9]? ? 馬龍，盧才武，顧清華，等. 多目標(biāo)0-1規(guī)劃問(wèn)題的元胞狼群優(yōu)化算法研究[J]. 運(yùn)籌與管理，2018，27（3）：17-24.

[10]? WU H S，XUE J J，XIAO R B，et al. Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm[J]. Frontiers of Information Technology & Electronic Engineering，2020，21（9）：1356-1368.

[11]? WU H S，XIAO R B. Flexible wolf pack algorithm for dynamic multidimensional knapsack problems[J]. Research，2020，2020（11）：1-13.

[12]? ZHANG L Y，ZHANG L，LIU S，et al. Three-dimensional underwater path planning based on modified wolf pack algorithm[J]. IEEE Access，2017，5：22783-22795.

[13]? 李勵(lì)，賴喜德，陳小明. 基于改進(jìn)狼群算法的水電站廠內(nèi)優(yōu)化運(yùn)行研究[J]. 水電能源科學(xué)，2019，37（6）：164-168.

[14]? CHEN Y B，MEI Y S，YU J Q，et al. Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm[J]. Neurocomputing，2017，266：445-457.

[15]? CHEN X Y，TANG C J，WANG J，et al. Improved wolf pack algorithm based on differential evolution elite set[J]. IEICE Transactions on Information and Systems，2018，E101. D（7）：1946-1949.

[16]? 周璟. 混沌狼群圍捕算法的車間機(jī)器人導(dǎo)航路徑規(guī)劃[J]. 機(jī)械設(shè)計(jì)與制造，2020（1）：251-255.

[17]? 惠曉濱，郭慶，吳娉娉，等. 一種改進(jìn)的狼群算法[J]. 控制與決策，2017，32（7）：1163-1172.

[18]? 張強(qiáng)，王梅. 自適應(yīng)分組差分變異狼群優(yōu)化算法[J]. 華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2017（3）：78-86.

[19]? ZHU Y，JIANG W L，KONG X D，et al. A chaos wolf optimization algorithm with self-adaptive variable step-size[J]. AIP Advances，2017，7（10）：105024.

[20]? 王盈祥，陳民鈾，程庭莉，等. 基于差分進(jìn)化的改進(jìn)狼群算法研究[J]. 計(jì)算機(jī)應(yīng)用研究，2019，36（8）：2305-2310.

[21]? 郭立婷. 基于自適應(yīng)和變游走方向的改進(jìn)狼群算法[J]. 浙江大學(xué)學(xué)報(bào)（理學(xué)版），2018，45（3）：284-293.

[22]? 顏學(xué)龍，汪斌斌. 自適應(yīng)狼群算法優(yōu)化ELM的模擬電路故障診斷[J]. 計(jì)算機(jī)工程與科學(xué)，2019，41（2）：246-252.

[23]? 曹爽，安建成. 改進(jìn)狼群優(yōu)化算法的Otsu圖像分割法[J]. 微電子學(xué)與計(jì)算機(jī)，2017，34（10）：16-21.

[24]? 張舉世. 改進(jìn)的狼群優(yōu)化二維Otsu閾值分割算法[J]. 電力學(xué)報(bào)，2020，35（1）：40-45.

[25]? 李靖宇，王磊，江克貴，等. 基于改進(jìn)狼群算法的概率積分法模型參數(shù)反演方法[J]. 采礦與巖層控制工程學(xué)報(bào)，2021，3（1）：79-86.

[26]? LI C，MA H，ZHOU Y，et al. Similarity analysis of DNA sequences based on the weighted pseudo-entropy[J]. Journal of Computational Chemistry，2011，32（4）：675-680.

[27]? 薛俊杰，王瑛，李浩，等. 一種狼群智能算法及收斂性分析[J]. 控制與決策，2016，31（12）：2131-2139.

[28]? WU H S，ZHANG F M. Wolf pack algorithm for unconstrained global optimization[J]. Mathematical Problems in Engineering，2014，2014：1-17.

[29]? MOAZZENI A R，KHAMEHCHI E. Rain optimization algorithm （ROA）：a new metaheuristic method for drilling optimization solutions[J]. Journal of Petroleum Science and Engineering，2020，195：107512.

[30]? JAIN L，KATARYA R，SACHDEVA S. Opinion leader detection using whale optimization algorithm in online social network[J]. Expert Systems With Applications，2020，142：113016.

[31]? NAIK A，SATAPATHY S C，ABRAHAM A. Modified Social Group Optimization—a meta-heuristic algorithm to solve short-term hydrothermal scheduling[J]. Applied Soft Computing，2020，95：106524.

[32]? CHOU J S，NGUYEN N M. FBI inspired meta-optimization[J]. Applied Soft Computing，2020，93：106339.

[33]? KARABOGA D，BASTURK B. A powerful and efficient algorithm for numerical function optimization：artificial bee colony （ABC） algorithm[J]. Journal of Global Optimization，2007，39（3）：459-471.

[34]? CUEVAS E，REYNA-ORTA A. A cuckoo search algorithm for multimodal optimization[J]. The Scientific World Journal，2014，2014：497514.

[35]? 鮮思東，李堂金. 基于改進(jìn)狼群算法的模糊時(shí)間序列預(yù)測(cè)模型[J]. 控制理論與應(yīng)用，2020，37（7）：1637-1643.

[36]? 韓忠華，劉約翰，李曼，等. 改進(jìn)狼群算法求解模具在模臺(tái)上組合分配問(wèn)題[J]. 系統(tǒng)仿真學(xué)報(bào)，2021，33（1）：127-140.

[37]? ZHANG H R，YUAN M，LIANG Y T，et al. A novel particle swarm optimization based on prey-predator relationship[J]. Applied Soft Computing，2018，68：202-218.

[38]? DEMSAR J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research，2006，7：1-30.

[39]? TANWEER M R，SURESH S，SUNDARARAJAN N. Self regulating particle swarm optimization algorithm[J]. Information Sciences，2015，294：182-202.

[40]? ZUCKER M，KUFFNER J，BRANICKY M. Multipartite RRTs for rapid replanning in dynamic environments[C]//Proceedings 2007 IEEE International Conference on Robotics and Automation. April 10-14，2007，Rome，Italy. IEEE，2007：1603-1609.

[41]? YANG H I，ZHAO Y J. Trajectory planning for autonomous aerospace vehicles amid known obstacles and conflicts[J]. Journal of Guidance，Control，and Dynamics，2004，27（6）：997-1008.

[42]? WANG H L，LYU W T，YAO P，et al. Three-dimensional path planning for unmanned aerial vehicle based on interfered fluid dynamical system[J]. Chinese Journal of Aeronautics，2015，28（1）：229-239.

[43]? 姚鵬，王宏倫. 基于改進(jìn)流體擾動(dòng)算法與灰狼優(yōu)化的無(wú)人機(jī)三維航路規(guī)劃[J]. 控制與決策，2016，31（4）：701-708.