基于混沌趨化行為的人工蜂群算法

孫晨驁，臧培荃，吳 濱，顧曉峰，周長喜

（江南大學 電子工程系 輕工過程先進控制教育部重點實驗室，江蘇 無錫214122）

0 引 言

人工蜂群 （artificial bee colony，ABC）算法［1］存在收斂精度低、容易早熟的缺陷。針對該問題已經(jīng)有多種改進方案，例如，在蜂群的搜索方程中增加全局最優(yōu)解，可提高算法的收斂精度和速度［2］；利用極值優(yōu)化思想重新設計ABC算法中跟隨蜂的搜索方程，可提高算法的局部搜索能力［3］；通過引入當前最優(yōu)思想，蜂群在當前最優(yōu)解的基礎上進行搜索，可提高算法的收斂精度和速度［4］；根據(jù)領域蜜源質(zhì)量動態(tài)調(diào)整信息共享程度，也能加快算法的收斂速度［5］。為進一步改善ABC算法的性能，提出一種基于混沌趨化行為的人工蜂群 （CCABC）算法。改進后的算法結合細菌覓食算法的趨化性和混沌理論的遍歷性，克服標準ABC算法中隨機搜索更優(yōu)解的缺點，能更快地收斂到最優(yōu)解。

1 標準人工蜂群算法

在標準ABC算法中，蜂群由雇傭蜂、跟隨蜂和偵查蜂3組蜜蜂組成，其中蜂群、最小值優(yōu)化問題中的可行解以及解的適應度值等的定義可參考文獻 ［6］。雇傭蜂進行全局搜索，確定蜜源的信息并反饋給跟隨蜂；跟隨蜂選擇其中一個蜜源并在其周圍進行局部搜索，如果在設定的搜索次數(shù)limit內(nèi)未搜索到更好的蜜源，則放棄該蜜源，同時雇傭蜂變?yōu)閭刹榉洌㈦S機產(chǎn)生一個新的蜜源。

ABC算法的實現(xiàn)是一個迭代優(yōu)化過程，具體描述如下：對于最小值優(yōu)化問題，設f（x）是被優(yōu)化的目標函數(shù)，且有SN 個解，每個解Xi＝ （xi1，xi2，…，xiD）為D 維向量。在算法初始化階段，照式 （1）隨機產(chǎn)生SN 個解；開始迭代搜索過程，雇傭蜂根據(jù)式 （2）進行全局搜索，產(chǎn)生一組新解；新解vi的適應度優(yōu)于xi的適應度時更新解，否則保留xi；當所有雇傭蜂完成式 （2）計算后，跟隨蜂按式 （3）選取部分優(yōu)質(zhì)解，并在其附近進行局部搜索

其中，M 和N 分別表示搜索空間的上下限；i，j均為隨機選擇；φ為 ［－1，1］的隨機數(shù)，決定xi領域的生成范圍；fiti為xi對應的適應度，可由式 （4）計算得到

在搜索過程中，如果解xi經(jīng)過limit次迭代后仍未搜索到更好的解，則該解將被放棄；同時，對應的雇傭蜂變?yōu)閭刹榉?，并按照式?）在搜索空間隨機產(chǎn)生一個新的解。

2 改進的人工蜂群算法CCABC

從式 （1）和式 （2）中可發(fā)現(xiàn)，ABC 算法中的搜索過程都是隨機的，如果新個體優(yōu)于原個體則更新，否則不更新。這樣的隨機搜索過程降低了算法的搜索效率和收斂精度，而且跟隨蜂基于輪盤賭選擇優(yōu)質(zhì)蜜源的方式可能會使算法陷入局部最優(yōu)［7］。針對此問題，本文引入了細菌覓食算法中的趨化操作和混沌變量進行改進。

2.1 細菌趨化行為

細菌覓食優(yōu)化 （bacteria foraging optimization，BFO）［8］算法是Passino基于大腸桿菌在腸道內(nèi)吞噬食物的行為而提出的一種仿生類算法。BFO 算法包括趨化、復制和遷移3個步驟，其中細菌向營養(yǎng)豐富區(qū)聚集的行為稱為趨化，趨化過程包括翻轉(zhuǎn)和前進。細菌向任意方向移動單位步長稱為翻轉(zhuǎn)；如果翻轉(zhuǎn)后細菌的適應度得到改善，則沿同一方向繼續(xù)移動，直至適應度不再改善或達到預定步數(shù)Ns，此過程稱為前進。細菌的趨化行為具體描述如下

綜上可知，趨化行為可以提高算法的局部搜索能力，減小算法陷入局部最優(yōu)的概率，因此在ABC 算法中引入BFO 算法的趨化行為，將式 （2）的搜索策略分解為兩步

其中，式 （6）和式 （7）分別代表翻轉(zhuǎn)和前進，Li表示翻轉(zhuǎn)后過程的移動步長。

