基于Levy飛行策略的自適應(yīng)改進(jìn)鳥群算法

楊文榮，馬曉燕，邊鑫磊

（河北工業(yè)大學(xué) 省部共建電工裝備可靠性與智能化國家重點(diǎn)實(shí)驗(yàn)室，天津 300130）

基于Levy飛行策略的自適應(yīng)改進(jìn)鳥群算法

楊文榮，馬曉燕，邊鑫磊

（河北工業(yè)大學(xué) 省部共建電工裝備可靠性與智能化國家重點(diǎn)實(shí)驗(yàn)室，天津 300130）

針對(duì)新型生物啟發(fā)式群智能算法—鳥群算法（BSA）因進(jìn)化初期種群多樣性不足，以及認(rèn)知和群體行為調(diào)節(jié)參數(shù)的改變而導(dǎo)致在優(yōu)化小部分多極值函數(shù)時(shí)種群收斂精度變差、收斂迭代次數(shù)偏大甚至出現(xiàn)早熟收斂、陷入局部最優(yōu)的問題，提出了Levy自適應(yīng)改進(jìn)鳥群算法（LSABSA）.該算法采用Levy飛行策略的隨機(jī)游走模式來增加種群多樣性和跳出局部最優(yōu)值，并通過（0，1）隨機(jī)均勻分布自適應(yīng)改進(jìn)慣性權(quán)重以及線性調(diào)整認(rèn)知和社會(huì)系數(shù)來平衡BSA算法的全局和局部搜索能力，進(jìn)而提高求解精度.最后采用10個(gè)典型測試函數(shù)對(duì)LSABSA算法以及粒子群算法（PSO）、改進(jìn)粒子群算法（GPSO）和鳥群算法（BSA）進(jìn)行仿真實(shí)驗(yàn)和分析對(duì)比，表明了LSABSA算法的收斂速度、精確度和穩(wěn)定性均優(yōu)于其他算法.

鳥群算法；Levy飛行；（0，1）隨機(jī)均勻分布；線性調(diào)整；仿真測試

0 引言

因利用傳統(tǒng)優(yōu)化算法難以快速和高效地解決現(xiàn)實(shí)生活中的例如非凸的和不可微的復(fù)雜優(yōu)化問題，受自然界生物進(jìn)化和選擇等抽象行為的影響，元啟發(fā)式群智能優(yōu)化算法日益興起，如仿效生物界“物競天擇，適者生存”法則尋優(yōu)的微分進(jìn)化算法（DE）[1]、源于對(duì)鳥類捕食行為研究的粒子群算法（PSO）[2]，模擬魚類覓食、聚群、追尾和隨機(jī)等行為尋優(yōu)的人工魚群算法（AFSA）[3]，以及果蠅優(yōu)化算法（FOA）[4]、雞群算法[5-6]等，上述智能算法雖能夠求解一些復(fù)雜優(yōu)化問題，但在解決超高維多極值優(yōu)化模型時(shí)，易早熟收斂和陷入局部最優(yōu)解，因此有必要研究更有效的通用智能算法.

鳥群算法（Bird Swarm Algorithm，BSA）是Meng Xian-Bing等人在2015年提出的一種新型生物啟發(fā)式全局優(yōu)化算法，來源于對(duì)鳥群覓食、警惕和飛行行為的模仿以及對(duì)鳥群覓食過程中共享信息的研究，具備調(diào)節(jié)參數(shù)少、收斂精度高和魯棒性能好等特點(diǎn)，已驗(yàn)證該算法在優(yōu)化函數(shù)方面優(yōu)于PSO和DE算法[7].BSA算法現(xiàn)已應(yīng)用在微電網(wǎng)系統(tǒng)的微電源優(yōu)化調(diào)度[8]、梯級(jí)水庫群優(yōu)化調(diào)度[9]和優(yōu)化投影尋蹤回歸的模型參數(shù)[10]等方面，且將會(huì)應(yīng)用到更廣闊的領(lǐng)域中.BSA算法在種群進(jìn)化初期多樣性不足，在解決小部分多極值函數(shù)（如Ackley函數(shù)）優(yōu)化問題時(shí)會(huì)出現(xiàn)局部收斂的情況，同時(shí)BSA算法的認(rèn)知和社會(huì)行為調(diào)節(jié)參數(shù)的變化易導(dǎo)致種群收斂精度變差和收斂迭代次數(shù)偏大，因此需要對(duì)BSA算法進(jìn)行改進(jìn).

