基于Log-Linear 模型的Gauss-Cauchy自適應(yīng)細(xì)菌覓食算法?

王 圣 閆仁武

（江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212003）

1 引言

由于國民經(jīng)濟和科學(xué)技術(shù)發(fā)展迅速，傳統(tǒng)的優(yōu)化算法已經(jīng)不能滿足人們在實踐中解決問題，一些具有全局優(yōu)化性能、極高通用性的算法受到各個領(lǐng)域的關(guān)注及應(yīng)用。其中最具代表性的進化算法是20世紀(jì)70年代來源于孟德爾遺傳定律和達(dá)爾文自然 選 擇 學(xué) 說 的 遺 傳 算 法［1］（Genetic Algorithm，GA）。Dorigo 等提出了蟻群優(yōu)化算法［2］（ACO）。Passion 模擬大腸桿菌在人體腸道內(nèi)吞噬食物的行為，提出了細(xì)菌覓食算法［4］（Bacteril Foraging Algorithm，BFA），該算法成為生物啟發(fā)式計算研究領(lǐng)域的又一熱點。

但是任何不同的算法都具有不同的特點。例如，雖然細(xì)菌覓食算法具有收斂速度快，易跳出局部最優(yōu)值的特點，但搜索能力和收斂精度方面仍較低。研究人員為了提高其性能，提出了與其他算法相融合的方法。與BFA 融合的算法主要有粒子群算法和分布估計算法等。儲穎等［5］通過借鑒PSO算法的信息共享機制，對BFA算法的群體感應(yīng)機制進行改進；麥雄發(fā)等［6］提出了一種混合PSO 的快速細(xì)菌覓食算法，該算法用粒子的移動代替細(xì)菌的趨向性操作，此兩種改進方法均使細(xì)菌的搜索能力得到提高。

綜上所述，為了解決BFA算法在運行過程中保持算法的多樣性，以及提高算法的收斂速度和尋優(yōu)精度，防止算法陷入局部極值的問題，本文仔細(xì)分析BFA算法生物基礎(chǔ)、基本操作、各類參數(shù)，并針對算法的缺陷，提出了一種基于Log-Linear 模型的Gauss-Cauchy自適應(yīng)細(xì)菌覓食算法（the New Bacterial Foraging Algorithm，NBFA）。

2 基本細(xì)菌覓食算法

細(xì)菌覓食算法是一種新興全局搜索算法。該算法主要通過趨向性操作、復(fù)制操作和遷移操作這三種操作的迭代計算來求解各類問題，下面介紹這三大操作及其流程［4，8～9］。

1）趨向性操作

細(xì)菌靠游動和翻轉(zhuǎn)在環(huán)境中進行搜索食物，這兩種基本行為可以確保細(xì)菌避開有毒環(huán)境和向食物濃度豐富的區(qū)域遷移。假如此刻食物濃度豐富，細(xì)菌的鞭毛會逆時針旋轉(zhuǎn)且方向向前游動進行消耗食物；若細(xì)菌所在區(qū)域的食物濃度高于以前位置時，細(xì)菌會增加移動的距離，這樣可以增加游動的時間；反之，當(dāng)細(xì)菌進入食物濃度低或毒性大的環(huán)境中，細(xì)菌的鞭毛先會順時針旋轉(zhuǎn)，然后停止此刻的前進方向，再接著進行翻轉(zhuǎn)隨機選擇一個方向繼續(xù)前進。因此上述的細(xì)菌行為轉(zhuǎn)化為算法趨向性操作的具體步驟是：算法計算初始，某個細(xì)菌在某個位置隨機選取方向并向前移動，若所在區(qū)域的適應(yīng)度值低于以前區(qū)域的值，細(xì)菌會依靠鞭毛的旋轉(zhuǎn)，再次隨機選取一個前進方向；若細(xì)菌在任意區(qū)域的適應(yīng)度值高于以前區(qū)域的適應(yīng)度數(shù)值，細(xì)菌不會改變方向并繼續(xù)向前遷移，直到遇到差的食物環(huán)境，會再次改變前進方向。

