一種有效的多峰優(yōu)化鳥群算法

肖海軍，王芬艷，盧常景，曹 穎

(中國地質(zhì)大學(xué) 數(shù)學(xué)與物理學(xué)院，武漢430074)

群智能優(yōu)化算法是近年來興起的一種概率搜索式算法,相比于線性規(guī)劃[1]、動態(tài)規(guī)劃[2]和混合規(guī)劃[3]等傳統(tǒng)優(yōu)化算法，它具有以下4種特征：(1)相互作用的個體分布在群體中；(2)所有個體都能感知當(dāng)前信息；(3)模型易于擴展；(4)具有自組織性,其基本理論是模擬生物群體之間的相互交流與合作，根據(jù)簡單有限的個體行為與智能，通過群體作用形成不可估量的整體效應(yīng),由于具有良好的直觀性和實用性，研究者們相繼提出了蟻群優(yōu)化算法(Ant Colony Optimization，ACO)[4]、混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)[5]、蝙蝠算法(Bat Algorithm，BA)[6]等優(yōu)化算法，現(xiàn)在這些算法已經(jīng)廣泛地應(yīng)用于工程中解決實際問題.

2016年，Meng等人受到鳥類群智能的啟發(fā)，提出了一種全新的群智能優(yōu)化算法——鳥群算法(Bird Swarm Algorithm，BSA)[7],鳥群算法是在基于鳥類社會行為和社交互動的基礎(chǔ)上，模擬其三種社會行為：覓食行為、警戒行為與飛行行為而來.相比于粒子群算法和差分進化算法等傳統(tǒng)優(yōu)化算法，鳥群算法不僅遺傳了尋優(yōu)速度快、變異性強等優(yōu)點，更具有自身獨特的特點,由于鳥群算法存在四條靈活的搜索路線，并且可以自由調(diào)整，其在尋優(yōu)的過程中能更好地平衡高效性與準(zhǔn)確性,由于該算法提出的時間較短，研究的文獻較少，目前主要的研究方向可分為兩個方面：算法的改進和應(yīng)用.在算法改進方面，2016年，劉曉龍等人[8]在鳥群算法中引入了一種輔助搜索策略，即萊維飛行，在鳥群飛行位置更新時采用這一方式，從而有效地提升了算法性能.在算法應(yīng)用方面，2016年，崔東波等人[9]提出了一種改進的鳥群算法，并成功應(yīng)用于梯級水庫群模型優(yōu)化中.目前，由于關(guān)于鳥群算法的研究非常有限，還存在較大的研究和改進空間.如何有效地提高鳥群算法的優(yōu)化性能，使得其在搜索和開發(fā)過程中保持更好的平衡將會是以后研究的重點.

在對鳥群算法進行研究的過程中，發(fā)現(xiàn)鳥群算法在優(yōu)化一些高維多峰問題時會陷入到局部極值中，且鳥群算法的仿生過程也仍有一些不合理之處.本文提出了一種有效的多峰優(yōu)化鳥群算法(Multi-peak Optimized Bird Swarm Algorithm，MOBSA)，其主要是將萊維飛行引入到鳥群空間位置初始化和位置更新中，并通過調(diào)整鳥類身份的分類策略來對標(biāo)準(zhǔn)鳥群算法進行改進.多峰優(yōu)化鳥群算法既能使得鳥群算法的仿生過程變得更加科學(xué)，還能得到比鳥群算法更好的優(yōu)化結(jié)果.通過基于18個基準(zhǔn)優(yōu)化問題的仿真實驗和比較證明了多峰優(yōu)化鳥群算法相比于粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)和差分進化算法具有更好的準(zhǔn)確性與穩(wěn)定性.

1 鳥群算法

1.1 鳥群算法的數(shù)學(xué)模型

由于群居生活會產(chǎn)生生存優(yōu)勢，每個個體都能從中受益，因此很多鳥類都是群體的，以達(dá)到良好的覓食效率和最優(yōu)的生存環(huán)境.通過最簡單的社會互動，群體行為可以發(fā)展為復(fù)雜的相互作用，鳥群算法就是在基于這些群體社會行為的基礎(chǔ)發(fā)展而來.

覓食行為：每只鳥在尋找食物時都會依靠自身經(jīng)驗和群體經(jīng)驗.因此，假設(shè)(2)可以描述為

(1)

其中j∈{1,2,…，D},rand(0,1)是產(chǎn)生一個(0,1)間均勻分?jǐn)?shù)的隨機數(shù),U和V是兩個人為定義的正數(shù),pi,j表示當(dāng)前第i只鳥在j維的最優(yōu)位置，gj表示當(dāng)前鳥群在j維的最優(yōu)位置.

