畢曉君，王艷嬌

(哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001)

Karaboga于2005年成功提出了解決函數(shù)優(yōu)化問題的人工蜂群算法(artificial bee colony algorithm，ABC算法)［1］，并與差分進化算法、粒子群算法等進行了比較，確定了ABC算法在函數(shù)優(yōu)化方面的優(yōu)越性，算法無需設(shè)置很多參數(shù)，操作簡單，特別適合工程應(yīng)用.然而，作為一種新的搜索算法，它的理論研究尚處于初級階段，文獻［2-3］分別引用聯(lián)賽選擇和boltzmann選擇方式代替ABC算法中的輪盤賭選擇方式;文獻［4］引入遺傳交叉因子增加種群多樣性，都在一定程度上降低了陷入局部最優(yōu)的可能，但收斂速度和精度并不高.為此，本文通過深入研究，借鑒自由搜索算法中提出的信息素、靈敏度模型代替輪盤賭方式進行選擇并引入OBL策略提出一種改進的人工蜂群算法，在此基礎(chǔ)上，結(jié)合NIT技術(shù)提出一種新的多峰優(yōu)化方法.優(yōu)化9個被廣泛選用的標準測試函數(shù)及5個多峰函數(shù)優(yōu)化實例.

1 人工蜂群算法

ABC算法模擬實際蜜蜂采蜜機制處理函數(shù)優(yōu)化問題，將人工蜂群分為3類:引領(lǐng)蜂、跟隨蜂和偵查蜂，引領(lǐng)蜂、跟隨蜂用于蜜源的開采，偵查蜂避免蜜源種類過少［1］.優(yōu)化問題的解及相應(yīng)的函數(shù)值抽象為蜜源的位置和花蜜的數(shù)量.尋找最優(yōu)蜜源的過程如下:隨機產(chǎn)生2N個位置，取較優(yōu)異的N個作為蜜源位置，引領(lǐng)蜂發(fā)現(xiàn)蜜源并記憶，在各蜜源附近按式(1)搜索新蜜源:

式中:Vij為新的蜜源位置，xij為蜜源的第j維位置，xkj為隨機選擇的不等于i的蜜源的第j維位置，Rij為［－1，1］間的隨機數(shù).

根據(jù)前后蜜源的花蜜數(shù)量(適應(yīng)度值)選擇較優(yōu)蜜源并作為初始標記蜜源;引領(lǐng)蜂釋放與標記蜜源質(zhì)量成正比的信息，用來招募跟隨蜂，跟隨蜂利用輪盤賭方式取合適的標記蜜源并在其附近按式(1)搜索新蜜源，并與初始標記蜜源進行比較，選取較優(yōu)異的蜜源更改本次循環(huán)的初始標記蜜源.但是如果在采蜜過程中，蜜源經(jīng)若干次搜索不變，相應(yīng)的引領(lǐng)蜂變成偵查蜂，隨機搜索新蜜源代替初始標記蜜源中的相應(yīng)位置，確定最終蜜源.按照上述方式反復(fù)循環(huán)迭代，直到達到算法的終止條件.

為了更進一步了解ABC算法，圖1給出了算法的程序流程.

圖1 ABC算法流程圖Fig.1 Flowchart of ABC algorithm

2 改進的人工蜂群算法

人工蜂群算法函數(shù)優(yōu)化效果較好，但由于采用輪盤賭選擇方式使算法易陷入局部最優(yōu)，而在迭代的過程中，每代的最差解會參與新解的產(chǎn)生從而影響了算法的收斂速度.為此，本文在選擇策略、最差解的替換方法方面做了改進.

2.1 選擇策略的調(diào)整

