曹天問，雷秀娟

陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院，西安 710062

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

曹天問，雷秀娟

陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院，西安 710062

1 引言

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

2 標(biāo)準(zhǔn)BFO算法

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

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

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

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

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

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

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

3 改進(jìn)后的BFO算法

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

3.1 最大游動步長的改進(jìn)

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

3.2 復(fù)制操作的改進(jìn)

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

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

3.3 遷徙操作的改進(jìn)

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

3.4 改進(jìn)的BFO算法流程

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

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

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

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

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

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

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

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

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

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

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

表2 參數(shù)設(shè)置

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

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

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

4.1 參數(shù)設(shè)置

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

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

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

4.2.1 單項改進(jìn)效果分析

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

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

圖1 趨向改進(jìn)對比圖

圖2 復(fù)制改進(jìn)對比圖

圖3 遷徙改進(jìn)對比圖

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

4.2.2 綜合改進(jìn)效果分析

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

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

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

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

表3 BFO及其改進(jìn)算法在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é)束語

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

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

[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]周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用[J].計算機(jī)工程與應(yīng)用，2010，46（20）：16-21.

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

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

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

[13]楊大煉，李學(xué)軍，蔣玲莉.一種細(xì)菌覓食算法的改進(jìn)及其應(yīng)用[J].計算機(jī)工程與應(yīng)用，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

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

細(xì)菌覓食優(yōu)化（BFO）；趨向；最大游動步長；復(fù)制；擇優(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.

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

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

2012-12-10

2013-03-04

1002-8331（2013）13-0175-05