基于鄰域分割的多種群協(xié)同進化人工蜂群算法

郭書杰,王步云,呂玉鵬

(91550部隊 指控中心，遼寧 大連 116023)*

基于鄰域分割的多種群協(xié)同進化人工蜂群算法

郭書杰,王步云,呂玉鵬

(91550部隊 指控中心，遼寧 大連 116023)*

在人工蜂群算法中，隨著優(yōu)化過程的進行，蜂群的多樣性會急劇降低，進而導致算法陷入局部最優(yōu).針對這一問題，提出了基于鄰域分割的多種群協(xié)同進化人工蜂群算法，該算法將待解問題的解空間分割成相互獨立的多個領域，在每個領域上和整個解空間上分別使用不同的蜂群來優(yōu)化，并且定期進行蜜源信息的交換，來提高蜂群的多樣性.使用標準函數(shù)對改進算法的優(yōu)化性能進行了測試，測試結果表明改進后的算法具有更好的全局尋優(yōu)能力.

人工蜂群算法；函數(shù)優(yōu)化；群智能

0 引言

為了解決函數(shù)優(yōu)化的問題，由Karaboga于2005年提出的了人工蜂群算法[1- 2](artificial bee colony algorithm，以下簡稱ABC 算法)，該算法是一種新興的模擬生物群體智能的優(yōu)化方法，具有實現(xiàn)簡單、參數(shù)數(shù)量較少、應用范圍廣等多種優(yōu)點.Karaboga和Akay的研究結果表明，ABC算法的性能比差分進化算法、微粒群算法以及遺傳算法等常見的群體智能優(yōu)化算法更具優(yōu)勢[3].鑒于ABC算法的上述優(yōu)點，ABC算法已經(jīng)被成功地應用于解決多種不同類型的實際優(yōu)化問題，如參數(shù)優(yōu)化[4]、符號回歸[5]、神經(jīng)網(wǎng)絡[6- 7]以及路徑優(yōu)化問題[8]等.盡管ABC算法具有諸多優(yōu)點，但也存在著過早收斂、局部搜索能力較弱等缺點.為了解決這些問題，在對算法優(yōu)化過程進行詳細研究的基礎上，對算法做了改進，提出了一種基于鄰域分割的多種群協(xié)同進化人工蜂群算法.

1 人工蜂群算法

人工蜂群算法通過模擬自然界中蜂群的采蜜行為，將蜂群分為引領蜂、跟隨蜂和偵察蜂三類，并將整個優(yōu)化過程分解為引領蜂開采、跟隨蜂開采、偵查蜂開采三個階段.在引領蜂開采階段，引領蜂在自己找到的蜜源周圍進行局部探索；在跟隨蜂開采階段，跟隨蜂根據(jù)引領蜂發(fā)現(xiàn)的蜜源的適應度擇優(yōu)選擇一個蜜源，并在該蜜源周圍進行局部探索；如果在某一蜜源附近的多次探索均未能找到更優(yōu)的蜜源，則進入偵察蜂開采階段：與該蜜源對應的引領蜂變成偵察蜂，隨機生產(chǎn)一個新蜜源進行探索.

假令蜜源的數(shù)量為NP，蜜源Xi對應的適應度為fiti，蜜源維持代數(shù)閾值為limit，待解問題的維數(shù)為D，第i維Xid的取值范圍為[Ldi,Udi]，則人工蜂群算法的搜索步驟如下[1,9- 10].

(1) 初始化各蜜源：設置優(yōu)化代數(shù)iterMax、維持代數(shù)limit、問題維度及各維度的取值范圍等參數(shù)；使用公式(1)隨機生成NP個蜜源.

(1)

(2)為蜜源Xi分配一只引領蜂，并按式(2)在該蜜源周圍進行索，得到新蜜源Vi.

(2)

其中,d是[1-D]中的隨機整數(shù)；j∈{1,2，…，NP}并且j≠i.

(3)對新蜜源Vi進行評價，若Vi優(yōu)于Xi則用Vi取代Xi，否則保留Xi.

(4)由式(3)計算引領蜂找到的蜜源被跟隨的概率，跟隨蜂采用輪盤賭的方法選擇蜜源Xj.

(3)

(5)跟隨蜂采用與引領蜂相同的方式進行搜索.

(6)判斷蜜源是否滿足被放棄的條件，即判斷Xi的持續(xù)未更新代數(shù)traili是否大于等于limit，若是，則使用式(1)隨機生成一個蜜源來取代Xi.

