基于小生境的菌群算法的改進(jìn)

羅 熹，周 鑫

(武漢理工大學(xué)理學(xué)院，湖北 武漢 430070)

菌群優(yōu)化算法(bacterial foraging optimization，BFO)是2002年由KEVIN提出來的一種基于大腸桿菌覓食行為模型的新的群智能算法[1－2]，它是一種簡單有效的隨機(jī)全局優(yōu)化技術(shù)，但是，基本BFO算法也存在精度不夠高、收斂速度不夠快的缺點(diǎn)。

在生物學(xué)上小生境是指特定環(huán)境下的一種組織結(jié)構(gòu)。在自然界中，特征、形狀相似的物種往往相聚在一起，并在同類中交配繁衍后代。小生境技術(shù)將每一代個體劃分為若干類，在每個類中選出若干適應(yīng)度較大的個體作為優(yōu)秀代表組成一個群，再在種群中以及不同種群之間雜交、變異產(chǎn)生新一代個體群[3]。同時(shí)采用預(yù)選擇機(jī)制和排擠機(jī)制或分享機(jī)制完成任務(wù)。加入了這種小生境技術(shù)的菌群優(yōu)化算法(NBFO)可以更好地保持解的多樣性，同時(shí)具有較高的全局尋優(yōu)能力和收斂速度，特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問題。

1 菌群優(yōu)化算法

菌群優(yōu)化算法只能指導(dǎo)優(yōu)化搜索，算法本身具備分布并行的尋優(yōu)能力、較好的全局搜索能力，具有對初值不敏感的特點(diǎn)。2002年，KEVIN通過大腸桿菌的覓食行為，提出了BFO算法，其定義菌群行為包括以下4個行為:趨向性行為，聚集行為，繁殖行為和遷徙行為。其中趨向性行為又包括兩個基本動作，即前進(jìn)和翻轉(zhuǎn)[4－5]。

假設(shè)要找到函數(shù)J(θ)的最小值，令j為趨向性行為的索引，k為繁殖行為的索引，l為遷徙行為的索引，并有如下變量假設(shè):p為搜索域的維數(shù);S為菌群總數(shù);Nc為趨向性行為總步數(shù);Ns為前進(jìn)長度;Nre為繁殖行為總步數(shù);Ned為遷徙行為總步數(shù);Ped為遷徙概率;C(i)為在隨機(jī)方向上進(jìn)行翻轉(zhuǎn)的步數(shù)。

令 P(i，k，l)={θi(j，k，l)}為每個菌群 S 內(nèi)成員在第j次趨向性行為、第k次繁殖行為以及第l次遷徙行為時(shí)的位置。令 J(i，j，k，l)為第 i個細(xì)菌在 θi(j，k，l)∈?p位置時(shí)的成本。

下面給出BFO算法的4種行為的數(shù)學(xué)表示:

(1)趨向性行為。這個過程模擬了大腸桿菌的前進(jìn)和翻轉(zhuǎn)動作。大腸桿菌以兩種方式進(jìn)行趨向:根據(jù)給出的方向前進(jìn)或進(jìn)行一定角度的翻轉(zhuǎn);或者在趨向的過程中交替進(jìn)行前進(jìn)和翻轉(zhuǎn)。根據(jù)以上假設(shè)，趨向性的過程可以用式(1)表示:

式中，Δ為隨機(jī)方向向量，元素值域?yàn)閇－1，1]。

(2)聚集行為。聚集行為是指一群大腸桿菌在受到外界刺激時(shí)，會產(chǎn)生一種化學(xué)物質(zhì)，幫助它們聚集成群，使得群體密度增加，以抵抗外界刺激。這個聚集成群的過程可由式(2)表示:

式中:Jcc[θ，P(j，k，l)]為需要進(jìn)行最小化的目標(biāo)函數(shù)，dattratant，ωattractant，hrepellant，ωrepellant分別為聚集系數(shù)和權(quán)重以及排斥系數(shù)和權(quán)重。

