基于改進(jìn)收益分配的人工蜂群算法

曹萌萌，皇甫大恩，劉曉斐

（1.開封大學(xué) 信息工程學(xué)院，河南 開封475004；2.中國礦業(yè)大學(xué) 安全工程學(xué)院，江蘇 徐州221116）

0 引 言

人工蜂群算法［1－4］由于在進(jìn)化過程和選擇策略中具有更強(qiáng)的隨機(jī)性，在很多問題中的全局搜索能力優(yōu)于其它一些群體智能算法，但也減慢了算法收斂速度。許多國內(nèi)外學(xué)者從各個(gè)角度出發(fā)，提出了多種改進(jìn)人工蜂群算法。例如：Alatas利用混沌映射系統(tǒng)來自適應(yīng)調(diào)整參數(shù)，提出了CABC算法［5］；暴勵(lì)等結(jié)合差分進(jìn)化算法，提出了BDABC算法［6］；Kang等結(jié)合的Rosenbrock旋轉(zhuǎn)方向法，提出了RABC算法［7］；羅鈞等采用 “分段搜索”方式對食物源進(jìn)行貪婪更新，提出了SABC算法［8］；付麗等提出了一種引入跟蹤搜索和免疫選擇的人工蜂群算法［9］；冀俊忠等引入了 “引導(dǎo)素”的概念，提出引導(dǎo)素更新和擴(kuò)散機(jī)制的人工蜂群算法［10］；劉三陽等利用隨機(jī)動態(tài)局部搜索算子和采用基于排序的選擇概率的方法，提出了LRABC算法［11］。從改良人工蜂群算法中收益度分配的角度出發(fā)，同時(shí)在觀察蜂的更新公式中增加了全局最優(yōu)個(gè)體的信息反饋，提出了一種具有較快收斂速度的改進(jìn)人工蜂群算法。

1 人工蜂群算法

人工蜂群算法主要由3部分組成：采蜜蜂、觀察蜂和偵查蜂。其中，采蜜蜂和觀察蜂數(shù)量相等，用m表示。偵查蜂是當(dāng)采蜜蜂放棄一個(gè)蜜源后轉(zhuǎn)變而成的。算法首先在初始化時(shí)，隨機(jī)產(chǎn)成m個(gè)初始解，然后按照蜜蜂采蜜原理進(jìn)行搜索。搜索過程為：①采蜜蜂選擇記憶中鄰近的一個(gè)蜜源；②觀察蜂根據(jù)信息選擇跟隨其中一個(gè)采蜜蜂；③觀察蜂在鄰近的蜜源內(nèi)選中最好的蜜源；④采蜜蜂放棄原來的蜜源，變成偵查蜂，隨機(jī)搜索新的蜜源。

通過上述過程蜜蜂進(jìn)行搜索，每個(gè)蜜源表示一個(gè)可能解，蜜源的質(zhì)量對應(yīng)著解的質(zhì)量，用收益度值表示。觀察蜂選擇蜜源的概率公式為

式中：θi——第i個(gè)蜜源，i∈｛1，2，…，S｝，S——蜜源的個(gè)數(shù)，F(xiàn)（θi）——第θi處蜜源的收益度值。在比較θi周圍的蜜源后，觀察蜂選擇其中一個(gè)蜜源。新的蜜源位置計(jì)算公式如下

式中：φi（c）——θi附近隨機(jī)產(chǎn)生的更新步長，如果新蜜源適應(yīng)值大于原來蜜源適應(yīng)值即F（θi（c＋1））＞ F（θi（c）），則觀察蜂選擇新蜜源θi（c＋1）；否則維持不變。如果達(dá)到限定循環(huán)次數(shù)后，蜜源質(zhì)量仍然沒有得到提高，則采蜜蜂放棄該蜜源，變成偵查蜂，位置xi更新如下

其中，φ′為 ［0，1］內(nèi)服從均勻分布的隨機(jī)數(shù)。

2 改進(jìn)算法的實(shí)現(xiàn)

