改進BFO算法在函數(shù)優(yōu)化問題上的應用

曹天問，雷秀娟

陜西師范大學 計算機科學學院，西安 710062

改進BFO算法在函數(shù)優(yōu)化問題上的應用

曹天問，雷秀娟

陜西師范大學 計算機科學學院，西安 710062

1 引言

Passino于2002年提出了模擬人類大腸桿菌覓食行為的細菌覓食優(yōu)化（Bacteria Foraging Optimization，BFO）算法[1]，由于其新穎性吸引了很多學者對它進行研究[2-6]。但是該算法存在早熟收斂的缺陷。Abraham等人[7-8]針對BFO算法的復制操作對算法的收斂性和穩(wěn)定性的影響進行了理論分析，并得出在復制操作中引入自適應機制能避免算法早熟。但這種理論分析是建立在一定的條件假設上的，只考慮了在一維的連續(xù)空間中兩個粒子組成的種群進行的復制操作。本文主要是從應用的角度出發(fā)，為了進一步提高標準BFO算法的局部搜索能力以及算法的精度以減少早熟現(xiàn)象的發(fā)生，對標準BFO算法的趨向、復制和遷徙操作進行了改進和優(yōu)化，并將改進BFO算法在函數(shù)優(yōu)化問題上進行了仿真實驗。

2 標準BFO算法

BFO算法的生物學基礎是人類腸道中大腸桿菌在覓食過程中體現(xiàn)出來的智能行為。細菌的覓食行為具有3個典型的模式，分別為趨向性行為、復制行為和遷徙行為[9]。

（1）趨向性操作。大腸桿菌的運動是通過其表面的鞭毛實現(xiàn)的。當鞭毛全部逆時針擺動的時候，大腸桿菌就會向前運動；當鞭毛全部順時針擺動的時候，它就會減速直至停止并在原地旋轉(zhuǎn)。細菌在覓食的過程中，這兩種行為交替進行。設θi(j，k，l)表示個體i當前的位置，其中，j表示第j代趨向性行為，k表示第k代復制行為，l表示第l代遷移行為。BFO算法中方向的調(diào)整按照下式進行：

其中，?(j)表示鞭毛擺動后確定的方向，c(i)表示游動步長單位。

（2）復制操作。當細菌完成設定的趨向性操作次數(shù)之后，細菌將進行分化，一部分個體由于無法得到足夠的食物而被淘汰掉，一部分覓食能力強的個體將得到進行個體繁殖的機會。新復制的個體將取代被淘汰掉的個體。設細菌種群大小為S，在復制過程中，群體中要被淘汰的個體數(shù)設為Sr=S/2。首先對群體中的個體按其位置的優(yōu)劣進行排序，而后將排在最后的Sr個個體刪除，剩余的個體進行自身的復制，即復制出與原來的個體一樣的新個體，這保證了算法群體規(guī)模的穩(wěn)定。

（3）遷徙操作。細菌群體所依附的生存環(huán)境的變化將對其造成很大的影響。這些都很可能使得群體逐漸或者突然發(fā)生變化。例如，整個區(qū)域內(nèi)的細菌全部死亡或者部分細菌移動到另外一個全新的環(huán)境。遷徙操作就是以一定概率對趨向性操作起到一個促進的作用，因為遷徙操作可能將部分細菌帶到離食物源更近的區(qū)域。

遷徙操作按照預先給定的概率P發(fā)生，如果某個體滿足遷徙操作發(fā)生的條件，那么將此個體刪除，重新生成一個新的個體。這相當于將原來的個體移到了一個新的位置。

BFO算法主要包括3層循環(huán)：最外層是遷徙操作循環(huán)；中間層是復制操作循環(huán)；最內(nèi)層是趨向性操作循環(huán)。

3 改進后的BFO算法

標準BFO算法中細菌個體全部使用相同的最大游動步長，不利于體現(xiàn)細菌個體能力之間的差異性；復制操作采用保留精英的方式對原有細菌進行100%復制，不利于保持種群多樣性；遷徙操作以一定概率發(fā)生，僅憑概率來決定細菌個體的更換與否，隨機性太強，不利于提高算法的全局收索能力。針對以上不足，主要對標準BFO算法作如下改進。

3.1 最大游動步長的改進