警戒行為：對于假設(shè)(3)，群體位置更新方法可以描述為

(2)

(3)

(4)

其中k∈{1,2,…，N}且k≠i,α1∈(0,2),α2∈(0,2).Fiti是當(dāng)前時刻第i只鳥最優(yōu)適應(yīng)度值，AllFit是當(dāng)前時刻所有鳥個體最優(yōu)適應(yīng)度值的總值,ε是計算機程序中的最小常數(shù)，用于避免出現(xiàn)零除法錯誤,meanj是群體處于j維的平均位置.

飛行行為：根據(jù)假設(shè)(4)，可以從鳥群中區(qū)分出生產(chǎn)者和乞討者，其位置更新方法可以描述為

(5)

(6)

其中k∈{1,2,…，N}且k≠i,randn(0,1)表示隨機生成一個服從(0,1)分布的高斯分布值,S(S∈(0,2))是乞討者跟隨生產(chǎn)者尋找食物的一個常數(shù),此外，假設(shè)鳥群以Q為時間頻率遷徙地點且Q為正整數(shù)[7].

1.2 鳥群算法的基本步驟

根據(jù)以上描述的數(shù)學(xué)模型和計算方法，鳥群算法的基本步驟可以歸納如下：

步驟2 由適應(yīng)度函數(shù)分別計算得出每只鳥所處位置的適應(yīng)度值，得到當(dāng)前個體最優(yōu)位置和群體最優(yōu)位置.

步驟3 判斷Q除t是否能整除,若整除，則進行步驟4；若有余數(shù)，則進行步驟5.

步驟4 將鳥群所有個體區(qū)分為乞討者和生產(chǎn)者,對生產(chǎn)者采用公式(5)進行位置更新，對乞討者采用公式(6)進行位置更新,結(jié)束后轉(zhuǎn)至步驟6.

步驟5 判別每只鳥在覓食還是警戒,對每只鳥，隨機生成一個服從(0,1) 均勻分布的數(shù)值，如果覓食概率P大于該數(shù)值，那么判別該鳥處于覓食狀態(tài)，采用公式(1)進行位置更新；不然判別該鳥處于警戒狀態(tài)，采用公式(2)進行位置更新,結(jié)束后轉(zhuǎn)至步驟6.

步驟6 根據(jù)適應(yīng)度函數(shù)計算所有鳥個體的適應(yīng)度值，然后更新當(dāng)前個體最優(yōu)位置和群體最優(yōu)位置.

步驟7 判斷t是否小于M,若是，則令t=t+1，轉(zhuǎn)至步驟3；若否，則迭代結(jié)束，轉(zhuǎn)至步驟8.

步驟8 輸出群體最優(yōu)位置和對應(yīng)的最佳適應(yīng)度值[7].

1.3 鳥群算法存在的問題

根據(jù)鳥群算法基本優(yōu)化原理及其實際優(yōu)化問題中的性能表現(xiàn)，可以發(fā)現(xiàn)其仍然存在著一些不足，可以總結(jié)為：

(1)鳥群算法在處理多極值優(yōu)化問題時容易出現(xiàn)早熟情況和陷入局部最優(yōu).標(biāo)準(zhǔn)鳥群算法性能測試實驗顯示，相對于粒子群算法和差分進化算法，鳥群算法在處理單峰問題時具有明顯優(yōu)勢，但在處理一些多峰優(yōu)化問題時同樣會陷入局部極值，優(yōu)化結(jié)果甚至可能會更差.

(2)鳥群算法仿生過程與實際存在著一些差異，沒有完美的體現(xiàn)生物群智能.標(biāo)準(zhǔn)鳥群算法將鳥群個體區(qū)分為生產(chǎn)者和乞討者，食物儲量最高者為生產(chǎn)者，食物儲量最低者為乞討者，而食物儲量介于這兩者之間的鳥則隨機選擇身份.綜合分析可知，如果規(guī)定食物儲量更高的鳥更可能是生產(chǎn)者，而食物儲量低的鳥更可能是乞討者的話將更加科學(xué).

(3)參數(shù)配置的合理性對優(yōu)化結(jié)果影響非常大.比如飛行頻率這一參數(shù)的變化，將會完全改變鳥群算法的迭代尋優(yōu)路徑，從而影響到最終結(jié)果.Meng等人也指出鳥群算法中的參數(shù)設(shè)置需要進行統(tǒng)一分析，如果單獨進行參數(shù)研究可能會沒有效果.

2 一種有效的多峰優(yōu)化算法

2.1 萊維飛行

