郭立婷

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院， 陜西 西安 710126)

0 引 言

受自然界生物活動現(xiàn)象的啟發(fā)，研究人員提出了多種智能優(yōu)化計算方法.文獻[1]模擬螞蟻社會分工與協(xié)作覓食的行為，提出了蟻群算法(ant colony optimization，ACO)；文獻[2]模擬魚群捕食中的覓食、聚群等行為提出了魚群算法(fish swarm algorithm，F(xiàn)SA)；文獻[3]模擬螢火蟲發(fā)光吸引同伴現(xiàn)象，提出螢火蟲優(yōu)化算法(glowworm swarm optimization，GSO). LIU等[4]模擬自然界狼群捕獵行為，提出了狼群算法(wolf colony algorithm，WCA)；吳虎勝等[5]模擬狼群捕食行為及其獵物分配方式，抽象出狼群游走、召喚、圍攻3種智能行為以及“勝者為王”的頭狼產(chǎn)生規(guī)則和“強者生存”的狼群更新機制，提出狼群算法(wolf pack algorithm，WPA)，并通過15個典型的復(fù)雜函數(shù)實驗將WPA算法與FSA算法、PSO算法、GA算法進行了比較，WPA算法在處理多峰、高維復(fù)雜函數(shù)上有明顯優(yōu)勢. 自適應(yīng)在智能優(yōu)化算法中應(yīng)用廣泛，文獻[6-7]基于人工魚群算法的尋優(yōu)機理，提出了4種自適應(yīng)人工魚群算法，通過賦予人工魚更多的智能，使人工魚根據(jù)魚群狀態(tài)自動地調(diào)整視野和步長，簡化了參數(shù)設(shè)定，提高了收斂速度和尋優(yōu)精度. 歐陽喆等[8]針對基本螢火蟲算法在求解多峰函數(shù)時精度不高和后期收斂較慢的問題，引入熒光因子以自適應(yīng)調(diào)整螢火蟲步長，提出一種自適應(yīng)步長螢火蟲優(yōu)化算法.文獻[9]提出了一種動態(tài)自適應(yīng)的改進蟻群算法等. 目前，已有一些文獻對狼群算法做了改進. 文獻[10-12]針對基本狼群算法的不足，分別提出了基于改進狼群搜索策略的狼群算法、基于領(lǐng)導(dǎo)者策略的狼群搜索算法和自適應(yīng)學(xué)習的狼群智能算法.

本文在WPA算法的基礎(chǔ)上，對狼群的移動步長和方向進行改進. 對游走、召喚、圍攻行為的移動步長提出了自適應(yīng)步長方法，使得每只狼的移動步長可根據(jù)狼群狀態(tài)動態(tài)變化，提高了搜索的精細程度，加快了收斂速度；通過改進游走行為的搜索方向，提高了搜索效率；通過全面覆蓋搜索范圍，對參加召喚行為的猛狼選取提出了新的策略. 綜合以上策略提出了一種基于自適應(yīng)和變游走方向的改進狼群算法(MACWPA).

1 基本狼群算法

基本狼群算法中，狼群按照職責分工，分為頭狼、探狼和猛狼. 頭狼為狼群首領(lǐng)，在每次迭代過程中提供基準信息；探狼負責搜尋食物，在游走行為中活動；猛狼負責向獵物方向奔襲，在奔襲行為中活動.假設(shè)在D維可行空間中初始化N只狼，頭狼的位置定義為Xlead=(xlead1,xlead2,…,xleadD)，目標函數(shù)值記為Ylead，其余狼位置定義為xi=(xi1,xi2,…,xiD),i=1,2,…,N-1，相應(yīng)目標函數(shù)值記為Yi.

1.1 頭狼產(chǎn)生規(guī)則

在迭代過程中，頭狼位置是變化的，具有最優(yōu)目標函數(shù)值的狼即為頭狼. 頭狼不執(zhí)行3種智能行為而直接進入下次迭代，直到被其他目標值更優(yōu)的狼替代.

1.2 游走行為

