一種基于EABC的新型搜索方法

遼寧省財政廳信息中心 牛 旭

1.引言

人工蜂群算法對于解決函數(shù)優(yōu)化問題有顯著的效果但其也有其缺陷，如易于過早陷入局部最優(yōu)、后期收斂速度慢、對于復雜的問題搜索最優(yōu)解能力弱[1]，計算精度不高等問題，針對以上缺陷，對該算法進行優(yōu)化設計。

2.人工蜂群算法

人工蜂群算法是一種群體智能優(yōu)化算法，主要思想是模擬蜂群的智能采蜜行為[2]。該算法首先，隨機產(chǎn)生初始種群P，SN個初始解，其中SN為采蜜蜂數(shù)也等于蜜源數(shù)。每個解都是一個D維的向量，D為優(yōu)化參數(shù)的個數(shù)。然后，以這些初始解為基礎對采蜜蜂、觀察蜂和偵查蜂進行循環(huán)搜索[2]。

根據(jù)蜂源的花蜜量[3]，觀察蜂選擇每個蜜源的概率為：

其中，為蜂源i的適應值。

已知當前記憶位置，通過下式產(chǎn)生新的候選位置vi，即ABC的搜索方程：

其中，k,j滿足k∈{1,2，…,SN}，j∈{1,2,…,D}，k不等于I，為[-1,1]區(qū)間內(nèi)的隨機數(shù)。

如果蜜源經(jīng)過指定的循環(huán)次數(shù)后仍沒有改進，則舍棄該位置。該處的采蜜蜂成為偵查蜂并按下式產(chǎn)生新位置。

其中，為搜索空間的上界和下界。

3.相關算法

（1）ABC/best算法[4]：相比于標準ABC的搜索方程，ABC/best/1和ABC/best/2產(chǎn)生的候選解只分布在當前種群的最優(yōu)個體附近。因此，改進的搜索方程具有很強的開發(fā)能力。同時，ABC/best算法的結構比較簡單易于執(zhí)行。只要在標準ABC算法框架中更換搜索方程即可。

（2）GABC算法[5]：受粒子群算法的啟發(fā)，GABC算法采用以下搜索方程：

其中，k,j滿足k∈{1,2,…,SN}，j∈{1,2,…,D}，k不等于i，為[-1,1]之間的隨機數(shù)，為[0,1.5]之間的隨機數(shù)，為當前種群的最優(yōu)個體?？梢钥闯?，受粒子群啟發(fā)的搜索方程(4)，由于有當前群體的最優(yōu)個體的引導，在保證算法探索能力的同時，在一定程度上也提高了算法的開發(fā)能力。

4.EABC算法

為了更大程度地提高計算精度和收斂速度，本文在研究ABC/best和GABC算法的基礎上，提出了新型的基于人工蜂群的EABC算法。以下方程分別為采蜜蜂階段和觀察蜂階段的搜索方程：

其中，r1,r2,j滿足r1,r2∈{1,2，…,SN}，j∈{1,2,…,D}，r1,r2,i互不相等，為當前群體最優(yōu)個體，α為[0,A]之間的隨機數(shù)，β為rand*B，這里B是一個均值為μ，方差為σ的高斯分布數(shù)。以下給出了EABC算法的偽代碼：

Step 1) 初始化:

Step 2) 采蜜蜂階段:For i=1,...SN,執(zhí)行以下程序

Step 2.1)采用式(1)產(chǎn)生一個新的候選位解Vi; 計算f(Vi),令FES=FES+1.

Step 2.2)如果

Step 3) 計算概率值Pi,令t=0，i=1.

Step 4) 觀察蜂階段:

While t<=SN,執(zhí)行以下程序

Step 4.1) IF rand（0,1），產(chǎn)生一個新的候選解Vi; 計算

f(Vi),令

Step 4.2) 令i=i+1,IF i=SN,令i=1.

Step 5) 偵查蜂階段:

隨機產(chǎn)生一個解替換Xi.

Step 6) IF FES>=Max.FES,結束運行并輸出最優(yōu)解,最優(yōu)個體;ELSE，轉至Step 2.

5.測試與分析

5.1 測試函數(shù)集及實驗參數(shù)設置

為比較EABC算法與幾種對比算法的性能，本章從文獻中選取了11個D=30或D=60的測試函數(shù)，1個D=100或D=200的測試函數(shù)，2個D=10的測試函數(shù)，1個D=4的低維測試函數(shù)，1個D=24的測試函數(shù)和2個D=30的測試函數(shù)。

對所有的測試函數(shù)，設置種群的規(guī)模為100（SN=50），limit=0.6*SN*D。為了能對算法結果進行有效統(tǒng)計，每個函數(shù)獨立優(yōu)化30次，統(tǒng)計其平均最優(yōu)值（Mean）和標準方差（SD）在對不同算法進行比較時，每個獨立運行的算法采用相同的初始群體，這樣使得每個算法之間的比較是公平的，實驗結果如圖1。

圖1 各算法運行比較

圖2 GABC/ EABC算法運行結果

為更直觀的反映算法的尋優(yōu)效果，將EABC算法與標準ABC算法，ABCbest1算法，ABCbest2算法，GABC算法進行比較。五種算法對相關測試函數(shù)的收斂曲線如圖1所示。由上圖可以看出，EABC算法的計算精度和收斂速度比標準ABC算法和GABC算法都有很大程度的提高。ABCbest1算法在多數(shù)函數(shù)中也取得了較好的結果。

5.2 實驗截圖

本文的數(shù)據(jù)是ABC算法, ABC/best/1算法, ABC/best/2算法,GABC算法, EABC算法分別在f1函數(shù), f2函數(shù)……, f32函數(shù)中實現(xiàn)得到的, 結果如圖2所示。

6.結論

本文針對蜂群算法的改進策略及適應性能進行探討和研究。針對現(xiàn)有算法存在的不足之處，受蟻群算法、差分進化算法、粒子群優(yōu)化算法的啟發(fā)，設計出了一些新的搜索方程，提出了改進的EABC算法。相比于標準ABC的搜索方程，EABC通過在采蜜蜂和觀察蜂階段采用不同的搜索方程來提高算法的開發(fā)能力。最后，通過數(shù)值試驗，驗證了所提出的搜索方程可以顯著地提高人工蜂群算法的性能。使其在保證探索能力的基礎上，可以提高開發(fā)能力。

[1]江銘焱.人工蜂群算法[M].北京:科學出版社,2015:56-57.

[2]賈俊平.統(tǒng)計學[M].北京:中國人民大學出版社,2015:11-17.

[3]BruceJohnson.VisualStudio2015高級編程(第6版) [M].北京:清華大學出版社,2016:105-108.

[4]申元霞,王國胤.新型粒子群優(yōu)化模型及應用[M].北京:科學出版社,2016:22-23.

[5]劉新宇.算法新解[M].北京:人民郵電出版社,2016:34-39.