丁 華，王志剛，尚旭東

（南京師范大學(xué)泰州學(xué)院，江蘇 泰州 225300）

人工蜂群[1](artificial bee colony，簡(jiǎn)稱ABC)算法是由土耳其學(xué)者Karaboga提出的一種元啟發(fā)式算法.算采用不同類型蜜蜂的分工協(xié)作的機(jī)制來求得問題的最優(yōu)解.實(shí)驗(yàn)結(jié)果表明，ABC算法的性能要優(yōu)于或相當(dāng)于粒子群算法、差分進(jìn)化算法和遺傳算法.目前，ABC算法已被成功應(yīng)用于求解不同類型的實(shí)際應(yīng)用問題，如作業(yè)車間調(diào)度、聚類分析、無線傳感網(wǎng)絡(luò)、車輛路徑問題等.但在ABC算法中，求解復(fù)雜函數(shù)時(shí)，引領(lǐng)蜂和跟隨蜂對(duì)食物源的附近進(jìn)行搜索時(shí)所采用的搜索策略在收斂速度、求解精度、最優(yōu)解等方面仍存在缺點(diǎn).為解決這些問題，專家們提出了不同的搜索策略來改善算法的性能.利用分段搜索策略實(shí)現(xiàn)對(duì)最優(yōu)食物源的充分優(yōu)化，對(duì)食物源進(jìn)行貪婪更新，并招募所有跟隨蜂選擇當(dāng)前最優(yōu)食物源；引入兩個(gè)參數(shù)來控制搜索策略中的擾動(dòng)頻率和擾動(dòng)尺度，提出了改進(jìn)的ABC算法[2-3]；受差分進(jìn)化算法中DE/best/1和DE/rand/1變異策略的啟發(fā)[4-5]，提出ABC/best/1和ABC/rand/1兩種改進(jìn)的搜索策略，并引入概率選擇參數(shù)來控制這兩種搜索策略的使用頻率.

本文研究了一種人基于混合搜索策略的人工蜂群算法—ABCMSS.新算法在引領(lǐng)蜂和跟隨蜂對(duì)食物源的附近進(jìn)行搜索時(shí)依據(jù)混合搜索策略以平衡算法的局部搜索能力和全局搜索能力.本文設(shè)計(jì)仿真實(shí)驗(yàn)，將ABCMSS算法與ABC算法和3種不同類型的改進(jìn)算法進(jìn)行了對(duì)比，驗(yàn)證ABCMSS算法的性能.

2 人工蜂群算法

ABC算法中，因蜜蜂不同的分工，引領(lǐng)蜂負(fù)責(zé)在食物源附近進(jìn)行搜索，其與所采集的食物源一一對(duì)應(yīng).引領(lǐng)蜂負(fù)責(zé)在食物源附近進(jìn)行搜索并獲得對(duì)應(yīng)食物源的位置、食物源的存儲(chǔ)量等相關(guān)信息，通過一定的方式與跟隨蜂交換信息，跟隨蜂根據(jù)與引領(lǐng)蜂交換的信息以一定的概率挑選較優(yōu)的食物源繼續(xù)開采.若一個(gè)食物源由于開采完而被放棄時(shí)，相應(yīng)的引領(lǐng)蜂會(huì)轉(zhuǎn)變他們的工作角色，成為偵察蜂并在蜂巢附近搜索的新的食物源.在求解優(yōu)化問題時(shí)，引領(lǐng)蜂的數(shù)量等于跟隨蜂的數(shù)量，1個(gè)食物源對(duì)應(yīng)問題的一個(gè)可能解，食物源的存儲(chǔ)量對(duì)應(yīng)于解的適應(yīng)值.

假設(shè) xi=(xi1,xi2,…,xiD)表示第 i個(gè)食物源(i=1,2,…,SN)，D表示待優(yōu)化問題的維數(shù).算法首先根據(jù)問題域的范圍按下式產(chǎn)生一個(gè)初始種群：