改進(jìn)人工蜂群算法與標(biāo)準(zhǔn)人工蜂群算法相比主要在以下兩個(gè)方面做了改進(jìn)：①改進(jìn)了蜂群算法中關(guān)于個(gè)體收益度的計(jì)算方法；②在觀察蜂的更新公式中增加了全局最優(yōu)個(gè)體的信息反饋，以加快算法的收斂速度。

2.1 收益度分配

人工蜂群算法中，收益度值時(shí)衡量蜜源位置好壞的一個(gè)度量值，因此受益度的計(jì)算是否合理對算法的性能有著直接而且非常重要的影響。在標(biāo)準(zhǔn)人工蜂群算法中收益度F（θi）計(jì)算公式為

式中：θi——第i個(gè)蜜源，i∈ ｛1，2，…，S｝，S表示蜜源的個(gè)數(shù)，fitness為函數(shù)適應(yīng)值。在式 （4）中，當(dāng)fitness＞1時(shí)，fitness值越大，蜜源位置就越差，收益度越小，這也與蜂群理論基本一致，但當(dāng)fitness＜1，且fitness趨近于0時(shí)，F(xiàn)（θi）趨近于常數(shù)1，這樣所有蜜源位置的受益度都基本相等，因此無法找出最優(yōu)蜜源位置，算法出現(xiàn)早熟現(xiàn)象。

為此，針對標(biāo)準(zhǔn)人工蜂群算法中在受益度分配上存在的不足的問題，提出了一種新的收益度計(jì)算方法。具體計(jì)算公式如下

對比標(biāo)準(zhǔn)蜂群算法收益度計(jì)算式 （4），在式 （5）中當(dāng)fitness＞1時(shí)，對fitness值進(jìn)行平方處理，有助于加大蜜源位置的區(qū)分度；當(dāng)0＜fitness＜1，由于fitness為double數(shù)據(jù)類型，因此1≤F（θi）＜309，且fitness相差一個(gè)數(shù)量級，F(xiàn)（θi）差值為1；fitness趨近于0時(shí)，F(xiàn)（θi）趨近于309，因此fitness＝0時(shí)，F(xiàn)（θi）＝309。由于目前的基準(zhǔn)測試函數(shù)最優(yōu)值多為0，因此式 （5）只是針對最優(yōu)值大于等于0的情況進(jìn)行討論，如fitness小于0需進(jìn)行轉(zhuǎn)換。

2.2 進(jìn)化策略

標(biāo)準(zhǔn)人工蜂群算法在更新策略中，沒有采用最優(yōu)蜜源位置進(jìn)行更新位置，而是采用根據(jù)蜜源位置的收益度大小，隨機(jī)選擇蜜源位置進(jìn)行更新的方法。這種方法使選擇策略具有更強(qiáng)隨機(jī)性，增加了算法的全局搜索能力，但是在很大程度上降低了算法的收斂速度，為此本文在蜜源位置更新公式中保留了隨機(jī)選擇蜜源位置進(jìn)行更新的方式，同時(shí)也增加最優(yōu)蜜源位置來更新蜜源位置。使算法性能更加均衡

2.3 改進(jìn)算法流程

改進(jìn)算法流程如圖1所示。

圖1 算法流程

改進(jìn)算法具體流程為：

（1）初始化種群，計(jì)算每個(gè)個(gè)體的適應(yīng)值；

（2）引領(lǐng)蜂根據(jù)式 （6）在蜜源附近進(jìn)行搜索產(chǎn)生新蜜源位置Vi，然后計(jì)算其適應(yīng)值；

（3）如果新蜜源Vi的適應(yīng)值好于原來蜜源Xi，則用新蜜源Vi替換原來蜜源Xi，將Vi作為當(dāng)前最蜜源，否則保持原來蜜源Xi不變；

（4）計(jì)算蜜源Xi的適應(yīng)值，根據(jù)式 （1）計(jì)算蜜源Xi的選擇概率值Pi；

