一種改進的鳥群優(yōu)化算法

馮娟婷，王進成，顧銀魯

(銀川能源學院 基礎(chǔ)部，寧夏 銀川 750021)

在過去的二十年里，人們提出了大量的群智能優(yōu)化算法.群智能優(yōu)化算法是一種人工智能算法，其思想來源于自然界中生物群體在遷移和覓食等活動中所表現(xiàn)出的社會行為.該算法簡單易于實現(xiàn)，近些年得到很大的發(fā)展，已被“國際進化計算會議(CEC)”列為討論專題之一.到目前為止所提出的算法有粒子群優(yōu)化(PSO)[1]、正余弦算法[2](SCA)、蛾火焰優(yōu)化算法[3](MFO)、蟻群優(yōu)化算法[3](ACO)、螢火蟲算法[4](GSO)、人工蜂群算法[5](ABC)和雞群算法[6](CSO)等.這些算法都具有較好的優(yōu)化能力，已被成功應(yīng)用于各個領(lǐng)域.

鳥群算法(Bird Swarm Algorithm，BSA)是由Meng X B等[7]于2015年提出的一種新的基于群體智能的啟發(fā)式算法，通過模仿鳥類的覓食、警覺和飛行行為來尋求最優(yōu)解.BSA具有運算速度快和健壯性好等優(yōu)點，不僅在解決多領(lǐng)域最優(yōu)化問題時具有明顯的優(yōu)勢[8]，而且在電網(wǎng)優(yōu)化調(diào)度、水庫優(yōu)化調(diào)度和年徑流量預(yù)測等方面取得了較好的應(yīng)用效果[9-10].然而對于算法的改進和提高算法的性能也成為一個重要的研究領(lǐng)域，本文針對BSA算法求解高維復(fù)雜優(yōu)化問題時容易陷入局部最優(yōu)等問題，提出一種改進的鳥群優(yōu)化算法(Improved Bird Swarm Optimization Algorithm，IBSA)，通過改進鳥群的覓食策略和飛行策略，有效地提高了算法的搜索性能.最后，通過對測試函數(shù)進行數(shù)值試驗，試驗結(jié)果與PSO、CSO和BSA算法對比，結(jié)果表明，IBSA算法具有較快的收斂速度和較好的尋優(yōu)精度.

1 鳥群算法

鳥群算法模仿的是鳥類的覓食、警戒和飛行行為來尋求最優(yōu)解，然而這些行為中都包含著一些簡單的規(guī)則[11-12].

規(guī)則1，每只鳥的選擇依賴于0到1上的隨機數(shù)，同時設(shè)定一個常量p，當隨機數(shù)小于p時，該鳥將進行覓食，否則，繼續(xù)保持警戒.

規(guī)則2，鳥群的覓食行為遵從每只鳥根據(jù)其自身和整個種群的經(jīng)驗來尋找食物.則覓食行為的位置更新公式為

(1)

其中，j∈[1,2,…,D]，rand(0,1)為0到1之間均勻分布的隨機數(shù)，C和S表示學習因子為兩個正數(shù)，分別稱為自我加速系數(shù)和社會加速系數(shù)，pi,j表示第i只鳥早先最優(yōu)位置，gj表示種群共享的早先最優(yōu)位置.

規(guī)則3，鳥群在保持警戒時，個體鳥會試圖飛向群體中心，鳥群之間存在著同類的競爭，因而每一只鳥不會直接向中心移動.則警戒行為的位置更新公式為

(2)

(3)

(4)

其中，k(k≠i)是從1到N之間的隨機正整數(shù)，a1,a2∈[0,2]，pFiti表示第i只鳥的最佳適應(yīng)度值，sumFit表示種群所有鳥最佳適應(yīng)度值之和，ε是計算機用來避免分母為零的很小常數(shù)，meanj表示在第j個元素上的平均位置.A1描述為一只鳥向鳥群中心移動過程中由環(huán)境引發(fā)的間接作用，而A2描述為由某個具體沖突而引發(fā)的直接作用.

規(guī)則4和5，因天敵的威脅、覓食或其他原因.每當?shù)竭_一個新的地點，鳥類將在生產(chǎn)者和乞討者之間做出選擇，自行覓食或者跟隨生產(chǎn)者獲取食物.則飛行行為中生產(chǎn)者和乞討者的位置更新公式分別為