在ABC算法中，跟隨蜂選擇蜜源時依據(jù)輪盤賭方式，這是一種基于貪婪策略的選擇方式，會使種群多樣性降低，從而引起過早收斂和提前停滯的現(xiàn)象.在自由搜索算法中，提出了一個重要概念——靈敏度，通過與信息素(與優(yōu)化問題的適應(yīng)度值有關(guān))配合選擇區(qū)域，理論上可以搜索任何區(qū)域，這就在很大程度上避免了陷入局部最優(yōu);所搜索區(qū)域的信息素必須適應(yīng)其靈敏度，這就使算法有導(dǎo)向作用，決定了目標函數(shù)在搜索空間中的收斂和發(fā)散.這種區(qū)域選擇的方式與跟隨蜂選擇蜜源的方式是類似的，所以可以考慮將靈敏度與信息素配合的方式代替輪盤賭方式選擇蜜源.具體過程如下:

1)計算N個蜜源的適應(yīng)度值f(X).

2)計算第i個蜜源的信息素nf(i):

3)隨機產(chǎn)生第 i個跟隨蜂的靈敏度 S(i)～U(0，1).

4)找出配合第i個跟隨蜂靈敏度的蜜源:隨機找出 i，滿足 nf(i)≤S(i).

2.2 最差蜜源的替換

在ABC算法迭代的過程中，引領(lǐng)蜂和跟隨蜂都可能依賴本代的最差蜜源按式(2)進行交叉操作產(chǎn)生新蜜源，但最差蜜源幾乎不可能對需要的最優(yōu)結(jié)果做出貢獻，這就在一定程度上影響了算法的收斂速度.因此可以考慮產(chǎn)生一個新蜜源替換最差蜜源.鑒于文獻［11］已從數(shù)學(xué)上證明:依靠產(chǎn)生候選解的相對點取代原候選解的OBL策略是對原候選解的一種較好估計，與產(chǎn)生隨機點代替原候選解的方式相比，通常會取得更佳的優(yōu)化效果，不僅大大提高了收斂速度，而且在一定程度上避免了陷入局部最優(yōu).因此引用文獻［6］提出的OBL策略產(chǎn)生新蜜源取代最差蜜源.具體方式如下:

在每代循環(huán)中，找到最差蜜源，對應(yīng)位置為Xb.引用OBL后的新蜜源位置為則新位置的第j維X＇為bj

如果新位置對應(yīng)的蜜源更佳，則用其代替原蜜源位置.

2.3 基于改進人工蜂群算法的多峰函數(shù)優(yōu)化

文獻［12］運用NIT技術(shù)識別小生境范圍，結(jié)合適應(yīng)值共享小生境計算共享適應(yīng)度值，指導(dǎo)遺傳算法的種群進化，使種群多樣性不至于過少，用以解決多峰函數(shù)優(yōu)化問題.該方法也存在不能求得所有峰及峰值點定位不準確的缺陷.究其原因，隨著種群的進化，個體分布不再均勻，使得某些峰所在范圍內(nèi)的個體數(shù)目較少，如圖2所示.按照NIT技術(shù)的方法，會使得這2個小生境被規(guī)劃為一個小生境從而造成漏峰的現(xiàn)象.可見，個體的分布情況嚴重影響小生境的識別效果.而隨著進化的進行，很難保證可行域內(nèi)的個體分布均勻，即圖2所示的情況很容易出現(xiàn)，這也是造成漏峰現(xiàn)象的一個主要原因.

圖2 個體分布情況Fig.2 Distribution of individuals

為避免這種現(xiàn)象的產(chǎn)生，結(jié)合NIT技術(shù)和改進的人工蜂群算法設(shè)計一種新的多峰優(yōu)化方法，即:

首先，在可行域內(nèi)產(chǎn)生大量均勻分布的點，利用NIT技術(shù)劃分可行域為若干個小生境;然后，在各個小生境內(nèi)獨立運行人工蜂群算法若干次，以便精確鎖定各個小生境內(nèi)的峰值點.與現(xiàn)有利用NIT技術(shù)解決多峰函數(shù)優(yōu)化問題的方法相比:本文方法不與其他方法結(jié)合指導(dǎo)種群進化，避免了在進化過程中，因多樣性分布不均而造成的如圖2所示的現(xiàn)象，有效的避免了漏峰.

