武林娟，胡桂武，陳建超

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

0 引言

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

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

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

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

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

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

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

X=xmin+rand*(xmax-xmin)

(1)

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

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

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

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

(2)

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

步驟4.2.游動(dòng):如果翻轉(zhuǎn)的適應(yīng)值改善，則按照翻轉(zhuǎn)的方向進(jìn)行游動(dòng)，直至適應(yīng)值不再改善或達(dá)到設(shè)定的最大移動(dòng)步數(shù)Ns為止?；诩?xì)菌感應(yīng)機(jī)制的適應(yīng)度采用Jcc表示：

(3)

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

(4)

因此聚集操作就是通過(guò)上述公式來(lái)對(duì)適應(yīng)值J(Xi)進(jìn)行修正，使得細(xì)菌達(dá)到聚集的目的。

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

步驟6：遷移循環(huán)。繁殖算子完成后，生成一個(gè)隨機(jī)概率，并將它與固定遷移概率Ped,如果小于Ped就進(jìn)行細(xì)菌遷移，在解空間內(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]研究了單個(gè)細(xì)菌的智能，并且應(yīng)用于分布式優(yōu)化和控制，對(duì)大腸桿菌的趨化行為進(jìn)行了理論建模和穩(wěn)定性分析。2002年P(guān)assino K M[1]提出了BFO，并且詳細(xì)分析了其仿生基礎(chǔ)，開始受到計(jì)算機(jī)界的重視。2003年Liu Y和Passino Kevin M[4]對(duì)多維菌群模型情況下的穩(wěn)定性進(jìn)行了分析和證明。2004年Gazi V和Passino K M[5]對(duì)基于菌群吸引與排斥行為的模型進(jìn)行了穩(wěn)定性分析。2009年Sambarta Dasgupta[6]等人對(duì)BFO的趨化操作進(jìn)行自適用改進(jìn)，并且做了嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)理論分析。2009年Sambarta Dasgupta[7]等人對(duì)BFO的理論基礎(chǔ)、理論分析、應(yīng)用做了詳細(xì)的闡述,進(jìn)行了詳細(xì)的理論基礎(chǔ)以及收斂性分析。2009年Sambarta Dasgupta[8]等人對(duì)BFO的趨化動(dòng)能的穩(wěn)定性進(jìn)行了分析。2010 年Arijit Biswas, Swagatam Das[9]等人對(duì)BFO的復(fù)制操作的穩(wěn)定性進(jìn)行了分析。

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

3.2 算法改進(jìn)

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

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

以上算法的研究主要是針對(duì)趨化的改進(jìn)，對(duì)復(fù)制、遷徙等方面的研究比較少，對(duì)算法模式的泛化設(shè)計(jì)鮮見。

3.3 算法混合研究

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

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

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

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

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

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

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

3.4 應(yīng)用研究

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

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

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

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

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

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

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

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

4 總結(jié)和展望

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

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

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

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

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

參考文獻(xiàn):

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