本文借助Levy飛行行為的短距離頻繁搜索和長距離少數(shù)搜索這種隨機(jī)游走的特性初始化鳥群空間位置，以此擴(kuò)大搜索范圍、豐富種群多樣性、跳出局部最優(yōu)解，同時(shí)采用（0，1）隨機(jī)均勻分布自適應(yīng)對(duì)慣性權(quán)重取值以及線性調(diào)整學(xué)習(xí)系數(shù)，來提高收斂速度和搜索精度，即基于Levy飛行策略的自適應(yīng)改進(jìn)鳥群算法（Levy Self-adaption BSA，LSABSA）.最后，利用10個(gè)經(jīng)典測試函數(shù)對(duì)LSABSA與PSO、GPSO和BSA算法進(jìn)行仿真并進(jìn)行對(duì)比分析，所得數(shù)據(jù)結(jié)果和收斂特性曲線驗(yàn)證了本文LSABSA算法的有效性.

1 鳥群算法仿生學(xué)基本原理

BSA算法是根據(jù)鳥類覓食、警惕和飛行行為衍生出的生物啟發(fā)式算法，這些社會(huì)行為和活動(dòng)的本質(zhì)是群體智能，鳥群從社會(huì)活動(dòng)中獲取食物的最佳位置即對(duì)應(yīng)于目標(biāo)函數(shù)中尋找最優(yōu)解.鳥類的行為簡化規(guī)則如下.

規(guī)則1：每只鳥隨機(jī)決定在警惕和覓食行為之間轉(zhuǎn)換身份.

規(guī)則2：當(dāng)選擇覓食時(shí)，鳥類及時(shí)記錄和更新該個(gè)體和種群先前最好的覓食位置，并以信息的方式共享于整個(gè)種群，以此來更好的尋找食物.

規(guī)則3：當(dāng)保持警惕狀態(tài)時(shí)，每只鳥都試圖向種群的中心位置飛去，此行為受到群體間競爭的干擾，高儲(chǔ)備量的鳥類更容易飛到種群的中心位置.

規(guī)則4：鳥類會(huì)定期飛到另一個(gè)區(qū)域，當(dāng)?shù)竭_(dá)終點(diǎn)時(shí)，鳥類將會(huì)在生產(chǎn)者和乞食者之間轉(zhuǎn)換角色，食物儲(chǔ)存量多的為生產(chǎn)者，反之為乞食者.其他鳥類則隨機(jī)選擇成為生產(chǎn)者或乞食者.

規(guī)則5：生產(chǎn)者積極尋找食物，乞食者則隨機(jī)跟隨生產(chǎn)者尋找食物.

1） 覓食行為

規(guī)則1為隨機(jī)決策，若rand（0，1）＜P（p∈（0，1）），鳥類選擇覓食，否則保持警惕.

每只鳥由自身和群體的經(jīng)驗(yàn)來尋找食物，規(guī)則2用數(shù)學(xué)公式表示如下

式中：j∈ [1，…，D]，rand（0，1）代表（0，1） 之間的獨(dú)立均勻分布數(shù)，C和S（C、S＞0） 分別稱作認(rèn)知系數(shù)和社會(huì)系數(shù).Pi，j是第i只鳥的先前最優(yōu)位置，gj代表種群的先前最優(yōu)位置.

2） 警惕行為

根據(jù)規(guī)則3，鳥類在保持警惕行為時(shí)會(huì)試圖飛向種群的中心位置，此時(shí)鳥群之間會(huì)發(fā)生競爭關(guān)系而不會(huì)直接飛向種群的中心，這些行為用如下公式表示