2.2 混沌優(yōu)化

混沌是自然界中普遍存在的一種非線性現(xiàn)象，具有隨機性和遍歷性等特點［10］。其基本原理為：通過混沌映射模型將需要優(yōu)化的參數(shù)映射到混沌變量空間，在混沌變量空間中進行尋優(yōu)搜索，最后將獲得的最優(yōu)解映射到原參數(shù)空間［11］。本文使用Logistic混沌映射模型，其迭代方程為

由于混沌的遍歷性可以提高局部搜索能力，所以在趨化操作的翻轉(zhuǎn)步驟中引入混沌變量，提出新的翻轉(zhuǎn)公式

式中：ch（i）——Logistic混沌變量序列，itx 和itmax——當前和最大迭代次數(shù)，exp（－itx／itmax）——動態(tài)參數(shù)，使最優(yōu)解搜索過程中，隨著迭代次數(shù)的增加，搜索空間逐漸減小，從而進一步提高算法的性能。

2.3 CCABC的算法流程

步驟1 設定最大迭代次數(shù)itmax，趨化行為中最大移動步數(shù)Ns，判斷雇傭蜂是否陷入停滯的參數(shù)limit，混沌序列長度K，解的維數(shù)D，解的數(shù)量SN。

步驟2 根據(jù)式 （8）生成Logistic混沌變量序列，根據(jù)式 （1）隨機產(chǎn)生SN 個可行解。

步驟3 根據(jù)式 （4）計算每個解的適應度。

步驟4 對每個雇傭蜂根據(jù)式 （9）進行翻轉(zhuǎn)操作，根據(jù)式 （7）進行前進操作，然后計算并比較適應度，如果得到改善則繼續(xù)進行前進操作，直至適應度不再改善或達到最大前進步數(shù)Ns。

步驟5 對每個跟隨蜂以式（3）計算概率，選擇優(yōu)質(zhì)解，執(zhí)行與步驟4中與雇傭蜂相同的操作，記錄未更新次數(shù)。

步驟6 檢查步驟5 中未更新次數(shù)是否達到設定值limit。若達到，則根據(jù)式 （1）產(chǎn)生一個新的解替代原來的解；若沒有達到，則繼續(xù)進行迭代運算。

步驟7 記錄并更新最優(yōu)解。

步驟8 檢查當前迭代次數(shù)是否達到最大迭代次數(shù)itmax，若達到，則結束算法并輸出最優(yōu)解；否則返回步驟3。

3 仿真實驗與分析

3.1 測試函數(shù)的選擇

為了測試CCABC算法的性能，使用5個典型測試函數(shù)進行仿真實驗，并與標準ABC 算法和文獻 ［3］中的Bestso－far ABC算法進行比較。表1列出了測試函數(shù)的搜索范圍和理論最優(yōu)值。Sphere和Step函數(shù)為單峰函數(shù)，主要測試算法的搜索精度；Rastrgin和Ackley函數(shù)為非線性多峰函數(shù)，存在多個局部極值點，主要測試算法的全局搜索能力［12］；Rosenbrock為復雜函數(shù)，其最小值位于拋物線形的山谷中，但山谷內(nèi)值的變化較小，找到最小值比較困難，所以該函數(shù)常用來測試算法的綜合性能。

表1 測試函數(shù)

3.2 仿真結果與分析

在對標準ABC、Best－so－far ABC （表2 中簡稱 BABC）和提出的CCABC這3種算法的仿真實驗中，設置最大迭代次數(shù)itmax＝1000，解的個數(shù)SN＝50，解的維度D＝30，最大前進步數(shù)Ns＝3，判斷停滯控制參數(shù)limit＝10，混沌序列長度K＝40。為了獲得可靠的實驗結果，進行50次獨立實驗取其平均值，結果列于表2，適應度的進化曲線示于圖1～圖5，其中表2中的時間表示搜尋最優(yōu)解過程達到穩(wěn)定的收斂精度所需的時間。

從表2 可以看出，對于Sphere 和Rosenbrock 函數(shù)，CCABC算法的各項測試數(shù)據(jù)明顯優(yōu)于標準ABC 算法和Best－so－far ABC算法。最優(yōu)值、最差值和均值的減小表明CCABC算法的收斂精度較高，方差的減小則表明CCABC算法的穩(wěn)定性較好。對于比較簡單的Step單峰函數(shù)，3種算法均能達到理論最優(yōu)值，但從迭代時間和圖2 可看出，CCABC算法迭代次數(shù)更少，收斂速度更快。對于多峰的Ackley和Rastrigin函數(shù)，搜索過程比較復雜，而CCABC算法中的前進操作增加了計算量，進而增加了迭代時間，但從均值中可以看出，其收斂精度得到了明顯提高。此外，從圖1～圖5中也可以直觀地發(fā)現(xiàn)，CCABC 算法的進化曲線最陡，迭代次數(shù)明顯少于其它兩種算法，平均適應度也顯著優(yōu)于其它兩種算法。

