菌群優化算法研究綜述

武林娟，胡桂武，陳建超

(1.廣東商學院 經濟貿易與統計學院，廣東 廣州 510320;2.廣東商學院 數學與計算科學學院，廣東 廣州 510320;3.中國人民大學 教育部數據工程與知識工程重點實驗室,北京 100872)

0 引言

自從仿生學創立以來，學者們從模仿生物出發，創造了很多含有新功能的計算工具。比如對社會性動物(如蟻群、鳥群、魚群等)的自組織行為進行數學建模并利用計算機對其進行仿真，這就是群智能(Swarm Intelligence，SI)的起源。群智能做為新興的優化方法，從整體上來說尚有大量的問題需要解決。

近年來有些學者嘗試對微生物的行為機制及其生理特性進行建模仿真，構建了一些新型群智能算法，最優代表性的是菌群覓食優化算法(Bacteria Foraging Optimization，BFO)[1]，從而豐富仿生優化算法中的微生物智能計算這一領域，由于微生物智能仿生技術問世的時間太短，國際學術界目前對BFO等相關研究尚有許多空白，這一新型的群智能優化算法還遠未獲得學術界應有的足夠重視。

1 基本菌群優化算法

菌群優化算法[1]算法的基本思路是從初始化一組隨機解開始，將細菌的位置表示為問題的潛在解，通過細菌的趨化操作實現細菌下一步趨向更為有利的生存環境，獲得較優的位置；通過復制操作保留優秀個體淘汰較差個體，從而實現整個細菌群體收斂到局部最優；通過遷移操作可以在一定程度上避免算法陷入局部最優。

細菌覓食優化算法對待優化問題進行求解的一般過程設為：對問題進行解的編碼；設計問題的評價函數；隨機產生初始群體；利用趨化、繁殖和遷移算子進行迭代優化，算法的主要實現步驟描述如下：

步驟1：初始化各參數。其中，Ned為遷移次數、Nre為繁殖次數、Nc為趨化次數；Ped為基本遷移概率；S為細菌規模數；Ns為游動次數。

步驟2：初始化細菌位置。采用式(1)產生初始化位置，利用適應度函數計算細菌的初始化適應度值。

X=xmin+rand*(xmax-xmin)

(1)

其中，rand為均勻分布在[0,1]區間的隨機數。

步驟3：遷移循環l=1:Ned；繁殖循環K=1:Nre；趨化循環j=1:Nc，使用θi(j,k,l)表示第i個細菌的空間位置向量，其中j表示第j代趨化循環，k表示第k代繁殖循環，l表示第l代遷移循環。

步驟4：執行細菌趨化循環.

步驟4.1.翻轉,按照公式(2)更新細菌位置

(2)

θi(j,k,l) 表示第i個體在第j代趨藥性循環,第k代復制循環，第l代遷移循環時的位置， △(i)表示方向調整后選定的方向向量，向量中的元素屬于區間[-1，1]，C(i)表示前進的步長。

步驟4.2.游動:如果翻轉的適應值改善，則按照翻轉的方向進行游動，直至適應值不再改善或達到設定的最大移動步數Ns為止。基于細菌感應機制的適應度采用Jcc表示：

(3)

J(Xi)=J(Xi)+Jcc(Xi)

(4)

因此聚集操作就是通過上述公式來對適應值J(Xi)進行修正，使得細菌達到聚集的目的。

步驟5：繁殖循環。趨化周期完成后，對每個細菌在生命周期內的適應度進行累加得到細菌能量，按照細菌能量進行排序，淘汰掉能量獲取能力差的半數細菌，對能量獲取能力較強的半數細菌進行再生。

步驟6：遷移循環。繁殖算子完成后，生成一個隨機概率，并將它與固定遷移概率Ped,如果小于Ped就進行細菌遷移，在解空間內按照公式(1)初始化。

步驟7：循環結束條件判斷，滿足則結束，輸出結果。

3 菌群優化算法的研究狀況

3.1 理論研究

