基于歐氏距離與多種搜索策略的人工蜂群算法*

佘合一， 吳錫生

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引 言

人工蜂群(artificial bee colony,ABC)算法[1]因結(jié)構(gòu)簡單、控制參數(shù)較少、魯棒性強(qiáng)等特點(diǎn)，越來越多地被各界學(xué)者所關(guān)注與研究。但其在優(yōu)化過程中，存在收斂精度低、收斂速度慢、易于早熟的缺點(diǎn)，其主要原因是ABC算法探索能力強(qiáng)而開發(fā)能力較弱[2]。

文獻(xiàn)[3]將混沌序列引入蜂群算法中，并用禁忌表記錄已搜索的局部最優(yōu)點(diǎn)來達(dá)到控制性的搜索；文獻(xiàn)[4]中針對(duì)標(biāo)準(zhǔn)ABC算法中新個(gè)體的產(chǎn)生,運(yùn)用了一種互學(xué)習(xí)策略，讓新個(gè)體的產(chǎn)生更傾向于在適應(yīng)度更優(yōu)的父代個(gè)體周圍；文獻(xiàn)[5]采用一種有方向的搜索策略，使搜索沿著最優(yōu)個(gè)體的方向進(jìn)行，減少了搜索過程中的盲目性。上述改進(jìn)算法的性能都有了一定程度改善, 但仍缺少對(duì)算法的探索能力與開發(fā)能力的平衡。

為此，本文提出了一種基于歐氏距離與多種搜索策略的改進(jìn)人工蜂群算法(improved ABC,IABC)。在IABC算法中，由三種具有不同特點(diǎn)的搜索策略組成策略池，用來實(shí)現(xiàn)更新的鄰居由指定半徑的歐氏距離決定。因每個(gè)搜索策略的特性不同，因而最大程度的平衡了算法的探索能力與開發(fā)能力。通過對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn),并與標(biāo)準(zhǔn)ABC算法及相關(guān)改進(jìn)算法進(jìn)行比較, 表明了本文所提出的IABC算法的有效性，較好地提高了算法的收斂速度和收斂精度。

1 人工蜂群算法搜索策略

對(duì)于一個(gè)D維空間的搜索問題，種群規(guī)模為2×SN,蜂群覓食過程中的蜜源相當(dāng)于D維空間域中的一個(gè)可行解，第i個(gè)蜜源位置xi={xi,1,xi,2,…,xi,D}，每一個(gè)蜜源與雇傭蜂和跟隨蜂一一對(duì)應(yīng)(雇傭蜂個(gè)數(shù)=跟隨蜂個(gè)數(shù)=SN)，蜜源的優(yōu)異程度則對(duì)應(yīng)其解的可行度，即適應(yīng)度。

ABC算法最初根據(jù)問題域按式(1)隨機(jī)產(chǎn)生一個(gè)初始種群

xij=xmin,j+rand(0,1)(xmax,j-xmin,j)

(1)

式中i=1,2,…,SN，j=1,2,…,D，xmin,j和xmax,j分別為變量xij的下界和上界。

初始化之后，雇傭蜂根據(jù)蜜源進(jìn)行開采，在蜜源的周圍由式(2)進(jìn)行隨機(jī)搜索

vij=xij+φij(xij-xkj)

(2)

式中k為隨機(jī)產(chǎn)生的整數(shù)，k=1,2,…,SN且k≠i,j=1,2,…,D；φij∈[-1,1]為一個(gè)隨機(jī)數(shù)。

2 本文IABC算法

2.1 3種搜索策略

不同的搜索策略需具有不同的搜索特性，滿足不同特性的優(yōu)化問題，使搜索的不同階段都能有合適的搜索策略。在文獻(xiàn)[2]提出了全局最優(yōu)指導(dǎo)的蜂群算法(global ABC,GABC)，利用最優(yōu)蜜源來指導(dǎo)候選蜜源的搜索。GABC的搜索策略公式如下

vij=xij+φij(xij-xkj)+ψij(gbestj-xij)

(3)

式中g(shù)bestj為全局最優(yōu)解的第j維值，k=1,2,…,SN,且k≠i,j=1,2,…,D，φij∈[-1,1]，ψij∈[0,C]，當(dāng)C=1.5時(shí)效果最好。

文獻(xiàn)[6]提出了一種改進(jìn)的ABC算法(modified ABC,MABC), MABC的搜索策略公式為

vij=xb,j+φij(xr1,j-xr2,j)

(4)