將解空間中除頭狼外最佳的S_num只狼視為探狼. 若探狼i當前位置目標函數(shù)值Yi大于Ylead，則Ylead=Yi；若Yi小于Ylead，則探狼向h個方向分別前進一步(游走步長為stepa)，并記錄每前進一步后的目標函數(shù)值后退回原位置，探狼i按照式(1)向第p(p=1,2,…,h)個方向前進

(1)

探狼i選擇的目標函數(shù)值最大且大于當前位置的方向前進一步，并更新之前狀態(tài)xi. 重復(fù)以上游走行為直到探狼的目標函數(shù)值Yi大于Ylead或游走次數(shù)T達到最大值Tmax.

1.3 召喚行為

頭狼召集周圍M_num只猛狼以奔襲步長stepb迅速向頭狼位置靠攏.則猛狼i根據(jù)式(2)更新當前位置

(2)

奔襲途中，若猛狼i感知到的目標函數(shù)值Yi大于Ylead，則Ylead=Yi，該猛狼轉(zhuǎn)化為頭狼并發(fā)起召喚行為；若Yi小于Ylead，則猛狼i繼續(xù)奔襲直到其與頭狼之間距離小于dnear:

(3)

式(3)中,ω表示距離判定因子.

1.4 圍攻行為

猛狼聯(lián)合探狼以攻擊步長stepc對獵物G=(G1,G2,…,GD)進行圍攻，以期將其捕獲.狼群的圍攻行為定義為

式(4)中λ為[-1,1]間均勻分布的隨機數(shù).

設(shè)待尋優(yōu)第d個變量的取值范圍為[mind,maxd]，3種智能行為中所涉及的游走步長stepa、奔襲步長stepb、攻擊步長stepc在第D維空間中存在以下關(guān)系：

式(5)中,S表示步長因子，即狼在解空間中搜尋最優(yōu)解的精細程度.

1.5 “強者生存”的狼群更新機制

除去目標函數(shù)值最差的R只狼，同時隨機產(chǎn)生R只狼.R取[n/(2×β),n/β]間的隨機整數(shù)，β為群體更新比例因子.

2 改進的自適應(yīng)和變游走方向狼群算法

2.1 自適應(yīng)法

吳虎勝等[5]提出的狼群算法中的移動步長分為3種，并按照式(5)定義. 但這種方式固化了步長，在算法初期會影響收斂速度，后期會降低搜索的精細程度，甚至可能錯過最優(yōu)值，僅獲取最優(yōu)值附近的較優(yōu)值. 考慮到狼群算法中獨有的特征： 頭狼在每一步中都可能被目標函數(shù)值更好的狼替代，因此，采用自適應(yīng)步長方法，狼i每一次移動的步長由該狼當前位置和當前頭狼位置決定，離頭狼位置越近的狼移動步長越小，以提高搜索的精細程度；離頭狼越遠的狼移動步長越大，以提高收斂速度，避免不必要的搜索.

本文采用自適應(yīng)步長：

step=rand×‖xi-Xlead‖2，

(6)

式(6)中rand表示[0,1]間的隨機數(shù). 自適應(yīng)步長以頭狼位置和狼當前位置為參考，當狼離頭狼距離遠時，以較大步長逼近頭狼；當離頭狼距離近時，以較小步長逼近頭狼，加快收斂速度.

2.1.1 自適應(yīng)游走行為

在游走行為中，按照游走次數(shù)的奇偶性，搜索方向在h和h+1兩者之間變動(詳見2.2).當游走次數(shù)為奇數(shù)次時，朝第p(p=1,2,…,h)個方向前進后，探狼i在第D維空間中所處的位置為

xid+sin(2π×p/h)×rand·norm(x(i,:)-Xlead)；

(7)

當游走次數(shù)為偶數(shù)次時，朝第p(p=1,2,…,h,h+1)個方向前進后，探狼i在第D維空間中所處的位置為

xid+sin(2π×p/(h+1))×rand×norm(x(i,:)-Xlead).(8)

在游走行為中，不必擔心某些狼因步長過長而錯過全局最優(yōu)解，游走行為中向h或h+1個方向試探的方法保證了搜索的全面覆蓋.