趨向操作中最大游動步長改進的理論基礎，源于第一個對學習中的強化做出理論分析的心理學家愛德華·桑代克（E L Thordike）的經(jīng)典效果律和經(jīng)濟學家巴萊多的巴萊多定律。桑代克的效果律中強調(diào)了3個重要的行為法則：其一，強化原則。在對相同的環(huán)境作出的幾種反應中，令人滿意的、受到鼓勵的行為結(jié)果將增加先前行為的力度，并增加未來再次發(fā)生此行為的可能性。其二，懲罰原則。不理想的或受到懲罰的行為結(jié)果將減少先前行為的力度，并減少未來再次發(fā)生此行為的可能性。其三，消退原則。如果行為之后沒有任何后果，既沒有正性的也沒有負性的事后結(jié)果，在若干時間后，這種行為將會逐漸消失。巴萊多定律則認為任何一組事物中，最重要的只占其中一小部分，約20%，其余80%的盡管是多數(shù)，卻是次要的。本文先初始化最大游動步長Ns，Ns根據(jù)種群中細菌個體的強化和懲罰進行動態(tài)變化，而對細菌個體強化和懲罰的判定條件則依據(jù)巴萊多定律，對種群中適應度值排在前20%的精英個體進行強化，即增加其最大游動步長；對適應度值排在后80%的普通個體進行懲罰，即減小其最大游動步長。這就賦予種群中的優(yōu)秀個體更大搜索空間的特權(quán)。由于每次趨向操作時都進行一輪適應度值計算并排序，種群中每一個個體都有得到強化的機會，因此，這種改進增加了種群間個體競爭的激烈程度，有利于提高算法的全局收索能力和收斂速度。

3.2 復制操作的改進

標準BFO算法的復制操作是按照細菌位置的優(yōu)劣排序，然后把排在后面的一半細菌淘汰掉，剩余的細菌進行自我復制，各自生成一個與自己完全相同的新個體。這使得新個體與原個體具有相同的覓食能力，雖然提高了算法的局部搜索能力，但同時也使種群的多樣性受到限制。改進BFO算法的復制操作在淘汰掉排在后面的Sr(Sr=S/2)個個體后，并沒有直接將前Sr個個體進行自我復制，而是增加了交叉步驟，將原有種群中的個體兩兩交叉，然后計算各細菌個體的適應度值，按優(yōu)劣排序，選擇排在前面的Sr個個體取代原種群中被淘汰掉的Sr個個體，保持種群數(shù)量不變的同時，也增加了種群個體的多樣性。

設pop(S，dim)為原種群，其中S為種群規(guī)模，dim為維度。在復制操作中將原有種群中的個體兩兩交叉，得到新的種群newpop(S，dim)，計算新種群各個體的適應度值，選擇新種群前S/2個個體取代原有種群pop(S，dim)中適應度值排在后面的S/2個個體。

3.3 遷徙操作的改進

遷徙操作使BFO算法具有隨機搜索的能力，有助于BFO算法保持種群的多樣性，減少早熟收斂的現(xiàn)象發(fā)生。標準BFO算法的遷徙操作是當細菌個體滿足遷徙條件時，隨機產(chǎn)生新的個體代替原有個體，而不考慮新生成個體的能力是否優(yōu)于原有個體。這種遷徙操作隨機性大，可能將本來優(yōu)良的個體滅亡后又隨機生成一個相對較差的新個體，影響了算法的收斂速度。改進的BFO算法在遷徙操作的過程中，如果得到的新個體優(yōu)于當前群體中最差的個體，則用新產(chǎn)生的個體取代當前最差個體進行擇優(yōu)遷徙；否則，保留原來的個體[10]。初始時設i=0，rand()是[0，1]區(qū)間上均勻分布的隨機數(shù)。改進后的遷徙操作能夠以更大的概率提高整個群體的平均適應度，為群體增加了優(yōu)秀的基因，使得算法能夠以更大的概率找到全局最優(yōu)解。

3.4 改進的BFO算法流程

設Nc、Nre、Ned分別是趨向性、復制和遷徙操作的執(zhí)行次數(shù)，j、k、l分別是對這3個操作的計數(shù)參數(shù)，S為種群數(shù)量。改進的BFO算法如下：