（5）跟隨蜂根據(jù)概率Pi選擇蜜源，然后根據(jù)式 （6）再蜜源附近進(jìn)行搜索產(chǎn)生新蜜源Vi，計(jì)算新蜜源適應(yīng)值；

（6）同步驟 （3）；

（7）判斷是否滿足放棄蜜源條件，若滿足，則偵查蜂根據(jù)式 （3）產(chǎn)生一個(gè)新蜜源Xi代替原蜜源；

（8）記錄迄今為止最好的蜜源；

（9）判斷是否符合算法結(jié)束條件，不滿足繼續(xù)迭代，否則輸出結(jié)果。

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

3.1 測試函數(shù)

本文選擇8個(gè)經(jīng)典基準(zhǔn)函數(shù)進(jìn)行測試，具體形式如下：

（5）Schwefel函數(shù)：f（x）＝418.98288727243369·n＋范 圍 ［－500，500］，在（420.9687，420.9687，…，420.9687）處取得最小值0。

（7） Ackley 函 數(shù)： f（x） ＝－ 20exp（－ 0.2范圍［－32，32］，在 （0，0，…，0）處取得最小值0。

3.2 基準(zhǔn)函數(shù)測試

為更好地測試本文算法的性能，選擇標(biāo)準(zhǔn)ABC算法和改進(jìn)算法IABC算法［12］進(jìn)行對比測試實(shí)驗(yàn)。算法參數(shù)設(shè)置為，蜜蜂個(gè)數(shù)為40，函數(shù)維數(shù)為30，評估次數(shù)為12萬次。本文算法簡稱DABC算法，表1為3種算法在30維函數(shù)上的測試結(jié)果，表中結(jié)果均為算法獨(dú)立運(yùn)行30次的平均值。

表1 3種算法在30維函數(shù)上的測試結(jié)果

從表1的測試結(jié)果可知：DABC算法在8個(gè)測試函數(shù)中，有7個(gè)測試函數(shù)測試結(jié)果是最好的，其中有5個(gè)測試函數(shù)比其它兩種算法結(jié)果都好。特別是在Sphere函數(shù)，Schwefel 2.22函數(shù)，Rosenbrock函數(shù)和Schwefel 2.21函數(shù)上。DABC算法結(jié)果與其它兩種算法相比結(jié)果有大幅度的提高，例如，Sphere函數(shù)結(jié)果比其它算法高了23個(gè)數(shù)量級，Schwefel 2.22函數(shù)比其它算法高了12個(gè)數(shù)量級。

3.3 T檢驗(yàn)結(jié)果

為了方便在統(tǒng)計(jì)意義上比較多個(gè)算法的性能，采用T檢驗(yàn)對結(jié)果進(jìn)行分析，以此判斷本文算法與其它兩種算法的性能是否存在顯著性差異。t檢驗(yàn)的分位數(shù)為單側(cè)0.05，樣本容量為30，T檢驗(yàn)的臨界值通過查表為1.697。當(dāng)t＞1.697時(shí)說明DABC算法優(yōu)于該算法，標(biāo)記為 “＋”；當(dāng)t＜－1.697時(shí)說明DABC算法差于該算法，標(biāo)記為 “－”；否則，說明DABC算法與該算法無明顯差異，標(biāo)記為 “＝”。“w／t／l”表示DABC算法與所選算法相比在w個(gè)函數(shù)上優(yōu)于該算法，t個(gè)函數(shù)上無明顯差異，一個(gè)函數(shù)上差于該算法。表2為T檢驗(yàn)的測試結(jié)果。

表2 T檢驗(yàn)結(jié)果

從表2可以明顯看出，在8個(gè)測試函數(shù)中，本文算法與標(biāo)準(zhǔn)ABC算法在全部8個(gè)函數(shù)上結(jié)果都有顯著提高，與IABC算法在5個(gè)函數(shù)上結(jié)果都有顯著提高，其它3個(gè)函數(shù)測試結(jié)果無明顯差異。