2.1.2 自適應(yīng)召喚行為

不同于基本W(wǎng)PA算法，在本文的改進算法中，參與召喚行為的猛狼不再只是頭狼附近的狼，而是在除頭狼外的全部狼群中隨機選取M_num只狼作為猛狼. 經(jīng)歷長時間的游走行為后，頭狼的位置發(fā)生多次更迭，如果只召喚頭狼附近的狼向頭狼逼近，會使算法陷入局部最優(yōu). 在除頭狼外的狼群中隨機選取猛狼，讓他們只朝著頭狼前進，使算法的搜索范圍更廣. 在奔襲過程中，當某只猛狼感知到其所在位置食物濃度更大時，會替代頭狼，重新選取猛狼，進行召喚，直到其所在位置的食物濃度小于頭狼位置的食物濃度. 同時，召喚行為也采取與游走行為相同的自適應(yīng)步長法(6)，則猛狼i根據(jù)式(9)更新當前位置：

xid=xid+step×(xleadd-xid)/|xleadd-xid|=

xid+rand×‖xi-xlead‖2×(xleadd-xid)/|xleadd-xid|，

d=1,2,…,D.

(9)

2.1.3 自適應(yīng)圍攻行為

猛狼聯(lián)合探狼對獵物進行緊密圍攻以期將其捕獲，移動步長采用自適應(yīng)步長法(6). 狼群圍攻行為由式(10)表示：

d=1,2,…,D.

(10)

2.2 變游走方向法

在基本W(wǎng)PA算法中，雖然文獻[5]提到每只探狼的獵物搜尋方式存在差異，h的取值是不同的，實際中可依據(jù)情況取[hmin,hmax]間的隨機整數(shù). 但是不論游走多少次，算法迭代多少次，對于探狼i來說，方向依然只有h個，而且在其試驗中，參數(shù)h固定設(shè)置為10，而不是文獻[5]所稱的h是隨機的. 從而導(dǎo)致搜索方向固定，搜索不精細.具體分析如下：

假如約定方向h為8個，一次移動后找到的最優(yōu)方向如圖1所示.

圖1 WPA的游走方向Fig.1 Scouting direction of WPA

下次尋找最優(yōu)方向時，每個方向都與該方向產(chǎn)生平行關(guān)系，并且之后都會沿著平行方向搜索，從而大大降低了搜索效率.

本文通過改進游走行為中h個方向的選取方法，根據(jù)游走次數(shù)T的奇偶性，搜索方向在h和h+1兩者間變動，提高了搜索的精細度.效果圖如圖2所示.

圖2 變游走方向的MACWPA算法Fig.2 Changed scouting direction of MACWPA

從圖2中可以看出，右邊的第T次游走和第T+1次游走選取的方向不再成平行關(guān)系.結(jié)合文獻[5]提出但未采用的每只探狼的搜索方向h在約定范圍內(nèi)隨機選擇的方法，豐富了搜索方向，進而擴大了搜索范圍.

綜上，根據(jù)最大游走次數(shù)交錯變換方向數(shù)，方法簡單、計算復(fù)雜度低，且不會對計算速度造成太大影響.

2.3 MACWPA算法描述

Step1數(shù)值初始化. 初始化狼群中狼位置Xi及其數(shù)目N，最大迭代次數(shù)Kmax，探狼比例因子α，最大游走次數(shù)Tmax，距離判定因子ω，更新比例因子β.

Step2選取目標函數(shù)值最好的狼為頭狼，位置記為Xlead，目標函數(shù)值記為Ylead，除頭狼外最佳的S_num只狼視為探狼，并按照公式(7)、(8)執(zhí)行游走行為，直到每只探狼游走次數(shù)達到最大游走次數(shù)Tmax，轉(zhuǎn)step3.

Step3從除頭狼外所有狼眾中隨機選取M_num只猛狼并按照公式(9)向獵物奔襲，若途中猛狼的目標函數(shù)值Yi>Ylead，則Ylead=Yi，替代頭狼并發(fā)起召喚行為；若Yi