步驟1初始化群體，利用評價函數(shù)對群體中的各個體進行優(yōu)劣評估，初始化j=0，k=0，l=0。

步驟2遷徙循環(huán)：l=l+1。

步驟3復制循環(huán)：k=k+1。

步驟4趨向性循環(huán)：j=j+1，對各個個體進行趨向性操作。

步驟5如果j＜Nc，轉(zhuǎn)向步驟4。

步驟6復制操作：將原種群中個體兩兩交叉，分別選取原種群和交叉后的種群中適應度排在前面的S/2個個體，作為復制后的新種群。

步驟7如果k＜Nre，轉(zhuǎn)向步驟3。

步驟8遷徙操作：如果種群中的某個細菌個體滿足遷徙發(fā)生的概率，則隨機地在解空間生成一個新個體，并計算新個體的適應度值，如果優(yōu)于當前種群個體中的最差的適應度值，則用新個體替換滿足遷徙概率的那一個細菌個體；否則，不予替換。

步驟9如果l＜Ned，則轉(zhuǎn)向步驟2；否則整個算法結(jié)束。

表1 用于測試的6個函數(shù)

表2 參數(shù)設置

4 仿真實驗及結(jié)果分析

為了顯示改進后的BFO算法的高效性，本文選擇了在函數(shù)優(yōu)化中經(jīng)常使用的6個Benchmark函數(shù)來體現(xiàn)改進算法的性能，如表1所示。

Rosenbrock函數(shù)的全局最優(yōu)點位于一個平滑且狹長的拋物線山谷內(nèi)，是一個經(jīng)典復雜優(yōu)化函數(shù)；Griewank和Rastrigin函數(shù)是典型的非線性多模態(tài)函數(shù)，具有廣泛的搜索空間、大量的局部極小點和高大的障礙物，通常被認為是很難處理的復雜多模態(tài)問題[11-12]；Shubert函數(shù)具有多個全局最小值點，可以很好地檢驗一個算法跳出局部極值的能力，最小值為-24.062 499；Michalewicz’s有一個全局極小值點，取值近似為-1.801 3。

4.1 參數(shù)設置

細菌覓食算法中細菌種群的大小直接影響到細菌尋求最優(yōu)解的能力，種群數(shù)量越小，種群在搜索過程中獲得與解有關(guān)的信息就越少，種群數(shù)量越大，個體初始時分布的區(qū)域多，靠近最優(yōu)解的概率就越大，能避免算法陷入局部極值，但不可避免地增加了算法的計算量[13]。綜合算法計算量和搜索精度兩方面的考慮，將種群的大小設為100，其他具體的參數(shù)設置如表2所示。

改進BFO算法中的最大游動步長4±1是指：趨向操作中的最大游動步長初始值Ns設為4，再在每一次趨向過程中根據(jù)細菌個體適應度值的排序情況，將強化的個體的最大游動步長加1，將懲罰的個體的最大游動步長減1。

4.2 實驗結(jié)果比較分析

4.2.1 單項改進效果分析

Griewank函數(shù)是典型的非線性多模態(tài)函數(shù)，具有廣泛的搜索空間，大量的局部極小點和高大的障礙物，通常被認為是很難處理的復雜多模態(tài)問題，能夠很好地測試算法的性能。因此對于單項改進效果的分析以Griewank函數(shù)為例，分別針對3種改進進行獨立實驗，分析每一種改進的優(yōu)勢。標準BFO算法和改進BFO算法分別對Griewank函數(shù)做20次獨立實驗，并計算其種群平均適應度值。如圖1～3，分別為只改進趨向、復制、遷徙后的BFO算法與標準BFO算法的優(yōu)化效果對比。

如圖1，顯示了只對趨向操作中最大游動步長進行改進的BFO算法與標準BFO算法在Griewank函數(shù)優(yōu)化上的效果對比，可以看出改進后的算法在對種群中細菌個體的能力差異進行區(qū)別后，提高了種群優(yōu)化解的搜索精度。圖2中改進BFO算法在迭代初期就將優(yōu)化解鎖定在0.2附近，而標準BFO算法初始鎖定的解區(qū)域在0.9周圍，這說明改進后的BFO算法在搜索起點上就明顯優(yōu)于標準BFO算法，大大提高了算法的初始搜索精度，為進一步的精確查找奠定了基礎。圖2中改進BFO算法從第10次迭代開始快速收斂，20代時基本收斂到最優(yōu)解，說明在復制操作中引入交叉步驟后，增加了種群個體的多樣性，大大提升了算法的局部搜索能力和收斂速度。圖3可以看出在37次迭代之后，改進遷徙操作后的BFO算法的收斂速度得到明顯提升。

