一種混合蜂群算法的自適應(yīng)細(xì)菌覓食優(yōu)化算法

杜鵬楨，唐振民，孫 研

(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094)

1 概述

細(xì)菌覓食優(yōu)化算法(Bacterial Foraging Optimization Algorithm,BFOA)[1]是一種模擬細(xì)菌覓食行為的群優(yōu)化算法，現(xiàn)已成功運(yùn)用于經(jīng)濟(jì)調(diào)度[2]、圖像處理[3]等領(lǐng)域。BFOA在適當(dāng)?shù)内吇介L(zhǎng)下，通過在解空間進(jìn)行連續(xù)的翻轉(zhuǎn)和泳動(dòng)可以達(dá)到較高的精度，是一種精細(xì)型搜索算法。但由于其采用直接復(fù)制的繁殖方式，降低了種群的多樣性，容易陷入局部最優(yōu)[4]。為克服基本BFOA存在的缺點(diǎn)，各學(xué)者提出了很多改進(jìn)方法，例如：文獻(xiàn)[5]將量子行為引入細(xì)菌的繁殖操作，增強(qiáng)了BFOA的種群多樣性，提高了算法的全局搜索能力；文獻(xiàn)[6-7]采用自適應(yīng)的趨化步長(zhǎng)，提高了算法的整體性能；文獻(xiàn)[8-9]分別將BFOA與其他算法相結(jié)合，改進(jìn)了繁殖方式，大幅提高了算法的求解質(zhì)量。

將多種算法進(jìn)行混合，發(fā)揮每個(gè)算法的優(yōu)點(diǎn)，是當(dāng)前智能優(yōu)化領(lǐng)域的研究熱點(diǎn)之一。文獻(xiàn)[10]研究表明，人工蜂群(Artificial Bee Colony,ABC)算法的尋優(yōu)能力與粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法相當(dāng)，強(qiáng)于差分進(jìn)化，且在同等條件下，ABC的收斂速度可達(dá)PSO的2倍[11]，是一種比較有競(jìng)爭(zhēng)力的新型智能優(yōu)化算法。為克服BFOA的缺點(diǎn)，本文將ABC的部分機(jī)理引入到BFOA中，提出一種混合ABC算法的自適應(yīng)BFOA算法(Bee Bacterial Foraging Optimization Algorithm,BBFO)。相比基本BFOA，BBFO有以下5點(diǎn)改進(jìn)：(1)提出雇傭蜂式趨化，對(duì)解空間進(jìn)行全局尋優(yōu)；(2)改進(jìn)BFOA原有趨化方式并自適應(yīng)調(diào)節(jié)趨化步長(zhǎng)，完成對(duì)解空間的局部調(diào)優(yōu)；(3)依據(jù)對(duì)種群的多樣性評(píng)價(jià)，完成2種趨化方式的自動(dòng)切換；(4)提出基于t分布擾動(dòng)的復(fù)制方式，提高種群多樣性；(5)提出基于對(duì)立學(xué)習(xí)的偵察蜂式遷移，避免算法早熟。

2 細(xì)菌覓食優(yōu)化算法

為方便描述，本文定義S個(gè)細(xì)菌組成的種群為：

其中，θi(j,k,l)表示第j次趨化，第k次復(fù)制，第l次驅(qū)散后的第i個(gè)個(gè)體。

BFOA把細(xì)菌覓食行為分解為趨化、聚群、復(fù)制和驅(qū)散4種算子。

(1)趨化算子模擬細(xì)菌向營(yíng)養(yǎng)豐富區(qū)域移動(dòng)的過程，包含翻轉(zhuǎn)和泳動(dòng)2種基本動(dòng)作。個(gè)體i在n維解空間 ?n按式(1)進(jìn)行翻轉(zhuǎn)，C(i)為趨化步長(zhǎng)。如果翻轉(zhuǎn)后細(xì)菌適應(yīng)值得到改善，則沿當(dāng)前方向φ(i)繼續(xù)泳動(dòng)預(yù)定步數(shù)Ns或泳動(dòng)到適應(yīng)值不再改善為止。

(2)聚群算子模擬個(gè)體間的相互影響，將個(gè)體間的吸引和排斥依式(3)計(jì)算為適應(yīng)值Jcc，并與個(gè)體原適應(yīng)值進(jìn)行疊加，見式(4)。其中，dattract，wattract，h r epellant 和wrepellant為預(yù)先設(shè)定的吸引因子、吸引權(quán)重、排斥因子和排斥權(quán)重。