式中：k（k≠i）是 [1，N]之間的隨機(jī)正整數(shù)，a1、a2∈ [0，2]，pFiti代表第i只鳥的最佳適應(yīng)度值，sumFit代表種群最佳適應(yīng)度值之和，ε是用來避免零分割的計(jì)算機(jī)中很小的常數(shù)，meanj代表整個(gè)種群中第j維的平均位置.

3） 飛行行為

因捕食者的威脅、覓食或其他原因，鳥類將會(huì)飛向另一個(gè)區(qū)域重新覓食.一些鳥作為生產(chǎn)者來尋找食物，另一些則根據(jù)這些生產(chǎn)者找到的食物信息來尋找食物，規(guī)則4可以區(qū)分出鳥類生產(chǎn)者和乞食者，用數(shù)學(xué)公式表示如下

式中：randn（0，1）代表服從均值為0，標(biāo)準(zhǔn)差為1的Gaussian中的一個(gè)隨機(jī)數(shù)，k∈ [1，2，3，…，N]，k≠i，F(xiàn)L（FL∈[0，1]）表示乞食者會(huì)跟隨生產(chǎn)者尋找食物的概率.FQ（FQ>0）為每只鳥飛往另一區(qū)域的時(shí)間間隔.

2 基于Levy飛行策略的自適應(yīng)改進(jìn)鳥群算法

2.1 基于Levy飛行行為的改進(jìn)策略

“Levy飛行策略”是生物在未知環(huán)境中尋找食物的理想方法，在500次Levy飛行中隨機(jī)步長分布圖如圖1所示，利用Levy飛行中頻繁的短距離搜索可在當(dāng)前最優(yōu)解周圍仔細(xì)搜尋以提高局部搜索能力，利用偶爾長距離的跳躍式搜索可擴(kuò)增搜索范圍增強(qiáng)全局搜索，防止陷入局部最優(yōu)解[11].Levy飛行策略已成功應(yīng)用于布谷鳥算法[12]、蝙蝠算法[11]、FOA算法[13]、PSO算法[14]等仿生學(xué)智能算法的改進(jìn)中，并取得了良好的優(yōu)化效果.鑒于以上Levy飛行策略的優(yōu)點(diǎn)和實(shí)例驗(yàn)證，將其應(yīng)用于BSA算法中，利用上述隨機(jī)游走模式初始化鳥群空間的位置，以此擴(kuò)大搜索范圍，增加種群的多樣性，跳出局部最優(yōu)值，較好的平衡BSA算法的全局和局部搜索能力.

采用Mantegna算法得出的Levy飛行路徑表達(dá)式如下

式中：r1（1，d）、r2（1，d）為[0，1]間的服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)；Levy（λ）為隨機(jī)步長；λ為冪次數(shù)；此處β=1.5.

初始化鳥群的空間位置公式如下

式中：xti為第i只鳥在t時(shí)刻的空間位置；ub、lb分別為每只鳥的搜索范圍限值；d為搜索維度；⊕代表矢量運(yùn)算；Levy（λ）為步長服從Levy分布的隨機(jī)搜索向量.

圖1 Levy飛行隨機(jī)步長分布圖Fig.1 Levy flight random step size distribution

2.2 （0，1）隨機(jī)均勻分布自適應(yīng)改進(jìn)慣性權(quán)重

BSA算法中鳥類覓食行為公式（1）類似于PSO算法中粒子的速度更新公式，故慣性權(quán)重w也是BSA算法的重要改進(jìn)參數(shù)，通過設(shè)置w可以改變上一時(shí)刻覓食位置對(duì)當(dāng)前時(shí)刻位置的影響.若利用傳統(tǒng)的線性微分遞減策略[15]，當(dāng)在鳥群搜索前期找到最優(yōu)值，則需要很大的w來快速收斂于此，此時(shí)遞減的w便降低了收斂速度，若在搜索后期才找到最優(yōu)值，此時(shí)w和鳥類飛行速度均很小，BSA算法易陷入局部最優(yōu)值.

為了解決上述問題，本文借鑒復(fù)雜適應(yīng)系統(tǒng)理論（CAS）中的自適應(yīng)性和個(gè)體與種群的協(xié)同進(jìn)化作用，采用（0，1）隨機(jī)均勻分布策略[16]替換線性微分遞減策略，從而w可以在迭代初期和后期均可得到較大的值，以此平衡BSA算法的全局與局部搜索能力，提高全局搜索效果.偽代碼如下

