基于模擬退火策略的細(xì)菌覓食優(yōu)化算法

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）10-2442-04

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

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

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

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

1.1BFOA的基本原理

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

1）趨化過(guò)程

2 模擬退火算法

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

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

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

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

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

參考文獻(xiàn)：

[1] 麥雄發(fā)，李玲.混合PSO的快速細(xì)菌覓食算法[J].廣西師范學(xué)院學(xué)報(bào)，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] 儲(chǔ)穎，靡華，紀(jì)震，等.基于粒子群優(yōu)化的快速細(xì)菌群游算法[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] 魏延，謝開(kāi)貴.模擬退火算法[J].蒙古師范高等?？茖W(xué)校學(xué)報(bào)，1999，1（4）：8-11.

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