改進人工蜂群算法

畢曉君，王艷嬌

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

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

1 人工蜂群算法

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

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

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

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

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

2 改進的人工蜂群算法

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

2.1 選擇策略的調整

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

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

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

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

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

2.2 最差蜜源的替換

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

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

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

2.3 基于改進人工蜂群算法的多峰函數優化

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

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

為避免這種現象的產生，結合NIT技術和改進的人工蜂群算法設計一種新的多峰優化方法，即:

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

由于小生境范圍大小相差較大，如果在各小生境內預設相同數目的個體進行進化就會造成較大范圍的小生境在固定迭代次數內未收斂，而較小范圍的小生境早就收斂、浪費時間，為此，自適應調節各小生境內的個體數目如下:

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

為了更好地了解該方法，下面給出本文提出的多分函數優化方法的實現步驟:

1)在定義域內設定較小步長，產生均勻分布的個體.

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

3)在各個小生境內執行改進的人工蜂群算法:

①初始化，設置相關的實驗參數，如引領蜂、跟隨蜂的最大種群大小，最大的迭代次數.

②確定小生境內的種群大小，并在小生境指定的范圍內產生隨機分布的個體.

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

④引領蜂隨機選擇蜜源并與自身蜜源進行交叉產生新的位置，與原位置進行比較，擇優標記蜜源.

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

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

⑦判斷是否達到了最大的迭代次數，如果達到記錄最優位置并轉到5)，否則轉至②.

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

5)輸出各小生境的最優位置.

3 實驗仿真與結果分析

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

3.1 FSABC算法的函數優化性能

表1 測試函數Table 1 Test function

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

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

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

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

由表2中數據可以得出以下結論:

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

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

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

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

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

3.2 多峰函數優化效果

為驗證本文提出的多峰優化方法是否有效，選取該領域廣泛采用的測試函數進行測試，如下:

一維測試函數1在定義域內有9個不等高不等距的峰.

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

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

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

測試函數5

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

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

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

測試函數4

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

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

3.3 檢測峰數的能力

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

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

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

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

圖5 二維函數尋優效果直觀圖Fig.5 The optimization effect of two-dimension

3.4 算法的精確性

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

表4 不同方法對函數4的仿真結果Table 4 Performance of function 4 based on several methods

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

表5 本文算法對函數4的仿真結果Table 5 Simulation of function 4 based on this method

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

表6 本文算法對函數5的仿真結果Table 6 Simulation of function 5 based on this method

從表中數據很容易看出本文方法給出的尋優結果十分接近理論值，即具有較高的尋優精度.

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

4 結束語

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

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

［2］暴勵，曾建潮.自適應搜索空間的混沌蜂群算法［J］.計算機應用研究，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］.計算機工程與應用，2009，45(31):53-55.DING Haijun，FENG Qingxian.Artificial bee colony algorithm based on Boltzmann selection policy［J］.Computer Engineering and Applications，2009，45(31):53-55.

［4］羅鈞，樊鵬程.基于遺傳交叉因子的改進蜂群優化算法［J］.計算機應用研究，2009，26(10):3751-3753.LUO Jun，FAN 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 ，Free 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］陸青，梁昌勇，楊善林，等.面向多模態函數優化的自適應小生境遺傳算法［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］薛文濤，吳曉蓓，徐志良.用于多峰函數優化的免疫粒子群網絡算法［J］.系統工程與電子技術，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.