圖1 趨向性操作流程圖

2）復(fù)制操作

生物遵循著優(yōu)勝劣汰的自然法則，當(dāng)生物環(huán)境優(yōu)越，生物繁殖數(shù)能力加強，種群數(shù)量增加；當(dāng)生存環(huán)境遭到破環(huán)，生物的種群數(shù)量下降。面對上述情況，大腸桿菌生存能力較弱的群體會被環(huán)境淘汰掉，而細(xì)菌種群中覓食能力強的個體會存活下來并進行自我復(fù)制，這樣可以使得細(xì)菌種群數(shù)量不變，能夠確保算法的全局尋優(yōu)性。

初始時設(shè)i=0，圖2是BFA的復(fù)制操作流程圖。

圖2 復(fù)制操作流程圖

3）遷移操作

隨著細(xì)菌覓食程度加深，細(xì)菌種群可能會遭遇突發(fā)情況而影響細(xì)菌的生存和種群數(shù)量，進而影響算法收斂性和尋優(yōu)精度，所以為了避免這種情況的發(fā)生，細(xì)菌會自動調(diào)整姿態(tài)，主動向優(yōu)越的生存環(huán)境游動。雖然細(xì)菌的這一行為會破壞自身的趨向性操作，但從細(xì)菌生存角度來看，這是對細(xì)菌有利的，它可以利用遷移操作提高細(xì)菌尋找到優(yōu)良生存空間或高濃度食物的概率。

當(dāng)細(xì)菌執(zhí)行了k 次的復(fù)制操作后，大環(huán)境中全體細(xì)菌會發(fā)生遷移行為的概率是Ped，此時全體細(xì)菌個體會自動生成一個隨機數(shù)rand( )，當(dāng)細(xì)菌的隨機數(shù)小于遷移發(fā)生的概率（rand( )＜Ped），細(xì)菌就會自動死亡，同時在細(xì)菌可生存的區(qū)域內(nèi)任一位置隨機生成新的個體，以此來代替因隨機數(shù)小于遷移發(fā)生概率Ped而死亡的細(xì)菌，但新生細(xì)菌的覓食能力和位置信息等會與原來的細(xì)菌存在某些差異。遷移操作不僅能夠確保細(xì)菌種群的多樣性和可靠性，還能使新生細(xì)菌個體更靠近全局最優(yōu)解，能避免算法陷入局部最優(yōu)解，設(shè)i=0，rand（）是[0 ,1]區(qū)間中的隨機數(shù)，圖3是BFA的遷移操作流程圖。

圖3 遷移操作流程圖

設(shè)Nc、Nre、Ned分別是趨向性、復(fù)制和遷移操作的執(zhí)行次數(shù)，j、k、l分別表示這3 個操作的計數(shù)參數(shù)，初始時j=0，k=0，l=0，圖4是BFA的流程圖。

圖4 BFA流程圖

除了上述三個主要操作外，BFA還有群聚性的特點［4，8～9］。每個細(xì)菌個體除按照自己的方式搜索食物外，還收到種群中其他個體發(fā)出的吸引力信號。因此BFA 中的每一個細(xì)菌個體尋找食物的決策行為受兩個因素的影響：一是自身的信息，即個體覓食的目的，目的是使個體在單位時間內(nèi)獲取的能量最大；二是其他個體信息，即種群中其他細(xì)菌傳遞的覓食信息。

設(shè)表示種群中個體的位置，J( )i,j,k,l 表示細(xì)菌i在第j次趨向性操作第k 次復(fù)制操作和第l次遷移操作的適應(yīng)度數(shù)值，種群之間傳遞信號的影響值如式（4）所示：

3 改進的自適應(yīng)細(xì)菌覓食算法

NBFA 算法對基本BFA 的趨向、遷移行為進行了優(yōu)化，自適應(yīng)地調(diào)整步長C 的值，并引入Gauss-Cauchy變異。

3.1 基于Log-Linear模型的細(xì)菌覓食算法