(5)

(6)

其中，randn(0,1)表示服從均值為0、標準差為1的高斯分布的隨機數(shù)，k∈[1,2,…,N]，k≠i，F(xiàn)L(FL∈[0,2])為乞討者跟隨生產(chǎn)者尋找食物的概率，F(xiàn)Q表示鳥群中的每只鳥飛行的時間間隔.

2 改進的鳥群優(yōu)化算法

2.1 慣性權(quán)重

慣性權(quán)重ω作為BSA算法引入的一個重要參數(shù)，對平衡算法的收斂速度和全局搜索能力有著重要的作用.Eberhart R C[13]等將慣性權(quán)重引入粒子群算法中，有效地提高了算法的局部和全局尋優(yōu)能力.本文對ω采用線性遞減策略，為保證算法在前期具有較好的全局搜索能力和在后期有較好的局部搜索能力.即慣性權(quán)重ω的更新公式如下

(7)

其中，t為當前迭代次數(shù)，T為最大迭代次數(shù)，ωmax為慣性權(quán)重最大值，通常取0.9，ωmin為慣性權(quán)重的最小值，通常取0.4.(7)式表示慣性權(quán)重由0.9線性遞減至0.4.

2.2 動態(tài)學習因子

傳統(tǒng)鳥群算法對社會認知部分與自我認知部分都采用恒定學習常數(shù)，一定程度上限制種群全局協(xié)調(diào)能力，在算法收斂后期種群多樣性喪失而導(dǎo)致全部個體收斂于搜索空間中的某一點，很容易出現(xiàn)早熟現(xiàn)象.因此，在初始搜索階段，C取大，S取小，個體可以在搜索空間中自由分布，從而增加了個體位置的多樣性.隨著迭代次數(shù)的增加，讓C線性減少，S線性增加，有利于加強算法局部搜索能力.為了在算法迭代過程中更好進行個體搜索能力，避免過早陷入局部早熟，本文采用動態(tài)調(diào)整學習因子，即更新公式如下

c(t)=cmax-cmax×(t-1)/T,

(8)

s(t)=cmin+(t-1)/T,

(9)

其中，t為當前迭代次數(shù)，T為最大迭代次數(shù)，cmax和cmin分別表示學習因子的上限和下限.為了避免無效率搜索，本文中控制學習因子上下限取2和1.

通過以上分析，改進的BSA算法中鳥群覓食行為的更新公式如下

(10)

2.3 飛行行為中生產(chǎn)者的改進

為了克服鳥群算法中生產(chǎn)者因選擇前期步長可能帶來的尋優(yōu)誤差，本文通過對原步長加權(quán)取均值來取代生產(chǎn)者前期步長的選擇，避免直接選取當前個體作為下一步迭代步長而導(dǎo)致算法陷入局部最優(yōu).即對鳥群算法中生產(chǎn)者的位置公式(5)做如下改進

(11)

2.4 IBSA算法步驟

Step1 隨機初始化每只鳥，設(shè)定種群規(guī)模、最大迭代次數(shù)、飛行行為頻率及其他相關(guān)參數(shù);

Step2 計算初始解，尋找當前最優(yōu)個體；

Step3 根據(jù)公式(7)、(8)和(9)計算慣性權(quán)重和學習因子；

Step4 判斷鳥群的飛行狀態(tài)，若鳥群在不飛行的覓食狀態(tài)下，則用公式(10)更新鳥的位置；若鳥群在不飛行的警戒狀態(tài)下，則根據(jù)公式(2)來更新鳥的位置.否則，用公式(11)和公式(6)更新所有鳥的位置；

Step5 更新相應(yīng)的適應(yīng)度值，若新個體對應(yīng)的適應(yīng)值比先前的好，則取代先前的個體.并尋找當前最優(yōu)適應(yīng)值對應(yīng)的個體;

Step6 判斷算法迭代終止條件是否滿足，若滿足則結(jié)束循環(huán)并輸出最優(yōu)解，否則返回步驟step2.

3 實驗結(jié)果與分析