由于小生境范圍大小相差較大，如果在各小生境內(nèi)預(yù)設(shè)相同數(shù)目的個體進行進化就會造成較大范圍的小生境在固定迭代次數(shù)內(nèi)未收斂，而較小范圍的小生境早就收斂、浪費時間，為此，自適應(yīng)調(diào)節(jié)各小生境內(nèi)的個體數(shù)目如下:

其中，n為測試問題的維數(shù);BiH，BiL分別代表第i維小生境的邊界;r為一個人為設(shè)定的步長.上式代表某小生境內(nèi)的個體數(shù)目為在該范圍的長度與步長相除取整.為避免某小生境內(nèi)的個體數(shù)目過少，令該范圍內(nèi)的個體數(shù)目為一人為設(shè)定的常數(shù).

為了更好地了解該方法，下面給出本文提出的多分函數(shù)優(yōu)化方法的實現(xiàn)步驟:

1)在定義域內(nèi)設(shè)定較小步長，產(chǎn)生均勻分布的個體.

2)依據(jù)改進的NIT技術(shù)對種群進行小生境的識別，記錄各個小生境每維的上下限.

3)在各個小生境內(nèi)執(zhí)行改進的人工蜂群算法:

①初始化，設(shè)置相關(guān)的實驗參數(shù)，如引領(lǐng)蜂、跟隨蜂的最大種群大小，最大的迭代次數(shù).

②確定小生境內(nèi)的種群大小，并在小生境指定的范圍內(nèi)產(chǎn)生隨機分布的個體.

③選擇初始種群中較優(yōu)的一半個體作為初始標記蜜源.

④引領(lǐng)蜂隨機選擇蜜源并與自身蜜源進行交叉產(chǎn)生新的位置，與原位置進行比較，擇優(yōu)標記蜜源.

⑤跟隨蜂在蜜源中按照2.1中的新選擇方式選擇合適蜜源進行交叉操作產(chǎn)生新的位置.

⑥選擇和④⑤中的較為優(yōu)秀的個體作為本代的標記蜜源.

⑦判斷是否達到了最大的迭代次數(shù)，如果達到記錄最優(yōu)位置并轉(zhuǎn)到5)，否則轉(zhuǎn)至②.

4)判斷是否遍歷完所有小生境，如果已遍歷完轉(zhuǎn)至5)，否則更改小生境范圍，轉(zhuǎn)至3).

5)輸出各小生境的最優(yōu)位置.

3 實驗仿真與結(jié)果分析

先驗證提出改進算法(以下簡稱為FSABC算法)性能及應(yīng)用效果，需進行大量仿真實驗.實驗仿真是在 Intel Centrino Duo，CPU:T7250、1G 內(nèi)存、2.0 GHz主頻的計算機上實現(xiàn)，程序采用 Matlab7.5語言實現(xiàn).

3.1 FSABC算法的函數(shù)優(yōu)化性能

表1 測試函數(shù)Table 1 Test function

為驗證本文提出的FSABC算法的函數(shù)優(yōu)化效果好壞，選用函數(shù)優(yōu)化領(lǐng)域被廣泛采用的9個標準測試函數(shù)［10］進行測試，表1給出了這些測試函數(shù)的定義、取值范圍，它們的理論最優(yōu)值都為0.并將其與ABC算法及目前改進效果較好的ABCP算法［9］進行了對比.

函數(shù)1～4是連續(xù)型單模態(tài)函數(shù)，函數(shù)5為非連續(xù)的單模態(tài)函數(shù)，它們主要用來測試算法的尋優(yōu)精度，考察執(zhí)行性能;函數(shù)6為噪音函數(shù)，很難收斂到全局最優(yōu)解，其余函數(shù)都為復(fù)雜的多模態(tài)函數(shù)，有許多局部極值點，一般算法都難于找到全局最優(yōu)值，因此可用來檢測算法的全局搜索性能和避免早熟的能力.

算法具體參數(shù)設(shè)置如下:引領(lǐng)蜂、跟隨蜂和蜜源的數(shù)量都為50;測試函數(shù)都取50維;limit為10;各函數(shù)迭代1 000次.為了測試算法性能優(yōu)劣，針對每個測試函數(shù)，各算法均隨機運行50次，選取測試函數(shù)的最優(yōu)值、最差值、平均值、方差、平均運行時間(即獲得最優(yōu)解的時間)來考察算法的尋優(yōu)性能.

