吉佳紅，高 尚

（江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003）

細(xì)菌覓食算法（Bacterial Foraging Algorithm，BFA）是一種新型的基于全局隨機(jī)搜索的仿生類算法[1]。該算法是由K.M.Passino于2002年基于大腸桿菌趨藥性、和細(xì)菌繁殖以及消除——驅(qū)散特性、以及群體感應(yīng)機(jī)制，提出的一種用于全局最優(yōu)化的新型群體進(jìn)化智能算法。細(xì)菌覓食算法模仿大腸桿菌在人體腸道內(nèi)覓食行為，屬于仿生類優(yōu)化算法。實(shí)際問(wèn)題中的優(yōu)化要求不斷提高、問(wèn)題的復(fù)雜性也隨之升高，往往需要面對(duì)的優(yōu)化命題都具有變量維數(shù)高、非線性強(qiáng)等難題[2]，從而使得相關(guān)變量的儲(chǔ)存、計(jì)算及命題的求解都變得相當(dāng)?shù)睦щy。在BFA模型中，優(yōu)化問(wèn)題的解對(duì)應(yīng)搜索空間中細(xì)菌的狀態(tài)，即優(yōu)化函數(shù)適應(yīng)值。

然而，以往大多的經(jīng)典優(yōu)化算法在計(jì)算的速度、初值的敏感性和收斂的速度上等多方面都遠(yuǎn)遠(yuǎn)不能成為解決實(shí)際應(yīng)用中面臨的問(wèn)題的方法[3]，而基于計(jì)算智能的群智能仿生優(yōu)化方法卻易于解決此類問(wèn)題。另外，參數(shù)的選擇直接決定了求解結(jié)果的好壞，細(xì)菌覓食算法的參數(shù)選擇也相當(dāng)重要。為使細(xì)菌覓食算法在求解全局最優(yōu)問(wèn)題中得到最高的效率，因此提出采用正交實(shí)驗(yàn)的方法來(lái)確定細(xì)菌覓食算法在解全局最優(yōu)問(wèn)題的最優(yōu)參數(shù)組合。

1 細(xì)菌覓食算法

1.1 大腸桿菌的覓食行為

大腸桿菌是目前生物學(xué)上研究相對(duì)比較透徹的微生物之一，也是人和許多動(dòng)物腸道中最主要且數(shù)量最多的一種細(xì)菌。細(xì)胞膜、細(xì)胞壁、細(xì)胞核和細(xì)胞質(zhì)是大腸桿菌的主要組成部分。它會(huì)向著中性的環(huán)境移動(dòng)，并且有效的避開(kāi)堿性和酸性的環(huán)境。為了能給下一次狀態(tài)的調(diào)整提供決策信息[4]，大腸桿菌在改變每一次狀態(tài)之后都應(yīng)及時(shí)對(duì)效果進(jìn)行評(píng)價(jià)。大腸桿菌的移動(dòng)完全取決于它的所有同方向上轉(zhuǎn)動(dòng)的鞭毛。大腸桿菌被推動(dòng)向前快速游動(dòng)即所有鞭毛都沿逆時(shí)針?lè)较蜣D(zhuǎn)動(dòng)；反之，當(dāng)所有鞭毛都沿順時(shí)針?lè)较蜣D(zhuǎn)動(dòng)的時(shí)候，大腸桿菌即被施加一個(gè)阻力因而不再向前游動(dòng)即原地旋轉(zhuǎn)。

1.2 算法的基本原理

細(xì)菌覓食算法[5]的提出是基于細(xì)菌的覓食行為過(guò)程。細(xì)菌覓食算法進(jìn)行建模迭代來(lái)產(chǎn)生最優(yōu)解是模擬了大腸桿菌在覓食行為過(guò)程中所體現(xiàn)出來(lái)的生理性行為，從而依照概率型而使結(jié)果涌現(xiàn)的一種的仿生搜索算法。生物學(xué)研究表明，大腸桿菌的覓食行為主要包括以下4個(gè)步驟[6]：