(3)繁殖行為。具有最小健康值的細(xì)菌最終將死掉，而更為健康的細(xì)菌則會生存下來，同時(shí)還會在同一個位置分裂成兩個相同的細(xì)胞，并進(jìn)行聚集等行為。

(4)遷徙行為。由于逐漸或突然的環(huán)境因素的變化，細(xì)菌會離開原有的環(huán)境，而出現(xiàn)在搜索域中新的區(qū)域內(nèi)。在BFO算法中為了模仿這一行為，可以隨機(jī)選擇一小部分細(xì)菌，對它們的位置進(jìn)行隨機(jī)地重新賦值。

BFO算法對每個細(xì)菌、每次循環(huán)過程都要進(jìn)行一次趨向性行為、聚集行為、繁殖行為和遷徙行為的運(yùn)算，其算法的復(fù)雜度為o(n4)，顯然這樣的算法收斂性是比較低的。且在BFO算法中考慮到細(xì)菌處理環(huán)境變化的一個過程，某些細(xì)菌可能會消失，但忽略了一部分細(xì)菌轉(zhuǎn)移到其他地方可能導(dǎo)致原本的收斂點(diǎn)轉(zhuǎn)移，從而降低BFO算法的收斂效率。

2 小生境及其與BFO算法的結(jié)合

小生境方法的基本思想來源于生物在進(jìn)化過程中總是與自己相同的物種生活在一起的特點(diǎn)[6－8]，反映到算法中就是使 BFO算法中的細(xì)菌個體在一個特定的生存環(huán)境中進(jìn)化，小生境BFO算法(NBFO)可以避免在進(jìn)化后期，適應(yīng)值高的個體大量繁殖而充滿整個群體。具體思想是:在每一代細(xì)菌進(jìn)化前，根據(jù)細(xì)菌之間的距離找到每個細(xì)菌小生境子的種群，每個小生境子種群由距離相似的個體組成，然后由BFO算法更新。進(jìn)化論中小生境概念是指生物在特定環(huán)境下的生存環(huán)境。其中“人以群分，物以類聚”反映了自然的進(jìn)化過程，同種生物之間存在著優(yōu)秀個體，不同生物之間存在著互相競爭和信息交換。“資源共享”體現(xiàn)在特定環(huán)境中共同生存的同種生物分享有限資源，互相協(xié)調(diào)達(dá)到共同進(jìn)化。

小生境粒子群算法主要分為兩個階段:①小生境技術(shù)首先根據(jù)細(xì)菌之間的距離找到每個例子的小生境群體，然后利用菌群優(yōu)化算法在每個小生境群體中進(jìn)行位置和適應(yīng)值的更新，其中菌群的群體最優(yōu)值在該小生境群體中起作用;②對于更新后的群體，根據(jù)細(xì)菌間的距離，利用共享機(jī)制提高細(xì)菌的適應(yīng)度，利用懲罰函數(shù)懲罰適應(yīng)度低的個體，保留每個粒子群的最優(yōu)個體，直到滿足終止條件。

2.1 小生境群體的劃分

對于細(xì)菌 θi(j，k，l)=(θi1，θi2，…，θip)，i=1，2，…，S，它的小生境群體是計(jì)算該細(xì)菌與其他細(xì)菌之間的范數(shù)。

對于給定限制參數(shù) σ0，如果 dik＜σ0，k=1，2，…，S，則該個體加入到該小生境群體θig，這里范數(shù)一般對于實(shí)值函數(shù)取為歐式距離。

2.2 細(xì)菌間的共享函數(shù)

細(xì)菌i與細(xì)菌j之間的共享函數(shù)為:

式中，λ為控制共享函數(shù)形狀的參數(shù)。

2.3 適應(yīng)值函數(shù)的更新

2.4 具體的算法流程

(2)按下列步驟確定小生境種群個體:①置i=1;②按照范數(shù)定義計(jì)算兩個細(xì)菌之間的距離;③根據(jù) dik＜σ0，k=i，i+1，…，N，確定小生境群 θig，gi為θig的元素個數(shù)，其中σ0依據(jù)問題NFP而定。