(3)復(fù)制算子模擬種群的繁殖。種群經(jīng)過Nc次趨化后，依據(jù)適應(yīng)值的累加和進(jìn)行排序，較優(yōu)的 Sr=S /2個(gè)細(xì)菌進(jìn)行分裂繁殖，直接復(fù)制自身替換較差的Sr個(gè)細(xì)菌。

(4)驅(qū)散算子模擬種群的遷移。經(jīng)過Nre次復(fù)制后，個(gè)體以概率Ped隨機(jī)生成新個(gè)體，并替換原個(gè)體。

BFOA算法步驟如下：

步驟1初始化參數(shù)S,Nc,Ns,Nre,Ned,Ped,C(i),da,wa,hr和wr，在解空間 ?n內(nèi)隨機(jī)初始化種群。

步驟2循環(huán)執(zhí)行趨化算子Nc次，每次翻轉(zhuǎn)操作后執(zhí)行聚群算子。

步驟3執(zhí)行復(fù)制算子，復(fù)制算子執(zhí)行次數(shù)加1。若復(fù)制算子已執(zhí)行Nre次，執(zhí)行次數(shù)清0，轉(zhuǎn)去執(zhí)行步驟4，否則轉(zhuǎn)去執(zhí)行步驟2。

步驟4執(zhí)行驅(qū)散算子，驅(qū)散算子執(zhí)行次數(shù)加1。若驅(qū)散算子已執(zhí)行Ned次，算法結(jié)束，否則轉(zhuǎn)去執(zhí)行步驟2。

3 BBFO算法

3.1 趨化

BBFO算法采用2種趨化方式：雇傭蜂式趨化(Employed Bees Style Chemotaxis,EC)和改進(jìn)的自適應(yīng)步長(zhǎng)趨化(Improved Chemotaxis,IC)。

3.1.1 雇傭蜂式趨化

為提高BBFO的全局搜索能力，EC借鑒ABC雇傭蜂更新蜜源的方式[10]，步長(zhǎng)根據(jù)下式確定：

其中，Cec(i)表示個(gè)體i的趨化步長(zhǎng)；rand(-1,1)表示–1與1之間的隨機(jī)數(shù)；表示第k(k≠i)只細(xì)菌第j維的值，k和j均為隨機(jī)生成。在EC中，無翻轉(zhuǎn)操作，僅執(zhí)行單維度泳動(dòng)，個(gè)體i沿步長(zhǎng)Cec(i)泳動(dòng)，若適應(yīng)值無改善，則退回原來位置。

3.1.2 改進(jìn)的自適應(yīng)步長(zhǎng)趨化

基本BFOA對(duì)步長(zhǎng)較為敏感，取值大則全局搜索能力強(qiáng)，但精度下降；取值小則局部調(diào)優(yōu)能力強(qiáng)，但收斂速度下降，算法時(shí)間復(fù)雜度上升。在BBFO中，IC采用自適應(yīng)步長(zhǎng)，見式(6)，泳動(dòng)依然采用式(1)。

其中，Cic(i,j)表示第i個(gè)個(gè)體第j次趨化后的步長(zhǎng)；δ∈(0,0.95)為步長(zhǎng)縮減因子；Cinit(i)表示第i個(gè)個(gè)體的初始步長(zhǎng)；domxh為解空間定義域的右邊界；domxl為解空間定義域的左邊界；D為自然數(shù)。

3.2 種群多樣性的評(píng)價(jià)及趨化方式的切換

算法初始時(shí)，種群分散在一個(gè)較大空間，多樣性較強(qiáng)，此時(shí)適宜進(jìn)行全局搜索，加快算法收斂。隨著迭代次數(shù)的增加，種群不可避免地聚集在相對(duì)狹小的空間，此時(shí)更適宜進(jìn)行局部調(diào)優(yōu)，以提高求解精度。鑒于此，本文利用式(8)[12]評(píng)價(jià)種群多樣性，同時(shí)引入閾值 Pc，當(dāng) diversity(P) ＞Pc時(shí)，采用雇傭蜂式趨化進(jìn)行全局搜索并提高收斂速度，否則，采用改進(jìn)的自適應(yīng)步長(zhǎng)趨化，提高求解精度。當(dāng) diversity(P)較小時(shí)，種群多樣性較低，此時(shí)算法可能已經(jīng)陷入局部最優(yōu)，具體跳出局部最優(yōu)的方法將在下文進(jìn)行闡述。

3.3 基于t分布擾動(dòng)的復(fù)制方式