第一步：尋找可能存在食物源區(qū)域；

第二步：決定是否進(jìn)入此區(qū)域，若進(jìn)入，則進(jìn)行下一步驟，若不進(jìn)入，則返回上一步；

第三步：在所選定的區(qū)域中尋找食物源；

第四步：在選定的區(qū)域的食物被消耗掉一部分后，開(kāi)始判斷是否繼續(xù)停留覓食還是進(jìn)行遷移。

大腸桿菌常常根據(jù)自身以往的覓食經(jīng)驗(yàn)，可以判斷出可能會(huì)有更為豐盛的食物的其他區(qū)域；于是適當(dāng)?shù)母淖冏陨硭阉鞣较?，根?jù)自身經(jīng)驗(yàn)朝著可能有相對(duì)豐富食物的方向前進(jìn)。

細(xì)菌覓食算法模擬了細(xì)菌系統(tǒng)中主要的4個(gè)操作[7]:趨向、聚集、復(fù)制和遷徙。實(shí)際上，每個(gè)真實(shí)的細(xì)菌可以看作是一個(gè)為尋找優(yōu)化問(wèn)題中的最優(yōu)解而移動(dòng)在函數(shù)曲面上的測(cè)試解。算法的參數(shù)是影響算法性能和效率的關(guān)鍵，如何確定算法最佳參數(shù)使得算法性能達(dá)到最優(yōu)本身就是一個(gè)相對(duì)復(fù)雜的優(yōu)化問(wèn)題。細(xì)菌覓食算法的參數(shù)眾多，比如種群大小S；游動(dòng)步長(zhǎng)大小C；趨向、復(fù)制和遷徙操作的執(zhí)行次數(shù)Nc，Nre，Ned等。 參數(shù)值的選取將直接影響細(xì)菌覓食算法的收斂效率以及優(yōu)化性能。但由于有大小不同的參數(shù)空間，目前在細(xì)菌覓食算法的實(shí)際應(yīng)用中還沒(méi)有給出確定最佳參數(shù)的通用方法，通常只能憑經(jīng)驗(yàn)選取。這里主要介紹的是一些指導(dǎo)性原則和在仿真結(jié)果中總結(jié)出來(lái)的經(jīng)驗(yàn)。

通過(guò)大量的仿真試驗(yàn)，得到BFO算法參數(shù)[7]的取值范圍為 S=50～100，Nc=40～100，Nre=2～4，Ped=0.1～0.3。 此外，趨向性操作的執(zhí)行次數(shù)、復(fù)制操作執(zhí)行的次數(shù)常作為算法的組適用于絕大部分問(wèn)題的最佳參數(shù)值，文獻(xiàn)[5]也僅僅給出了參數(shù)粗略的取值范圍，并且隨著問(wèn)題特征的變化，有效參數(shù)值的差異通常非常顯著。因此，怎樣通過(guò)設(shè)定細(xì)菌覓食算法的控制參數(shù)來(lái)改善細(xì)菌覓食算法的性能，還需要要基于細(xì)菌覓食算法理論研究的發(fā)展，結(jié)合實(shí)際的問(wèn)題深入研究。終止條件的設(shè)置需要兼顧具體問(wèn)題并根據(jù)算法的優(yōu)化質(zhì)量和搜索效率等多方面性能。從理論上講，事實(shí)中可能并不存在一組適用于所有優(yōu)化問(wèn)題的最佳參數(shù)組，但若對(duì)于同一個(gè)問(wèn)題，可能存在著相對(duì)最好的參數(shù)組合對(duì)，如果參數(shù)設(shè)置不當(dāng)有可能導(dǎo)致達(dá)不到給定的收斂精度，甚至不收斂。因此，以下針對(duì)細(xì)菌覓食算法的參數(shù)組進(jìn)行配對(duì)組合研究。

2 基于正交試驗(yàn)的細(xì)菌覓食算法參數(shù)設(shè)置

2.1 正交試驗(yàn)