細(xì)菌在覓食時會因自身和環(huán)境等情況而消亡，消失的細(xì)菌會影響種群數(shù)量進而影響算法精度，所以為了保持細(xì)菌種群在運算過程中不變，對細(xì)菌種群引入Log-Linear 模型［53］，確保了算法的候選可行解不會變動［10］，如式（6）所示：

3.2 優(yōu)化趨向、遷移行為

對細(xì)菌覓食算法的趨向和遷移兩個操作進行改進，并為了Log-Linear模型增加慣性權(quán)重系數(shù)［11］，如式（8）所示：

根據(jù)慣性權(quán)重優(yōu)化基本BFA中的趨向行為，細(xì)菌根據(jù)式（9）來更新自己的位置：

其中rand()是閉區(qū)間［-1，1］內(nèi)任意的數(shù)。

大腸桿菌在執(zhí)行遷移行為時可以根據(jù)式（10）來移動：

其中Xbest為細(xì)菌的最優(yōu)狀態(tài)。

3.3 C值的設(shè)置

在基本細(xì)菌覓食算法中，細(xì)菌移動步長C 被設(shè)定為一個固定值，但這種參數(shù)設(shè)定對算法的尋優(yōu)精度和收斂性造成不良的影響，進而影響算法運算的結(jié)果，使得求解出的調(diào)度方案不符合真實情況。如果將算法中細(xì)菌的移動步長C 值取的過高，細(xì)菌的覓食范圍較廣，算法的全局尋優(yōu)能力得到加強；若在BFA算法后期時C值取的較小，細(xì)菌的每次搜尋食物的范圍區(qū)域小，則可以借助這一特點，利用局部搜索來提高算法的尋優(yōu)精度。

可以用式（11）、（12）兩個公式來自適應(yīng)調(diào)整上述問題中步長系數(shù)的取值：

其中，G 和Gmax分別表示算法已經(jīng)執(zhí)行遷移次數(shù)和整個算法周期里執(zhí)行遷移的最大次數(shù)，式（11）乘積采用點乘。步長C 的值在算法初期時較大，可以提高算法的效率，使算法能夠在較大的范圍內(nèi)用較短的時間尋找到最優(yōu)值；隨著算法的進行，步長C的值逐漸減小，可以提高算法的尋優(yōu)精度。

3.4 Gauss-Cauchy變異

細(xì)菌執(zhí)行完遷移和復(fù)制操作后都會改變種群的生存環(huán)境，例如當(dāng)食物濃度降低時，細(xì)菌種群會集體向某一高食物濃度區(qū)域靠近，這種行為雖然能使細(xì)菌繼續(xù)生存，但缺乏整體信息的考慮，這樣使算法結(jié)果極易出現(xiàn)局部最優(yōu)值替代全局最優(yōu)值的情況，最終影響算法的收斂效率和尋優(yōu)精度。

為避免細(xì)菌覓食算法出現(xiàn)全局最優(yōu)值被局部最優(yōu)替代的問題，故對本算法執(zhí)行完復(fù)制和遷移操作后產(chǎn)生新細(xì)菌種群引入Gauss 和Cauchy 兩種變異，并且變異后的細(xì)菌最優(yōu)值與變異前公告板中細(xì)菌最優(yōu)值進行比對，若變異后的最優(yōu)值優(yōu)于變異前的最優(yōu)值，則將變異后的最優(yōu)值更新到公告板中；反之，公告板的最優(yōu)值不更新，但若兩次算法迭代過程中公告板的最優(yōu)值沒有更新則停止變異。這兩種變異可以保證細(xì)菌執(zhí)行完復(fù)制和遷移行為后種群的多樣性，讓細(xì)菌覓食算法在計算過程中更考慮整體信息。

細(xì)菌在執(zhí)行完復(fù)制行為后為保持細(xì)菌種群的多樣性，對細(xì)菌進行如式（13）的變異［14］：

其中N( 0,1) 服從均值0、均方差為1的Gauss分布，乘積采用點乘。