3.4 高維函數(shù)測試

為進(jìn)一步檢測算法處理更高維數(shù)函數(shù)問題的能力。仍然選擇標(biāo)準(zhǔn)ABC算法和改進(jìn)算法IABC算法［12］進(jìn)行對比測試實(shí)驗(yàn)。函數(shù)維數(shù)為40，評估次數(shù)為24萬次，其它參數(shù)設(shè)置保持一致。3種算法的測試結(jié)果見表3，表中結(jié)果均為算法獨(dú)立運(yùn)行30次的平均值。

表3 3種算法在60維函數(shù)上的測試結(jié)果

由表3測試結(jié)果可知：DABC算法在8個(gè)測試函數(shù)中，有7個(gè)測試函數(shù)測試結(jié)果是最好的，其中有6個(gè)測試函數(shù)比其它兩種算法結(jié)果都好。并且對比表1和表3數(shù)據(jù)可知：ABC算法和IABC算法在維數(shù)增加后，有些函數(shù)的結(jié)果有明顯的下降趨勢，比如，Schwefel函數(shù)，而DABC算法結(jié)果則下降趨勢較慢，因此在60維函數(shù)測試中，DABC算法優(yōu)于其它算法的結(jié)果增加了一個(gè)。

3.5 魯棒性測試

為了進(jìn)一步驗(yàn)證DABC算法的魯棒性，選擇其中的4個(gè)測試函數(shù)繼續(xù)增加函數(shù)的維數(shù)進(jìn)行測試，其中評估次數(shù)為4000＊n，n為函數(shù)維數(shù)，算法的其它參數(shù)保持不變。

圖2為Sphere函數(shù)的測試結(jié)果，由圖可知，隨著函數(shù)維數(shù)的增長，測試結(jié)果基本上保持在10－58數(shù)量級左右，圖3為Schwefel 2.22函數(shù)的測試結(jié)果，與圖2一致，測試結(jié)果基本上保持在10－28數(shù)量級左右，相差一兩個(gè)數(shù)量級左右。圖4為Rastrigin函數(shù)的測試結(jié)果，所有維數(shù)結(jié)果都為0，沒有任何變化，圖5為Ackley函數(shù)的測試結(jié)果，雖然30維和40維之間，結(jié)果出現(xiàn)一定下降，但是總體上差異不大。綜上可知，隨著函數(shù)維數(shù)的增長，DABC算法的測試結(jié)果基本上保持在同一個(gè)數(shù)量之間，并沒有出現(xiàn)，明顯下降的趨勢。由此可見DABC算法具有很強(qiáng)魯棒性，且具有較強(qiáng)的處理高維復(fù)雜函數(shù)的能力。

圖2 Sphere函數(shù)的測試結(jié)果

圖3 Schwefel 2.22函數(shù)的測試結(jié)果

圖4 Rastrigin函數(shù)的測試結(jié)果

圖5 Ackley函數(shù)的測試結(jié)果

4 結(jié)束語

針對標(biāo)準(zhǔn)人工蜂群算法中在受益度分配上存在的不足，提出了一種新的收益度計(jì)算方法，同時(shí)在更新策略中增加最優(yōu)蜜源位置來更新蜜源位置。在8個(gè)測試函數(shù)的仿真結(jié)果中，與對比算法相比，DABC算法在30維和60維上測試結(jié)果都優(yōu)于其它兩種，T測試表明DABC算法在大多數(shù)函數(shù)上測試結(jié)果都有顯著性提高；此外，進(jìn)一步加大函數(shù)維數(shù)測試結(jié)果表明DABC算法具有很強(qiáng)魯棒性，且具有較強(qiáng)的處理高維復(fù)雜函數(shù)的能力。

［1］GAO Xiangming，LIU Fubin，YANG Shifeng.Intelligent fault diagnosis of water supply network based on ELM ［J］.Computer Engineering and Design，2013，34 （8）：2887－2891（in Chinese）.［高相銘，劉付斌，楊世鳳.基于極限學(xué)習(xí)機(jī)的供水管網(wǎng)故障智能診斷方法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34 （8）：2887－2891.］