式中，i=1,2,…,SN，j=1,2,…,D，rand 為(0,1)之間均勻分布的隨機(jī)數(shù)，Lj、Dj分別是蜂群搜索空間的下界和上界.初始化種群后，ABC算法根據(jù)蜜蜂的類型，把優(yōu)化過程分位下面3個(gè)階段.

1）引領(lǐng)蜂階段：每一只引領(lǐng)蜂在食物源xi附近采用如下搜索策略進(jìn)行搜索，并生成新食物源vi

式中，k∈{1,2,…,SN}和 j∈{1,2,…,D}是隨機(jī)選取的，但k≠i，φij是[-1,1]間的隨機(jī)數(shù)，若 vi處的蜂蜜量更多，則將其替換xi.

2）跟隨蜂階段：引領(lǐng)蜂在食物源附近搜索完畢后，跟隨蜂則根據(jù)從引領(lǐng)蜂處接收到的信息采用如下概率來選擇食物源

式中，Pi是第i個(gè)食物源被選中的概率，fiti為第i個(gè)食物源的適應(yīng)值.fiti計(jì)算公式為

式中，fi為第i個(gè)食物源的目標(biāo)函數(shù)值.跟隨蜂選中食物源后，采用與引領(lǐng)蜂相同的搜索策略在食物源附近進(jìn)行搜索并生成新食物源.

3）偵察蜂階段：若引領(lǐng)蜂對(duì)應(yīng)的食物源經(jīng)過limit次循環(huán)后仍未得到改進(jìn)，則放棄該食物源，且該食物源處的引領(lǐng)蜂就轉(zhuǎn)變?yōu)閭刹旆?，并按?1)重新隨機(jī)搜索一個(gè)新食物源.

3 基于混合搜索策略的人工蜂群算法

在ABC算法中，算法性能的優(yōu)劣在很大程度上取決于引領(lǐng)蜂和跟隨蜂所采用的搜索策略.但從式(2)可以看出，引領(lǐng)蜂和跟隨蜂所采用的搜索策略是在當(dāng)前食物源的鄰域內(nèi)產(chǎn)生新食物源，這使得算法具有較好的全局搜索能力，但局部搜索能力不足，該算法在收斂速度和求解精度等方面存在問題.受差分進(jìn)化算法中DE/rand/1和DE/best/1變異操作模式的啟發(fā)，專家們提出了如下搜索策略：

上式中，r，r1，r2∈{1,2,…,SN}，j∈{1,2,…,D}，r≠r1≠r2≠i，xbest為種群的全局最優(yōu)個(gè)體.

式(5)由種群中三個(gè)互不相同的隨機(jī)個(gè)體組成，有利于保持種群的多樣性，全局搜索能力強(qiáng)，但收斂速度較慢.式(6)由于有種群的全局最優(yōu)個(gè)體xbest作引導(dǎo)，因而局部搜索能力強(qiáng)，收斂速度快，但會(huì)加大算法陷入局部最優(yōu)的可能性.眾所周知，平衡全局搜索能力和局部搜索能力是智能優(yōu)化算法獲得較高性能的關(guān)鍵，但ABC算法中使用的單一搜索策略很難同時(shí)平衡算法的全局搜索能力和局部搜索能力.通過上述對(duì)式(5)和式(6)兩種搜索策略的分析，結(jié)合這兩種搜索策略的特點(diǎn)，本文提出一種新的混合搜索策略：

此外，ABC算法中的蜂群在對(duì)食物源的貪婪選擇過程中都是基于適應(yīng)值fiti，但由式(4)可以看出，若函數(shù)優(yōu)化問題的目標(biāo)函數(shù)值大于0且無限接近0時(shí)，對(duì)應(yīng)的適應(yīng)值fiti就不具有區(qū)分度.因此，本文算法在蜂群對(duì)食物源的選擇過程中直接采用目標(biāo)函數(shù)值fi來代替適應(yīng)值.

4 仿真實(shí)驗(yàn)

