基于自適應步長和萊維飛行策略的改進狼群算法

李彥蒼，徐培東

（河北工程大學 土木工程學院，河北 邯鄲 056038）

群居是一種常見的自然現(xiàn)象，在群居中，社會群體能夠適應自然選擇原則，在物種內(nèi)部競爭中生存下來。大雁向南遷移，魚成群結隊游蕩在水中搜索食物和蟻群在信息素濃度的幫助下選擇最短路徑，它們通過減少自身能量消耗增加集體利益，是長期自然選擇的結果[1-4]。這些集群行為表現(xiàn)為群體的自組織、自適應和團隊協(xié)作，能夠增強群體對環(huán)境的整體適應性。群智能算法是一種模擬自然生物進化或覓食行為的一種算法[5]。受動物群體現(xiàn)象啟發(fā)，人們開發(fā)了許多優(yōu)化計算方法解決復雜問題。常見的群智能算法主要有粒子群優(yōu)化算法[6]、蟻群優(yōu)化算法[7]、人工魚群算法[8]、人工蜂群算法[9]。蝴蝶算法是O’Neil 等[10]模仿蝴蝶覓食行為提出的自然啟發(fā)式優(yōu)化算法；果蠅算法是Pan 等[11]基于果蠅覓食行為提出的全局優(yōu)化方法；花粉算法是Yang 等[12]模擬自然開花植物自授粉和異花授粉生物學特性提出的隨機全局優(yōu)化算法；雞群算法是Meng 等[13]通過模擬雞的等級和行為提出的優(yōu)化算法。鳥類、魚類、螞蟻和蜜蜂等，它們通過不斷適應環(huán)境和相互合作，表現(xiàn)出強大的群體智能，給人類提供許多解決復雜問題的新思路，提高處理優(yōu)化問題的能力，有效推動計算智能的發(fā)展，但在計算精度方面仍需進一步研究。

狼群算法（wolf pack algorithm，WPA）是吳勝虎[14]于2013 年提出的一種新的群智能算法。該算法在進行優(yōu)化問題求解時，具有較好的尋優(yōu)性能，但算法也存在一些不足之處：收斂速度慢、收斂精度不高、魯棒性低等[15]。文獻[16]針對后期收斂速度慢的問題，引入交互式步行運動，提出具有領導策略的狼群搜索算法。文獻[17]為解決高維函數(shù)優(yōu)化問題，提出非人工狼群算法（uncultivated wolf pack algorithm，UWPA）。文獻[18]采用Tent 混沌序列來啟動個體位置，提出結合粒子群的狼群優(yōu)化算法。文獻[19]引入差分進化策略，提出基于差分進化的改進狼群算法（improved wolf pack algorithm，IWPA）。文獻[20]引入控制自適應參數(shù)a和混沌思想，提出自適應調(diào)整的混沌灰狼算法。文獻[21]提出改進的灰狼算法，通過添加可調(diào)參數(shù)，提高算法魯棒性，同時對幾種結構進行分析，獲得更好解決方案。改進后的算法在一定程度上提高了精確度和收斂精度。

研究在狼群算法的基礎上，對狼的游走行為提出了基于萊維飛行的搜索策略，對召喚、圍攻行為時的移動步長提出自適應性改進，使每匹狼每次移動的步長由該狼當前位置和當前頭狼位置決定。經(jīng)過測試，提出的自適應步長和萊維飛行策略的改進狼群算法（levy flight and adaptive step size strategy improved wolf pack algorithm，LWPA），收斂速度加快，收斂精度提高，增強了算法的尋優(yōu)性能和魯棒性。最后，使用LWPA 對桁架結構進行優(yōu)化設計，并與其他算法進行比較。

1 萊維飛行策略和自適應步長的狼群算法

1.1 智能行為和規(guī)則的描述

1.1.1 狼群的初始化

設狼群規(guī)模為N，搜索空間的維數(shù)為D，第i只人工狼的位置可表示為

式中：xmax和xmin分別是搜索空間的最大范圍和最小范圍；rand ∈(0,1)的一個隨機數(shù)。

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

在初始解空間中，目標函數(shù)值最優(yōu)的人工狼被選為頭狼，每次迭代后更新人工狼的位置。此時如有多個最優(yōu)人工狼情況，則隨機選一個成為頭狼。頭狼不執(zhí)行以下智能行為，直接進入迭代，直到被其他更強的人工狼替代。

1.1.3 基于萊維飛行的游走行為