for i=1：M；%M為最大迭代次數(shù)

if個(gè)體最優(yōu)值==全局最優(yōu)值；

w=0.4+0.5*rand（）；

else

w=0+0.9*rand（）；

end

end

2.3 線性調(diào)整學(xué)習(xí)系數(shù)

BSA算法中C和S分別代表認(rèn)知和社會(huì)系數(shù)，類似于PSO算法中的自身和社會(huì)學(xué)習(xí)因子，通過自適應(yīng)調(diào)整自身認(rèn)知經(jīng)驗(yàn)和社會(huì)經(jīng)驗(yàn)，使鳥群搜索覓食前期C取較大值S取較小值，增加認(rèn)知經(jīng)驗(yàn)的比重，增強(qiáng)鳥類的全局搜索能力，搜尋覓食后期C取較小值，S取較大值，增加搜尋食物的社會(huì)經(jīng)驗(yàn)比重，使得局部搜索能力增強(qiáng)，線性調(diào)整的學(xué)習(xí)系數(shù)更新公式為

式中：Ce=Ss=0.5，Cs=Se=2.5.

改進(jìn)后的覓食公式為

綜上，本文利用Levy飛行行為初始化鳥群所在的空間位置，采用（0，1）隨機(jī)均勻分布自適應(yīng)改變慣性權(quán)重，同時(shí)采用線性調(diào)整策略改進(jìn)認(rèn)知和社會(huì)系數(shù)，稱這種算法為基于Levy飛行策略的自適應(yīng)改進(jìn)鳥群算法（LSABSA）.

3 實(shí)驗(yàn)仿真與分析

為驗(yàn)證LSABSA算法的改進(jìn)效果，本文以10個(gè)典型Benchmark函數(shù)為例，采用MATLAB R2014a編寫了相關(guān)程序，并對(duì)LSABSA算法與PSO、GPSO和BSA算法的仿真實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比驗(yàn)證.

3.1 基本測試函數(shù)與實(shí)驗(yàn)參數(shù)的設(shè)置

本文測試函數(shù)如表1所示，Sphere、Quadric、Rosenbrock為單模態(tài)函數(shù)，Rastrigin、Schaffers、Ackley等剩余函數(shù)為包含局部極值的多模態(tài)函數(shù).具體實(shí)驗(yàn)參數(shù)設(shè)置如下

1） PSO算法

2） GPSO算法

其中：c1e=c2s=0.5，c1s=c2e=2.5，wmax=0.9，wmix=0.4，m為當(dāng)前迭代次數(shù)，M為最大迭代次數(shù)，與此同時(shí)GPSO算法中加入了自適應(yīng)變異來增加種群的多樣性.

3） BSA算法

LSABSA算法的實(shí)驗(yàn)參數(shù)設(shè)置如式（7） ～式（12） 所示.PSO、GPSO、BSA和LSABSA算法的種群規(guī)模均為50，最大迭代次數(shù)均為1 000.

表1 典型的Benchmark函數(shù)Tab.1 Typical Benchmark function

3.2 測試函數(shù)的仿真結(jié)果與分析

在PSO、GPSO、BSA和LSABSA4種智能優(yōu)化算法下，對(duì)10個(gè)測試函數(shù)分別獨(dú)立尋優(yōu)運(yùn)行20次，相應(yīng)的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)方差數(shù)據(jù)如表2所示，其最優(yōu)個(gè)體適應(yīng)度值收斂特性曲線如圖2所示.

從表2中可得出如下結(jié)論：

1）除病態(tài)函數(shù)Rosenbrock以外，LSABSA算法比其他算法在所有優(yōu)化函數(shù)上的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)方差都要小，即收斂精度要高穩(wěn)定性要強(qiáng)，且優(yōu)化Rosenbrock函數(shù)時(shí)LSABSA算法性能略低于其他算法.尤其在解決Sphere、Quadric、Ackley和Schaffers函數(shù)時(shí)LSABSA算法的改進(jìn)效果十分明顯，說明了LSABSA算法改進(jìn)后的有效性.

