蔣 成，汪繼文，邱劍鋒

（1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院；2.安徽大學(xué) 計算智能與信號處理教育部重點實驗室,安徽 合肥 230601）

1 引言

群智能算法是一類模擬自然界中某些動物群體行為的智能優(yōu)化算法.模擬的動物群體通常包括蟻群、鳥群和蜂群等等.這些動物群體都有一個共同的特點：當(dāng)我們僅僅觀察群體中的單個個體，往往是簡單而雜亂無章的；但當(dāng)這些個體合作形成群體的時候卻可以完成復(fù)雜的任務(wù)，表現(xiàn)出一定的智能.比較著名的群智能算法有蟻群算法[1,2]、粒子群算法[3,4]以及蜂群算法等等.蟻群算法主要是模擬螞蟻通過信息素搜索最佳路徑.粒子群算法是模擬鳥類的集群活動.蜂群算法則是模擬蜂群尋找最佳蜜源的行為.和傳統(tǒng)優(yōu)化算法相比，這些新型的群智能優(yōu)化算法收斂速度更快且易于實現(xiàn)，因此也引起了了很多研究者的興趣.

人工蜂群算法是由Karaboga[5]在2005年首次提出的.該算法將蜂群分成引領(lǐng)蜂、跟隨蜂和偵察蜂三類.不同類別的蜜蜂通過交換彼此的信息來完成覓食的任務(wù).由于人工蜂群算法的優(yōu)化效果不錯，而且操作簡單、控制參數(shù)少，算法提出后備受研究者們的關(guān)注.人工蜂群算法在函數(shù)優(yōu)化、生產(chǎn)調(diào)度、神經(jīng)網(wǎng)絡(luò)以及機器人路徑規(guī)劃等領(lǐng)域得到了廣泛的應(yīng)用.Karaboga和Gorkemli[6]將人工蜂群算法應(yīng)用于旅行商問題中.Ozturk[7]等使用了人工蜂群算法解決無線傳感器網(wǎng)絡(luò)的動態(tài)部署問題.胡中華等[8]實現(xiàn)了將人工蜂群算法應(yīng)用于機器人路徑規(guī)劃問題.肖永豪等[9]提出了一種基于蜂群算法的圖像邊緣檢測方法.

然而隨著對人工蜂群算法研究的深入，人們發(fā)現(xiàn)該算法同樣存在著缺點：算法收斂速度較慢，且容易陷入局部最優(yōu).針對這些缺點，國內(nèi)外的學(xué)者們相繼提出了改進的人工蜂群算法.丁海軍等[10]基于Boltzmann選擇機制提出了一種改進的人工蜂群算法用來優(yōu)化多變量函數(shù).暴勵等[11]結(jié)合差分進化算法提出了一種新的雙種群差分蜂群算法.Lee等[12]在人工蜂群算法中引入群體多樣性的機制，根據(jù)群體多樣性的門檻值選擇采用不同的搜索公式.Alam等[13]提出了一種基于指數(shù)分布的自適應(yīng)變異步長機制的人工蜂群算法，動態(tài)控制搜索過程中的探索和開發(fā)能力.

在人工蜂群算法中，全局搜索和局部開采的平衡是決定算法性能好壞的關(guān)鍵.本文在基本人工蜂群算法的基礎(chǔ)上，借鑒差分進化算法的突變算子，提出了一種新型的錯位突變策略，應(yīng)用于蜜蜂的搜索過程中，以提高種群的多樣性.同時，還用排序選擇機制代替了原來的輪盤賭選擇機制來防止算法的過早收斂.為了測試改進算法的性能，本文用了幾個標(biāo)準(zhǔn)測試函數(shù)來做實驗.實驗結(jié)果表明，改進算法的性能優(yōu)于基本人工蜂群算法.

2 基本人工蜂群算法