萊維飛行是一類非高斯隨機過程，其隨機行走過程服從萊維分布[10].有研究顯示，信天翁、布谷鳥等鳥類生活習(xí)性都適用于萊維飛行.因此，近年來許多優(yōu)化算法中都引入了萊維飛行，如2010年Yang等人利用萊維飛行優(yōu)化了布谷鳥搜索算法[11].2014年Hakl等人在粒子群優(yōu)化算法中融合了萊維飛行[12].2016年Sharma等人提出了一種基于萊維飛行的人工蜂群優(yōu)化算法[13].在引入萊維飛行后，這些優(yōu)化算法性能都得到了有效提升.

萊維飛行是按隨機步長進行的一種游走，其具有一定概率分布特性,隨機步長可以表示為

L(s)～|s|-1-β,0<β≤2,

(7)

其中β為指數(shù)變量，s為隨機步長.

由于實現(xiàn)萊維飛行過于復(fù)雜，本文采用了Yang提出的Mantegna算法[14]來模擬產(chǎn)生隨機步長.在Mantegna算法中，隨機步長s的計算可通過

(8)

其中β一般取1.5，u和β都服從于正態(tài)分布

(9)

(10)

當(dāng)|s|≥|s0|，s0為設(shè)定的最小步長，這種分布將符合萊維分布,Γ(·)為伽瑪函數(shù)，其計算可通過

(11)

為了驗證萊維飛行與隨機行走的性能，本文進行了一個簡單的MATLAB仿真對比實驗，在兩種游走都設(shè)置為200步的情況下，最終結(jié)果如圖1所示.

圖1 兩種游走的位置分布Fig.1 Distribution of two kinds of walks

由圖1可知，隨機游走產(chǎn)生的位置相對來說比較集中，而利用萊維飛行可以產(chǎn)生更廣的位置分布范圍.因此，在優(yōu)化算法中引入萊維飛行，會增強算法的區(qū)域搜索能力和跳出局部極值的能力，從而提升算法優(yōu)化性能.

2.2 多峰優(yōu)化鳥群算法(MOBSA)

根據(jù)標(biāo)準(zhǔn)鳥群算法存在的問題，本文提出的多峰優(yōu)化鳥群算法主要在以下3個方面對鳥群算法進行改進：

(1)將萊維飛行引入到鳥群空間位置初始化中，以增強算法初期位置分布的多樣性,位置初始化公式可以表示為

(12)

(2)當(dāng)鳥群群體最優(yōu)位置迭代6次還未進化時，則對鳥群飛行行為采用萊維飛行更新位置，以增強算法跳出局部極值的能力,那么公式(5)將變?yōu)?/p>

(13)

(3)調(diào)整鳥類身份的分類策略.標(biāo)準(zhǔn)鳥群算法將鳥群個體區(qū)分為生產(chǎn)者和乞討者，食物儲量最高者為生產(chǎn)者，食物儲量最低者為乞討者，而食物儲量介于這兩者之間的鳥個體則隨機選擇身份.本文認(rèn)為，如果將食物儲量高者設(shè)定為具有更大概率成為生產(chǎn)者，而食物儲量低者更可能成為乞討者更為科學(xué).因此，本文根據(jù)鳥類食物儲量高低的不同，設(shè)定了一組介于[0,1]之間大小不同的Pi,如果對第i只鳥，[0,1]間隨機生成的數(shù)值大于Pi，則該鳥定義為生產(chǎn)者，否則為乞討者.這種更加科學(xué)化的設(shè)置，增強了算法仿生智能，使算法更為靈活.

2.3 算法流程圖

根據(jù)多峰優(yōu)化鳥群算法(MOBSA)的具體流程繪制出圖2.

圖2多峰優(yōu)化鳥群算法(MOBSA)流程圖Fig.2 Multi-peak Optimized Bird Swarm Algorithm(MOBSA) flow chart

3 仿真實驗

3.1 測試函數(shù)

如表1所示，表中列出了所選取的函數(shù)表達(dá)式，取值范圍及最優(yōu)解.在6個測試函數(shù)中，F(xiàn)1、F2、F3為單峰函數(shù)，主要用于測試算法優(yōu)化精度，F(xiàn)4、F5、F6為多峰函數(shù)，主要用于評估算法跳出局部極值的能力.本文將在測試函數(shù)維度D為30的情況下進行實驗.

表1 測試函數(shù)

3.2 實驗環(huán)境與參數(shù)設(shè)置

所有實驗均在統(tǒng)一的環(huán)境中進行，實驗環(huán)境為：Intel i5奔騰雙核處理器，2.5GHz，2G運行內(nèi)存，Win7操作系統(tǒng)，MATLAB R2014a.此外，3種算法的關(guān)鍵參數(shù)，如最大迭代次數(shù)、種群規(guī)模等都保持一致，相關(guān)參數(shù)設(shè)置可見表2.

3.3 實驗結(jié)果與對比

