融合差分進(jìn)化思想的自適應(yīng)人工蜂群算法

封 碩，劉 琨

(1.長安大學(xué) 機(jī)械工程學(xué)院 陜西 西安 710061；2.長安大學(xué) 理學(xué)院 陜西 西安 710061)

0 引言

人工蜂群算法(artificial bee colony，ABC)是模仿蜜蜂群體采蜜行為提出來的一種啟發(fā)式智能優(yōu)化算法，與遺傳算法(genetic algorithm，GA)[1]、差分進(jìn)化算法(differential evolution，DE)[2]、蟻群算法(ant colony optimization，ACO)[3]和粒子群算法(particle swarm optimization，PSO)[4]相比，由于ABC算法具有參數(shù)少、精度高和結(jié)構(gòu)簡單易實(shí)現(xiàn)等優(yōu)點(diǎn)，近幾年來受到廣泛的關(guān)注，并被應(yīng)用到數(shù)據(jù)挖掘[5]、生產(chǎn)調(diào)度[6]和信息處理[7]等領(lǐng)域。

與其他優(yōu)化算法相似，ABC算法在解決復(fù)雜優(yōu)化函數(shù)時，存在收斂速度慢、算法后期種群多樣性下降及易陷入局部最優(yōu)解等缺點(diǎn)。許多學(xué)者對其進(jìn)行改進(jìn)，主要在提高算法的收斂速度、增加種群的多樣性以及改進(jìn)算法的尋優(yōu)機(jī)制等方面嘗試。Gao等提出了基于差分進(jìn)化算子的改進(jìn)人工蜂群算法[8]；Zhu等受到粒子群算法的影響，利用最優(yōu)解指導(dǎo)雇傭蜂的局部搜索[9]；魏鋒濤等引入量子行為模擬蜂群求解過程[10]；趙玉霞等受到貓群思想搜索過程啟發(fā)，對較優(yōu)解與較差解分別執(zhí)行搜尋與跟蹤模式[11]。

以上研究主要改進(jìn)了搜索公式，提升了算法的尋優(yōu)效率。但仍存在不足之處：首先，在初始化階段中隨機(jī)產(chǎn)生初始種群，其隨機(jī)性導(dǎo)致種群的多樣性不足，不利于算法求得潛在最優(yōu)解。其次，雇傭蜂搜索過程中僅利用先前個體的信息產(chǎn)生候選解,這種機(jī)制利于勘探不利于開發(fā)。最后，算法后期種群多樣性下降，導(dǎo)致算法收斂速度慢。為解決以上問題，本文在初始化階段利用反向?qū)W習(xí)策略，根據(jù)種群的適應(yīng)度值貪婪選擇較優(yōu)的初始個體，擴(kuò)大種群的多樣性，提高解的質(zhì)量，加強(qiáng)算法跳出局部最優(yōu)解的能力。同時，本文將雇傭蜂搜索過程與差分進(jìn)化算法融合，并加入自適應(yīng)策略平衡算法的勘探與開發(fā)能力，加快人工蜂群算法的收斂速度。最后，在偵查蜂階段中引入混沌序列，增加種群的多樣性。

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

1.1 基于反向?qū)W習(xí)策略的初始化階段

Tizhoosh提出反向?qū)W習(xí)策略(opposition-based learning，OBL)[12]，并將其應(yīng)用到神經(jīng)網(wǎng)絡(luò)及強(qiáng)化學(xué)習(xí)中，主要思想是在取值區(qū)域內(nèi)同時考慮當(dāng)前個體和與它方向相反的個體，質(zhì)量更優(yōu)的個體進(jìn)入下一代。Rahnamayan等從數(shù)學(xué)的角度證明了與隨機(jī)產(chǎn)生候選解的方式相比[13]，反向?qū)W習(xí)策略不但可以提高種群的多樣性，還可以提高解的質(zhì)量，在一定程度上避免算法陷入局部最優(yōu)?；诜聪?qū)W習(xí)策略的反向初始種群的公式為

(1)

1.2 融合差分進(jìn)化思想的自適應(yīng)搜索階段