(4)

(7)判斷算法是否滿足終止條件，若滿足則終止，并輸出最優(yōu)解，否則轉到步驟(2)繼續(xù)執(zhí)行.

2 改進的人工蜂群算法

2.1 算法模型

為了便于描述，給出以下定義.

定義1 領域：令A為函數(shù)F(Xi)的解空間，將A分割為k個子集合{S1，S2，…,Sk}，使得S1，S2，…Sk滿足以下條件：①Si(i=1,…,k)≠φ;②S1∩S2∩…∩Sk=φ;③S1∪S2∪…∪Sk=A，則稱{S1，S2，…,Sk}定義了A的一個k分割；稱Si為A的一個領域.

定義2 主群(Master)：令A為函數(shù)F(Xi)的解空間，使用人工蜂群算法對函數(shù)F(Xi)進行優(yōu)化時，在整個A上進行優(yōu)化搜索的蜂群為主群.

定義3 從群(Slave)：令A為函數(shù)F(Xi)的解空間，使用人工蜂群算法對函數(shù)F(Xi)進行優(yōu)化時，對A進行一次k(k>1)分割，則在整個A的領域Si上進行優(yōu)化搜索的蜂群為從群.

在基于鄰域分割的多種群協(xié)同進化人工蜂群算法中，對待解函數(shù)F(Xi)的解空間進行一次k分割，形成k個領域{S1，S2，…,Sk}，在每一個領域Si上生成1個從群，使用人工蜂群算法在該領域內進行優(yōu)化搜索；在F(Xi)的解空間A上生成1個主群，使用人工蜂群算法在該空間中進行優(yōu)化搜索.主群和各個從群間定期進行信息交流：每隔一定的進化代數(shù)，從各個子群中選出最優(yōu)秀的蜜源，取代主群的最差蜜源.改進算法的模型如圖1所示.

圖1 改進的人工蜂群算法的模型圖

2.2 算法步驟

基于鄰域分割的多種群協(xié)同進化人工蜂群算法的處理步驟如下.

(1)設置算法參數(shù)：種群大小NP、優(yōu)化代數(shù)iterMax、維持代數(shù)limit、問題維度D和各維度的取值范圍Ldi及Udi、遷移代數(shù)NT、領域個數(shù)NS;

(2)對每一個領域Si，根據(jù)步驟(1)設定的參數(shù)，完成參數(shù)配置，生成從群Slavei；按照第一節(jié)中給出的人工蜂群算法啟動優(yōu)化搜索;

(3)在解空間A上生成主群Master；根據(jù)步驟(1)設定的參數(shù)，完成參數(shù)配置，并按照第一節(jié)中給出的人工蜂群算法啟動優(yōu)化搜索;

(4)如果當前進化代數(shù)iter是遷移代數(shù)NT的整數(shù)倍，則從各個Slavei中選出最優(yōu)解來替換主群Master中的最劣解;

(5)判斷算法是否滿足終止條件，若滿足則終止，并輸出最優(yōu)解.

圖2 改進的人工蜂群算法的流程圖

算法處理流程如圖2所示.

3 實驗及結果分析

為了測試改進算法的優(yōu)化性能，使用VisualStudio2010編寫了標準算法和改進算法兩套程序，選取兩個標準函數(shù)，通過對比標準算法和改進算法的優(yōu)化結果來驗證改進算法的先進性.

3.1 測試函數(shù)

測試中選取了一個單峰函數(shù)和一個非線性多峰值函數(shù)來檢驗改進算法的全局搜索性能.測試函數(shù)如表1所示；被測函數(shù)的三維映像圖如圖3、4所示.

表1 標準函數(shù)

圖3 f1：Sphere函數(shù)三維映像圖

圖4 f2：Rastrigin函數(shù)三維映像圖

3.2 測試結果

使用相同的參數(shù)配置的標準人工蜂群算法和改進后的人工蜂群算法，分別對函數(shù)f1和f2的不同維數(shù)進行優(yōu)化搜索，每種算法獨立運行20次，所搜索到的最有解的平均值如表2所示.算法的參數(shù)配置為如下：種群大小NP=50、優(yōu)化代數(shù)iterMax=100、維持代數(shù)limit=5、遷移代數(shù)NT=2、領域個數(shù)NS=5.

表2 測試結果