為評估IBSA算法的優(yōu)化性能，選取十二個標準測試函數(shù)進行仿真測試(見表2)，其中,F1～F7均為高維單峰函數(shù)，而F8～F12均為高維多峰函數(shù).將IBSA算法與PSO、CSO和BSA算法的仿真測試結(jié)果進行對比(見表3)，四種算法分別在8個測試函數(shù)上獨立運行30次，設(shè)置算法相關(guān)參數(shù)見表1.試驗都是在win7系統(tǒng)MATLAB 2012a中完成的，電腦配置為-Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz.

表1 參數(shù)設(shè)置

表2 測試函數(shù)

序號函數(shù)名測試函數(shù)定義域最優(yōu)解F8Generalizedpenalizedfunctionfx()=0.1∑D-1i=1(xi-1)2[1+10sin2(3,πxi+1]+10sin2(3πx1)+(xn-1)2{)+ ∑Di=1uxi,10,100,4()[-50,50]0

從表示3可以看出，對于單峰函數(shù)，PSO、CSO所得的結(jié)果遠遠大于BSA、IBSA，CSO、PSO都可能陷入了局部最優(yōu)，而IBSA在BSA的基礎(chǔ)上進一步提高了解的質(zhì)量，搜索結(jié)果更加準確；對于多峰函數(shù)，PSO、CSO算法可能在迭代初期已經(jīng)陷入了局部極值，BSA、IBSA的尋優(yōu)精度相差不大，而IBSA相比其他三種算法有更好的尋優(yōu)精度.根據(jù)表3的統(tǒng)計結(jié)果顯示，IBSA在8個測試函數(shù)上的尋優(yōu)精度都顯著優(yōu)于其他三種算法.

表3 PSO、CSO、BSA和IBSA數(shù)值結(jié)果

函數(shù)算法最差解最佳解平均值方差F6PSO7.3410×1022.9343×1031.6640×1033.6181×105CSO-2.5483×102-1.8293×102-2.1583×1023.3879×102BSA-2.4449×102-6.6773×101-1.2825×1022.1827×102IBSA-2.9502×102-2.9502×102-2.9502×1026.7945×10-7F7PSO1.8635×1027.1945×1067.5013×1052.3608×1012CSO1.09515.8565×1052.0282×1021.1413×106BSA2.87332.99962.99114.9792×10-4IBSA3.2505×10-79.0806×10-51.6160×10-52.7848×10-10F8PSO2.8617×1031.3489×1071.4974×1068.1313×1012CSO1.7411×10-12.1080×1011.85021.7379×101BSA4.0961×10-11.09648.3391×10-13.1923×10-2IBSA2.3624×10-85.2382×10-67.4299×10-78.6108×10-13

圖1～圖8給出了四種算法的收斂曲線圖，從圖1～6圖可以看出，對單峰函數(shù)，CSO和PSO收斂速度較為緩慢，而BSA和IBSA都具有較好的收斂趨勢，但IBSA較BSA收斂速度更快；從圖7～圖8可以看出，對多峰函數(shù)，CSO、PSO和BSA的收斂速度都低于IBSA，不僅前期收斂速度較慢而且后期不穩(wěn)定，而IBSA具有較好的收斂速度和穩(wěn)定性.綜上所述，本文所提出的IBSA收斂穩(wěn)定性和收斂速度都明顯優(yōu)于CSO、PSO和BSA.

圖1 四種算法對F1的收斂圖 圖2 四種算法對F2的收斂圖

圖3 四種算法對F3的收斂圖 圖4 四種算法對F4的收斂圖

圖5 四種算法對F5的收斂圖 圖6 四種算法對F6的收斂圖

圖7 四種算法對F7的收斂圖 圖8 四種算法對F8的收斂圖

4 結(jié)論

針對鳥群算法存在的缺點，本文提出了一種基于改進的鳥群優(yōu)化算法.通過對鳥群算法的覓食行為和飛行行為的改進，增強了個體的全局尋優(yōu)能力，有效地平衡了種群局部和全局搜索能力.通過對八個標準測試函數(shù)進行測試以及與PSO、CSO和BSA算法相比，無論是單峰函數(shù)還是多峰函數(shù)，IBSA在收斂速度和尋優(yōu)精度方面都明顯優(yōu)于其他三種算法.