該領域最早的理論研究可上溯到1986 Stephens D和Krebs J的著作《Foraging Theory》[2].2000年Passino Kevin M[3]研究了單個細菌的智能，并且應用于分布式優化和控制，對大腸桿菌的趨化行為進行了理論建模和穩定性分析。2002年Passino K M[1]提出了BFO，并且詳細分析了其仿生基礎，開始受到計算機界的重視。2003年Liu Y和Passino Kevin M[4]對多維菌群模型情況下的穩定性進行了分析和證明。2004年Gazi V和Passino K M[5]對基于菌群吸引與排斥行為的模型進行了穩定性分析。2009年Sambarta Dasgupta[6]等人對BFO的趨化操作進行自適用改進，并且做了嚴謹的數學理論分析。2009年Sambarta Dasgupta[7]等人對BFO的理論基礎、理論分析、應用做了詳細的闡述,進行了詳細的理論基礎以及收斂性分析。2009年Sambarta Dasgupta[8]等人對BFO的趨化動能的穩定性進行了分析。2010 年Arijit Biswas, Swagatam Das[9]等人對BFO的復制操作的穩定性進行了分析。

總體來說菌群優化算法作為一種新型群智能優化算法，數學理論基礎薄弱，普遍意義的理論性分析不充分，待更深入的研究。

3.2 算法改進

任何群智能算法不具備絕對的完備性和可信度，菌群優化算法作為一種新的群智能算法，以提高算法性能的理論、算法設計以及與其它算法的融合研究是群智能研究的必經之路[10～11]。在參數調整方面，2003年Liu Y等改進了大腸桿菌間的相互作用機制，并對收斂性進行了初步分析[2]；2005年Mishra等基于TS的模糊規則系統提出了改進MBFO算法[12]；2006年Tripathy和Mishra等改進了適應度函數，提出了改進型的BFOA[13]，2008年Datta設計了一種具有自適應趨化步長的BFO算法[14]；2009年Majhi等設計了自動趨化步長的BFO模型，并將其應用于神經網絡的訓練[15]。

2010年Niu 等[16]在BFO算法中引入趨化步長的線性變化和非線性變化，并且應用到投資組合優化問題。此外，2011年Biswas 等[17]基于BFO算法中繁殖操作的簡單數學分析，提出了一個新的算法，表現優于標準BFO算法。

以上算法的研究主要是針對趨化的改進，對復制、遷徙等方面的研究比較少，對算法模式的泛化設計鮮見。

3.3 算法混合研究

菌群優化算法的另外一個研究方向是將BFO與其它優化方法相結合,克服單個算法的不足，成為克服群智能算法缺點的一個十分有效的工具[13]。

Kim等[18]提出了一個新的基于模糊方法、覓食行為和克隆選擇的混合模型。Biswas等將BFO算法與粒子群算法相結合，提出了一種混合優化算法并應用于多峰函數優化[19]。

Kim等人在BFO算法中引入了遺傳算法的交叉、變異算子，提出了GABFO算法[20]，并用于函數優化問題；Dasgupta等人[21]將差分進化(DE)的變異與交叉引入BFO算法，提出了趨向性差分進化(CDE)，提高了BFO算法在處理高維問題時的性能。

Panigrahi等人[22]把單純形法和細菌覓食行為相結合，提出一種新的隨機混合優化方法。Chu等[23]結合BFO算法中大腸桿菌的覓食機制和PSO算法中鳥群的集群模式提出了快速細菌群算法(FBSA)。

Lohokare等[24]基于BBO算法和BFO算法的混合提出了智能生物地理學優化(IBBO)方法，結果比BBO算法和其它修正算法更優。Shao等[25]把BFO算法與禁忌搜索混合，得到TS-BFO混合算法，對于模式發現來說是一個具有潛力的方法。

Hanmandlu等[26]使用模糊邏輯技術擴展了BFO算法，涉及迭代學習的BFO算法比GA和熵方法有更好的表現。

通過以上的研究可以看到，BFO算法和群體智能、進化計算、混沌優化等的混合研究還有很大的研究空間。

3.4 應用研究

隨著菌群優化算法研究的不斷發展,研究者已嘗試著將其用于工程、控制領域、經濟等相關領域,并取得了較好的成果[13]。

Tripathy和Mishra將BFOA用于優化mesh電力網絡的有效功率損耗問題[11]、Kim利用BFO來優化神經網絡的權重[27]。

Farhat等[28]用線性遞減的趨化步長取代原始BFO算法中不變的趨化步長，求解STHTS問題。