表2 3種算法的性能比較Table 2 Performance comparison of three algorithms

由表2中數(shù)據(jù)可以得出以下結(jié)論:

1)在尋優(yōu)性能上，ABC算法在解決不是很復(fù)雜的問題(如函數(shù)1和2)時，可以取得較好的效果，而在解決較復(fù)雜的函數(shù)時，基本不會得到滿意解;ABCP算法與之相比較，在處理較簡單問題時，解的精度有較大提高，但仍未達到理論最優(yōu)值，而在處理較復(fù)雜的多模態(tài)函數(shù)時，尋優(yōu)結(jié)果并不理想，說明ABCP算法雖有較好的執(zhí)行性能但易陷入局部最優(yōu)、全局尋優(yōu)性能較差;而本文提出的FSABC算法無論處理上述的哪種測試函數(shù)，幾乎都可以收斂到理論最優(yōu)解，而且算法較穩(wěn)定.由此可見，本文算法更容易跳出局部最優(yōu)，具有良好的全局搜索能力.

2)在運行時間上，雖然FSABC比ABC算法復(fù)雜一些，使迭代一次的時間有所增加，但FSABC算法獲得最優(yōu)解的迭代次數(shù)比ABC少得多，因此FSABC算法獲得最優(yōu)解的運行時間比ABC算法短，且比ABCP算法短得多，因此可以說本文算法縮短了運行時間.

為了直觀對比這3種算法的性能優(yōu)劣，圖3給出了2個函數(shù)的進化過程曲線.

圖3 3種算法的進化過程比較Fig.3 The Evolution com parison of three algorithms

由上述的數(shù)據(jù)比較及進化過程曲線可以得出結(jié)論，與目前現(xiàn)有的人工蜂群算法相比，本文提出的算法大大提高了尋優(yōu)能力，并且縮短了運行時間，具有良好的函數(shù)優(yōu)化效果.

3.2 多峰函數(shù)優(yōu)化效果

為驗證本文提出的多峰優(yōu)化方法是否有效，選取該領(lǐng)域廣泛采用的測試函數(shù)進行測試，如下:

一維測試函數(shù)1在定義域內(nèi)有9個不等高不等距的峰.

測試函數(shù)2 Ackley function在定義域 x，y∈［－3.5，3.5］內(nèi)有49 個極大值點.

測試函數(shù)3該函數(shù)是非均勻分布的多峰函數(shù)，有一個全局最優(yōu)值和99個局部極值，其中包含64個山峰和36個在 x，y∈［－2，2］邊界上形成的峰值點.一般算法很難搜索到所有峰.

該函數(shù)有6個高度為1的全局最優(yōu)解，在0.5高度處有一個很難突破的平坦區(qū)域，可用該函數(shù)的平均適應(yīng)度來評價算法收斂的準確性.

測試函數(shù)5

這是一個改進的Himmenblau函數(shù)，有一個全局最優(yōu)解和3個局部最優(yōu)解，定義域為x，y∈［－6，6］，全局最優(yōu)解位于(3，2)處，函數(shù)值為200.0，而局部最優(yōu)點位于(3.581 5，1.820 8)、(2.787 1，3.128 2)及(3.763 4，3.266 1)處，對應(yīng)的函數(shù)值分別為198.50，196.51 和 192.63.

測試函數(shù)1是較為復(fù)雜的一維多峰函數(shù)，用以驗證算法對于一維函數(shù)的優(yōu)化性能;函數(shù)2、3是典型的二維測試函數(shù)，具有較多個峰，常用以檢測算法識別出的峰數(shù)能力;而其余函數(shù)用以測試算法的精確性.

對一維函數(shù)測試的實驗參數(shù)設(shè)置如下:步長為0.1、各小生境的最少種群數(shù)目為8、常數(shù)為0.01.仿真結(jié)果如圖4所示.

測試函數(shù)4