除頭狼外選取最佳的S_sum 匹人工狼視為探狼，S_sum 隨機取之間的整數(shù)，α為探狼比例因子。在實際情況中發(fā)現(xiàn)，游走過程中探狼只會盲目跟隨頭狼并逼近頭狼位置的獵物氣息濃度，不會關心自己身邊是否有更優(yōu)獵物氣息濃度，在算法后期，導致種群喪失多樣性，易陷入局部收斂，出現(xiàn)早熟收斂現(xiàn)象。針對這種缺陷，利用萊維飛行對群體中的探狼進行全局搜索。萊維飛行屬于隨機游動，是一種很好的搜索策略，能擴大搜索范圍[22]。新一代的探狼i的計算公式如下

式中:xid(t)表示探狼i在t次迭代第d維的位置；⊕為點對點乘法；c為探狼i位置的隨機數(shù)，由式（4）決定，Levy(δ)代表隨機搜索路徑，由式（5）決定。

式中：δ的取值范圍一般為1 ＜δ＜3，δ取1.5，Xbest表示歷史最優(yōu)探狼位置，u和v服從式（6）所示的正態(tài)分布

σu和σv取值為

此時，探狼感知的獵物氣息濃度函數(shù)值為Yip，選擇最大的獵物氣息濃度函數(shù)值，若大于當前函數(shù)值Yi，則向Yip的方向前進一步，同時更新探狼狀態(tài)，重復以上游走行為，直到某匹探狼i的函數(shù)值Yi＞Ylead或游走次數(shù)達到最大游走次數(shù)T1max。

1.1.4 奔襲行為

在基本的狼群算法中，狼群位置變動是由步長step 決定的，對于每一個固定的D維空間，相應的[dmin,dmax]是固定的，因而每一次迭代對應的步長step 是固定的。如果step 過大，會影響算法優(yōu)化的準確度；如果step 過小，影響算法的收斂速度，當達到最大迭代次數(shù)時，最優(yōu)解還未被找到。借鑒文獻[23]，狼i每一次移動的步長由該狼當前位置和當前頭狼位置決定，因此在奔襲和圍攻行為時采用自適應步長