(3)按照菌群優(yōu)化算法對小生境群體進(jìn)行速度和適應(yīng)度更新:①初始化菌群算法各種行為的次數(shù)以及相應(yīng)的參數(shù);②按照菌群算法的趨向性行為更新各種細(xì)菌的位置、速度以及運(yùn)動方向。其中群體最優(yōu)值為小生境群體的最優(yōu)值，不再是整個群體的最優(yōu)值;③檢查條件，對于更新后的個

式中體 θi(j+1，k，l)按照式(1)對 θi(j，k，l)中的第 i個細(xì)菌進(jìn)行速度和位置的更新，得到個體的更新適應(yīng)度;④細(xì)菌完成繁殖行為和遷徙行為;⑤利用更新適應(yīng)度 J'(i，j，k，l)及懲罰函數(shù) Penalty對該子群中低適應(yīng)度的細(xì)菌進(jìn)行懲罰，即當(dāng) θj，θk∈Mgi，‖xj－xk‖ ＜L，L ＜σ 時(shí)，比較兩個細(xì)菌間的距離，并對其中適應(yīng)度較低的細(xì)菌進(jìn)行懲罰:Jmin(θj，θk)=Penalty，j，l=i，i+1，…，i+gi+1;⑥當(dāng) i+gi＜N，置 i←i+pi，返回步驟②，否則，進(jìn)入下一步。

(4)計(jì)算每個細(xì)菌的適應(yīng)值，保留最優(yōu)的適應(yīng)值和個體，檢查是否達(dá)到優(yōu)化條件，如果達(dá)到誤差精度，則結(jié)束，然后進(jìn)入下一個細(xì)菌的小生境進(jìn)行優(yōu)化。

(5)若沒有最優(yōu)值，則將每一個細(xì)菌的小生境群體保留的最優(yōu)個體組合成新的群體空間，并重復(fù)步驟(2)。

上述方法通過利用細(xì)菌間的距離劃分每個例子的小生境群體，然后在小生境群體內(nèi)利用菌群算法的進(jìn)化機(jī)理對群體內(nèi)的每個細(xì)菌進(jìn)行更新。對更新后的群體，利用共享機(jī)制算法更新適應(yīng)值，對于適應(yīng)值最低的例子利用懲罰函數(shù)進(jìn)行懲罰。

3 小生境菌群算法的性能測試

NBFO算法參數(shù)設(shè)置如表1所示。為了驗(yàn)證算法NBFO的有效性，將該算法用于優(yōu)化測試函數(shù) Shubert進(jìn)行測試[9]:

Shubert函數(shù)是極為困難的多峰值函數(shù)，函數(shù)在定義域 x，y∈(－10，10)上有760個局部極小值點(diǎn)，其中只有一個(－1.425 13，－0.800 32)為全局最小，最小值為－186.730 90。該函數(shù)極容易陷入局部極小值－186.340 00[10]。因此該函數(shù)僅含一個取最小值的解，Shubert函數(shù)在－10≤x，y≤10的函數(shù)圖像如圖1所示。NBFO算法尋找其最小值時(shí)的適應(yīng)值曲線和BFO適應(yīng)值曲線的比較如圖2所示。

從圖1可以發(fā)現(xiàn)NBFO算法在運(yùn)行完畢之后所產(chǎn)生的細(xì)菌盡可能地聚攏在某幾個最優(yōu)值的點(diǎn)上，而從圖2則可以發(fā)現(xiàn)NBFO在迭代到第2代時(shí)就已收斂到函數(shù)的最小值附近，然后菌群的最小值再產(chǎn)生微小的變化，并不斷向最小值逼近。

表1 NBFO算法參數(shù)設(shè)置

圖1 Shubert函數(shù)NBFO算法細(xì)菌的最終分布位置

圖2 BFO與NBFO函數(shù)迭代收斂圖