復(fù)制是BFOA的主要進(jìn)化操作[13]，為避免BFOA中直接復(fù)制所帶來的多樣性降低問題，BBFO采用基于t分布擾動(dòng)的復(fù)制方式，具體見式(9)。

其中，θi為被替換個(gè)體；θk為被復(fù)制個(gè)體；t(υ)表示自由度為υ的t分布。

t分布又稱學(xué)生分布，當(dāng)υ趨向無窮大時(shí)，等同于標(biāo)準(zhǔn)高斯分布，當(dāng)υ=1時(shí)，等同于柯西分布。本文將種群多樣性作為t分布的自由度，見式(10)，當(dāng)種群多樣性較低時(shí)，t分布近似于柯西分布，具有較大的擾動(dòng)，有利于跳出局部最優(yōu)，增強(qiáng)全局搜索能力；當(dāng)種群多樣性較高時(shí)，t分布近似于標(biāo)準(zhǔn)高斯分布，擾動(dòng)較小，更利于提高求解精度。

3.4 基于對(duì)立學(xué)習(xí)的偵察蜂式遷移

在ABC算法中，若蜜源一定次數(shù)內(nèi)無法被改善，則拋棄該蜜源，由相應(yīng)的偵察蜂重新對(duì)解空間進(jìn)行隨機(jī)搜索。BBFO借鑒偵察蜂方式，設(shè)立參數(shù)trails，若某個(gè)解連續(xù)trails次趨化無法被更新，則重新生成該解。由于BBFO是精細(xì)型搜索算法，為了避免在原位置附近進(jìn)行無用的搜索，同時(shí)提高跳出局部最優(yōu)的能力，本文采用對(duì)立學(xué)習(xí)的方法生成新解，遷移方式如下：

其中，θi為遷移個(gè)體；θio為θi的近似對(duì)立數(shù)；domxh為解空間定義域的右邊界；domxl為解空間定義域的左邊界。

3.5 算法流程

BBFO中不需要參數(shù)Ns，整個(gè)流程采用3層循環(huán)的框架，對(duì)大小為S的種群，需要 Ned×Nre×Nc次評(píng)價(jià)，其時(shí)間復(fù)雜度為O(Ned×Nre×Nc)，具體的流程如下偽碼所示：

4 仿真分析

為了驗(yàn)證BBFO的性能，本文選取10個(gè)Benchmark函數(shù)進(jìn)行測(cè)試，所有函數(shù)均為30維，理論最小值均為0，詳見表1。其中，f1～f7為單峰函數(shù)，用于測(cè)試算法的求解精度和收斂速度，f8～f10為多峰函數(shù)，用于測(cè)試算法的搜索能力和跳出局部最優(yōu)的能力。測(cè)試所引入的對(duì)比算法有：基本BFOA[1]，ABC[10]，BSA[7]，QBFO[5]和EDABFO[6]，相關(guān)參數(shù)參照相應(yīng)文獻(xiàn)。由于BBFO將ABC引入BFOA，因此本文將其與ABC和BFOA進(jìn)行縱向比較，同時(shí)，從混合型算法的角度出發(fā)，本文將BBFO與BSA、EDABFO和QBFO進(jìn)行橫向比較。BBFO參數(shù)設(shè)置如下：種群大小S=100，切換閾值 Pc=0.08，縮減因子 δ=0.08，定義域劃分?jǐn)?shù)D=50，遷移次數(shù) Ned=10，復(fù)制次數(shù)Nre=8，趨化次數(shù)Nc=40，總迭代次數(shù)為Ned·Nre·Nc= 320 0。仿真平臺(tái)CPU 2.9 GHz，內(nèi)存2 GB，VS2010編譯套件。

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

4.1 尋優(yōu)性能比較

針對(duì)表1函數(shù)，ABC、BFOA和BBFO各運(yùn)算30次，每次進(jìn)行3200次迭代，所得統(tǒng)計(jì)結(jié)果見表2。BFOA是一種精細(xì)型搜索算法，全局搜索能力較弱，在測(cè)試中效果不理想，相應(yīng)的，其局部尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)并未得到體現(xiàn)。ABC具有較強(qiáng)的全局搜索能力，也獲得了較為理想的效果，但與BBFO相比，還有較大的局部調(diào)優(yōu)空間。最優(yōu)值可以衡量算法的精度，平均值衡量算法的性能，標(biāo)準(zhǔn)差衡量算法的穩(wěn)定性。BBFO在各方面均優(yōu)于ABC和BFOA，兼具兩者優(yōu)點(diǎn)。最優(yōu)值和平均值的比對(duì)表明，BBFO在具有較高的全局尋優(yōu)能力的同時(shí)，保持了較高的局部調(diào)優(yōu)能力。標(biāo)準(zhǔn)差的對(duì)比結(jié)果表明BBFO具有較強(qiáng)的穩(wěn)定性。