式（8）中rand 表示[0,1］間的隨機數(shù)，當狼離頭狼距離遠時，以較大步長逼近頭狼，加快收斂速度，避免不必要的搜索；當離頭狼距離近時，以較小步長逼近頭狼，提高搜索精細程度。

與以往狼群算法不同，隨機選取除頭狼外的全部狼群中M＿num 只猛狼參與召喚，而不僅是頭狼附近的人工狼。在猛狼奔襲過程中，當某只猛狼感知到其所在位置獵物氣息濃度更高時，則替代頭狼，重新選取猛狼，進行召喚，直到其所在位置的獵物氣息濃度低于頭狼位置氣息濃度。同時，召喚行為的步長取式（8），猛狼根據(jù)式（9）更新當前位置

式中：x*id表示更新后猛狼的位置；xid為當前猛狼的位置；xleadd為頭狼的位置。

1.1.5 圍攻行為

同時，猛狼聯(lián)合探狼對獵物進行圍捕。移動步長采用式（8），狼群圍攻行為由式（10）表示

式中：Gd為獵物在D維空間的位置，λ為區(qū)間[-1,1］均勻分布的隨機數(shù)。

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

獵物的分配遵循“由強到弱”的原則，即在算法中去除目標函數(shù)值最差的R匹人工狼,同時隨機產(chǎn)生R匹人工狼，在實際捕獵過程中，每次捕獵的數(shù)量都是隨機的，這也導致不同數(shù)量的弱狼被淘汰。基于此，β取[n(2 ×β),n β]之間的隨機整數(shù)，β為更新比例因子。

1.2 改進狼群算法描述

Step1 初始化狼群中人工狼的數(shù)目N和其所在位置Xi，最大迭代次數(shù)Kmax，探狼比例因子α，更新比例因子β，最大游走次數(shù)T1max，最大奔襲次數(shù)T2max。

Step2 根據(jù)頭狼產(chǎn)生規(guī)則確定頭狼。

Step3 探狼按照萊維飛行策略公式（3）～（7）執(zhí)行游走行為，直到某匹探狼i的函數(shù)值Yi＞Ylead或游走次數(shù)達到最大游走次數(shù)T1max，轉Step4。

Step4 猛狼執(zhí)行奔襲行為，并按照公式（9）向獵物奔襲。在奔襲過程中，若猛狼感知的獵物氣息濃度的函數(shù)值Yi＞Ylead，則令Yi=Ylead，該猛狼轉化為頭狼并發(fā)起召喚行為；若Yi＜Ylead，則繼續(xù)奔襲直到某匹猛狼的函數(shù)值小于頭狼函數(shù)值或奔襲達到最大奔襲次數(shù)T2max，轉Step5。

Step5 按照公式(10)，更新參與圍攻的人工狼位置，進行圍攻。

Step6 執(zhí)行狼群的更新機制。

Step7 判斷算法是否滿足優(yōu)化精度要求或最大迭代次數(shù)Kmax，若滿足要求，輸出頭狼位置，即所求問題的最優(yōu)解，否則轉Step2。

圖1 LWPA 算法的基本流程圖Fig. 1 LWPA algorithm iteration diagram

2 實驗仿真與分析

2.1 基本測試函數(shù)與參數(shù)設置

表1 中的“U”表示函數(shù)為單模態(tài)函數(shù)，“M”為多模態(tài)函數(shù)，“S”為可分離函數(shù)，“N”為不可分離函數(shù)。多模態(tài)函數(shù)比單模態(tài)函數(shù)復雜，一般算法難以找到具有多個局部極值的全局最優(yōu)值，容易陷入局部極值或局部極值之間的振蕩[24]。因此，多模態(tài)常被用來測試算法的全局搜索性和避免早熟收斂能力[25-26]。由于不可分函數(shù)變量之間的關系較復雜，很難找到不可分函數(shù)的全局最優(yōu)值[27-28]。WPA、UWPA 以及IWPA 算法所涉及到的參數(shù)分別參考文獻[14-19］進行設置。N取50，Kmax取1 000，β取4，α取4，T1max（T2max）取10。

表1 用于測試算法性能的15 個函數(shù)Table 1 15 functions for testing algorithm performance

2.2 算法對比驗證

為充分計算算法的性能，使用LWPA、UWPA、WPA 以及IWPA 分別對15 個復雜函數(shù)進行了100 次連續(xù)優(yōu)化計算[29]。基于表2 的6 種指標對該算法進行評估。當不同的計算結果與最優(yōu)值之間的誤差超過e-3，被認為是一種失敗。結果見表2。

表2 4 種算法在15 個測試函數(shù)中的結果比較Table 2 Comparison of results of four algorithms in 15 test functions

2.3 LWPA 主要參數(shù)分析

LWPA 雖然具有一定優(yōu)越性，但所涉及的參數(shù)也眾多，主要參數(shù)對算法性能的影響也不盡相同。T1max/T2max分別是狼群在游走/奔襲過程中的最大次數(shù)，β是狼群的更新比例系數(shù)。根據(jù)15 個函數(shù)的特性將其分成7 大類，分別改變Tmax和β的大小對這7 種函數(shù)進行50 次尋優(yōu)計算，Tmax和β對算法性能的影響如表3、4 所示。

表3 Tmax 對算法的影響Table 3 Effect of Tmaxon the algorithm

2.4 LWPA 收斂性分析

Markov 鏈是一種無后效性的隨機過程，常被應用于分析收斂性問題。由于LWPA 是基于游走、召喚和圍攻3 種智能行為的不斷重復，每種行為都與當前的群體狀態(tài)有關，而與之前無關，因此LWPA 的種群序列為Markov 鏈。設Qk={X1,X2,…,XN}為LWPA 的第k代種群，其中N為人工狼總數(shù)，Xi為第i匹人工狼的狀態(tài)。

定理1 文獻[30]已經(jīng)證明若一個進化算法滿足：1）對可行解空間中任意2 點x1和x2，x2是x1由算法中的各種算子產(chǎn)生且是可達的；2）若種群序列Q1,Q2,…,QN是單調(diào)的，則此進化算法是以概率1 收斂于問題的全局最優(yōu)解。

定理2 LWPA 算法以概率1 收斂于問題的全局最優(yōu)解。

證明：由文獻[14]的推理可知LWPA 種群序列的Markov 鏈也是遍歷鏈，且LWPA 優(yōu)化序列是一個有限齊次Markov 鏈，每次迭代狼群個體位置狀態(tài)只有遇到更優(yōu)解時才會更新。因此，LWPA 產(chǎn)生的子代Qk+1中的任意解都不差于Qk中的任意解。由此可知種群序列Q1,Q2,…,QN是單調(diào)的，于是由定理1 得證，LWPA 以概率1 收斂于問題的全局最優(yōu)解。

2.5 結果分析

由表2 各種算法的對比結果可知:

1）對于單峰、低維的不可分函數(shù)Eason、Matyas, LWPA 與UWPA 都尋優(yōu)成功且具有較好性能，接近于最優(yōu)值，就耗時而言，UWPA 的消耗時間是LWPA 的2 倍，IWPA 和WPA 的精度較差。

2）對于多峰、低維的可分函數(shù)Booth、Bohachevs1、Eggcrate，LWPA 的收斂精度明顯高于其他3 種算法，達到1e-6 以上，耗時方面，LWPA 和UWPA 的耗時最短，IWPA 次之，WPA 耗時最長；

3）對于多峰、低維的不可分函數(shù)Schaffer、Six Hump Camel Back、Bohachevs3、Bridge，WPA 與IWPA 由于陷入局部最優(yōu)而導致尋優(yōu)失敗，LWPA 與UWPA 尋優(yōu)成功且LWPA 具有更好的尋優(yōu)性能，同時，LWPA 的耗時最短，明顯少于其他3 種算法；

4）對于單峰、高維的不可分函數(shù)Trid6，LWPA 與UWPA 尋優(yōu)成功且性能較好。耗時方面，除WPA 耗時較長外，其他3 種算法耗時相當；

5）對于單峰、高維的可分函數(shù)Sumsquares、Sphere，LWPA 與UWPA 尋優(yōu)成功，LWPA 的尋優(yōu)精度明顯優(yōu)于其他3 種算法，達到1e-7 以上，但在耗時方面，UWPA 略優(yōu)于LWPA；

6）對于多峰、高維的可分函數(shù)Rastrigin、Quadric，隨著維數(shù)的遞增，只有LWPA 尋優(yōu)成功且精度較高，LWPA 與UWPA 的耗時都較短；

7）對于多峰、高維的不可分函數(shù)Ackley，只有LWPA 尋優(yōu)成功，耗時也最短。

就時間復雜度而言，由于探狼在游走過程中，探狼采取萊維飛行的隨機搜索策略，擴大搜索范圍，增加了運行時間。但在對召喚、圍攻行為的移動步長進行自適應性改進，當狼群離頭狼較遠時，以較大步長逼近頭狼；當離頭狼距離較近時，以較小步長逼近頭狼，實現(xiàn)自適應性的靈活調(diào)節(jié)，使算法更具靈活性，極大縮短運行時間，搜索效率進一步提高。

綜上可知，無論是從精度方面還是耗時方面，基于自適應步長和萊維飛行策略的改進狼群算法在處理函數(shù)問題時比其他改進的狼群算法更精確、效果更好，尤其是對多峰、高維的復雜函數(shù)，效果更佳。UWPA 的效果次之，IWPA 和WPA 較差。由表3 可知，隨著Tmax增大，標準差呈現(xiàn)出先減小后增大的趨勢。若Tmax值太小，會導致狼群搜索效率降低，耗時較長，找不到最優(yōu)解；若Tmax值太大，以至于忽略最優(yōu)解，達不到所需精度。綜上，算法中Tmax取10。由表4 可知，隨著β增大，標準差呈現(xiàn)先減小后增大趨勢。若β太小，狼群更新數(shù)量太多，狼群難以聚集，導致算法優(yōu)化效果降低；但若β太大時，狼群更新的數(shù)量太少，導致狼群多樣性的急劇下降，并且容易陷入局部最優(yōu)。綜上，算法中β取4。

表4 β 對算法的影響Table 4 Effect of β on the algorithm

為進一步直觀說明LWPA 的優(yōu)越性，圖2 給出了LWPA 與 UWPA、IWPA、WPA 在各測試函數(shù)中的收斂曲線圖。從圖中看出，對于單峰、低維的不可分復雜函數(shù)，當算法迭代到300 次時，LWPA 已經(jīng)找到最優(yōu)值且趨于穩(wěn)定，而其他3 種算法迭代到400 次時雖也趨于穩(wěn)定，但精度較差；對于簡單的低維函數(shù)，UWPA 在前期搜索中效果最好，但隨著后期搜索效率不高，導致耗時長且易陷入局部最優(yōu)；對于復雜函數(shù)，LWPA 的收斂精度明顯高于其他3 種算法，當維數(shù)增加到30 維、60 維、120 維，甚至200 維時，UWPA、IWPA、WPA 3 種算法尋優(yōu)效果明顯較差，出現(xiàn)前期搜索時間較長，后期陷入局部最優(yōu)的情況。因此，針對算法在后期容易陷入局部最優(yōu)問題，LWPA 已經(jīng)有很好改進。比較可知，與其他3 種改進狼群算法相比，在收斂速度還是收斂精度方面，LWPA 的優(yōu)化性能都有明顯提升，說明改進方向的正確性。

圖2 15 個測試函數(shù)的收斂曲線圖Fig. 2 Convergence curves of 15 test functions

3 LWPA 對桁架結構優(yōu)化實例

3.1 桁架結構優(yōu)化模型

1）優(yōu)化模型

以截面積為設計變量的桁架優(yōu)化模型問題可描述為

式中：gi(x)為約束函數(shù)；p為約束個數(shù)。

2）目標函數(shù)

式中：W(A)為結構的重量；Ai為第i根桿件的截面積；Li為第i根桿件的長度；γ為材料密度；n為設計變量個數(shù)。

3）約束條件

各桿必須滿足對強度、剛度、穩(wěn)定性和截面尺寸要求，約束條件如下

式中：σi為第i桿的軸向正應力；[σ]為材料的許用應力；μj為節(jié)點j的位移；μmax為節(jié)點j的許用位移；Amin、Amax分別為桿件截面的上限、下限。

3.2 算例1

10 桿平面桁架結構見圖3，此桁架有6 個節(jié)點，10 個設計變量，如表5 所示。優(yōu)化目標是獲得最小的結構總重量。E=68 950 Mpa，ρ=2 768 kg/m3，全部桿件的許用應力為±172.4 MPa，各桿件截面積的下限為0.645 cm2，上限為258 cm2，工況只有一個，在5、6 號節(jié)點作用向下載荷P=4.445 KN 的集中力，可動節(jié)點向下的位移約束均5.08 cm，圖中l(wèi)=914.4 cm。

圖3 10 桿平面桁架結構圖Fig. 3 Plane truss structure diagram of 10-bar

3.3 算例2

25 桿空間桁架結構如圖4 所示，該結構有10 個節(jié)點，25 根桿件。應力約束為[-275.8,275.8］Mpa，材料的密度ρ=2 768 kg/m3，彈性模量E=68 950 Mpa，1、2 節(jié)點的最大豎向位移不能超過dmax=0.889 cm，L=63.5 cm。根據(jù)對稱性，將25 根桿件分成8 組，即設計變量為8 個，如表6-7 所示。

表6 25 桿空間桁架工況荷載Table 6 Load cases of the 25-bar spatial truss structure

圖4 25 桿空間桁架結構圖Fig. 4 The 25-bar spatial truss structure

3.4 算法迭代曲線對比

算例1 為無約束優(yōu)化問題，算例2 為含約束優(yōu)化問題，通過以上2 種經(jīng)典算例模型進行優(yōu)化對比，由表5和表7 的優(yōu)化結果可知改進后算法LWPA 在優(yōu)化程度和精度方面表現(xiàn)更加良好，達到減輕重量目的；通過圖5 的4 種算法迭代曲線，在初始條件相同情況下， LWPA 算法相較于其它算法在迭代初期的迭代速度更快、全局搜索能力更強，以較快迭代速度尋找質(zhì)量較好的全局最優(yōu)解，在尋優(yōu)迭代過程中算法表現(xiàn)穩(wěn)定，驗證了LWPA 有較高收斂速度和精度，具有其獨特優(yōu)越性。

表7 25 桿空間桁架結構優(yōu)化結果對比Table 7 Comparison of optimal results for the 25-bar spatial truss structure

圖5 2 個算例的尋優(yōu)迭代曲線示意圖Fig. 5 The optimization iteration curve of two examples

4 結 論

筆者在基本狼群算法上引入自適應性步長和萊維飛行搜索策略，避免探狼游走過于盲目，使算法能夠在搜索后期擴大搜索范圍，避免陷入局部收斂，在提高收斂精度的同時能較好提高收斂速度，達到改進目的。通過仿真實驗和方法對比，驗證了改進狼群算法的可行性、有效性，并將其運用于桁架結構的優(yōu)化中，優(yōu)化結果表明改進后的狼群算法達到了預期重量最輕的目的。該方法可用于求解組合優(yōu)化問題。雖然對算法的改進有一定成效，但實際工程中的問題復雜多變，今后的研究重點是如何將改進的狼群算法解決更加復雜的工程優(yōu)化問題。