式中xb,j為全局最優(yōu)解的第j維值,r1=1,2,…,SN，r2=1,2,…,SN且r1≠r2≠i，j=1,2,…,D。

GABC算法參考文獻(xiàn)[7]進(jìn)一步對(duì)式(4)修改為

vij=xb,j+φij(xb,j-xkj)

(5)

由式(3)、式(5)以及式(2)組成了搜索策略池。在跟隨蜂開發(fā)蜜源階段，利用策略池中3種搜索策略分別產(chǎn)生3個(gè)候選蜜源，由產(chǎn)生的候選蜜源計(jì)算對(duì)應(yīng)的適應(yīng)度，根據(jù)3個(gè)候選解的適應(yīng)度進(jìn)行擇優(yōu)選取。由策略池中3種不同特性的搜索策略可以在算法搜索階段表現(xiàn)出不同的搜索特點(diǎn)，使算法在不同搜索階段都有適合的搜索策略。

2.2 歐氏距離在搜索策略中的應(yīng)用

在式(3)、式(5)中忽略了解結(jié)構(gòu)相似性的聯(lián)系，破壞解的多樣性?？紤]到解結(jié)構(gòu)之間的相似性，可以采用歐氏距離來劃分解的鄰域[8]，鄰居的解結(jié)構(gòu)存在較高的相似度。

如二個(gè)蜜源xi與xm之間的歐氏距離用d(i,m)表示，那么對(duì)于xi與所有蜜源的平均距離可表示如下

(6)

如果d(i,m)≤r×mdi，則xm是xi的一個(gè)鄰居，參數(shù)r為鄰域半徑。

蜜源xi獲得其全部鄰居蜜源后，根據(jù)每個(gè)鄰居蜜源適應(yīng)度選出鄰居內(nèi)最優(yōu)蜜源xb，其計(jì)算公式如下

(7)

2.3 IABC算法流程

1)設(shè)置算法參數(shù)，最大循環(huán)次數(shù)FES，控制參數(shù)limit，隨機(jī)產(chǎn)生初始解集,i=1,2,…,SN，j=1,2,…,D，計(jì)算解的適應(yīng)度。

2)雇傭蜂按式(2)搜索候選蜜源vi，計(jì)算其適應(yīng)度，并進(jìn)行貪婪選擇,若vi適應(yīng)度仍小于原先蜜源，則limit+1。

3)跟隨蜂根據(jù)輪盤賭方式對(duì)蜜源進(jìn)行概率性選擇，對(duì)選擇的蜜源計(jì)算與其他蜜源歐氏距離，根據(jù)式(6)計(jì)算出平均距離mdi，確定其鄰居蜜源。

5)分別用式(2)與步驟(4)更新的式 (3)、式(5)，產(chǎn)生3個(gè)候選蜜源，計(jì)算3個(gè)蜜源的適應(yīng)度，并根據(jù)3個(gè)候選蜜源的適應(yīng)度進(jìn)行貪婪選擇，生成vi。

6)對(duì)生成的vi與原先蜜源進(jìn)行貪婪選擇，若vi的適應(yīng)度仍小于原先蜜源，則limit+3。

7)判斷是否有需要被放棄的蜜源,若有, 則重新產(chǎn)生新的蜜源。

8)如果滿足終止條件, 則算法結(jié)束, 輸出最終結(jié)果; 否則,轉(zhuǎn)步驟(2)。

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

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

本文選取了6個(gè)典型的測(cè)試函數(shù)進(jìn)行測(cè)試。其中，f1,f2,f3(Sphere,Rosenbrock,Schwefel)為單峰函數(shù)，在定義域范圍內(nèi)只有1個(gè)極值，用于測(cè)試算法的收斂精度與收斂速度；f4,f5,f6(Rastrigin,Griewank,Ackley)為多峰函數(shù)，在定義域范圍內(nèi)存在多個(gè)極值，用于測(cè)試算法避免早熟能力與全局尋優(yōu)能力。其中,f2全局極小值位于一條平滑而狹長的拋物線形狀的山谷底部,該函數(shù)中變量之間具有很強(qiáng)的關(guān)聯(lián)性，不易找到其全局極小值，通常用該函數(shù)來評(píng)價(jià)優(yōu)化算法的性能。

3.2 結(jié)果分析

在對(duì)本文算法(IABC),ABC算法,文獻(xiàn)[5] (directed ABC,dABC)算法和文獻(xiàn)[9](quick ABC,qABC)算法進(jìn)行對(duì)比實(shí)驗(yàn)時(shí),實(shí)驗(yàn)參數(shù)設(shè)置為：種群規(guī)模為50(SN=25)，函數(shù)維度D=30，limit=300，最大循環(huán)次數(shù)FES=1 000，鄰域半徑r=1.5。將4種算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次，測(cè)試結(jié)果如表1所示。