Datta等[17]將自適應增量調制引入BFO算法中，用以優化直線天線陣權重的振幅和相位，提高了收斂速度和精度。

Majhi等[19]使用BFO和自適應BFO技術發展了有效預測模型用于各種股票指數的預測。

Kulkarni等[29]在無線傳感器網絡的分布式迭代定位問題中使用BFO算法，從定位節點數量、定位信息的精確度和計算時間三方面對BFO和PSO進行了比較。

Majhi等[30]在自適應信道均衡器中使用BFO算法適當地更新均衡器的權重。新的均衡器改進了收斂性和誤碼率。

通過以上的研究可以看到，BFO算法在連續優化問題中取得了很好的成果，PID控制器的設計等工程、控制領域的應用取得了一些成功，再金融等經濟領域也有一些嘗試，但由于是新的算法，其應用研究特別在離散領域的研究有待進一步加強。

4 總結和展望

菌群優化算法作為一種新興的群智能技術，憑借著其算法結構簡單、靈活、魯棒性強和自組織能力等優點吸引了學者越來越多的關注，為人工智能處理系統和算法的設計提供了有益的啟發。但是,菌群優化算法是一種新興的群智能算法，還存在諸多需要完善的地方，存在的問題及其未來研究方向主要有以下幾方面：

1)菌群優化算法缺乏具備普遍意義的理論性分析，數學理論基礎薄弱。算法參數比較多，對各種參數設置沒有確切的理論依據，通常都是按照經驗型方法確定,具有很強的不確定性。

2)菌群優化算法模式設計研究不足，聚集操作中函數的通用性設計值得研究，適應值修正操作對適應值函數依賴性比較高，影響算法的穩定性，復制操作操作有一定的主觀性，限制了該算法求解諸如：動態優化、多目標優化等復雜優化問題的能力。

3)算法性能評估及其評估標準測試集研究不足，與其它經典算法比較研究不充分，主要研究是停留在連續的優化問題上，基于離散問題的很少涉及。

將來的研究工作,應以更高層次的數學或人工智能理論為基礎的菌群優化算法研究，進一步探尋算法的基本原理，夯實理論基礎。另外,還應擴展菌群優化算法在工程、控制領域、經濟、管理等領域的應用研究，與神經計算、混沌優化、進化計算、移動計算等各種先進技術的融合亟待更深入的研究。

參考文獻:

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

[2]Stephens D W, Krebs J R.Foraging Theory [M].NJ: Princeton University Press,1986.

[3]Passino K M.Distributed Optimization and Control Using Only a Germ of Intelligence[J].IEEE International Symposium on Intelligent Control,2000:5～13.

[4]Liu Y, Passino K M, Polycarpou M.Stability analysis of m-dimensional asynchronous swarms with a fixed communication topology [J].IEEE Trans on Automatic Control, 2003,48(1):76～95.

[5]Gazi V, Passino K M.Stability Analysis of Social Foraging Swarms[J].IEEE Trans on Systems, Man and Cystems PART B: Cybernetic, 2004,34(1):539～557.

[6]Dasgupta S, Biswas A, Abraham A.Adaptive Computational Chemotaxis in Bacterial Foraging Optimization: An Analysis[J].IEEE Transactions on Evolutionary Computation, 2009,13(4): 919～941.

[7]Das S, Biswas A, Dasgupta S.Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Application[J].Foundations of Computational Intelligence, 2009,3: 23～55.

[8]Dasgupta S, Das S, Abraham A, et al.On Stability of the Chemotactic Dynamics in Bacterial-Foraging Optimization Algorithm[J].IEEE Transactions on systems, man, and cybernetics, 2009,39(3):670～679.

[9]Biswas A, Das S, Abraham A, et al.Stability analysis of the reproduction operator in bacterial foraging optimization [J].Theoretical Computer Science,2010:2127～2139.

[10]Ben Niu, Yan Fan, Lijing Tan, et al.A Review of Bacterial Foraging Optimization Part I: Background and Development[J].Advanced Intelligent Computing Theories and Applications Communications in Computer and Information Science, 2010(93):535-543.

