郭書杰,王步云,呂玉鵬

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

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

郭書杰,王步云,呂玉鵬

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

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

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

0 引言

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

1 人工蜂群算法

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

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

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

(1)

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

(2)

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

(3)對(duì)新蜜源Vi進(jìn)行評(píng)價(jià)，若Vi優(yōu)于Xi則用Vi取代Xi，否則保留Xi.

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

(3)

(5)跟隨蜂采用與引領(lǐng)蜂相同的方式進(jìn)行搜索.

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

(4)

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

2 改進(jìn)的人工蜂群算法

2.1 算法模型

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

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

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

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

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

圖1 改進(jìn)的人工蜂群算法的模型圖

2.2 算法步驟

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

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

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

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

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

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

圖2 改進(jìn)的人工蜂群算法的流程圖

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

3 實(shí)驗(yàn)及結(jié)果分析

為了測(cè)試改進(jìn)算法的優(yōu)化性能，使用VisualStudio2010編寫了標(biāo)準(zhǔn)算法和改進(jìn)算法兩套程序，選取兩個(gè)標(biāo)準(zhǔn)函數(shù)，通過(guò)對(duì)比標(biāo)準(zhǔn)算法和改進(jìn)算法的優(yōu)化結(jié)果來(lái)驗(yàn)證改進(jìn)算法的先進(jìn)性.

3.1 測(cè)試函數(shù)

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

表1 標(biāo)準(zhǔn)函數(shù)

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

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

3.2 測(cè)試結(jié)果

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

表2 測(cè)試結(jié)果

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

4 結(jié)論

通過(guò)將問(wèn)題的解空間進(jìn)行分割形成相互獨(dú)立的多個(gè)領(lǐng)域，對(duì)每一個(gè)領(lǐng)域i中分別使用一個(gè)人工蜂群算法Slavei來(lái)探索該領(lǐng)域內(nèi)的最優(yōu)解，同時(shí)，在問(wèn)題的整個(gè)解空間上也使用一個(gè)人工蜂群算法Master來(lái)探索整個(gè)解空間上的最優(yōu)解，通過(guò)定期將每個(gè)Slavei找到的最優(yōu)解遷移到Master中來(lái)替換其最劣解，可以有效保持蜂群的多樣性，提高算法的優(yōu)化性能.由于基于鄰域分割的多種群協(xié)同進(jìn)化人工蜂群算法需要同時(shí)維持多個(gè)蜂群的優(yōu)化搜索，因此其時(shí)間復(fù)雜度要高于經(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ù)的海雜波參數(shù)優(yōu)化方法[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),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]周新宇,吳志健,王明文.基于正交實(shí)驗(yàn)設(shè)計(jì)的人工蜂群算法[J].軟件學(xué)報(bào),2015,26(9):2167- 2190.

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

下期待發(fā)表文章摘要預(yù)報(bào)

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

國(guó)家“863”高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2012AA041402- 4)；遼寧省教育廳優(yōu)秀青年學(xué)者成長(zhǎng)計(jì)劃資助項(xiàng)目(LJQ2013048)

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

A