表1 4種算法性能比較

從表1可以看出:在所有的測(cè)試函數(shù)中標(biāo)準(zhǔn)的ABC算法的平均值最高，除了函數(shù)f2的方差要低于dABC算法與qABC算法，其他函數(shù)的方差均高于其他3個(gè)算法，說明標(biāo)準(zhǔn)ABC算法解的精度與穩(wěn)定性較差;dABC算法與qABC算法相對(duì)于標(biāo)準(zhǔn)的ABC算法，無論在單峰函數(shù)還是在多峰函數(shù)中，最優(yōu)值、最差值與平均值3個(gè)方面的實(shí)驗(yàn)數(shù)據(jù)均明顯好于標(biāo)準(zhǔn)ABC算法，其中，qABC算法在函數(shù)f4中得到了函數(shù)的理論最優(yōu)值，只有在函數(shù)f2中的方差要比標(biāo)準(zhǔn)ABC算法大,可知dABC算法與qABC算法解的精度較好。在穩(wěn)定性方面，總體上較標(biāo)準(zhǔn)ABC算法要好。

本文IABC算法在6個(gè)函數(shù)中，其性能都優(yōu)勢(shì)明顯。為了更直觀地顯示本文IABC算法的收斂速度與收斂精度，圖1～圖6為4種算法對(duì)測(cè)試函數(shù)的收斂曲線。結(jié)合表1與圖1～圖6，可以發(fā)現(xiàn)，本文算法在每一個(gè)測(cè)試函數(shù)中，每項(xiàng)數(shù)據(jù)都明顯優(yōu)于另外3種算法。在所有測(cè)試函數(shù)中，本文IABC算法的最優(yōu)值、最差值與平均值與方差都優(yōu)于其他算法。對(duì)于解的精度：在測(cè)試函數(shù)f2中，標(biāo)準(zhǔn)ABC算法、dABC算法與qABC算法很容易陷入局部最優(yōu)解，很容易早熟收斂，而本文IABC算法的解明顯好于另外3個(gè)算法的解，并且仍然有向最優(yōu)解進(jìn)化趨勢(shì)。根據(jù)圖4和圖5可以看到本文IABC算法對(duì)測(cè)試函數(shù)f4與f5分別迭代500多次與600多次便找到了理論最優(yōu)值。對(duì)于收斂速度：從圖1～圖6可以直觀的看出，標(biāo)準(zhǔn)ABC算法收斂速度緩慢，dABC算法與qABC算法相對(duì)標(biāo)準(zhǔn)ABC來說，收斂速度得到改善，但改善的幅度仍然不是很大，而本文IABC算法的收斂速度相比較另外3個(gè)算法的收斂速度都有了很大改善。

圖1 Sphere函數(shù)進(jìn)化曲線

圖2 Rosenbrock函數(shù)進(jìn)化曲線

圖3 Schwefel函數(shù)進(jìn)化曲線

圖4 Rastrigin函數(shù)進(jìn)化曲線

圖5 Griewank函數(shù)進(jìn)化曲線

本文IABC算法與qABC算法都引入了歐氏距離，來確定具有相似解結(jié)構(gòu)的最優(yōu)鄰居，以避免利用全局最優(yōu)解而忽略其他較優(yōu)解的開發(fā)能力。但本文IABC算法在歐氏距離的基礎(chǔ)上，用3種不同的搜索策略，來滿足不同搜索階段的特性，使搜索過程中每個(gè)階段都有適合的搜索策略，以此均衡算法的探索能力與開發(fā)能力，增加解的多樣性，使算法更容易找出最優(yōu)值，從而進(jìn)一步提高了收斂速度與精度。

圖6 Ackley函數(shù)進(jìn)化曲線

4 結(jié) 論

提出了一種改進(jìn)的基于歐氏距離與多種搜索策略的人工蜂群算法(IABC)。仿真結(jié)果表明：本文算法在求解函數(shù)最小值優(yōu)化問題時(shí),能夠顯著提高收斂速度，并能有效地避免算法陷入局部最優(yōu)，提升解的收斂精度。該算法可以很好地解決復(fù)雜優(yōu)化問題，可以將本文IABC算法應(yīng)用到圖像處理中。如何利用IABC算法進(jìn)行圖像分割中最優(yōu)閾值的選取是下一步的研究內(nèi)容。