正交試驗(yàn)法，顧名思義就是指使用正交表來(lái)安排試驗(yàn)方案和進(jìn)行結(jié)果分析的一種試驗(yàn)設(shè)計(jì)的方法。正交表是一種簡(jiǎn)單的數(shù)學(xué)表格，它具有正交性、典型性等多方面特點(diǎn)，它一般適用于多指標(biāo)因素和具有隨機(jī)誤差的試驗(yàn)。通過(guò)正交試驗(yàn)，可以分析得出各因素對(duì)試驗(yàn)指標(biāo)影響的相對(duì)大小，并且通過(guò)比較重要程度找出它們的主次關(guān)系，以此來(lái)確定試驗(yàn)指標(biāo)的相對(duì)最優(yōu)參數(shù)組合。

2.2 細(xì)菌覓食算法的參數(shù)設(shè)計(jì)

這些參數(shù)對(duì)算法性能、效率影響很大，目前還沒(méi)有通用算法能得到實(shí)際應(yīng)用中的最佳參數(shù)，往往都是憑經(jīng)驗(yàn)選取。王帆[7]等人對(duì)細(xì)菌覓食算法各參數(shù)預(yù)期產(chǎn)生的影響進(jìn)行了深刻分析。本文試考慮影響試驗(yàn)結(jié)果的4個(gè)因素：種群大小S，趨向性操作次數(shù)Nc，復(fù)制次數(shù)Nre以及遷移概率Ped。此處采用四因素三水平的正交表L9（34），具體數(shù)據(jù)見(jiàn)表1。

表1 因素水平正交表Tab.1 The orthogonal table of factors and levels

選用信噪比[8]公式（1），對(duì)試驗(yàn)結(jié)果中的數(shù)據(jù)進(jìn)行相關(guān)計(jì)算分析：

其中xi為經(jīng)過(guò)多次參數(shù)組合對(duì)全局尋優(yōu)問(wèn)題（本文主要為多維測(cè)試函數(shù)）得到的最小消耗時(shí)間的最接近近似最優(yōu)值的結(jié)果。 各參數(shù)如{A1，B1，C1，D1}，首先變換 D 的 3 個(gè)水平取值，下一次則選擇變化C的取值。如此下去，從而得到如表2的數(shù)據(jù)結(jié)果。

表2 正交試驗(yàn)數(shù)據(jù)分析表結(jié)果Tab.2 The results and analysis of orthogonally designed tests

通過(guò)各因素對(duì)試驗(yàn)的最后結(jié)果的影響進(jìn)行分析，得到最好的方案：S=80，Nc=40，Nre=3，Ped=0.3。 將此參數(shù)組運(yùn)用于細(xì)菌覓食算法并進(jìn)行程序運(yùn)行，通過(guò)比較多次試驗(yàn)結(jié)果表明該方案比其他的方案的運(yùn)行結(jié)果都好。

3 實(shí)驗(yàn)仿真及結(jié)果分析

為了驗(yàn)證上述基于正交試驗(yàn)的細(xì)菌覓食算法的參數(shù)選擇的性能，采用試驗(yàn)數(shù)據(jù)對(duì)試驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)，選擇4個(gè)常用的Bench－mark函數(shù)進(jìn)行數(shù)值試驗(yàn)，這些函數(shù)廣泛應(yīng)用于文獻(xiàn)中，用來(lái)評(píng)價(jià)優(yōu)化算法的性能．函數(shù)1和函數(shù)2是單峰函數(shù)，函數(shù)3和函數(shù)4則是多峰函數(shù)，函數(shù)的具體表達(dá)式如表3所示。

表3 Bench-mark測(cè)試函數(shù)及其邊界Tab.3 The Bench-mark function and its boundary

由于測(cè)試函數(shù)的峰值不同，文中通過(guò)正交實(shí)驗(yàn)得到的細(xì)菌覓食算法的最優(yōu)參數(shù)的組合也不同，具體得到的最優(yōu)參數(shù)設(shè)置見(jiàn)下表4。

表4 正交試驗(yàn)得出的最優(yōu)參數(shù)Tab.4 The optimal parameters obtained by orthogonal experiment