由上述測試結果不難看出，不論是求解單峰函數(shù)的優(yōu)化問題還是求解非線性多峰值函數(shù)的優(yōu)化問題，與經(jīng)典人工蜂群算法相比，改進后的算法能夠有效防止過早收斂的發(fā)生，具有較好的全局搜索能力；求解單峰函數(shù)的優(yōu)化問題時，改進算法的優(yōu)勢更為明顯.

4 結論

通過將問題的解空間進行分割形成相互獨立的多個領域，對每一個領域i中分別使用一個人工蜂群算法Slavei來探索該領域內的最優(yōu)解，同時，在問題的整個解空間上也使用一個人工蜂群算法Master來探索整個解空間上的最優(yōu)解，通過定期將每個Slavei找到的最優(yōu)解遷移到Master中來替換其最劣解，可以有效保持蜂群的多樣性，提高算法的優(yōu)化性能.由于基于鄰域分割的多種群協(xié)同進化人工蜂群算法需要同時維持多個蜂群的優(yōu)化搜索，因此其時間復雜度要高于經(jīng)典算法.

[1]KARABOGAD.Anideabasedonhoneybeeswarmfornumericaloptimization[R].TechnicalReport,Kayseri:ErciyesUniversity,2005.

[2]KARABOGAD,BASTURKB.Apowerfulandefficientalgorithmfornumericalfunctionoptimization:Artificialbeecolony(ABC)algorithm[J].JournalofGlobalOptimization,2007,39(3):459- 471.

[3]KARABOGAD,AKAYB.Acomparativestudyofartificialbeecolonyalgorithm[J].AppliedMathematicsandComputation,2009,214(1):108- 132.

[4]賈宗圣,司錫才,王桐.基于人工蜂群技術的海雜波參數(shù)優(yōu)化方法[J].中南大學學報(自然科學版),2012,43(9):3485- 3489.

[5]KARABOGAD,OZTURKC,KARABOGAN,etal.Artificialbeecolonyprogrammingforsymbolicregression[J].InformationSciences,2012,209(11):1- 15.

[6]GARROBA,SOSSAH,VZQUEZRA.Artificialneuralnetworksynthesisbymeansofartificialbeecolony(ABC)algorithm[C].//Proc.oftheIEEECongressonEvolutionaryComputation.NewOrleans:IEEE,2011:331- 338.

[7]YEHW,HSIEHT.Artificialbeecolonyalgorithm-neuralnetworksforS-systemmodelsofbiochemicalnetworksapproximation[J].NeuralComputingandApplications,2012,21(2):365- 375.

[8]SZETOWY,WUY,HOSC.Anartificialbeecolonyalgorithmforthecapacitatedvehicleroutingproblem[J].EuropeanJournalofOperationalResearch,2011,215(1):126- 135.

[9]周新宇,吳志健,王明文.基于正交實驗設計的人工蜂群算法[J].軟件學報,2015,26(9):2167- 2190.

[10]秦全德，程適，李麗，等．人工蜂群算法研究綜述[J]．智能系統(tǒng)學報，2014，9(2):127- 135．

下期待發(fā)表文章摘要預報

Multi Group Cooperative Evolutionary Artificial Bee Colony Algorithm based on Neighborhood Segmentation

GUO Shujie,WANG Buyun,LV Yupeng

(Command and Control Center of 91550 Troops PLA,Dalian 116023,China)

In artificial bee colony algorithm,the diversity of the swarm will be reduced dramatically with the optimization process,which leads to the local optimization of the algorithm.To solve this problem,a multi swarm cooperative evolutionary artificial bee colony algorithm based on neighborhood segmentation is proposed.In this algorithm, the solution space of the problem to be solved is divided into a plurality of fields which are independent of each other.Different swarm optimizations are used in each field and the whole solution space,and regularly exchanges the information of nectar are conducted to improve the diversity of the swarm.The optimization performance of the improved algorithm is tested by using the standard function.The test results show that the improved algorithm has better global searching ability.

artificial bee colony algorithm;function optimization;swarm intelligence

1673- 9590(2017)03- 0112- 04

2016- 10- 11

國家“863”高技術研究發(fā)展計劃資助項目(2012AA041402- 4)；遼寧省教育廳優(yōu)秀青年學者成長計劃資助項目(LJQ2013048)

郭書杰(1978-)，男，工程師，博士，主要從事軟件工程方面的研究E-mail:shujieguo@126.com.

A