Gao等受到DE算法的啟發(fā)[8]，基于差分進(jìn)化算子與雇傭蜂搜索階段的性質(zhì)，提出了ABC/best/1算法，本文算法在ABC/best/1算法的基礎(chǔ)上加入自適應(yīng)策略，平衡算法的勘探與開發(fā)能力，以加快算法的收斂速度，

vij=a(t)xjbest+(1-a(t))R(xij-xkj)，

(2)

(3)

式(2)中：a(t)表示自適應(yīng)參數(shù)；xjbest表示當(dāng)前種群中的最優(yōu)解；k∈{1,2,…，SN}，j∈{1,2,…，D}，k和j都是隨機(jī)選取的，且k≠i。式(3)中：iter表示當(dāng)前迭代次數(shù)；Maxcycle表示最大的迭代次數(shù)。算法初期階段應(yīng)側(cè)重于勘探能力，此時自適應(yīng)參數(shù)取較小值；隨著迭代次數(shù)的增加，算法后期階段應(yīng)側(cè)重于開發(fā)能力，此時自適應(yīng)參數(shù)取較大值。

1.3 基于混沌序列的偵查蜂階段

文獻(xiàn)[11]指出，算法后期食物源的位置相似度高，導(dǎo)致位置更新速度慢；算法后期的多樣性下降，導(dǎo)致搜索能力下降?；煦鏪14]是一種非線性現(xiàn)象，具有非周期性、遍歷性、隨機(jī)性等特點(diǎn)，即混沌序列在取值區(qū)域內(nèi)不重復(fù)地遍歷所有狀態(tài)。本文算法在偵查蜂階段中引入Logistic混沌序列，增加種群的多樣性，加快算法的收斂速度。Logistic混沌序列的主要思想為

Ci+1=μ×Ci×(1-Ci)，

(4)

式中：μ為控制參數(shù)，當(dāng)μ=4時，公式(4)處于完全混沌狀態(tài)；Ci表示第i次的混沌映射變量，Ci是(0,1)上均勻分布的隨機(jī)數(shù)且Ci≠0.25,0.5,0.75,i=0,1，…，M，為混沌序列的長度；初始混沌變量C0=0.32。

基于Logistic混沌序列偵查蜂搜索公式為

xij=ximin+Cj(ximax-ximin)。

(5)

1.4 本文算法的步驟

綜上所述，本文提出的融合差分進(jìn)化思想的自適應(yīng)ABC 算法主要步驟如下。

Step1 在D維空間中生成SN個初始解,根據(jù)初始種群與反向種群的適應(yīng)度值排序，貪婪選擇SN個個體作為初始種群；

Step2 雇傭蜂在初始位置的附近利用搜索公式(2)進(jìn)行局部鄰域搜索，貪婪選擇適應(yīng)度值較優(yōu)的食物源；

Step3 全部的雇傭蜂完成一次局部搜索后，觀察蜂根據(jù)雇傭蜂提供的適應(yīng)度值，按照概率Pi選擇食物源，并在該食物源附近進(jìn)行鄰域搜索，尋找新的食物源，貪婪選擇較優(yōu)的食物源；

Step4 如果食物源的收益率沒有通過預(yù)先確定的循環(huán)次數(shù)(limit)得到改善時，該處食物源被放棄，與之對應(yīng)的雇傭蜂轉(zhuǎn)化為偵察蜂。偵察蜂利用公式(5)產(chǎn)生新解。

Setp5 若迭代次數(shù)小于最大迭代次數(shù)，轉(zhuǎn)至Step2；否則，輸出最優(yōu)解，算法結(jié)束。

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

為測試本文算法的性能,選用表1給出的基準(zhǔn)函數(shù)[8]進(jìn)行測試。其中：f1～f3為單峰函數(shù)，用于檢驗(yàn)算法收斂速度和精度；f4～f8為多峰函數(shù)，其局部最優(yōu)解的個數(shù)會隨著問題維數(shù)的增加呈指數(shù)增長，用于檢驗(yàn)算法的整體尋優(yōu)能力和算法跳脫局部最優(yōu)值的能力。針對表1所列的8個函數(shù)，選取ABC算法、PSO算法、DE算法、EABC算法、ABC/best/1算法與本文算法分別在維數(shù)為50和100情況下獨(dú)立運(yùn)行50次，統(tǒng)計(jì)各算法的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差，實(shí)驗(yàn)結(jié)果如表2～5所示。平均值反映了算法的求解精度，標(biāo)準(zhǔn)差反映了算法的穩(wěn)定性。