圖1 趨向改進對比圖

圖2 復制改進對比圖

圖3 遷徙改進對比圖

就趨向、復制、遷徙3項操作在Griewank函數(shù)優(yōu)化進行獨立實驗的結(jié)果來看，遷徙操作改進后算法在迭代的前中期開始慢慢提高優(yōu)化解的精度；趨向操作的改進使得算法的搜索精度得到明顯提升，使改進后的算法能快速找到最優(yōu)解；復制操作的改進對算法的性能提升最大，不管是搜索精度還是收斂速度方面都比標準BFO算法有了相當大程度的改進。

4.2.2 綜合改進效果分析

上一小節(jié)對3項改進操作分別進行了獨立實驗，分析了各項改進后算法的優(yōu)化效果。本小節(jié)將3項改進綜合后，與標準BFO算法進行函數(shù)優(yōu)化效果的對比分析。

由于復制操作中種群交叉操作與遺傳算法的交叉操作類似，因此將遺傳算法與改進前后的BFO算法一起進行對比分析。對于各測試函數(shù)，每種優(yōu)化算法運行20次求得的結(jié)果的最小值(fmin)、最大值(fmax)、平均值(fmean)，平均運行時間(tmean/s)如表3所示。

從表3可以看出改進BFO算法在各個函數(shù)上都具有較快的收斂速度和較強的全局搜索能力，尤其是搜索精度得到了很大程度的提升，如Griewank函數(shù)的優(yōu)化精度比標準BFO算法提高了34倍，Rastrigin函數(shù)提高了975倍，Sphere函數(shù)提高了1 513倍。由于改進的BFO算法增加了更多的操作，使得其運行時間較標準BFO算法要長，但從表3可以看出兩者平均運行時間的差距并不明顯，相對改進BFO算法在優(yōu)化效果的強勢表現(xiàn)而言，這種平均1 s左右的時間差距是完全可以接受的。另外，改進BFO算法對于Shubert函數(shù)的優(yōu)化比標準BFO算法用時更少。

如圖4～9，分別表示遺傳算法和改進前后的BFO算法對6個函數(shù)進行優(yōu)化時20次實驗的平均種群適應值變化趨勢。從圖中可以看出，改進后的BFO算法較標準BFO算法收斂更快，優(yōu)化精度更高，能持續(xù)有效地搜索全局最小點，具有很強的挖掘能力。尤其是Griewank和Rastrigin函數(shù)，改進BFO算法能快速收斂，展現(xiàn)出了更加卓越的優(yōu)化性能。改進的BFO算法能夠建立全局搜索和局部搜索兩者之間更有效的平衡機制。

表3 BFO及其改進算法在Benchmark函數(shù)上的優(yōu)化對比

圖4 Sphere函數(shù)優(yōu)化對比圖

圖5 Rosenbrock函數(shù)優(yōu)化對比圖

圖6 Griewank函數(shù)優(yōu)化對比圖

圖7 Rastrigin函數(shù)優(yōu)化對比圖

圖8 Shubert函數(shù)優(yōu)化對比圖

圖9 Michalewicz’s函數(shù)優(yōu)化對比圖

5 結(jié)束語

本文主要對標準BFO算法的趨向、復制和遷移操作均進行改進和優(yōu)化，然后將改進BFO算法在函數(shù)優(yōu)化問題上進行了仿真實驗，并對比改進前后的算法在函數(shù)優(yōu)化性能上的表現(xiàn)。

實驗結(jié)果表明，改進后的BFO算法不管是在單模態(tài)還是多模態(tài)Benchmark問題上均優(yōu)于標準BFO算法，在復制操作中增加交叉步驟，將細菌原始種群和交叉后的種群中的優(yōu)良個體同時保存下來，增加了細菌個體的多樣體和種群的進化質(zhì)量，使細菌更容易找到正確的搜索方向，從而在多模態(tài)問題上易越過局部極值而向全局極值收斂。圖2表明復制操作的改進對BFO算法的優(yōu)化性能有了很大提高，這也為BFO算法的進一步研究提供了基礎。

