基于錯(cuò)位突變策略的改進(jìn)人工蜂群算法

蔣 成，汪繼文，邱劍鋒

（1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院；2.安徽大學(xué) 計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230601）

1 引言

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

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

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

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

2 基本人工蜂群算法

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

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

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

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

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

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

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

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

3.1 錯(cuò)位突變策略

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

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

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

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

3.2 新的比較機(jī)制

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

3.3 排序選擇機(jī)制

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

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

3.4 算法的詳細(xì)步驟

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)前需要設(shè)置初始的參數(shù).最大循環(huán)次數(shù)為2000，種群規(guī)模為20(SN=10)，解空間的維數(shù)為10，limit的值等于SN*D也就是100.將基本ABC算法和改進(jìn)的DMABC算法分別運(yùn)行30次，結(jié)果的對(duì)比見表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都達(dá)到了理論最優(yōu)值.除了最終的優(yōu)化結(jié)果，收斂速度也是評(píng)判算法性能的標(biāo)準(zhǔn)之一.圖1中展示了基本ABC算法和DMABC算法的收斂速度對(duì)比.

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

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

表3 DMABC算法與其他ABC改進(jìn)算法的對(duì)比

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

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

5 結(jié)論

針對(duì)基本人工蜂群算法收斂速度較慢、容易陷入局部最優(yōu)的缺點(diǎn)，本文借鑒差分進(jìn)化算法的突變策略，在蜜蜂搜索過程中引入了錯(cuò)位突變策略，并改進(jìn)了基本人工蜂群算法的比較機(jī)制和選擇機(jī)制.通過對(duì)5個(gè)基準(zhǔn)函數(shù)的測(cè)試，證明改進(jìn)的DMABC算法在收斂速度和結(jié)果精度上均優(yōu)于基本ABC算法.筆者下一步準(zhǔn)備將DMABC算法應(yīng)用于實(shí)際問題中，例如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〕胡中華,趙敏.基于人工蜂群算法的機(jī)器人路徑規(guī)劃[J].電焊機(jī)，2009，39(4)：93-96.

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

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

〔11〕暴勵(lì)，曾建潮.一種雙種群差分蜂群算法[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〕陳國(guó)龍，陳火旺，郭文忠，等.基于隨機(jī)錯(cuò)位算術(shù)交叉的遺傳算法及其應(yīng)用[J].模式識(shí)別與人工智能，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.