孫晨驁，臧培荃，吳 濱，顧曉峰，周長(zhǎng)喜

（江南大學(xué) 電子工程系 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫214122）

0 引 言

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

1 標(biāo)準(zhǔn)人工蜂群算法

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

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

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

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

2 改進(jìn)的人工蜂群算法CCABC

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

2.1 細(xì)菌趨化行為

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

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

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

2.2 混沌優(yōu)化

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

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

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

2.3 CCABC的算法流程

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

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

步驟3 根據(jù)式 （4）計(jì)算每個(gè)解的適應(yīng)度。

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

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

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

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

表1 測(cè)試函數(shù)

3.2 仿真結(jié)果與分析

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

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

表2 函數(shù)測(cè)試結(jié)果

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

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

4 結(jié)束語(yǔ)

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

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

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

通過(guò)在ABC算法中引入細(xì)菌覓食算法中的趨化操作和混沌變量，提出了一種基于混沌趨化行為的CCABC 算法。改進(jìn)的算法將蜂群隨機(jī)搜索的過(guò)程分解為翻轉(zhuǎn)和前進(jìn)兩步，并在翻轉(zhuǎn)過(guò)程引入混沌變量和動(dòng)態(tài)參數(shù)，使蜂群在優(yōu)質(zhì)蜜源區(qū)能進(jìn)行更細(xì)致的搜索。利用5個(gè)典型測(cè)試函數(shù)進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明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）.［葛宇，梁靜，王學(xué)平.基于極值優(yōu)化策略的改進(jìn)的人工蜂群算法 ［J］.計(jì)算機(jī)科學(xué)，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ìn)的蜂群算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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的人工蜂群并行算法的研究與實(shí)現(xiàn) ［J］.微電子學(xué)與計(jì)算機(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ìn)人工蜂群算法的視頻水?。跩］.計(jì)算機(jī)工程與設(shè)計(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）.［吳波，赫春梅.細(xì)菌覓食優(yōu)化算法在嵌入式系統(tǒng)多任務(wù)調(diào)度中的應(yīng)用 ［J］.微電子學(xué)與計(jì)算機(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］.計(jì)算機(jī)應(yīng)用與軟件，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］.西安電子科技大學(xué)學(xué)報(bào)，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）.［張雪銀，田學(xué)民，曹玉蘋(píng).改進(jìn)搜索策略的人工蜂群算法［J］.計(jì)算機(jī)應(yīng)用，2012，32 （12）：3326－3330.］