摘要:針對(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).