表2給出了計(jì)算20次Shubert函數(shù)最小值時(shí)，BFO算法和NBFO算法的比較，由表2可知，原始BFO算法雖然沒有陷入局部極小值－186.340 00，但由于全局尋優(yōu)能力的不足，往往陷入了其他的局部極小值中，計(jì)算結(jié)果在－186.705 00左右波動。而NBFO的算法不僅可以收斂到最小極值點(diǎn)，同時(shí)運(yùn)算的方差也遠(yuǎn)小于BFO。

表2 BFO與NBFO在Shubert函數(shù)上的測試結(jié)果(σ0=7)

表3則給出了BFO算法和NBFO算法在其他測試函數(shù)中的表現(xiàn)，并用平均值和標(biāo)準(zhǔn)差，評價(jià)了BFO和NBFO的優(yōu)劣。由表3可知，NBFO具有絕對的優(yōu)勢，能獲得較好的解，收斂成功率高。但是，在實(shí)際計(jì)算過程中，由于NBFO的小生境技術(shù)導(dǎo)致了NBFO的時(shí)間代價(jià)相對稍高。

表3 多個優(yōu)化函數(shù)測試表

4 結(jié)論

將進(jìn)化論中的小生境技術(shù)與菌群優(yōu)化算法結(jié)合，提出了小生境菌群算法，該算法在原菌群算法的基礎(chǔ)上引入了共享機(jī)制，對菌群進(jìn)行群聚分類，在經(jīng)過BFO算法的演化后提取出適應(yīng)度較高的細(xì)菌，組成下一代菌群進(jìn)行迭代。該算法克服了菌群算法收斂效率低，容易收斂到其他極值點(diǎn)的問題。用Shubert函數(shù)驗(yàn)證了該算法的性能，并與原算法進(jìn)行了比較，通過更多的優(yōu)化函數(shù)(Rosenbrock、Rastrigin和Ackley)說明了該算法可以獲得較好的解，極大地提高了收斂成功率。雖然該算法在原有算法的基礎(chǔ)上增加了群聚的過程，但是由于每次挑出了適應(yīng)度較大的細(xì)菌組成新的下一代菌群進(jìn)行迭代，有效地減少了循環(huán)迭代的次數(shù)，在提高收斂率的情況下，付出的時(shí)間代價(jià)相對較小。

[1] 黃席樾，張著洪，何傳江，等.現(xiàn)代智能算法理論及應(yīng)用[M].北京:科學(xué)出版社，2005:54－87.

[2] 黃友銳.智能優(yōu)化算法及其應(yīng)用[M].北京:國防工業(yè)出版社，2008:56－98.

[3] 黃聰明，陳湘秀.小生境遺傳算法的改進(jìn)[J].北京理工大學(xué)學(xué)報(bào)，2004，24(8):675 －678.

[4] SWAGATAM D，ARIJIT B，SAMBARTA D.Bacterial foraging optimization algorithm:theoretical foundations，analysis，and applications[M].Berlin:Springer，2009:23－55.

[5] ARIJIT B，SWAGATAM D，AJITH A，et al.Stability analysis of the reproduction operator in bacterial foraging optimization[J].Theoretical Computer Science，2008，411(21):2127 －2139.

[6] 章軍.小生境粒子群優(yōu)化算法及其在多分類器集成中的應(yīng)用研究[D].合肥:中國科學(xué)技術(shù)大學(xué)圖書館，2007.

[7] 周傳華.小生境量子遺傳算法及其在軟測量建模中的應(yīng)用研究[D].上海:華東理工大學(xué)圖書館，2007.

[8] 李孝源.動態(tài)環(huán)境下基于聚類的小生境微粒群算法的研究[D].湘潭:湘潭大學(xué)圖書館，2008.

[9] 周北岳，郭觀七.引入適應(yīng)值曲面結(jié)構(gòu)的小生境遺傳算法初探[J].岳陽師范學(xué)院學(xué)報(bào):自然科學(xué)版，2002，15(1):59 －62.

[10] 周北岳，鄧斌，郭觀七.基于小生境技術(shù)的改進(jìn)遺傳算法的研究[J].機(jī)械強(qiáng)度，2002，24(1):13 －16.