Karaboga提出的基本人工蜂群算法將蜜蜂分為三類：引領(lǐng)蜂、跟隨蜂和觀察蜂.蜂群在一個D維的空間中尋找蜜源，這里的D是在算法開始時人為設(shè)定的，在函數(shù)優(yōu)化問題中D就等于目標(biāo)函數(shù)的變量數(shù).一個蜜源對應(yīng)目標(biāo)函數(shù)的一個可行解.在算法中，蜜源用它在D維空間的位置向量表示.例如，第 i個蜜源用表示，向量中每個分量的取值范圍由目標(biāo)函數(shù)的解空間決定.尋找最優(yōu)蜜源，在本文中也就是尋找一組能讓目標(biāo)函數(shù)取得最小值的可行解.

蜂群分成兩半，一半是引領(lǐng)蜂，一半是跟隨蜂.引領(lǐng)蜂和蜜源一一對應(yīng)，每個引領(lǐng)蜂的位置就是一個蜜源的位置.因此，在程序中，引領(lǐng)蜂的數(shù)目、跟隨蜂的數(shù)目和蜜源的數(shù)目都相等，設(shè)為SN,則種群的規(guī)模也就是2*SN.SN也是一個需要人工設(shè)定的參數(shù).整個算法是一個循環(huán)算法.每次循環(huán)的開始，引領(lǐng)蜂會在各自對應(yīng)的蜜源周圍進行搜索.搜索的公式如下：

其中，φ(i,j)是-1到1的隨機數(shù)，k是引領(lǐng)蜂隨機選擇的一個鄰近蜜源，作為擾動項，增強全局搜索能力.引領(lǐng)蜂搜索的時候只改變位置向量的一個分量，這個要被改變的分量也是隨機選擇出來的.通過(2)式得到一個新的蜜源位置后，引領(lǐng)蜂會對新蜜源進行評估，計算出適應(yīng)度值與舊蜜源比較.適應(yīng)度的計算公式如下：

fi是用第i個蜜源的位置向量作為可行解計算出來的目標(biāo)函數(shù)值.從(3)式可以看出，目標(biāo)函數(shù)值越小，該蜜源的適應(yīng)度值就越大.引領(lǐng)蜂經(jīng)過比較后，如果新蜜源的適應(yīng)度值大于舊蜜源，則更新蜜源的位置；反之，則保留舊蜜源.跟隨蜂則通過輪盤賭機制選擇蜜源進行搜索.適應(yīng)度值越高的蜜源會有更大概率被跟隨蜂選中從而得到更新.跟隨蜂的搜索方程與引領(lǐng)蜂相同.輪盤賭的選擇概率使用下面的公式計算出來的：

由于人工蜂群算法有陷入局部最優(yōu)的可能，因此算法中設(shè)置了偵察蜂的操作來跳出局部最優(yōu).當(dāng)一個蜜源經(jīng)過很多次循環(huán)仍無法得到更新，那么該蜜源對應(yīng)的引領(lǐng)蜂就會轉(zhuǎn)化為偵察蜂，舍棄舊蜜源，在搜索空間內(nèi)隨機生成一個新的蜜源.偵察蜂的搜索公式如下：

lj和uj分別是搜索空間的下界和上界，rand(0,1)是0到1的隨機值.偵察蜂操作的觸發(fā)條件是有蜜源的停滯次數(shù)達到了限定值，姑且將這個限定值設(shè)為limit.limit的值是需要人工設(shè)定的.大量的實驗表明，limit的設(shè)定會影響到算法的效果，定值太小會減緩收斂速度，定值太大又起不到跳出局部最優(yōu)的效果.后來研究者們發(fā)現(xiàn)，將limit的值設(shè)為SN*D可以得到不錯的實驗效果，因此本文中l(wèi)imit的值也是SN*D.除此之外，還有一個最大循環(huán)次數(shù)需要人工設(shè)定，這是算法的終止條件.

3 基于錯位突變策略的人工蜂群算法