2） PSO和 GPSO算法在解決 Quadric、Rastrigin、Ackley、Needle-in-a-haystack、Leung&Wang和Periodic函數(shù)優(yōu)化問題時(shí)易陷入局部最優(yōu)解，PSO算法在解決Sphere和Griewank函數(shù)以及BSA算法在解決Ackley函數(shù)時(shí)也易陷入局部最優(yōu)解，但此時(shí)BSA算法均小于PSO和GPSO算法的均值和和標(biāo)準(zhǔn)方差，而BSA和LSABSA算法在優(yōu)化Rastrigin、Griewank函數(shù)時(shí)的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)方差相同，即此時(shí)兩種算法有相同的收斂穩(wěn)定性和精確度.總體上，LSABSA和BSA算法明顯比其他算法性能優(yōu)越，除Rosenbrock函數(shù)外，LSABSA算法在優(yōu)化其他函數(shù)時(shí)的均值和方差也均優(yōu)于BSA算法，即驗(yàn)證了加入Levy飛行策略增加了種群的多樣性，不至于陷入局部最優(yōu).

圖2表示了4種算法有關(guān)準(zhǔn)確性和收斂速度的最優(yōu)個(gè)體適應(yīng)度值曲線，由圖易得：Sphere、Quadric、Rastrigin、Ackley、Griewank、Needle-in-a-haystack和Schaffers函數(shù)在優(yōu)化過程中運(yùn)用LSABSA算法相對(duì)于其他算法的收斂速度和收斂精度明顯提高，能在極短迭代次數(shù)下接近于收斂，且BSA算法收斂效果僅次于LSABSA算法.PSO算法收斂效果最差，在處理Rastrigin和Ackley函數(shù)時(shí)PSO算法易陷入局部最優(yōu)解.以上說明采用（0，1）隨機(jī)均勻分布自適應(yīng)改進(jìn)慣性權(quán)重以及線性調(diào)整學(xué)習(xí)系數(shù)的方法，增強(qiáng)了與外界的適應(yīng)能力，從而提高了收斂速度和精度.

基于表2和圖2的對(duì)比結(jié)果，整體上來講LSABSA算法的全局尋優(yōu)性能、收斂速度、求解精度和穩(wěn)定性均優(yōu)于BSA、PSO和GPSO算法，驗(yàn)證了所提算法的優(yōu)越性.

表2 PSO、GPSO、BSA和LSABSA算法對(duì)比結(jié)果Tab.2 Comparison of PSO，GPSO，BSA and LSABSA algorithm

圖2 PSO、GPSO、BSA和LSABSA算法的收斂曲線圖Fig.2 The convergence curve of PSO，GPSO，BSA and LSABSA algorithm

4 結(jié)論

針對(duì)新型仿生學(xué)群智能算法-鳥群算法在進(jìn)化初期種群多樣性不足以及在求解部分復(fù)雜高維多極值問題時(shí)，易出現(xiàn)局部收斂和早熟的問題，引入Levy飛行策略增加種群的多樣性，擴(kuò)大鳥群的搜索空間，采用（0，1）隨機(jī)均勻分布自適應(yīng)改進(jìn)慣性權(quán)重和線性調(diào)整學(xué)習(xí)因子策略來平衡全局搜索和局部搜索、提高收斂性能.通過10個(gè)典型測試函數(shù)的仿真數(shù)據(jù)結(jié)果和收斂特性曲線可得：無論是單模態(tài)還是多模態(tài)函數(shù)，從整體上看，LSABSA算法的效果優(yōu)于PSO、GPSO和BSA算法，其改進(jìn)策略提高了算法的全局搜索能力和搜索精度，以此驗(yàn)證了該算法具有較好的收斂速度、求解精度和穩(wěn)定性.

[1]Das S，Suganthan P N.Differential evolution：a survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation，2011，15（1）：4-31.

[2] Jordehi A R，Jasni J.Parameter selection in particle swarm optimisation：a survey[J].Journal of Experimental&Theoretical Artificial Intelligence，2013，25（4）：527-542.