圖4 一維測試效果Fig.4 The optimization effect one-dimension

從圖4可以看出，本文方法非常準確的鎖定了各個峰值點，一維多峰函數(shù)優(yōu)化效果很好.

3.3 檢測峰數(shù)的能力

為了驗證本文提出方法具有良好的識別峰數(shù)的能力，對函數(shù)3進行測試，參數(shù)設(shè)置為:以橫、縱軸的步長都為0.08產(chǎn)生小生境分割所需要的點，各小生境內(nèi)的最小種群數(shù)目為8、常數(shù)取為0.001，迭代次數(shù)為30.并與文獻［13］中方法進行比較，結(jié)果見表3.

表3 不同方法對測試函數(shù)3的仿真結(jié)果Table 3 Performance of function 3 based on several methods

從表中數(shù)據(jù)可以看出，與另外3種方法相比，該方法可以搜索到較多的峰，且需要較少的迭代次數(shù).這是因為在初始階段NIT技術(shù)可以較為準確的識別各個小生境，從而自動的劃分成多個種群，就不會因進化的趨向性使種群多樣性降低，因此具有較高的識別峰的能力.而對于Opt-aiNet算法，當目標函數(shù)的峰值較密集且大于種群規(guī)模時，開拓搜索空間的能力就會較差，不易搜索到所有峰值.

不失一般性，用該方法對測試函數(shù)2進行仿真，參數(shù)設(shè)置及實驗條件同上，函數(shù)2、3的仿真結(jié)果如圖5所示，從圖5可以直觀的看出本文方法具有很好的識別峰數(shù)的能力.

圖5 二維函數(shù)尋優(yōu)效果直觀圖Fig.5 The optimization effect of two-dimension

3.4 算法的精確性

為驗證提出算法不僅可以搜索到所有的峰還具有較高的尋優(yōu)精度，對函數(shù)4進行測試，參數(shù)設(shè)置除以橫、縱軸的步長都為0.1產(chǎn)生小生境分割所需要的點外，其他條件同上.并將其與文獻［4］中方法進行比較，比較結(jié)果如表4所示.

表4 不同方法對函數(shù)4的仿真結(jié)果Table 4 Performance of function 4 based on several methods

從表中數(shù)據(jù)可以看出，與另外2種較好的多峰優(yōu)化方法相比，該算法在較少的迭代次數(shù)下可以獲得更為精確地結(jié)果.這是由于在已精確劃定小生境范圍的基礎(chǔ)上，各小生境都是較為簡單的形狀，而改進的人工蜂群算法是一種非常優(yōu)秀的函數(shù)優(yōu)化方法，所以精確搜索到各個峰值點也是一個必然的結(jié)果.表5給出一次仿真結(jié)果.

表5 本文算法對函數(shù)4的仿真結(jié)果Table 5 Simulation of function 4 based on this method

為了進一步說明提出方法的普遍性，對函數(shù)5進行測試，參數(shù)設(shè)置除以橫、縱軸的步長都為0.2，產(chǎn)生小生境分割所需要的點外，其他條件同上.仿真結(jié)果見表6.

表6 本文算法對函數(shù)5的仿真結(jié)果Table 6 Simulation of function 5 based on this method

從表中數(shù)據(jù)很容易看出本文方法給出的尋優(yōu)結(jié)果十分接近理論值，即具有較高的尋優(yōu)精度.

綜上所述，本文提出基于人工蜂群算法的多模態(tài)優(yōu)化方法不僅具有較好的識別峰數(shù)的能力，而且尋優(yōu)精度較高，是一種行之有效的多峰優(yōu)化方法.

4 結(jié)束語

