基于正交試驗的細菌覓食算法的全局最優化

吉佳紅，高 尚

（江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003）

細菌覓食算法（Bacterial Foraging Algorithm，BFA）是一種新型的基于全局隨機搜索的仿生類算法[1]。該算法是由K.M.Passino于2002年基于大腸桿菌趨藥性、和細菌繁殖以及消除——驅散特性、以及群體感應機制，提出的一種用于全局最優化的新型群體進化智能算法。細菌覓食算法模仿大腸桿菌在人體腸道內覓食行為，屬于仿生類優化算法。實際問題中的優化要求不斷提高、問題的復雜性也隨之升高，往往需要面對的優化命題都具有變量維數高、非線性強等難題[2]，從而使得相關變量的儲存、計算及命題的求解都變得相當的困難。在BFA模型中，優化問題的解對應搜索空間中細菌的狀態，即優化函數適應值。

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

1 細菌覓食算法

1.1 大腸桿菌的覓食行為

大腸桿菌是目前生物學上研究相對比較透徹的微生物之一，也是人和許多動物腸道中最主要且數量最多的一種細菌。細胞膜、細胞壁、細胞核和細胞質是大腸桿菌的主要組成部分。它會向著中性的環境移動，并且有效的避開堿性和酸性的環境。為了能給下一次狀態的調整提供決策信息[4]，大腸桿菌在改變每一次狀態之后都應及時對效果進行評價。大腸桿菌的移動完全取決于它的所有同方向上轉動的鞭毛。大腸桿菌被推動向前快速游動即所有鞭毛都沿逆時針方向轉動；反之，當所有鞭毛都沿順時針方向轉動的時候，大腸桿菌即被施加一個阻力因而不再向前游動即原地旋轉。

1.2 算法的基本原理

細菌覓食算法[5]的提出是基于細菌的覓食行為過程。細菌覓食算法進行建模迭代來產生最優解是模擬了大腸桿菌在覓食行為過程中所體現出來的生理性行為，從而依照概率型而使結果涌現的一種的仿生搜索算法。生物學研究表明，大腸桿菌的覓食行為主要包括以下4個步驟[6]：

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

第二步：決定是否進入此區域，若進入，則進行下一步驟，若不進入，則返回上一步；

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

第四步：在選定的區域的食物被消耗掉一部分后，開始判斷是否繼續停留覓食還是進行遷移。

大腸桿菌常常根據自身以往的覓食經驗，可以判斷出可能會有更為豐盛的食物的其他區域；于是適當的改變自身搜索方向，根據自身經驗朝著可能有相對豐富食物的方向前進。

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

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

2 基于正交試驗的細菌覓食算法參數設置

2.1 正交試驗

正交試驗法，顧名思義就是指使用正交表來安排試驗方案和進行結果分析的一種試驗設計的方法。正交表是一種簡單的數學表格，它具有正交性、典型性等多方面特點，它一般適用于多指標因素和具有隨機誤差的試驗。通過正交試驗，可以分析得出各因素對試驗指標影響的相對大小，并且通過比較重要程度找出它們的主次關系，以此來確定試驗指標的相對最優參數組合。

2.2 細菌覓食算法的參數設計

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

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

選用信噪比[8]公式（1），對試驗結果中的數據進行相關計算分析：

其中xi為經過多次參數組合對全局尋優問題（本文主要為多維測試函數）得到的最小消耗時間的最接近近似最優值的結果。 各參數如{A1，B1，C1，D1}，首先變換 D 的 3 個水平取值，下一次則選擇變化C的取值。如此下去，從而得到如表2的數據結果。

表2 正交試驗數據分析表結果Tab.2 The results and analysis of orthogonally designed tests

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

3 實驗仿真及結果分析

為了驗證上述基于正交試驗的細菌覓食算法的參數選擇的性能，采用試驗數據對試驗結果進行評價，選擇4個常用的Bench－mark函數進行數值試驗，這些函數廣泛應用于文獻中，用來評價優化算法的性能．函數1和函數2是單峰函數，函數3和函數4則是多峰函數，函數的具體表達式如表3所示。

表3 Bench-mark測試函數及其邊界Tab.3 The Bench-mark function and its boundary

由于測試函數的峰值不同，文中通過正交實驗得到的細菌覓食算法的最優參數的組合也不同，具體得到的最優參數設置見下表4。

表4 正交試驗得出的最優參數Tab.4 The optimal parameters obtained by orthogonal experiment

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

表5 BFA算法的性能測試結果Tab.5 The results of BFA algorithm performance

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

圖1 基于測試函數的細菌覓食算法收斂圖Fig.1 The convergence graph based on the test function of the bacterial foraging

4 結束語

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

[1]周雅蘭.細菌覓食優化算法的研究與應用[J].計算機工程與應用，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]高尚，楊靜宇.群智能算法及其應用[M].北京：中國水利水電出版社，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]張璨.改進的細菌覓食算法及其在結構優化設計中的應用[D].廣州：廣東工業大學，2013.

[6]胡潔，曾祥金.細菌覓食優化算法的改進及應用研究[D].武漢：武漢理工大學，2012.

[7]王帆.面向高維及多目標的協同細菌覓食算法研究[D].大連：大連理工大學，2013.