細(xì)菌在感應(yīng)到高濃度食物區(qū)域便會自動執(zhí)行遷移操作，使其個體向該區(qū)域游動，經(jīng)過細(xì)菌吸收完此區(qū)域的食物營養(yǎng)后，細(xì)菌的整體生存環(huán)境發(fā)生變化（食物濃度降低、酸堿度失衡、鹽度降低、水分減少等），細(xì)菌的生存能力降低致使種群數(shù)量減少，所以為了確保算法執(zhí)行完遷移操作后細(xì)菌種群的多樣性，對細(xì)菌進行了如式（14）所示的Cauchy 變異：

3.5 細(xì)菌覓食優(yōu)化算法思想和步驟

NBFA 算法思想：添加Log-Linear 模型改進大腸桿菌的趨向、遷移兩種基本覓食行為；添加Gauss-Cauchy 變異可以在整個算法周期內(nèi)保持細(xì)菌種群的多樣性，進而保證算法的收斂性和尋優(yōu)精度；并對大腸桿菌的移動步長C 進行自適應(yīng)調(diào)整，這樣能夠提升算法的收斂性和全局尋優(yōu)精度。

NBFA算法步驟如下。

步驟1）初始化：對細(xì)菌種群數(shù)數(shù)量初始化為N，以及移動步長C，細(xì)菌間擁擠程度系數(shù)（擁擠因子）λ。

步驟2）更新公告板：根據(jù)公式計算每個細(xì)菌的狀態(tài)，并在公告板上實時更新細(xì)菌的狀態(tài)信息。

步驟3）求解過程：將初始化的信息帶入算法中，執(zhí)行趨向、復(fù)制、遷移三種基本算法操作。

步驟4）自適應(yīng)調(diào)整C 的值：根據(jù)式（11）和式（12）對細(xì)菌覓食的移動步長C值進行自適應(yīng)調(diào)整。

步驟5）細(xì)菌種群變異：細(xì)菌個體在整個運算周期中執(zhí)行完復(fù)制和遷移兩個操作，便利用Gauss-Cauchy對細(xì)菌個體進行變異，當(dāng)細(xì)菌種群的多樣性與第一次變異前一致才停止對細(xì)菌的變異。

步驟6）判斷運算結(jié)果：對細(xì)菌覓食優(yōu)化算法的運算結(jié)果進行判斷，如果運算結(jié)果符合算法終止條件，則算法計算結(jié)束，輸出最終計算結(jié)果；如果計算結(jié)果不符合算法終止條件，則跳轉(zhuǎn)到步驟2）重新計算。

4 仿真實驗

選取以下六種函數(shù)作為證明細(xì)菌覓食優(yōu)化算法具有高性能特點的測試函數(shù)，選取其他改進方向的細(xì)菌覓食算法作為參照算法，并在Matlab環(huán)境下進行實驗。六種測試函數(shù)的全局最優(yōu)值都為0，四個改進算法分別計算六種測試函數(shù)而得出得全局最優(yōu)值和測試函數(shù)的全局最優(yōu)值0 進行比較來驗證NBFA算法的優(yōu)越性。

在實驗中四種算法分別對六種測試函數(shù)運行50 次以上，這樣可以避免算法結(jié)果的隨機性影響。將算法中的細(xì)菌種群數(shù)量設(shè)置為500，通過增加細(xì)菌種群的多樣性來提高算法的全局尋優(yōu)精度；整個算法運行周期允許最大迭代循環(huán)次數(shù)是500次，變量的維數(shù)為30，Cmin=0.5，λ=0.8。將文獻［7］中的EDA-BFO、文獻［16］中的BFAVP、文獻［17］中的ABFO算法與本文提出的NBFA算法進行實驗對比。表1～6 分別表示四種算法運行六種測試函數(shù)的實驗結(jié)果。

表1 四種算法測試f1 實驗數(shù)據(jù)

對比表1 的實驗數(shù)據(jù)可知，NBFA 算法的標(biāo)準(zhǔn)差最小，表明NBFA 算法求出的最優(yōu)值更加靠近平均最優(yōu)值。而且NBFA 算法求出最優(yōu)解的的全局迭代運行時間為12s，是四種算法中耗時最短的算法。綜上所述，NBFA 算法在求解測試函數(shù)f1時具有收斂效率高、尋優(yōu)精度高、可靠性強等優(yōu)勢。

