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

李彥蒼，徐培東

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

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

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

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

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

1.1 智能行為和規則的描述

1.1.1 狼群的初始化

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

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

1.1.2 頭狼產生規則

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

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

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

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

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

σu和σv取值為

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

1.1.4 奔襲行為

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

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

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

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

1.1.5 圍攻行為

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

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

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

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

1.2 改進狼群算法描述

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

Step2 根據頭狼產生規則確定頭狼。

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

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

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

Step6 執行狼群的更新機制。

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

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

2 實驗仿真與分析

2.1 基本測試函數與參數設置

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

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

2.2 算法對比驗證

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

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

2.3 LWPA 主要參數分析

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

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

2.4 LWPA 收斂性分析

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

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

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

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

2.5 結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3 LWPA 對桁架結構優化實例

3.1 桁架結構優化模型

1）優化模型

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

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

2）目標函數

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

3）約束條件

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

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

3.2 算例1

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

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

3.3 算例2

25 桿空間桁架結構如圖4 所示，該結構有10 個節點，25 根桿件。應力約束為[-275.8,275.8］Mpa，材料的密度ρ=2 768 kg/m3，彈性模量E=68 950 Mpa，1、2 節點的最大豎向位移不能超過dmax=0.889 cm，L=63.5 cm。根據對稱性，將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 為無約束優化問題，算例2 為含約束優化問題，通過以上2 種經典算例模型進行優化對比，由表5和表7 的優化結果可知改進后算法LWPA 在優化程度和精度方面表現更加良好，達到減輕重量目的；通過圖5 的4 種算法迭代曲線，在初始條件相同情況下， LWPA 算法相較于其它算法在迭代初期的迭代速度更快、全局搜索能力更強，以較快迭代速度尋找質量較好的全局最優解，在尋優迭代過程中算法表現穩定，驗證了LWPA 有較高收斂速度和精度，具有其獨特優越性。

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

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

4 結 論

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