摘要：針對標準細菌覓食優(yōu)化算法（BFOA）求解精度不高、穩(wěn)定性較差、容易陷入局部極值的問題，提出了一種基于模擬退火策略的細菌覓食優(yōu)化算法（SA-BFO）。該算法在趨向操作完成后，采用模擬退火策略對全局最優(yōu)個體進行優(yōu)化，提高算法的優(yōu)化精度和穩(wěn)定性，利用模擬退火算法的概率突跳性來避免陷入局部極值。仿真實驗結(jié)果表明，改進算法比標準細菌覓食優(yōu)化算法具有較高的優(yōu)化性能。

關(guān)鍵詞：細菌覓食優(yōu)化算法；模擬退火；概率突跳性；精度；穩(wěn)定性

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2013）10-2442-04

細菌覓食優(yōu)化算法（Bacterial Foraging Optimization algorithm， BFOA）是一種源于微生物世界的新型仿生類智能優(yōu)化算法[1]。它是由Kevin M.Passino在對人類腸道中真實大腸桿菌的覓食行為研究的基礎(chǔ)上提出的一種全局啟發(fā)式算法。目前已在電器工程與控制、濾波器問題、人工神經(jīng)網(wǎng)絡訓練、模式識別、調(diào)度問題等方面得到成功應用。但也存在一些缺點，如算法在趨向性操作中容易陷入局部極值、求解精度不高、穩(wěn)定性較差。

為了提高BFOA的性能，人們對算法的改進進行了研究，主要集中在算法參數(shù)和算法融合兩個方面。梁艷春等人對趨向性操作進行改進提出了兩種新的搜索策略：基于個體信息和基于群體信息的搜索策略；陳瀚寧等人分析步長C對BFOA局部開采和全局探索能力的影響提出自適應趨向性步長，并利用步長C的特點提出了協(xié)同細菌覓食算法[2]；儲穎等人針對細菌覓食優(yōu)化收斂速度慢的特點，提出一種快速細菌群游算法[3]，加強了算法在優(yōu)化初期的全局搜索能力以及優(yōu)化后期的局部搜索能力；Dasgupta和Das等人理論分析了使用自適應機制的步長對算法收斂性和穩(wěn)定性的影響[4]，但是他們的理論分析是基于一定的條件假設，只考慮在一維的連續(xù)空間中一個單獨粒子進行的趨向性操作；Mishra提出用Takagi-Sugeno型模糊推理機制選取最優(yōu)步長，該算法被稱為模糊細菌覓食算法，但是，模糊細菌覓食算法的性能完全依賴于隸屬函數(shù)和模糊規(guī)則參數(shù)的選擇[5]。Biswas等人結(jié)合BFOA和PSO形成了混合算法—細菌種群優(yōu)化（BSO） [6]，有效地平衡了局部開采能力和全局探索能力，但是該算法在細菌的趨化算子內(nèi)嵌入粒子群方法，賦予細菌對全局極值的感知能力，所有細菌通過與全局極值的對比，根據(jù)粒子群迭代公式更新細菌位置，此時算法中的趨化算子并沒有起到作用；Dasgupta等人將差分進化算法中的交叉與變異操作引入到BFOA，提出了一種混合全局優(yōu)化算法[7]，雖然增加了種群的多樣性，但同時也容易導致群體中優(yōu)秀個體的缺失。

本文將模擬退火策略引入到基本的BFOA，提出了一種基于模擬退火策略的細菌覓食優(yōu)化算法。該算法在趨向操作完成后，采用模擬退火策略對全局最優(yōu)個體進行優(yōu)化，提高算法的優(yōu)化精度和穩(wěn)定性，利用模擬退火算法的概率突跳性來避免陷入局部極值。

1 基本細菌覓食優(yōu)化算法

1.1BFOA的基本原理

BFOA模擬的是大腸桿菌在人體腸道內(nèi)吞噬食物的行為，該算法主要有三大基本操作：趨化操作、復制操作、遷移操作。一個優(yōu)化周期主要由3個部分組成，它們分別是趨化過程（Chemotaxis），繁殖過程（Reproduction），遷徙過程（Elimination and Dispersal）。

1）趨化過程

2 模擬退火算法

模擬退火算法的思想最早是由Metropolis等提出的，1983年Kirkpatrick等將其用于解決組合優(yōu)化問題[8]。該算法的出發(fā)點來源于工程中固體物質(zhì)的退火原理，模擬了高溫金屬降溫的熱力學過程。從某一較高溫度出發(fā)，伴隨溫度參數(shù)的不斷下降，逐漸產(chǎn)生新的狀態(tài)，結(jié)合概率突跳性在解空間中隨機尋找目標函數(shù)的全局最優(yōu)值，最終固體內(nèi)粒子逐漸有序，達到平衡態(tài)。模擬退火算法在搜索過程中的概率突跳能力可以有效避免算法陷入局部極值，從而高效快速的找到全局最優(yōu)解[9]。算法優(yōu)化流程如下：

3）輸出算法搜索結(jié)果。

3 改進的細菌覓食優(yōu)化算法

3.1 對優(yōu)化變量進行越界處理

將退火策略引入基本細菌覓食優(yōu)化算法中，提出了一種基于退火策略的細菌覓食優(yōu)化算法。該算法利用模擬退火算法的概率突跳性來避免陷入局部極值，采用模擬退火策略對全局最優(yōu)個體進行優(yōu)化，提高算法的優(yōu)化精度和穩(wěn)定性。實驗結(jié)果表明，改進算法具有更好的求解精度和魯棒性，但是運行速度較慢，有待在后續(xù)研究中改進并將其應用于實際工程優(yōu)化問題中。

參考文獻：

[1] 麥雄發(fā)，李玲.混合PSO的快速細菌覓食算法[J].廣西師范學院學報，2010，4（27）：91-95.

[2] Chen H，Zhu Y，Hu K.Cooperative bacterial foraging optimization[J].Discrete Dynamicsin Natureand Society，2009，3（5）：635-656.

[3] 儲穎，靡華，紀震，等.基于粒子群優(yōu)化的快速細菌群游算法[J].數(shù)據(jù)采集與處理，2010，25（4）：442-448.

[4] Das S，Dasgupta S，Biswas A，et al.Onstability of the chemotactic dynamicsin bacterial foraging optimization algorithm[J].IEEETransactionson Systems，Man，and Cybernetics-PartA：Systems and Humans，2009，39（3）：670-679.

[5] Mishra S.Hybridleast-square adaptive bacterial foraging strategy forharm onicestimation[J].IEEEProceedings-Generation，Transmission，Distribution，2005，152（3）：379-389.

[6] Biswas A，Dasgupta S，Das S，et al.Synergy of PSO and bacterial foraging optimization-Acomparative study on Merical benchmarks[J].Innovationsin Hybrid Intelligent Systems，2007，26（13）：44（3）：255-263.

[7] Dasgupta S，Biswas A，Das S，et al.Automatic circled etectiononimages with an adaptive bacterial foraging algorithm[C]，2008Genetic and Evolutionary ComputationConference（GECCO 2008），2008，13（5）：1695-1696.

[8] 魏延，謝開貴.模擬退火算法[J].蒙古師范高等?？茖W校學報，1999，1（4）：8-11.

[9] 王聯(lián)國，洪毅，趙付青，等.一種模擬退火和粒子群混合優(yōu)化算法[J].計算機仿真，2008，25（11）.