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

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

1.引言

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

2.人工蜂群算法

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

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

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

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

其中，k,j滿足k∈{1,2，…,SN}，j∈{1,2,…,D}，k不等于I，為[-1,1]區間內的隨機數。

如果蜜源經過指定的循環次數后仍沒有改進，則舍棄該位置。該處的采蜜蜂成為偵查蜂并按下式產生新位置。

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

3.相關算法

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

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

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

4.EABC算法

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

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

Step 1) 初始化:

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

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

Step 2.2)如果

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

Step 4) 觀察蜂階段:

While t<=SN,執行以下程序

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

f(Vi),令

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

Step 5) 偵查蜂階段:

隨機產生一個解替換Xi.

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

5.測試與分析

5.1 測試函數集及實驗參數設置

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

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

圖1 各算法運行比較

圖2 GABC/ EABC算法運行結果

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

5.2 實驗截圖

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

6.結論

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

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

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

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

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

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