對比表2的實驗數(shù)據(jù)，NBFA 算法的最優(yōu)解、平均最優(yōu)解、標(biāo)準(zhǔn)差、全局迭代運行時間均小于其他三種算法，可以得出NBFA在求解測試函數(shù)f2時具有優(yōu)越的全局和局部尋優(yōu)精度、收斂效率、可靠性等特點。NBFA 算法求出最優(yōu)值所耗費時間是24s，求解速度快于其他算法。

表2 四種算法測試f2 實驗數(shù)據(jù)

詳細(xì)分析表3 的實驗數(shù)據(jù)，NBFA 算法求解f3測試函數(shù)的最優(yōu)解、平均最優(yōu)解最靠近測試函數(shù)f3全局最優(yōu)值，標(biāo)準(zhǔn)差的值在四種算法實驗數(shù)據(jù)中是最小，說明NBFA 算法具有較高的可靠性、收斂效率、全局和局部尋優(yōu)精度。NBFA 算法求解最優(yōu)解的時間是19s，求解速度明顯快于其他三種算法。

表3 四種算法測試f3 實驗數(shù)據(jù)結(jié)果

測試函數(shù)f4的全局最優(yōu)值為0，由表4 的實驗數(shù)據(jù)可知，NBFA 算法的收斂效率、尋優(yōu)精度、可靠性等方面優(yōu)于其他算法，并且NBFA 算法求解測試函數(shù)f4的時間是38s，求解問題的速度明顯高于其他算法。

分析表5 的實驗數(shù)據(jù)，NBFA 算法的計算結(jié)果更加靠近測試函數(shù)f5的全局最優(yōu)值0，因此算法NBFA 的可靠性、收斂效率、尋優(yōu)精度高于其他算法；NBFA 算法求解測試函數(shù)f5的全局迭代運行時間是21s，該算法求解速度快且能夠節(jié)約研究者的時間。

根據(jù)表6 的實驗數(shù)據(jù)可知，NBFA 算法的運算結(jié)果相比其他三種算法更加靠近測試函數(shù)f6的全局最優(yōu)值0，標(biāo)準(zhǔn)差最低，求解f6函數(shù)時耗時最短（共69s）。故證明NBFA 算法的收斂效率、可靠性、尋優(yōu)精度優(yōu)于其他三種算法。

表4 四種算法測試f4 實驗數(shù)據(jù)結(jié)果

表5 四種算法測試f5 實驗數(shù)據(jù)結(jié)果

表6 f6 實驗數(shù)據(jù)結(jié)果

綜上所述可得，在六個測試函數(shù)的實驗結(jié)果中NBFA 所得函數(shù)最優(yōu)解和平均最優(yōu)解都優(yōu)于其他算法，表明NBFA 算法在尋優(yōu)過程中的精度有明顯提高，算法后期局部搜索精度也有所提高；實驗數(shù)據(jù)顯示NBFA 的標(biāo)準(zhǔn)差也小于其他算法，表明該算法穩(wěn)定性提高。最后從算法全局迭代運行的時間上可以看出，NBFA 算法的速度明顯快于其他算法，算法效率有所提高。

5 結(jié)語

本章介紹細(xì)菌覓食算法的基本概念和運算流程，分析算法的基本操作和各類參數(shù)，針對算法的缺陷進行適當(dāng)?shù)馗倪M，將算法中的細(xì)菌種群引入Log—Linear 模型改進算法的趨向和遷移這兩個基本行為，并將步長改進為自適應(yīng)步長，這樣使得算法的局部搜索更加精確；細(xì)菌執(zhí)行復(fù)制和遷移之后，引入Gauss—Cauchy 變異來保證細(xì)菌種群的多樣性，確保算法結(jié)果靠近全局最優(yōu)值。最終通過對比四類細(xì)菌覓食算法的六個函數(shù)的仿真實驗結(jié)果可證得NBFA算法具有較高的收斂性和尋優(yōu)精度。