[1]Passino K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine，2002，22：52-67.

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

[3]Li M S，Tang W J，Tang W H，et al.Bacterial foraging algorithm with varying population for optimal power flow[C]// Proc of Evol Workshops，2007，4448：32-41.

[4]Abraham A，Biswas A，Dasgupta S，et al.Analysis of reproduction operator in bacterial foraging optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation（CEC 2008），2008：1476-1483.

[5]Lei Xiujuan，Wu Shuang，Ge Liang，et al.Clustering and overlapping modules detection in PPI network based on IBFO[J]. Proteomics，2013，13（2）：278-290.

[6]Kim D H，Abraham A，Cho J H.A hybrid genetic algorithm and bacterial foraging approach for global optimization[J]. Information Sciences，2007，177（18）：3918-3937.

[7]Das S，Biswas A，Dasgupta S，et al.Bcterial foraging optimization algorithm：theoretical foundations，analysis，and applications[J].Foundations of Comput Intel，2009，3：23-55.

[8]Biswas A，Das S，Dasgupta S，et al.Stability analysis of the reproduction operator in bacterial foraging optimization[C]// Proceedings of the IEEE/ACM International Conference on Soft Computing as Transdisciplinary Science and Technology（CSTST 2008），Paris，F(xiàn)rance，2008：568-575.

[9]周雅蘭.細菌覓食優(yōu)化算法的研究與應用[J].計算機工程與應用，2010，46（20）：16-21.

[10]梁艷春，吳春國，時小虎，等.群智能優(yōu)化算法理論與應用[M].北京：科學出版社，2009.

[11]雷秀娟，付阿利，孫晶晶.改進PSO算法的性能分析與研究[J].計算機應用研究，2010，27（2）：453-458.

[12]雷秀娟.群智能優(yōu)化算法及其應用[M].北京：科學出版社，2012.

[13]楊大煉，李學軍，蔣玲莉.一種細菌覓食算法的改進及其應用[J].計算機工程與應用，2012，48（13）：31-34.

CAO Tianwen,LEI Xiujuan

College of Computer Science,Shanxi Normal University,Xi’an 710062,China

The principle of the Bacterial Foraging Optimization（BFO）algorithm as well as the current research status is analyzed firstly,then the standard BFO algorithm is improved to overcome its insufficiency mainly based on the classic effect law of psychologist Edward Thorndike grams（E L Thordike）and the Pareto’s law of economist Pareto.The experimental results on Benchmark function optimization problems show that the improved BFO algorithm has the higher searching performance and convergence rate than the standard BFO algorithm.

Bacteria Foraging Optimization（BFO）;trends;the maximum swim step;replication;preferential migration

分析了細菌覓食優(yōu)化（BFO）算法的原理以及當前的研究狀況，主要根據(jù)心理學家愛德華·桑代克（E L Thordike）的經(jīng)典效果律和經(jīng)濟學家巴萊多的巴萊多定律等對標準BFO算法存在的不足進行改進；將改進后的BFO算法在函數(shù)優(yōu)化問題上進行仿真實驗，實驗結(jié)果表明改進后的BFO算法比標準BFO算法具有更快的收斂速度和更強的搜索性能。

細菌覓食優(yōu)化（BFO）；趨向；最大游動步長；復制；擇優(yōu)遷徙

A

TP301

10.3778/j.issn.1002-8331.1212-0095

CAO Tianwen,LEI Xiujuan.Application of improved Bacteria Foraging Optimization algorithm on function optimization.Computer Engineering and Applications,2013,49（13）：175-179.

國家自然科學青年基金（No.61100164，No.61173190）；教育部留學回國人員科研啟動基金（教外司留[2012]1707號）；陜西省2010年自然科學基礎研究計劃青年基金（No.2010JQ8034）。

曹天問（1989—），男，碩士研究生，主要研究方向為細菌覓食優(yōu)化；雷秀娟（1975—），通訊作者，女，博士，教授，主要研究領域為智能計算與智能優(yōu)化，生物信息計算。E-mail：xjlei168@163.com

2012-12-10

2013-03-04

1002-8331（2013）13-0175-05