基本人工蜂群算法在搜索蜜源的時候，由于其搜索方向是隨機的，因此具有較好的全局搜索能力.但正因為它的搜索完全隨機，沒有任何啟發(fā)式的引導(dǎo)，不能利用上一代的搜索信息，導(dǎo)致算法在測試單峰函數(shù)時收斂速度很慢.為了提高人工蜂群算法的收斂速度，加強局部搜索能力，首先，本文采用了錯位突變策略對蜜蜂的搜索公式進行改進.既加快了優(yōu)化單峰函數(shù)時的收斂速度，也能在優(yōu)化多峰函數(shù)時仍保持較好的全局搜索能力.其次，基本人工蜂群算法在比較蜜源的好壞時用的衡量標(biāo)準(zhǔn)是適應(yīng)度值，而根據(jù)(3)式計算適應(yīng)度值會出現(xiàn)“大數(shù)吃小數(shù)”的情況導(dǎo)致后期無法準(zhǔn)確比較蜜源好壞.因此，本文將直接通過比較函數(shù)值大小來評估蜜源以避免出現(xiàn)上述情況.最后，輪盤賭選擇機制在適應(yīng)度值相差較大的時候，只選較好蜜源而讓差蜜源遲遲得不到更新，破壞了種群的多樣性.本文使用排序選擇機制代替輪盤賭，讓蜜源被跟隨蜂選中的概率只與該蜜源的序號有關(guān)，從而差的蜜源也有被選中的機會.下面是對改進之處的詳細介紹.

3.1 錯位突變策略

在人工蜂群算法的改進算法中，將差分進化算法與人工蜂群算法融合是一種很有效的辦法.差分進化算法是一種啟發(fā)式的優(yōu)化算法，它和遺傳算法類似，也具有交叉、選擇和突變的操作.其中，差分進化算法的突變操作和人工蜂群算法中的蜜蜂搜索操作很相似.在文獻[14]中，作者借鑒差分進化算法的突變策略，將人工蜂群算法的搜索公式改成：

其中，best是指當(dāng)前所有蜜源中的最優(yōu)蜜源，r1和r2都是隨機選擇的臨近蜜源，且best≠r1≠r2.由于新的搜索公式引入了全局最優(yōu)的蜜源作為引導(dǎo)，不再像基本人工蜂群算法中那樣盲目搜索，改進算法在單峰函數(shù)上的收斂速度明顯提高.但正因為最優(yōu)蜜源向?qū)У募尤?，蜜蜂都往最?yōu)蜜源區(qū)域探索，削弱了種群的多樣性，導(dǎo)致改進算法在多峰函數(shù)上的優(yōu)化效果并不令人滿意.為了保持種群的多樣性，本文將公式(6)當(dāng)中的最優(yōu)蜜源向?qū)Ц某呻S機臨近蜜源向?qū)?

另外，原來的突變策略只是在同一維上進行啟發(fā)式的突變.通過觀察大量的實驗數(shù)據(jù)，可以發(fā)現(xiàn)在算法運行的后期，同一維度上的數(shù)據(jù)非常相近甚至雷同，這樣的話同位突變的效果甚微.為了增強突變的效果，本文借鑒了文獻[15]中的錯位交叉算子，將公式(6)的同位突變改為錯位突變.新的搜索公式如下：

其中，j1和j2都是隨機生成的，且j1≠j2.公式(7)相比公式(6)，不再一味地向最優(yōu)蜜源探索，保護了種群多樣性，同時錯位突變的策略的加入可以更有效地利用其它維上的有利信息.

3.2 新的比較機制

在基本人工蜂群算法中，評估蜜源好壞的方法是比較它們的適應(yīng)度值.然而，通過(3)式計算出來的適應(yīng)度值有時候并不能真實的反映出蜜源的好壞.通過對基本人工蜂群算法的大量實驗，我們發(fā)現(xiàn)當(dāng)函數(shù)值被優(yōu)化到非常接近0的時候，用公式(3)計算會出現(xiàn)“大數(shù)吃小數(shù)”的情況.兩個數(shù)量級有差別但都非常接近0的函數(shù)值通過(3)式計算得到的適應(yīng)度值都是1.這樣的話，即使找到了更小的函數(shù)值也無法進行更新.為了避免這樣的情況發(fā)生，本文直接采用比較函數(shù)值來評價蜜源.

3.3 排序選擇機制