[11]Ben Niu, Yan Fan, Lijing Tan,et al.A Review of Bacterial Foraging Optimization Part II: Background and Development[J].Advanced Intelligent Computing Theories and Applications Communications in Computer and Information Science, 2010(93):544～550.

[12]Mishra S.A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation[J].IEEE Transactions on Evolutionary Computation,2005,9(1): 61～73.

[13]Tripathy M, Mishra S.Bacteria foraging-based to optimize both real power loss and voltage stability limit[J].IEEE Transactions on Power systems ,2007,22(1):240～248.

[14]Datta T, Misra I S, Mangaraj B B, et al.Improved adaptive bacteria foraging algorithm in optimization of antenna array for faster convergence[J].Progress in Electromagnetics Research C,2008,1: 143～157.

[15]Majhi R, Panda G, Sahoo G.Efficient Prediction of Stock Market Indices Using Adaptive Bacterial Foraging Optimization (ABFO) and BFO Based Techniques[J].Expert Systems with Applications,2009,36(6):10097～10104.

[16]Niu B, Fan Y, Zhao P, et al.A Novel Bacterial Foraging Optimizer with Linear Decreasing Chemotaxis Step[C].Proceedings of 2nd International Workshop on Intelligent Systems and Applications, Wuhan, China, 2010:1～4.

[17]Abraham A, Biswas A, Dasgupta S, et al.Analysis of the Reproduction Operator in an Artificial Bacterial Foraging System[J].Applied Mathematics and Computation,2010,215(9): 3343～3355.

[18]Kim D H, Cho J H.Advanced Bacterial Foraging and Its Application Using Fuzzy Logic Based Variable Step Size and Clonal Selection of Immune Algorithm[C].International Conference on Hybrid Information Technology, 2006,(1): 293～298.

[19]Biswas A, Dasgupta S, Das S, et al.Synergy of PSO and bacterial foraging optimization-a comparative study on numerical benchmarks[J].Innovatious in Hybrid Intelligent Systems,2007,44:255～263.

[20]Kim D H, Abraham A, Cho J H.A hybrid genetic algorithm and bacterial foraging approach[J].Information Sciences, 2007(177): 3918～3937.

[21]Dasgupta A, Dasgupta S, Das S, et al.A Synergy of Differential Evolution and Bacterial Foraging Optimization for Global Optimization[J].Neural Network Word, 2007,17(6): 607～607.

[22]Paniarahi B K, Ravikumar P V.Bacterial Foraging Optimization: Nelder-Mead Hybrid Algorithm for Economic Load Dispatch[J].IET Generation, Transmission & Distribution, 2008,2(4):556～565.

[23]Chu Y, Mi H, Liao H, et al.A Fast Bacterial Swarming Algorithm for High-Dimensional Function Optimization[C].IEEE World Congress on Computational Intelligence, 2008: 3135～3140.

[24]Lohokare M R, Pattnaik S S, Devi S, et al.Intelligent Biogeography-Based Optimization for Discrete Variables[J].World Congress on Nature & Biologically Inspired Computing, 2009:1088～1093.

[25]Shao L, Chen Y.Bacterial Foraging Optimization Algorithm Integrating Tabu Search for Motif Discovery[J].IEEE International Conference on Bioinformatics and Biomedicine, 2009:415～418.

[26]Hanmandlu M, Verma O P, Kumar N K, et al.A Novel Optimal Fuzzy System for Color Image Enhancement Using Bacterial Foraging[J].IEEE Transactions on Instrumentation and Measurement,2009,58(8): 2867～2879.

[27]Kim D H, Cho C H.Bacterial foraging based neural network fuzzy learning[C].IICAI 2005,2005:2030～2036.

[28]Farhat I A, El-Hawary M E.Short-Term Hydro-Thermal Scheduling Using an Improved Bacterial Foraging Algorithm [J].IEEE Conference on Electrical Power & Energy, 2009: 1～5.

[29]Kulkarni R V, Venayagamoorthy G K, Cheng M X.Bio-Inspired Node Localization in Wireless Sensor Networks[J].IEEE International Conference on Systems, Man and Cybernetics, 2009: 205～210.

[30]Majhi B, Panda G, Choubey A.On the Development of a New Adaptive Channel Equalizer Using Bacterial Foraging Optimization Technique[J].IEEE Annual India Conference, 2006:1～6.