Step4按照公式(10)對參與圍攻行為的狼的位置進行更新，執(zhí)行圍攻行為.

Step5按“勝者為王”的頭狼產(chǎn)生規(guī)則對頭狼位置進行更新；按照“強者生存”的狼群更新機制進行群體更新.

Step6判斷是否達到優(yōu)化精度要求或最大迭代次數(shù)Kmax，若達到則輸出頭狼位置，即所求問題的最優(yōu)解，否則轉(zhuǎn)step2.

3 仿真實驗

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

為了充分測試算法的性能和特點，并與文獻[3]的WPA算法進行對比，實驗選取文獻[3]中13個有代表性的測試函數(shù)，另外又添加了4個，共17個測試函數(shù)作為實驗對象，如表1所示. 表1中特征“U”表示單峰(unimodal)函數(shù)，“M”表示多峰(multimodal)函數(shù)，“S”表示可分(separable)函數(shù)，“N”表示不可分(non-separable)函數(shù). 單峰函數(shù)在定義域內(nèi)只有全局最優(yōu)值；多峰函數(shù)在定義域內(nèi)有多個布局極值，用來檢驗算法全局收斂的能力. 表1中17個函數(shù)的變量維數(shù)從低到高排列，可以較全面地測試算法的性能.

實驗用MACWPA算法、WPA算法以及經(jīng)典的PSO和FSA算法分別對表1中的17個復(fù)雜函數(shù)進行重復(fù)100次尋優(yōu)計算. 從平均值、最優(yōu)值、最差值、標準差、迭代次數(shù)、耗時等方面對算法進行評估.

實驗設(shè)置最大迭代次數(shù)Kmax=2 000，最大游走次數(shù)Tmax=20，初始狼群規(guī)模N=50，探狼比例因子α=4，更新比例因子β=6，距離判定因子ω=500.其他參數(shù)參考文獻[5]設(shè)置.實驗環(huán)境為Windows 8系統(tǒng)，2GB內(nèi)存，Pentium(R) Dual-Core CPU E5800，Matlab R2010a.

表2和表3給出了4種算法對17個復(fù)雜函數(shù)尋優(yōu)計算的統(tǒng)計結(jié)果. 當算法耗時超過2 000 s時，其結(jié)果記為“-”，不在考慮范圍.

以Bridge函數(shù)為例，設(shè)定最大迭代次數(shù)為2 000，改變距離判定因子ω后分別對Bridge函數(shù)進行50次尋優(yōu)計算，ω對算法性能的影響如表4所示.

以Eggcrate函數(shù)為例，設(shè)定最大迭代次數(shù)為2 000，分別測試變游走方向和固定游走方向的改進狼群算法，對Eggcrate函數(shù)進行50次尋優(yōu)計算，對比結(jié)果如表5所示. 改進狼群算法收斂精度為10-7，基本狼群算法收斂精度設(shè)置為10-3.

3.2 實驗分析

表2給出了4種算法對6個單峰函數(shù)的計算結(jié)果. 從平均值、最優(yōu)值、最差值和標準差來看，對于Easom、Maytas和Trid6三個單峰不可分函數(shù)，MACWPA和PSO算法的精度均較高，效果均明顯優(yōu)于WPA和FSA算法；對于Maytas、Sphere 2個單峰可分函數(shù)，維數(shù)由10維增加至30維，PSO算法的求解精度由10-37降低至10-1，而MACWPA算法的求解精度由10-7上升至10-8；對于30維的Rosenbrock 函數(shù)，MACWPA算法的求解精度較PSO算法高4個單位，可見MACWPA在處理高維函數(shù)時有一定優(yōu)勢.從消耗時間、達到收斂精度的迭代次數(shù)看，PSO算法耗時最短，MACWPA算法迭代次數(shù)最少，2種算法各有優(yōu)勢.FSA算法對全部測試函數(shù)的求解精度均較低，效果較差.對于Maytas函數(shù)、Trid6函數(shù)以及Sumsquare函數(shù)、Rosenbrock 函數(shù)，WPA算法分別在迭代800， 200，400次后速度明顯減慢，達到最大迭代次數(shù)耗費時間過長，短時間內(nèi)達不到收斂精度要求. 由文獻[5]知，WPA算法對于單峰、不可分的低維復(fù)雜函數(shù)的尋優(yōu)性能較差，改進后的MACWPA算法對這類函數(shù)的尋優(yōu)性能有很大提升，算法更加穩(wěn)定，表現(xiàn)出較高的尋優(yōu)精度和較好的算法執(zhí)行能力，改善了WPA算法對此類函數(shù)的尋優(yōu)性能.