［2］YU Ming，AI Yueqiao.SVM parameter optimization and application based on artificial bee colony algorithm ［J］.Journal of Optoelectronics Laser，2012，23 （2）：241－243 （in Chinese）.［于明，艾月喬.基于人工蜂群算法的支持向量機(jī)參數(shù)優(yōu)化及應(yīng)用 ［J］.光電子激光，2012，23 （2）：241－243.］

［3］Singh A.An artificial bee colony algorithm for the leaf－constrained minimum spanning tree problem ［J］.Applied Soft Computing，2009，9 （2）：625－631.

［4］KANG Fei，LI Junjie，XU Qing.Hybrid simplex artificial bee colony algorithm and its application in material dynamic parameter back analysis of concrete dams ［J］.Journal of Hydraulic Enginessring，2009，40 （6）：736－742 （in Chinese）. ［康飛，李俊杰，許青.混合蜂群算法及其在混凝土壩動力材料參數(shù)反演中的應(yīng)用 ［J］.水利學(xué)報(bào)，2009，40 （6）：736－742.］

［5］Alatas B.Chaotic bee colony algorithms for global numerical optimization ［J］.Expert Systems with Applications，2010，37 （8）：5682－5687.

［6］BAO Li，ZENG Jianchao.A bi－group differential artificial bee colony algorithm ［J］.Control Theory and Applications，2011，28 （2）：266－272 （in Chinese）. ［暴勵(lì)，曾建潮.一種雙種群差分 蜂 群 算 法 ［J］.控 制 理 論 與 應(yīng) 用，2011，28 （2）：266－272.］

［7］Kang F，Li J，Ma Z.Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions［J］.Information Sciences，2011，181 （16）：3508－3531.

［8］LUO Jun，XIAO Xianghai，F(xiàn)U Li，et al.Modified artificial bee colony algorithm based on segmental search strategy ［J］.Control and Decision，2012，27 （9）：1402－1405 （in Chinese）.［羅鈞，肖向海，付麗，等.基于分段搜索策略的改進(jìn)蜂群算法 ［J］.控制與決策，2012，27 （9）：1402－1405.］

［9］FU Li，LUO Jun.Artificial bee colony algorithm with tracking search and immune selection ［J］.Pattem Recognition and Aitificial Intelligence，2013，26 （7）：688－694 （in Chinese）. ［付麗，羅鈞.引入跟蹤搜索和免疫選擇的人工蜂群算法 ［J］.模式識別與人工智能，2013，26 （7）：688－694.］

［10］JI Junzhong，WEI Hongkai，LIU Chunnian，et al.Artificial bee colony algorithm based on inductive pheromone updating and diffusion ［J］.Journal of Computer Research and Development，2013，50 （9）：2005－2014 （in Chinese）.［冀俊忠，魏紅凱，劉椿年，等.基于引導(dǎo)素更新和擴(kuò)散機(jī)制的人工蜂群算法 ［J］.計(jì)算機(jī)研究與發(fā)展，2013，50 （9）：2005－2014.］

［11］LIU Sanyang，ZHANG Ping，ZHU Mingmin.Artificial bee colony algorithm based on local search ［J］.Control and Decision，2014，29 （1）：123－128 （in Chinese）. ［劉三陽，張平，朱明敏.基于局部搜索的人工蜂群算法 ［J］.控制與決策，2014，29 （1）：123－128.］

［12］GAO Weifeng，LIU Sanyang，HUANG Lingling.Inspired artificial bee colony algorithm for global optimization problems［J］.Acta Electronic Sinica，2012，40 （12）：2396－2403 （in Chinese）.［高衛(wèi)峰，劉三陽，黃玲玲.受啟發(fā)的人工蜂群算法在全局優(yōu)化問題中的應(yīng)用 ［J］.電子學(xué)報(bào)，2012，40（12）：2396－2403.］