表2 尋優(yōu)性能縱向?qū)Ρ?/p>

為進(jìn)一步驗(yàn)證BBFO的有效性，將其與BSA、EDABFO和QBFO進(jìn)行了橫向比對(duì)。其中，BBFO進(jìn)行1000次迭代，由于BBFO的2種趨化依據(jù)多樣性進(jìn)行自動(dòng)切換，因此切換閾值更改為Pc=0.15，結(jié)果見表3?？梢钥闯?，BBFO的平均值和標(biāo)準(zhǔn)差均優(yōu)于對(duì)比算法，表明BBFO具有較高的全局搜索能力，同時(shí)具有較強(qiáng)的魯棒性。

表3 尋優(yōu)性能橫向?qū)Ρ?/p>

4.2 收斂速度比較

收斂速度是衡量算法的重要指標(biāo)之一，為對(duì)BBFO的收斂速度進(jìn)行驗(yàn)證，本文選取Rosenbrock函數(shù)和Schwefel 1.2函數(shù)進(jìn)行測(cè)試。Rosenbrock函數(shù)在最優(yōu)值附近存在陡峭區(qū)域，易陷入局部最優(yōu)，相關(guān)算法在測(cè)試中效果并不理想，Schwefel 1.2函數(shù)最優(yōu)值存在于一個(gè)狹小區(qū)域，比較考驗(yàn)算法的局部調(diào)優(yōu)性能。結(jié)合4.1節(jié)尋優(yōu)性能的比對(duì)實(shí)驗(yàn)，可對(duì)算法進(jìn)行較為全面的測(cè)試。由圖1可見：(1)BFOA收斂速度曲線整體比較平緩；(2)迭代早期BBFO收斂速度與ABC相當(dāng)；(3)在某一迭代區(qū)間，BBFO開始高速收斂。BFOA全局搜索能力較弱，在2個(gè)測(cè)試中均未搜索到全局最優(yōu)區(qū)域，僅在局部最優(yōu)區(qū)域進(jìn)行調(diào)優(yōu)，因而整體效果較差。BBFO存在2種趨化方式，迭代早期種群多樣性較高，采用雇傭蜂式趨化，尋優(yōu)性能與ABC相當(dāng)。但從某個(gè)迭代區(qū)間開始，BBFO依據(jù)種群多樣性自動(dòng)切換為改進(jìn)的自適應(yīng)步長(zhǎng)趨化，在圖中表現(xiàn)為曲線的急速下降。從整體效果看，BBFO明顯優(yōu)于ABC和BFOA，充分證明了本文算法的有效性。

圖1 收斂速度比較

4.3 多樣性分析

在一般情況下，較高的種群多樣性，表示算法有更大的可能跳出局部最優(yōu)，可以有效避免早熟。但當(dāng)已經(jīng)搜索到全局最優(yōu)區(qū)域時(shí)，過高的種群多樣性反而表示算法收斂速度較低，局部調(diào)優(yōu)能力不足。BBFO中2種趨化方式的切換和t分布擾動(dòng)都基于種群多樣性。為驗(yàn)證BBFO中種群多樣性的重要性，對(duì)BFOA、ABC和BBFO進(jìn)行仿真比對(duì)，結(jié)果見圖2，從中可以看出，ABC一直保持較高的種群多樣性，具有較強(qiáng)的全局搜索能力，但結(jié)合圖1可見，在迭代后期，ABC的收斂速度明顯下降，表明ABC局部調(diào)優(yōu)能力不足。基本BFOA以固定概率進(jìn)行隨機(jī)遷移，很大程度上提高了種群的多樣性，但其繁殖方式導(dǎo)致多樣性迅速下降，所以多樣性曲線以固定迭代代數(shù)波動(dòng)。BBFO在迭代早期擁有較強(qiáng)的全局搜索能力，相應(yīng)多樣性保持在一個(gè)較高的水平上，在迭代后期，隨著趨化方式的改變，算法側(cè)重于局部調(diào)優(yōu)，種群多樣性迅速下降。特別的，圖2(a)中BBFO的多樣性曲線在迭代后期出現(xiàn)了劇烈的波動(dòng)，原因是基于t分布擾動(dòng)的復(fù)制方式在起作用，隨著多樣性的降低，t分布近似于柯西分布，可以產(chǎn)生較大的擾動(dòng)。整體來看，BBFO依據(jù)多樣性進(jìn)行趨化方式自動(dòng)切換的理念是合理可行的，效果非常明顯。