為驗(yàn)證ABCMSS算法的性能，選取8個(gè)常用的基準(zhǔn)測(cè)試函數(shù)用于仿真實(shí)驗(yàn)，表1給出了8個(gè)基準(zhǔn)測(cè)試函數(shù)的名稱、表達(dá)式、類型、搜索范圍和最優(yōu)值.其中，在函數(shù)類型中，U表示單峰函數(shù)，M表示多峰函數(shù)，S為可分函數(shù)，N為不可分函數(shù).

表1 基準(zhǔn)測(cè)試函數(shù)

4.1 ABCMSS算法與ABC算法的收斂性能比較

將ABCMSS算法與ABC算法在D=30時(shí)進(jìn)行仿真實(shí)驗(yàn)，并對(duì)測(cè)試結(jié)果進(jìn)行比較.實(shí)驗(yàn)時(shí)，種群規(guī)模均為SN=20，limit=SN×D，最大評(píng)價(jià)次數(shù)MaxFEs=5000D.兩種算法在每個(gè)函數(shù)上獨(dú)立運(yùn)行30次.

圖1 Schwefel 2.21函數(shù)收斂曲線

圖2 Quartic函數(shù)收斂曲線

在單峰函數(shù)的測(cè)試中，ABCMSS算法在解的精度和穩(wěn)定性兩方面都明顯優(yōu)于ABC算法.在多峰函數(shù)的測(cè)試中，對(duì)于f5(x)，ABCMSS算法和ABC算法都能得到理論最優(yōu)值，而對(duì)于f6(x)，ABCMSS算法可以求得理論最優(yōu)值，ABC算法則陷入局部最優(yōu)，對(duì)于其他的復(fù)雜多峰函數(shù)，ABCMSS算法的求解結(jié)果要明顯優(yōu)于ABC算法.

圖3 Ackley函數(shù)收斂曲線

圖4 Schaffer函數(shù)收斂曲線

圖1-圖4給出了ABCMSS算法和ABC算法對(duì)于部分測(cè)試函數(shù)在30維時(shí)的收斂曲線，從圖中可以看出，ABCMSS算法的收斂曲線下降速度比ABC算法的收斂曲線下降速度要快，且能夠收斂到較高精度的解.

4.2 ABCMSS算法與幾種改進(jìn)的ABC算法比較

為進(jìn)一步測(cè)試ABCMSS算法的性能，將其與GABC、MSSABC、ABCVSS等改進(jìn)算法在 時(shí)進(jìn)行了比較，所有算法的最大評(píng)價(jià)次數(shù)均為MaxFEs=5000D，SN=20，limit=SN×D.表2給出了4種算法的測(cè)試結(jié)果.

表2 4種算法的測(cè)試結(jié)果

從表2可以看出，在8個(gè)基準(zhǔn)測(cè)試函數(shù)中，對(duì)于f5(x)，4種算法都能求得理論最優(yōu)值，對(duì)于f6(x)，只有ABCMSS和ABCVSS兩種算法能求得理論最優(yōu)值，對(duì)于其他函數(shù)，ABCMSS算法在解的精度和穩(wěn)定性兩方面都優(yōu)于GABC、MSSABC以及ABCVSS等改進(jìn)算法.

5 結(jié)論

針對(duì)ABC算法搜索策略存在的不足，提出一種基于混合搜索策略的人工蜂群算法.在該算法中，引領(lǐng)蜂和跟隨蜂進(jìn)行鄰域搜索時(shí)混合使用兩種不同的搜索策略，使算法可以較好的平衡全局搜索能力和局部搜索能力，避免了ABC算法收斂速度慢和易陷入局部最優(yōu)的缺陷.8個(gè)基準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果表明，與基本人工蜂群算法及一些改進(jìn)的人工蜂群算法相比，新算法在優(yōu)化性能和魯棒性等方面有了較大的改善.下一步的研究工作將考慮把算法應(yīng)用到多目標(biāo)優(yōu)化、圖像處理等實(shí)際優(yōu)化問題中，并結(jié)合其他一些新興的智能優(yōu)化算法，提出性能更好的優(yōu)化算法.