菌群優(yōu)化算法研究綜述

武林娟，胡桂武，陳建超

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

0 引言

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

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

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

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

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

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

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

X=xmin+rand*(xmax-xmin)

(1)

其中，rand為均勻分布在[0,1]區(qū)間的隨機數(shù)。

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

步驟4：執(zhí)行細菌趨化循環(huán).

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

(2)

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

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

(3)

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

(4)

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

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

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

步驟7：循環(huán)結(jié)束條件判斷，滿足則結(jié)束，輸出結(jié)果。

3 菌群優(yōu)化算法的研究狀況

3.1 理論研究

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

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

3.2 算法改進

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

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

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

3.3 算法混合研究

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

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

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

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

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

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

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

3.4 應用研究

隨著菌群優(yōu)化算法研究的不斷發(fā)展,研究者已嘗試著將其用于工程、控制領(lǐng)域、經(jīng)濟等相關(guān)領(lǐng)域,并取得了較好的成果[13]。

Tripathy和Mishra將BFOA用于優(yōu)化mesh電力網(wǎng)絡的有效功率損耗問題[11]、Kim利用BFO來優(yōu)化神經(jīng)網(wǎng)絡的權(quán)重[27]。

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

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

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

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

Majhi等[30]在自適應信道均衡器中使用BFO算法適當?shù)馗戮馄鞯臋?quán)重。新的均衡器改進了收斂性和誤碼率。

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

4 總結(jié)和展望

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

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

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

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

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

參考文獻:

[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.