圖2 種群多樣性比較

5 結(jié)束語

在對(duì)細(xì)菌覓食優(yōu)化算法進(jìn)行研究的基礎(chǔ)上，本文提出一種混合蜂群算法的自適應(yīng)細(xì)菌覓食優(yōu)化算法(BBFO)。通過設(shè)計(jì)新的雇傭蜂式趨化方式提高了全局搜索能力，同時(shí)改進(jìn)BFOA原有趨化中的固定步長(zhǎng)為自適應(yīng)步長(zhǎng)，充分發(fā)揮了BFOA局部調(diào)優(yōu)能力強(qiáng)的優(yōu)點(diǎn)。在此基礎(chǔ)上，引入種群多樣性評(píng)價(jià)，并依據(jù)評(píng)價(jià)結(jié)果完成2種趨化方式的自動(dòng)切換。提出基于t分布擾動(dòng)的復(fù)制方式，有效提高了算法的收斂速度和求解精度。此外，還將種群多樣性作為t分布的自由度，使擾動(dòng)強(qiáng)度可以自適應(yīng)調(diào)節(jié)。為避免算法早熟，提出基于對(duì)立學(xué)習(xí)的偵察蜂式遷移，在跳出局部最優(yōu)的同時(shí)提高了種群的多樣性。實(shí)驗(yàn)結(jié)果表明，本文算法在尋優(yōu)能力、求解精度和收斂速度方面均優(yōu)于對(duì)比算法，并具有較強(qiáng)的穩(wěn)定性。下一步工作是利用該算法解決更高維復(fù)雜的工程問題，并應(yīng)用于相關(guān)收斂性理論的研究。

[1]Passino K M.Biomimicry of Bacterial Foraging for Distributed Optimization and Control[J].IEEE Control Systems,2002,22(3):52-67.

[2]Pandit N,Tripathi A,Tapaswi S,et al.An Improved Bacterial Foraging Algorithm for Combined Static/Dynamic Environmental Economic Dispatch[J].Applied Soft Computing,2012,36(12):3500-3513.

[3]Sathya P D,Kayalvizhi R.Modified Bacterial Foraging Algorithm Based Multilevel Thresholding for Image Segmentation[J].Engineering Applications of Artificial Intelligence,2011,24(4):595-615.

[4]Chatzis S P,Koukas S.Numerical Optimization Using Synergetic Swarms of Foraging Bacterial Populations[J].Expert Systems with Applications,2011,38(12):15332-15343.

[5]章國(guó)勇,伍永剛,譚宇翔.一種具有量子行為的細(xì)菌覓食優(yōu)化算法[J].電子與信息學(xué)報(bào),2013,35(3):614-621.

[6]王雪松,程玉虎,郝名林.基于細(xì)菌覓食行為的分布估計(jì)算法在預(yù)測(cè)控制中的應(yīng)用[J].電子學(xué)報(bào),2012,38(2):333-339.

[7]Tang W J,Wu Q H,Saunders J R.A Bacterial Swarming Algorithm for Global Optimization[C]//Proceedings of CEC’07.Singapore:IEEE Press,2007:1207-1212.

[8]劉小龍,趙奎領(lǐng).基于免疫算法的細(xì)菌覓食優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2012,32(3):634-637.

[9]劉小龍,李榮鈞,楊 萍.基于高斯分布估計(jì)的細(xì)菌覓食優(yōu)化算法[J].控制與決策,2011,26(8):1233-1238.

[10]Akay B,Karaboga D.A Modified Artificial Bee Colony Algorithm for Real-parameter Optimization[J].Information Sciences,2012,192(6):120-142.

[11]El-Abd M.Performance Assessment of Foraging Algorithms Vs.Evolutionary Algorithms[J].Information Sciences,2012,182(1):243-263.

[12]Sun J,Fang W,Palade V,et al.Quantum-behaved Particle Swarm Optimization with Gaussian Distributed Local Attractor Point[J].Applied Mathematics and Computation,2011,218(7):3763-3775.

[13]Abraham A,Biswas A,Dasgupta S,et al.Analysis of Reproduction Operator in Bacterial Foraging Optimization Algorithm[C]//Proceedings of CEC’08.Hong Kong,China:[s.n.],2008:1476-1483.