表1 測試函數(shù)表達(dá)式、搜索空間和理論最優(yōu)值

表2 各算法在50維情況下對單峰函數(shù)測試的實(shí)驗(yàn)結(jié)果

2.1 同維數(shù)不同算法的實(shí)驗(yàn)結(jié)果分析

單峰函數(shù)實(shí)驗(yàn)結(jié)果(表2)表明，ABC算法的穩(wěn)定性差，收斂精度不高。實(shí)驗(yàn)結(jié)果可以看出，本文算法的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差的精度與另外5種算法的精度相比都有明顯提高。因此，說明在收斂速度和精度方面，本文算法優(yōu)于其他算法，可以有效提高算法的局部搜索能力。多峰函數(shù)實(shí)驗(yàn)結(jié)果(表4)表明，ABC算法易陷入局部最優(yōu)值，整體尋優(yōu)能力差。f4和f8函數(shù)的實(shí)驗(yàn)結(jié)果顯示，本文算法的最優(yōu)值和最差值的精度與其他5種算法相比都有提高；f5、f6和f73個函數(shù)的實(shí)驗(yàn)結(jié)果顯示，本文算法的最優(yōu)值、最差值與另外5種算法相比都有明顯提高。因此說明，算法在整體尋優(yōu)能力及跳脫局部最優(yōu)解方面，本文算法整體尋優(yōu)能力較高，易于跳出局部最優(yōu)解。

2.2 不同維數(shù)相同算法的實(shí)驗(yàn)結(jié)果分析

算法分別在50維和100維情況下，分別分析單峰函數(shù)實(shí)驗(yàn)結(jié)果(表2和表3)以及多峰函數(shù)實(shí)驗(yàn)結(jié)果(表4和表5)。數(shù)據(jù)表明：當(dāng)維度是100時，f1、f2、f3、f5、f6和f76個函數(shù)的本文算法的尋優(yōu)指標(biāo)值優(yōu)于另外5種算法；當(dāng)函數(shù)維數(shù)降到50維時，本文算法的優(yōu)勢更為明顯。

表3 各算法在100維情況下對單峰函數(shù)測試的實(shí)驗(yàn)結(jié)果

表4 各算法在50維情況下對多峰函數(shù)測試的實(shí)驗(yàn)結(jié)果

表5 各算法在100維情況下對多峰函數(shù)測試的實(shí)驗(yàn)結(jié)果

2.3 算法的性能測試

為了更直觀地反映算法的性能, 針對表1所列的8個函數(shù)，分別采用ABC算法、DE算法、PSO算法、EABC算法、ABC/best/1算法與本文算法進(jìn)行測試。圖1展示了維數(shù)為50時，6種算法對測試函數(shù)的收斂曲線(為便于發(fā)現(xiàn)曲線間的差距，將各函數(shù)的適應(yīng)度值取對數(shù))。

圖1 基準(zhǔn)函數(shù)迭代曲線

根據(jù)圖1(a)～(c)的單峰函數(shù)進(jìn)化曲線可以得出，在收斂速度和求解精度方面，本文算法明顯優(yōu)于另外5種算法。故本文算法大幅度加快了算法的收斂速度，提高了求解精度。圖1(d)為Rosenbrock函數(shù)的收斂曲線，該函數(shù)是一個病態(tài)的螺旋型函數(shù)，算法的初期階段側(cè)重于勘探能力，導(dǎo)致算法陷入局部最優(yōu)解。隨著迭代次數(shù)的增加，算法后期階段側(cè)重于開發(fā)能力，最優(yōu)解的質(zhì)量提高，對局部搜索行為指導(dǎo)作用明顯。根據(jù)圖1(e)～(g)的函數(shù)進(jìn)化曲線可以得出，本文算法在收斂速度、精度和全局優(yōu)化能力方面明顯優(yōu)于其他5種算法，本文算法收斂速度快且易于跳出局部最優(yōu)解。圖1(h)的函數(shù)進(jìn)化曲線可以得出，在跳脫局部最優(yōu)解方面，本文算法與其他5種算法相比都有提高。