封 碩，劉 琨

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

0 引言

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

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

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

1 改進的人工蜂群算法

1.1 基于反向學習策略的初始化階段

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

(1)

1.2 融合差分進化思想的自適應搜索階段

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

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

(2)

(3)

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

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

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

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

(4)

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

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

xij=ximin+Cj(ximax-ximin)。

(5)

1.4 本文算法的步驟

綜上所述，本文提出的融合差分進化思想的自適應ABC 算法主要步驟如下。

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

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

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

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

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

2 仿真實驗及結果分析

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

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

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

2.1 同維數(shù)不同算法的實驗結果分析

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

2.2 不同維數(shù)相同算法的實驗結果分析

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

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

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

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

2.3 算法的性能測試

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

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

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