對于選定的6個測試函數(shù)，每種算法都分別進行了10次實驗，實驗結(jié)果包括均值、最優(yōu)值、最差值和標(biāo)準(zhǔn)差，3種算法在維度為30的最終優(yōu)化結(jié)果見表3.

表2 算法參數(shù)設(shè)置Tab.2 Algorithm parameter settings

表3 維度為30時優(yōu)化結(jié)果對比Tab.3 Comparison of optimization results when the dimension is 30

結(jié)論1：MOBSA與BSA在優(yōu)化單峰函數(shù)時性能明顯優(yōu)于PSO算法，且MOBSA相對于BSA能有效地提高尋優(yōu)精度.事實上，由表3可知，對于F1和F2這2個單峰函數(shù)，PSO算法在30維上都陷入到了局部最優(yōu)，而MOBSA與BSA在30維上的平均優(yōu)化結(jié)果最終都接近于0.值得注意地是，MOBSA的平均優(yōu)化結(jié)果要好于BSA幾個數(shù)量級,對于F3這個單峰函數(shù)，雖然在維度為30的PSO算法偶爾能優(yōu)化到0，但是其大多數(shù)時候還是會陷入到局部最優(yōu).相比之下，MOBSA與BSA在優(yōu)化F3函數(shù)時結(jié)果能一直穩(wěn)定在0.

結(jié)論2：當(dāng)優(yōu)化多峰函數(shù)時，MOBSA能有效跳出部分局部極值，從而提升鳥群算法優(yōu)化性能.事實上，以F4和F5這2個多峰函數(shù)為例，由于極值眾多且分布復(fù)雜，大多數(shù)優(yōu)化算法都會陷入到局部極值中，MOBSA、BSA與PSO算法也都未能幸免.在30維上，PSO算法的平均優(yōu)化結(jié)果偏離最優(yōu)解都非常大，MOBSA與BSA的平均優(yōu)化結(jié)果雖然也有一定偏離，但相比之下已經(jīng)足夠優(yōu)異.當(dāng)然，相對于BSA的平均優(yōu)化結(jié)果，MOBSA的平均優(yōu)化結(jié)果也會有一定程度的提升.但是，從標(biāo)準(zhǔn)差來看，MOBSA優(yōu)化效果的穩(wěn)定性會不如BSA.F6作為一個簡單的多峰函數(shù)，MOBSA與BSA優(yōu)化時在維度為30時都能穩(wěn)定地尋找到最優(yōu)解0，而PSO算法卻仍然陷入到了局部極值.

綜上可知，不管在優(yōu)化單峰函數(shù)還是多峰函數(shù)時，多峰優(yōu)化鳥群算法都能實現(xiàn)優(yōu)化性能的提升,這主要源于多峰優(yōu)化鳥群算法增強了算法初期位置分布的多樣性，從而擴大了尋優(yōu)空間，此外萊維飛行模式在位置更新上的引入也加強了算法跳出局部極值的能力.不過跳躍能力的增強也帶來了一定的局限性，它造成算法的穩(wěn)定性下降，這種缺陷在復(fù)雜多峰函數(shù)上會更明顯.

4 結(jié)語

本文主要介紹了一種有效的多峰優(yōu)化鳥群算法(MOBSA)，并進行了MATLAB仿真對比實驗來說明改進鳥群算法的優(yōu)越性.首先具體介紹了標(biāo)準(zhǔn)鳥群算法，包括算法數(shù)學(xué)模型、算法基本原理及算法存在的缺陷.隨后，針對鳥群算法存在的缺陷，提出了改進方法，那就是將萊維飛行引入到算法中，用于初始位置的生成和飛行位置的更新，同時對算法仿真過程進行了一些調(diào)整.為了測試MOBSA的性能，以標(biāo)準(zhǔn)BSA和PSO作為對比算法，選取了3個單峰函數(shù)和3個優(yōu)化函數(shù)，并設(shè)置維度為30進行實驗.實驗結(jié)果表明，MOBSA與 BSA在所有函數(shù)上的性能都會優(yōu)于PSO算法.相對于BSA，MOBSA在單峰函數(shù)上能有效提高優(yōu)化精度，在多峰函數(shù)上也能跳出部分極值，得到比BSA更好的優(yōu)化結(jié)果.因此，MOBSA實現(xiàn)了鳥群算法性能的提升，是一種有效地智能優(yōu)化算法.雖然本文提出的多峰優(yōu)化鳥群算法達(dá)到了鳥群算法優(yōu)化性能的提升，但是鳥群算法的改進方法不僅限于此.未來關(guān)于鳥群算法的改進可以集中于雜交其他元啟發(fā)式算法或優(yōu)化算法.另外，引入多群思想也是可以考慮的一個方向.