基本人工蜂群算法的輪盤賭選擇機制使跟隨蜂更偏向于適應(yīng)度高的蜜源.一旦出現(xiàn)超長個體，其適應(yīng)度值遠高于其他個體，跟隨蜂很難通過輪盤賭選到較差的個體，這樣很容易陷入局部最優(yōu)導(dǎo)致過早收斂.為了克服這一缺點，本文采用了文獻[16]提出的排序選擇機制.引領(lǐng)蜂操作完成后，算法將根據(jù)所有蜜源對應(yīng)的函數(shù)值排序，函數(shù)值越小的排序越靠前，序號也就越小.排序過后，每個蜜源被跟隨蜂選中的概率用公式(8)計算.

其中，d(t)是隨著循環(huán)次數(shù)變化的自適應(yīng)參數(shù).它的作用是保護種群多樣性，不讓蜜源選擇概率之間的差距過大.

3.4 算法的詳細步驟

（1）初始化：隨機生成SN個蜜源，計算出各蜜源的函數(shù)值，記錄最優(yōu)蜜源的函數(shù)值以及解向量；

（2）引領(lǐng)蜂根據(jù)式(7)搜索新蜜源，若新蜜源更好，則更新；反之，保留舊蜜源，該蜜源停滯次數(shù)加一.

（3）對所有蜜源進行排序，函數(shù)值最小的序號為1，依次往后排到SN.

（4）根據(jù)式(8)計算出各蜜源被跟隨蜂選中的概率.

（5）跟隨蜂按照上面算出的概率選擇蜜源，搜索方式與引領(lǐng)蜂相同.

（6）選出本輪循環(huán)最優(yōu)蜜源，與之前記錄的全局最優(yōu)蜜源比較，若本輪更好，則更新全局最優(yōu)蜜源；反之，無操作.

（7）檢查是否有蜜源的停滯次數(shù)達到limit.若有，則舍棄該蜜源，用式(5)生成新蜜源，計算出函數(shù)值.

（8）判斷是否達到最大循環(huán)次數(shù)Maxcycles.若達到，則終止；反之，返回第2步.

4 仿真實驗及結(jié)果分析

本文的實驗是將改進的算法應(yīng)用于函數(shù)優(yōu)化以測試其性能.選取的測試函數(shù)是5個常用的標(biāo)準(zhǔn)測試函數(shù)，見表1，其中UM代表單峰函數(shù)，MM代表多峰函數(shù).

表1 標(biāo)準(zhǔn)測試函數(shù)

實驗前需要設(shè)置初始的參數(shù).最大循環(huán)次數(shù)為2000，種群規(guī)模為20(SN=10)，解空間的維數(shù)為10，limit的值等于SN*D也就是100.將基本ABC算法和改進的DMABC算法分別運行30次，結(jié)果的對比見表2.

表2中，Best是指30次結(jié)果中最好的結(jié)果，Worst是指最差的結(jié)果，Mean是30次結(jié)果的平均值.Std則是30次結(jié)果的標(biāo)準(zhǔn)偏差，其值越接近0表示算法越穩(wěn)定.從表2可以看出，在單峰函數(shù)的優(yōu)化上，DMABC比基本ABC的優(yōu)化精度有大幅度提升；多峰函數(shù)優(yōu)化方面，Ackley函數(shù)兩者效果差不多，而在Griewank函數(shù)和Rastrigin函數(shù)上DMABC都達到了理論最優(yōu)值.除了最終的優(yōu)化結(jié)果，收斂速度也是評判算法性能的標(biāo)準(zhǔn)之一.圖1中展示了基本ABC算法和DMABC算法的收斂速度對比.

表2 基本ABC和DMABC優(yōu)化效果對比

圖1 各測試函數(shù)的收斂曲線圖

表3 DMABC算法與其他ABC改進算法的對比

從圖1中，可以看出，DMABC的收斂速度明顯優(yōu)于基本ABC.為了進一步測試DMABC的性能，本文還將DMABC和其他的ABC改進算法進行對比，初始參數(shù)與表2一致.選擇的ABC改進算法為基于DE差分進化算法的ABC/current_to_best以及基于反向輪盤賭機制的MABC算法，實驗的參數(shù)設(shè)置與之前一致.種群規(guī)模為20，維數(shù)為10，limit為100，最大循環(huán)次數(shù)為2000.實驗結(jié)果見表3.