表1 17個標準測試函數(shù)

表2 單峰函數(shù)優(yōu)化結(jié)果對比

表3 多峰函數(shù)優(yōu)化結(jié)果對比

表4 距離判定因子ω對MACWPA性能的影響

表5 變游走方向h對算法性能的影響

表3給出了4種算法對11個多峰函數(shù)的計算結(jié)果.對于二維多峰函數(shù)來說，PSO算法較其他幾種算法的求解精度高，而MACWPA算法也都保持了10-10的求解精度.對于Schaffer函數(shù)，MACWPA算法和PSO算法都會不同程度地陷入局部最優(yōu)，但PSO算法穩(wěn)定性更強，WPA和FSA算法收斂精度欠佳.對于Griewank、Rastrigin、Quadric、Ackley函數(shù)來說，當維數(shù)由30升至200時，MACWPA算法的求解精度最高，進一步說明MACWPA算法在處理高維函數(shù)時具有優(yōu)勢.

由表4知，距離判定因子的變化對MACWPA算法的尋優(yōu)效果影響不大，6種參考數(shù)據(jù)均保持相同水平，大大提升了算法的穩(wěn)定性和尋優(yōu)能力.自適應(yīng)步長方法一改WPA算法[5]因距離判定因子ω過大降低尋優(yōu)精細度、過小使迭代次數(shù)增加降低收斂速度的缺點，使算法可根據(jù)種群當前情況自主調(diào)節(jié)步長，增加了算法的尋優(yōu)精細度，加快了收斂速度.

由表5知，采用變游走方向可提高WPA和MACWPA算法的求解精度. 從耗時來看，當算法同時迭代2 000次時，所消耗的時間相差不多，亦無增加算法的復(fù)雜度；從收斂精度看，當同時達到收斂精度時，變游走方向法會大大加快收斂速度，所需的迭代次數(shù)更少，WPA算法尤其明顯，避免了不必要的游走行為.從平均結(jié)果和標準差來看，變游走方向會增強算法的魯棒性，使算法更加穩(wěn)定.

為了更直觀地說明MACWPA算法的優(yōu)越性，圖3給出了Easom、Sphere、Booth、Eggcrate及Six Hump Camel Back函數(shù)的收斂曲線圖.

圖3 5個函數(shù)的收斂曲線圖Fig.3 Convergence curves of five functions

從圖3可以看出，MACWPA算法在迭代初期，迭代結(jié)果較WPA算法更接近真實最優(yōu)值；MACWPA算法通過200次迭代即可逼近最優(yōu)值；其迭代過程無明顯的分期變化，而WPA算法則存在明顯的分期變化，在迭代中期，出現(xiàn)逼近真實的最優(yōu)解，在迭代的初期和末期，收斂速度較慢. 總之，MACWPA算法在求解精度和收斂速度上均優(yōu)于WPA算法.

4 結(jié) 論

在WPA算法基礎(chǔ)上，提出了自適應(yīng)步長和變游走方向的方法. 在3種智能行為中運用自適應(yīng)步長，加快了算法的收斂速度，減少了參數(shù)，降低了參數(shù)對算法的影響，增強了算法的魯棒性；變游走方向法擴大了算法的搜索范圍，避免了多余的游走行為，同時提高了算法的收斂速度和搜索精度. MACWPA算法既克服了WPA算法對單峰函數(shù)優(yōu)化能力差的缺點，又保持了其在處理高維函數(shù)上的優(yōu)勢.