表2 函數(shù)測試結果

圖1 Sphere函數(shù)進化曲線

圖2 Step函數(shù)進化曲線

4 結束語

圖3 Rastrigin函數(shù)進化曲線

圖4 Ackley函數(shù)進化曲線

圖5 Rosenbrock函數(shù)進化曲線

通過在ABC算法中引入細菌覓食算法中的趨化操作和混沌變量，提出了一種基于混沌趨化行為的CCABC 算法。改進的算法將蜂群隨機搜索的過程分解為翻轉(zhuǎn)和前進兩步，并在翻轉(zhuǎn)過程引入混沌變量和動態(tài)參數(shù)，使蜂群在優(yōu)質(zhì)蜜源區(qū)能進行更細致的搜索。利用5個典型測試函數(shù)進行了仿真實驗，結果表明CCABC算法提高了局部搜索能力，具有更好的收斂精度和收斂速度。

［1］Akay B， Karaboga D. A modified artificial bee colony algorithm for real－parameter optimization ［J］.Information Sciences，2012，192：120－142.

［2］Zhu Guopu，Kwong Sam.Gbest－guided artificial bee colony algorithm for numerical function optimization ［J］.Applied Mathematics and Compution，2010，217 （7）：3166－3173.

［3］GE Yu，LIANG Jing，WANG Xueping.Improved artificial bee colony algorithms based on ectremal optimization strategy［J］.Computer Science，2013，40 （6）：247－251 （in Chinese）.［葛宇，梁靜，王學平.基于極值優(yōu)化策略的改進的人工蜂群算法 ［J］.計算機科學，2013，40 （6）：247－251.］

［4］Banharsakun A，Achalakul T，Sirrinaovakul B.The best－sofar selection in artificial bee colony algorithm ［J］.Applied Soft Computing，2011，11 （2）：2888－2901.

［5］WANG Hui.Improved artificial bee colony algorithm ［J］.Computer Engineering and Design，2011，32 （11）：3869－3872（in Chinese）.［王輝.改進的蜂群算法 ［J］.計算機工程與設計，2011，32 （11）：3869－3872.］

［6］LI Shuang，LI Wenjing，YANG Wen，et al.Research and implementation of parallel random perturbation artificial bee colony algorithm based on multi－core PC ［J］.Microelectronics and Computer，2012，29 （9）：63－66 （in Chinese）. ［李雙，李文敬，楊文，等.基于多核PC的人工蜂群并行算法的研究與實現(xiàn) ［J］.微電子學與計算機，2012，29 （9）：63－66.］

［7］WANG Xin，TAN Huazhong，JIANG Hua.Vedio watermark scheme based on improved artificial bee colony algorithm ［J］.Computer Engineering and Design，2014，35 （6）：2095－2099（in Chinese）.［王鑫，譚華忠，蔣華.基于改進人工蜂群算法的視頻水印［J］.計算機工程與設計，2014，35 （6）：2095－2099.］

［8］Passino KM.Bacterial foraging optimization ［J］.International Journal of Swarm Intelligence Research，2010，1 （1）：1－16.

［9］WU Bo，HE Chunmei.Task scheduling of multi－core processor system based on improved bacteria foraging optimization algorithm ［J］.Microelectonics and Computer，2013，30 （3）：143－147 （in Chinese）.［吳波，赫春梅.細菌覓食優(yōu)化算法在嵌入式系統(tǒng)多任務調(diào)度中的應用 ［J］.微電子學與計算機，2013，30 （3）：143－147.］

［10］FENG Bin，WANG Zhang，SUN Jun.Niche quantum－behaved particle swarm optimization with chaotic mutation operator［J］.Computer Applications and Software，2009，26（1）：50－52 （in Chinese）.［馮斌，王璋，孫俊.基于混沌變異算子的小生境量子粒子群算法 ［J］.計算機應用與軟件，2009，26 （1）：50－52.］

［11］LIU Daohua，YUAN Sicong，LAN Yang，et al.Method of particle swarm optimization based on the chaos map ［J］.Journal of XiDian University，2010，37 （4）：764－769 （in Chinese）.［劉道華，原思聰，蘭洋，等.混沌映射的粒子群優(yōu)化方法［J］.西安電子科技大學學報，2010，37 （4）：764－769.］

［12］ZHANG Xueyin，TIAN Xuemin，CAO Yuping.Artificial bee colony algorithm with modified search strategy ［J］.Journal of Computer Applications，2012，32 （12）：3326－3330 （in Chinese）.［張雪銀，田學民，曹玉蘋.改進搜索策略的人工蜂群算法［J］.計算機應用，2012，32 （12）：3326－3330.］