針對ABC算法易陷入局部最優(yōu)、收斂速度慢的缺點，本文利用信息素與靈敏度模型實現(xiàn)了概率選擇，引入OBL策略改變了每次迭代的最差解，由此提出一種改進的人工蜂群算法——FSABC算法.與傳統(tǒng)的ABC算法及ABCP算法相比，該算法獲得的最優(yōu)解精度明顯提高很多，而且只需要經(jīng)過較少次的迭代，也就是說算法的尋優(yōu)能力得到大幅度提高;在運行時間上，F(xiàn)SABC算法獲得最優(yōu)解的運行時間要比ABCP算法短得多，也比ABC算法短，即本文算法縮短了運行時間.該算法不僅大大提高了算法的尋優(yōu)能力，而且縮短了運行時間.基于這種函數(shù)優(yōu)化效果很好的改進人工蜂群算法及NIT技術(shù)而提出的兩階段多峰優(yōu)化方法，經(jīng)實驗證實不僅具有較強的識別峰的能力，而且精度很高.由此可見，本文提出的FSABC算法在解決函數(shù)優(yōu)化類問題上優(yōu)勢明顯.

［1］KARABOGA D，BASTURK B.On the performance of artificial bee colony(ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687-697.

［2］暴勵，曾建潮.自適應(yīng)搜索空間的混沌蜂群算法［J］.計算機應(yīng)用研究，2010，27(4):1331-1335.BAO Li，ZENG Jianchao.Self-adapting search space chaos-artificial bee colony algorithm［J］.Application Research of Computers，2010，27(4):1331-1335.

［3］丁海軍，馮慶嫻.基于Boltzmann選擇策略的人工蜂群算法［J］.計算機工程與應(yīng)用，2009，45(31):53-55.DING Haijun，F(xiàn)ENG Qingxian.Artificial bee colony algorithm based on Boltzmann selection policy［J］.Computer Engineering and Applications，2009，45(31):53-55.

［4］羅鈞，樊鵬程.基于遺傳交叉因子的改進蜂群優(yōu)化算法［J］.計算機應(yīng)用研究，2009，26(10):3751-3753.LUO Jun，F(xiàn)AN Pengcheng.Improved particle swarm optimization based on genetic hybrid genes［J］.Application Research of Computer，2009，26(10):3751-3753.

［5］PENEV K，LITTLEFAIR G ，F(xiàn)ree Search—a comparative analysis［J］.Information Sciences，2005，172(1):173-193.

［6］RAHNAMAYAN S，TIZHOOSH H R，SALAMA M M A.opposition-Based differential evolution［J］.IEEE Transactions on Evolutionary Computation ，2008，12(1):64-79.

［7］KARBOGA D，BASTURK B.A powerful and efficiental gorithm for numerical function optimization:artificial bee colony(ABC)algorithm［J］.Journal of Global Optimization，2007，39(3):459-471.

［8］TIAHOOSH H R.Opposition-based learning:a new scheme for machine intelligence［C］//Proceedings of International Computational Intelligence for Modeling Control and Automation.Sydney，Australia，2005:695-701.

［9］LIU Xingbao，CAI Zixing.Artificial bee colony programming made faster［J］.Natural Computation，2009(8):14-16.

［10］JANEZ B，SASO G，BORKO B.Self-adapting control parameters in differential evolution:a comparative study on numerical benchmark pro-blems［J］.IEEE Transactions on Evolutionary Comp-utation，2006，12(10):646-657.

［11］RAHNAMAYAN S，TIZHOOSH H R，SALAMA M M A.Opposition versus randomness in soft computing techniques［J］.Applied Soft Computing，2008，8(2):906-918.

［12］陸青，梁昌勇，楊善林，等.面向多模態(tài)函數(shù)優(yōu)化的自適應(yīng)小生境遺傳算法［J］.模式識別與人工智能，2009，22(1):91-100.LU Qing，LIANG Changyong，ZHANG Enqiao，et al.An adaptive niche genetic algorithm for multi modal function optimization［J］.Pattem Recognition and Artificial Intelligence，2009，22(1):91-100.

［13］薛文濤，吳曉蓓，徐志良.用于多峰函數(shù)優(yōu)化的免疫粒子群網(wǎng)絡(luò)算法［J］.系統(tǒng)工程與電子技術(shù)，2009，31(3):705-709.XUE Wentao，WU Xiaobei，XU Zhiliang.Immune particle swarm network algorithm formultimodal function optimization［J］.Journal of Systems Engineering and Electronics，2009，31(3):705-709.