一種有效的多峰優化鳥群算法

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

(中國地質大學 數學與物理學院，武漢430074)

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

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

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

1 鳥群算法

1.1 鳥群算法的數學模型

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

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

(1)

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

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

(2)

(3)

(4)

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

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

(5)

(6)

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

1.2 鳥群算法的基本步驟

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

步驟2 由適應度函數分別計算得出每只鳥所處位置的適應度值，得到當前個體最優位置和群體最優位置.

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

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

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

步驟6 根據適應度函數計算所有鳥個體的適應度值，然后更新當前個體最優位置和群體最優位置.

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

步驟8 輸出群體最優位置和對應的最佳適應度值[7].

1.3 鳥群算法存在的問題

根據鳥群算法基本優化原理及其實際優化問題中的性能表現，可以發現其仍然存在著一些不足，可以總結為：

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

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

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

2 一種有效的多峰優化算法

2.1 萊維飛行

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

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

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

(7)

其中β為指數變量，s為隨機步長.

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

(8)

其中β一般取1.5，u和β都服從于正態分布

(9)

(10)

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

(11)

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

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

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

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

根據標準鳥群算法存在的問題，本文提出的多峰優化鳥群算法主要在以下3個方面對鳥群算法進行改進：

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

(12)

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

(13)

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

2.3 算法流程圖

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

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

3 仿真實驗

3.1 測試函數

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

表1 測試函數

3.2 實驗環境與參數設置

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

3.3 實驗結果與對比

對于選定的6個測試函數，每種算法都分別進行了10次實驗，實驗結果包括均值、最優值、最差值和標準差，3種算法在維度為30的最終優化結果見表3.

表2 算法參數設置Tab.2 Algorithm parameter settings

表3 維度為30時優化結果對比Tab.3 Comparison of optimization results when the dimension is 30

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

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

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

4 結語

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