從表3可以看出，與其他ABC改進算法相比，DMABC在Sphere函數(shù)和Griewank函數(shù)上表現(xiàn)最好，其他函數(shù)也有較好表現(xiàn).綜合來看，DMABC算法在函數(shù)優(yōu)化方面表現(xiàn)不錯，具有一定的實用性.

5 結(jié)論

針對基本人工蜂群算法收斂速度較慢、容易陷入局部最優(yōu)的缺點，本文借鑒差分進化算法的突變策略，在蜜蜂搜索過程中引入了錯位突變策略，并改進了基本人工蜂群算法的比較機制和選擇機制.通過對5個基準(zhǔn)函數(shù)的測試，證明改進的DMABC算法在收斂速度和結(jié)果精度上均優(yōu)于基本ABC算法.筆者下一步準(zhǔn)備將DMABC算法應(yīng)用于實際問題中，例如TSP問題、調(diào)度問題等等.

〔1〕Colorni A,Dorigo M,Maniezzo V,et al.Distributed optimization by ant colonies[A].Proc of European Conf on Artificial Life[C].Paris,1991:134-142.

〔2〕Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents [J].IEEE Transactions on Systems,Man,and Cybernetics-Part B(S1083-4419),1996,26(1):29-41.

〔3〕Fukuyama Y.Fundamentals of particle swarm techniques[A].Lee K Y,EI-Sharkawi M A.Modern Heuristic Optimization Techniques With Applications to Power Systems[M].IEEE Power Engineering Society,2002:45-51.

〔4〕Eberhart R C,Shi Y.Particle swarm optimization:developments,applications and resources[A].Proceedings of the IEEE Congress on Evolutionary Computation [C].Piscataway,NJ:IEEE Service Center,2001:81-86.

〔5〕Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Engineering Faculty Computer Engineering Department,Ereiyes University,2005.

〔6〕Karaboga D,Gorkemli B.A combinatorial artificial bee colony algorithm for travelling salesman problem[C].International Symposium on Innovations in Intelligent Systems and Applications,Istanbul,2011:50-53.

〔7〕Ozturk C,Karaboga D,Gorkemli B.Probabilistic dynamic deployment of wireless sensor networksby artificial bee colony algorithm[J].Sensors,2011,11(6):6056-6065.

〔8〕胡中華,趙敏.基于人工蜂群算法的機器人路徑規(guī)劃[J].電焊機，2009，39(4)：93-96.

〔9〕肖永豪，余衛(wèi)宇.基于蜂群算法的圖像邊緣檢測[J].計算機應(yīng)用研究，2010，27(7):2748-2750.

〔10〕丁海軍，馮慶嫻.基于boltzmann選擇策略的人工蜂群算法[J].計算機工程與應(yīng)用，2009，45(1)：53-55.

〔11〕暴勵，曾建潮.一種雙種群差分蜂群算法[J].控制理論與應(yīng)用，2011，28(2):266-272.

〔12〕Lee W P,CAI W T.A novel artificial bee colony algorithm with diversity strategy[C].The 2011 7th International Cofnference on Natural Computation,Shanghai,2011:1441-1444.

〔13〕Alam M S,Uikabir M W,Islam M M.Self-adaption of mutation step size in artificial bee colony algorithm for continuous function optimization[C].The 2010 13th International Conference on Computer and Information Technology,Dhaka,Bangladesh,2010:69-74.

〔14〕Gao W F,Liu S Y.Improved artificial bee colony algorithm for global optimization.Information Process Letters[J].2011,111(17):871-882.

〔15〕陳國龍，陳火旺，郭文忠，等.基于隨機錯位算術(shù)交叉的遺傳算法及其應(yīng)用[J].模式識別與人工智能，2014,17(2):250-256.

〔16〕Bao L,Zeng J C.Comparison and analysis of the selection mechanism in the artificial bee colony algorithm[C].The 9th Int Conf on Hybrid Intelligent Systems.Shenyang:IEEE Press,2009:411-416.