參考文獻(References)：

[1] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agent[J].IEEETrans,onSystems,Man,andCybernetics, 1996, 26(1): 29-41.

[2] 李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式： 魚群算法[J].系統(tǒng)工程理論與實踐，2002,22(11): 32-38.

LI X L, SHAO Z J, QIAN J X. An optimizing method based on autonomous animals: Fish-swarm algorithm[J].SystemsEngineeringTheoryandPractice, 2002, 22(11): 32-38.

[3] KRISHNAND K N, GHOSE D. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions [J].SwarmIntelligence, 2009, 3(2): 87-124.

[4] LIU C, YAN X, LIU C, et al. The wolf colony algorithm and its application[J].ChineseJournalofElectronics, 2011, 20(2): 212-216.

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

WU H S, ZHANG F M, WU L S. New swarm intelligence algorithm： Wolf pack algorithm [J].SystemsEngineeringandElectronics, 2013, 35(11): 2430-2438.

[6] 陳斐.改進的人工魚群算法分析與研究[D].西安： 西安電子科技大學(xué)，2012.

CHEN F.AnalysisandResearchonImprovedArtificialFishSwarmAlgorithm[D]. Xi’an: Xidian University, 2012.

[7] 劉彥君，江銘炎.自適應(yīng)視野和步長的改進人工魚群算法[J].計算機工程與應(yīng)用，2009,45(25): 35-37.

LIU Y J, JIANG M Y. Improved artificial fish swarm algorithm based on adaptive visual and step length[J].ComputerEngineeringandApplications, 2009, 45(25): 35-37.

[8] 歐陽喆，周永權(quán).自適應(yīng)步長螢火蟲優(yōu)化算法[J].計算機應(yīng)用，2011,31(7): 1804-1807.

OUYANG Z, ZHOU Y Q. Self-adaptive step glowworm swarm optimization algorithm[J].JournalofComputerApplications, 2011, 31(7): 1804-1807.

[9] 李開榮，陳宏建，陳崚.一種動態(tài)自適應(yīng)蟻群算法[J].計算機工程與應(yīng)用，2004,40(29): 149-152.

LI K R, CHEN H J, CHEN L. A dynamic and adaptive ant algorithm[J].ComputerEngineeringandApplications, 2004, 40(29): 149-152.

[10] 李國亮，魏振華，徐蕾.基于改進搜索策略的狼群算法[J].計算機應(yīng)用，2015,35(6): 1633-1636,1687.

LI G L, WEI Z H, XU L. Wolf pack algorithm based on modified search strategy[J].JournalofComputerApplications, 2015, 35(6): 1633-1636, 1687.

[11] 周強，周永權(quán).一種基于領(lǐng)導(dǎo)者策略的狼群搜索算法[J].計算機應(yīng)用研究，2013,30(9): 2629-2632.

ZHOU Q, ZHOU Y Q. Wolf colony search algorithm based on leader strategy[J].ApplicationResearchofComputers, 2013, 30(9): 2629-2632.

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

XUE J J, WANG Y, LI H, et al. A smart wolf pack algorithm and its convergence analysis [J].ControlandDecision, 2016,31(12): 2131-2139.

[13] WU H, ZHANG F. A uncultivated wolf pack algorithm for high dimensional functions and its application in parameters optimization of PID controller[C]//IEEECongressonEvolutionaryComputation. Beijing: IEEE Press, 2014: 2430-2438.

[14] 吳虎勝.狼群算法及其應(yīng)用研究[D].西安： 空軍工程大學(xué)，2014.

WU H S.WolfPackAlgorithmandItsApplicationResearch[D]. Xi’an: Air Force Engineering University, 2014.

[15] GUO L T, LIU S Y.An improved binary wolf pack algorithm based on adaptive step length and improved update strategy for 0-1 Knapsack problems[C]//DataScience:ThirdInternationalConferenceofPioneeringComputerScientists,EngineersandEducators. Changsha: ICPCSEE, 2017: 442-452. DOI: 10.1007/978-981-10-6388-6-37.