[3] Gao X Z，Wu Y，Kai Z，et al.A knowledge-based artificial fish-swarm algorithm[C]//IEEE，International Conference on Computational Science and Engineering.IEEE，2010：327-332.

[4] Pan W T，Pan W T.A new fruit fly optimization algorithm：taking the financial distress model as an example[J].Knowledge-Based Systems，2012，26（2）：69-74.

[5] Meng X，Liu Y，Gao X，et al.A new bio-inspired algorithm：chicken swarm optimization[M].Advances in Swarm Intelligence.Springer International Publishing，2014：86-94.

[6] Smith K L，Zielinksi S.The startling intelligence of the common chicken[J].Scientific American，2014，2（2）.

[7] Meng X B，Gao X Z，Lu L，et al.A new bio-inspired optimisation algorithm：bird swarm algorithm[J].Journal of Experimental&Theoretical Artificial Intelligence，2016，28（4）：673-687.

[8] 曾嶒，彭春華，王奎，等.基于鳥群算法的微電網(wǎng)多目標(biāo)運(yùn)行優(yōu)化[J].電力系統(tǒng)保護(hù)與控制，2016，44（13）：117-122.

[9] 崔東文，金波.改進(jìn)鳥群算法及其在梯級(jí)水庫優(yōu)化調(diào)度中的應(yīng)用[J].三峽大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，38（6）：7-14.

[10]崔東文，金波.鳥群算法-投影尋蹤回歸模型在多元變量年徑流預(yù)測中的應(yīng)用[J].人民珠江，2016,37（11）：26-30.

[11]劉長平，葉春明.具有Lévy飛行特征的蝙蝠算法[J].智能系統(tǒng)學(xué)報(bào)，2013（3）：240-246.

[12]Yang X S，Deb S.Engineering optimisation by cuckoo search[J].International Journal of Mathematical Modelling&Numerical Optimisation，2010，1（4）：330-343.

[13]張前圖，房立清，趙玉龍.具有Levy飛行特征的雙子群果蠅優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2015，35（5）：1348-1352.

[14]付強(qiáng)，葛洪偉，蘇樹智.引入螢火蟲行為和Levy飛行的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2016，36（12）：3298-3302.

[15]梅真.基于改進(jìn)粒子群算法的微電網(wǎng)優(yōu)化運(yùn)行策略研究[D].武漢：湖北工業(yè)大學(xué)，2015.

[16]劉舉勝，何建佳，李鵬飛.基于CAS理論的改進(jìn)PSO算法[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（5）：57-63.

Adaptive improved bird swarm algorithm based on Levy flight strategy

YANG Wenrong,MA Xiaoyan,BIAN Xinlei

（State Key Laboratry of Reliability and Intelligence of Electrical Equipment,Hebei University of Technology,Tianjin 300130,China）

The new type of biological heuristic swarm intelligence algorithm-the bird swarm algorithm (BSA)suffers from poor population convergence precision，large convergence iteration number and even convergence earlier and be in local optimal problems due to the population diversity deficiency in early evolution and the change of cognitive and group behavioral adjustment parameters.To solve these problems,a levy adaptive improved bird swarm algorithm (LSABSA)is proposed.The random walk model of Levy flight strategy is used to increase the diversity of population and jump out of local optimal value,and by means of(0,1)random uniform distribution adaptive modified the inertia weight and linear adjustment of cognitive and social coefficients to balance the global and local search ability of BSA algorithm,and then improve the accuracy of the algorithm.Finally,10 typical test functions are used to simulate and compare the LSABSA algorithm,particle swarm optimization(PSO)algorithm,improved particle swarm optimization(GPSO)algorithm and BSA algorithm,and the result shows the convergence speed,accuracy and stability of LSABSA algorithm are better than other algorithms.

bird swarm algorithm;Levy flight;(0,1)random uniform distribution;linear adjustment;simulation test

TP18

A

1007-2373（2017） 05-0010-08

10.14081/j.cnki.hgdxb.2017.05.002

2017-04-21

河北省自然科學(xué)基金（E2015202241）

楊文榮（1969-），女，教授，博士.

[責(zé)任編輯 代俊秋]