本試驗(yàn)中4個(gè)測(cè)試函數(shù)的維度均設(shè)置為30維，迭代總次數(shù)則設(shè)定為107。為了降低由于系統(tǒng)和統(tǒng)計(jì)的誤差，文中對(duì)求解的每個(gè)參數(shù)組都進(jìn)行了20次的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果是20次仿真的統(tǒng)計(jì)值（平均最優(yōu)值和方差）。表5主要給出了使用正交實(shí)驗(yàn)得出的參數(shù)組合求解4個(gè)測(cè)試函數(shù)的結(jié)果，成功率能更加直觀地反映這種參數(shù)組合的優(yōu)勢(shì)。圖1給出了其中兩個(gè)測(cè)試函數(shù)在尋找最優(yōu)值的進(jìn)化特征曲線。

表5 BFA算法的性能測(cè)試結(jié)果Tab.5 The results of BFA algorithm performance

顯然表5和圖1都表現(xiàn)出了正確的參數(shù)設(shè)置對(duì)提高細(xì)菌覓食算法搜索能力的高效性的優(yōu)勢(shì)，但是本文提出的算法也存在參數(shù)越多，設(shè)計(jì)試驗(yàn)的工作量越大的問(wèn)題。并且沒(méi)有給出明確的算法來(lái)統(tǒng)一給出參數(shù)組合，仍依賴人工的選取和結(jié)果分析。對(duì)于細(xì)菌覓食算法求解復(fù)雜函數(shù)最小值的全局最優(yōu)化問(wèn)題，我們還需要對(duì)細(xì)菌覓食算法進(jìn)行改進(jìn)或融入其他的一些算法，以使算法能夠以最快最好的效率求得最優(yōu)解。

圖1 基于測(cè)試函數(shù)的細(xì)菌覓食算法收斂圖Fig.1 The convergence graph based on the test function of the bacterial foraging

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

本文通過(guò)針對(duì)細(xì)菌覓食算法求解全局最優(yōu)化的問(wèn)題提出了一種用正交實(shí)驗(yàn)的方法來(lái)進(jìn)行細(xì)菌覓食算法的參數(shù)組合設(shè)置。該算法通過(guò)正交試驗(yàn)來(lái)設(shè)置細(xì)菌覓食算法在求解全局最優(yōu)化的最優(yōu)參數(shù)組合，從而加快算法的高效性和收斂速度，使算法在短時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。本文對(duì)細(xì)菌覓食算法的基本原理進(jìn)行了闡述并明確給出了具體的實(shí)現(xiàn)方案，而且如果問(wèn)題的目標(biāo)函數(shù)越復(fù)雜，那參數(shù)選擇就越困難。最后通過(guò)典型的多維測(cè)試函數(shù)樣例進(jìn)行實(shí)驗(yàn)運(yùn)行仿真，結(jié)果證明了該策略針對(duì)全局最優(yōu)化的問(wèn)題中不但收斂速度上而且在求解精度上都有很大的優(yōu)勢(shì)。

[1]周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（20）:16-21.ZHOU Ya-lan.The bacterial foraging optimization algorithm and application[J].Computer engineering and Applications，2010，46（20）:16-21.

[2]Holland J H.Adaptation in natural and artificial system[M].Ann Arbor:The University of Michigan Press，1975.

[3]高尚，楊靜宇.群智能算法及其應(yīng)用[M].北京：中國(guó)水利水電出版社，2006.

[4]Mishra S.A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation[J].IEEE Trans on Evolutionary Computation，2005，9（1）:61-73.

[5]張璨.改進(jìn)的細(xì)菌覓食算法及其在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用[D].廣州：廣東工業(yè)大學(xué)，2013.

[6]胡潔，曾祥金.細(xì)菌覓食優(yōu)化算法的改進(jìn)及應(yīng)用研究[D].武漢：武漢理工大學(xué)，2012.

[7]王帆.面向高維及多目標(biāo)的協(xié)同細(xì)菌覓食算法研究[D].大連：大連理工大學(xué)，2013.