基于免疫算法的BFA優(yōu)化研究

王家蘭

(池州職業(yè)技術(shù)學(xué)院信息技術(shù)系，安徽池州 247100)

BFA(Bacterial Foraging Algorithm，細(xì)菌覓食算法)是一種新興的尋優(yōu)智能優(yōu)化算法[1-2]，在2002年由K M Passino提出[3]。時(shí)至今日，BFA被廣泛應(yīng)用于最優(yōu)化問(wèn)題求解之中，但是傳統(tǒng)意義的BFA算法的搜索能力能收斂精度有待提高[4-8]。

鑒于此，國(guó)內(nèi)外學(xué)者針對(duì)BFA的優(yōu)化問(wèn)題進(jìn)行了大量研究。Farhat I A將BFA和粒子群算法相融合，對(duì)BFA的群體感應(yīng)機(jī)制做出些許改變，一定程度上改善了BFA的搜索能力，但是仍然無(wú)法獲得較好的收斂精度[9]；Panigrahi B K利用粒子的移動(dòng)替代了BFA中的趨向性操作環(huán)節(jié)，但是卻大大降低了BFA尋優(yōu)的速度[10]，尤其是容易陷入局部最優(yōu)的陷阱；李闖利用解析解的思想對(duì)BFA進(jìn)行了部分優(yōu)化，提高了BFA的收斂精度和尋優(yōu)速度，但是李闖針對(duì)的是特定問(wèn)題，沒(méi)有系統(tǒng)探討B(tài)FA，更沒(méi)有涉及BFA的搜索能力[11]；Tang W J[12]將繁殖算子的思想融合進(jìn)入BFA，提高了BFA的尋優(yōu)能力，但是卻犧牲了精度和尋優(yōu)的速度。

現(xiàn)有的針對(duì)BFA的研究成果往往針對(duì)BFA的尋優(yōu)能力和搜索能力進(jìn)行優(yōu)化，無(wú)法兼顧尋優(yōu)速度和收斂精度。在BFA算法的復(fù)制操作環(huán)節(jié)、趨向性操作環(huán)節(jié)和遷移操作環(huán)節(jié)基礎(chǔ)上，融合免疫算法(generate and test)的相關(guān)思想，一種比BFA更優(yōu)化的算法GBFA(Generate Bacterial Foraging Algorithm)應(yīng)用而生，具體表現(xiàn)：在趨向性操作環(huán)節(jié)中由原來(lái)固定步長(zhǎng)變?yōu)榉枪潭ú介L(zhǎng)，并在計(jì)算過(guò)程中隨時(shí)可以改變，而趨向性操作步長(zhǎng)的動(dòng)態(tài)更新機(jī)制也被建立起來(lái)；而后，BFA的復(fù)制操作環(huán)節(jié)被免疫算法(generate and test)所替代，我們將對(duì)細(xì)菌群落一一比較擇優(yōu)，挑選出適應(yīng)度相對(duì)高的細(xì)菌去替代適應(yīng)度相對(duì)低的細(xì)菌；在最后遷移操作這一步中，適應(yīng)度最高的個(gè)體很少被驅(qū)散。我們可以通過(guò)一些實(shí)例，去檢驗(yàn)GBFA算法的尋優(yōu)速度和收斂精度。

1 GBFA的基本思想

這樣，我們就用這組細(xì)菌前m部分的細(xì)菌取代原來(lái)整個(gè)細(xì)菌群落，從而大大增強(qiáng)整個(gè)細(xì)菌群落的覓食能力。而后，我們按照下面的方法對(duì)細(xì)菌群落進(jìn)行變異和繁衍。

(1)擇優(yōu)選出適應(yīng)度高的細(xì)菌，記為clone群體A；

(2)將clone群體A繁衍為群體B,

其中，Round為取舍數(shù)學(xué)函數(shù)；S為細(xì)菌群落的細(xì)菌個(gè)數(shù)；A(i)為計(jì)算的克隆群體A的個(gè)數(shù)；i為計(jì)算次數(shù)；α為克隆的系數(shù)。簡(jiǎn)化計(jì)算，我們把適應(yīng)度F標(biāo)準(zhǔn)化。

這里，max是取最大值數(shù)學(xué)函數(shù)。

(3)變異群體B操作，生產(chǎn)群體C,

B(i)=B(i)+βrandomn(C).

這里，random為隨機(jī)函數(shù)；B(i)為計(jì)算的克隆群體B的個(gè)數(shù)；β為變異概率，計(jì)算方法為：

β=e-F(n-i+1).

其中，適應(yīng)度和變異概率之間關(guān)系成正比例。

交叉方法為：

H=B(x1)-B(x2)+B(x3)-B(x4).

其中，x1,x2,x3,x4為克隆群體A中4個(gè)不同的細(xì)菌標(biāo)本。把兩個(gè)群體B和C融合到一起，形成群體D。

D=B+C.

(4)把群體D里前m部分的細(xì)菌克隆n次，剩下全部刪除。

在這里，將BFA算法和GBFA算法進(jìn)行對(duì)比一下。

BFA算法思路：首先預(yù)設(shè)一個(gè)遷移概率Ped，假如Ped比隨機(jī)數(shù)大，則細(xì)菌被遷移。優(yōu)點(diǎn)解決細(xì)菌躍出局部最優(yōu)解的陷阱，缺點(diǎn)是Ped沒(méi)有經(jīng)過(guò)篩選，也沒(méi)有考慮適應(yīng)度，這樣所有細(xì)菌隨時(shí)都可能被遷移。

GBFA算法改進(jìn)之處在于在遷移操作這一步驟中，若某細(xì)菌的適應(yīng)度是最高的，則不被驅(qū)散,這樣大大提高了搜索的速度。

依據(jù)此思想，繪制出算法流程圖——GBFA算法，如圖1所示。

2 GBFA的收斂性

在此之前，DASGUPTA對(duì)傳統(tǒng)BFA算法的收斂性進(jìn)行了研究[13]，但由于BFA算法的局限性，本文研究GBFA算法融合了免疫算法，筆者認(rèn)為有必要在此重新論證一下GBFA的收斂性。

圖1 算法流程圖——GBFA算法

依據(jù)李濤的研究[14]，抗體種群A0，抗體空間幾何為I*，v(A(k))為計(jì)算所得最優(yōu)解的個(gè)數(shù)，B*為最優(yōu)解的個(gè)數(shù)，

經(jīng)過(guò)整理得到

由此可見(jiàn)，該算法收斂到最優(yōu)解集的概率為1，即當(dāng)算法運(yùn)行到一定數(shù)量時(shí)，定會(huì)收斂的。

而本文的GBFA融入了免疫算法，在抗體種群A0不變的情況下，有

這里，Ai(k)表示細(xì)菌i在第k次操作時(shí)所在的位置，而Ai(k)是由Ai(k-1)經(jīng)過(guò)克隆、變異而得。

簡(jiǎn)化表述記為：

P0(k)=P{v(A(k))=0}=P{A(k)∩B*}.

則有

P0(k+1)=P{v(A(k+1))=0|v(A(k))≠0}P{v(A(k))≠0}

+P{v(A(k+1))=0|v(A(k))=0}P{v(A(k))=0}.

因?yàn)?/p>

P{v(A(k+1))=0|v(A(k))≠0}=0.

那么

P0(k+1)=P{v(A(k+1))=0|v(A(k))=0}P{v(A(k))=0}.

又因?yàn)?/p>

P{v(A(k+1))≥1|v(A(k))=0}≥>0.

所以

P{v(A(k+1))=0|v(A(k))=0}=1-P{v(A(k+1))≠1|v(A(k))=0}≤1-<1.

因此

0≤p0(k+1)≤…≤(1-)k+1P0(0).

又因?yàn)?/p>

所以

最后

結(jié)合以上所述，GBFA的收斂概率為1。

3 GBFA的性能分析

選取Sphere函數(shù)f1(x1)、Griewank函數(shù)f2(x2)、Rastrigrin函數(shù)f3(x3)作為測(cè)試函數(shù)：

圖2 Sphere函數(shù)的尋優(yōu)曲線

圖3 Griewank函數(shù)的尋優(yōu)曲線

圖4 Rastrigrin函數(shù)的尋優(yōu)曲線

在圖2中，對(duì)于Sphere函數(shù)的尋優(yōu)曲線，GBFA僅僅需要12次迭代便可以尋找出最優(yōu)值，而傳統(tǒng)BFA需要22次迭代才可以尋找出最優(yōu)值，迭代次數(shù)為GBFA的2.67倍；Griewank函數(shù)具有很強(qiáng)的震蕩性質(zhì)，一般無(wú)法找到它們的最優(yōu)解。根據(jù)圖3可以看出，傳統(tǒng)BFA無(wú)法找到Griewank函數(shù)的最優(yōu)解，但GBFA搜索到的最優(yōu)解為0，這說(shuō)明GBFA的搜索能力遠(yuǎn)大于傳統(tǒng)BFA。在圖4中，對(duì)于Rastrigrin函數(shù)的尋優(yōu)曲線，GBFA僅僅需要23次迭代便可以尋找出最優(yōu)值，而傳統(tǒng)BFA需要53次迭代才可以尋找出最優(yōu)值，迭代次數(shù)為GBFA的2.30倍。簡(jiǎn)而言之，GBFA的搜索能力和搜索速度遠(yuǎn)大于傳統(tǒng)BFA。

表1是GBFA和傳統(tǒng)BFA收斂精度的比較。

表1 GBFA和傳統(tǒng)BFA收斂精度

根據(jù)表1，對(duì)于Sphere函數(shù)f1(x1)、Griewank函數(shù)f2(x2)、Rastrigrin函數(shù)f3(x3)，GBFA的精度遠(yuǎn)大于傳統(tǒng)BFA，尋優(yōu)能力更強(qiáng)。并且，GBFA的方差均小于傳統(tǒng)BFA的方差，說(shuō)明GBFA的穩(wěn)定性更好。

4 結(jié)論

本文針對(duì)BFA算法的3個(gè)操作環(huán)節(jié)(復(fù)制操作環(huán)節(jié)、趨向性操作環(huán)節(jié)和遷移操作環(huán)節(jié))，融合免疫算法的相關(guān)思想，提出BFA的一種優(yōu)化算法GBFA。并利用Sphere函數(shù)f1(x1)、Griewank函數(shù)f2(x2)、Rastrigrin函數(shù)f3(x3)作為實(shí)例進(jìn)行驗(yàn)證，發(fā)現(xiàn)GBFA的搜索能力和搜索速度遠(yuǎn)優(yōu)于傳統(tǒng)BFA，尋優(yōu)能力更強(qiáng)，穩(wěn)定性更好。

[1]張榮沂.一種新的集群優(yōu)化方法——粒子群優(yōu)化算法[J].黑龍江工程學(xué)院學(xué)報(bào),2004,18(4):34-36.

[2]J Yi,D Huang,S Fu,et al.Optimized relative transformation matrix using bacterial foraging algorithm for process fault detection[J].IEEE Transactions on Industrial Electronics,2016,63(4):1.

[3]Spooner J T,Maggiore M,Passino K M. Stable adaptive control and estimation for nonlinear systems: neural and fuzzy approximator techniques[M].John Wiley & Sons,Inc.,2001.

[4]Hernández-Ocaa B,Pozos-Parra M D P,Mezura-Montes E,et al.Two-Swim operators in the modified bacterial foraging algorithm for the optimal synthesis of Four-Bar Mechanisms[J].Computational Intelligence & Neuroscience,2016.

[5]Awadallah M A.Variations of the bacterial foraging algorithm for the extraction of PV module parameters from nameplate data[J].Energy Conversion & Management,2016(113):312-320.

[6]J Jeslin Drusila Nesamalar,P Venkatesh,S Charles Raja.Managing multi-line power congestion by using Hybrid Nelder-Mead-Fuzzy adaptive particle swarm optimization (HNM-FAPSO)[J].Applied Soft Computing, 2016(43):222-234.

[7]Isaac Kweku Aidoo,Pawan Sharma,Bjarte Hoff.Optimal controllers designs for automatic reactive power control in an isolated wind-diesel hybrid power system[J].International Journal of Electrical Power and Energy Systems,2016(81):387-404.

[8]Sanyal N,Chatterjee A,Munshi S.An adaptive bacterial foraging algorithm for fuzzy entropy based image segmentation[J].Expert Systems with Applications,2011,38(12):15489-15498.

[9]Farhat I A,El-Hawary M E.Dynamic adaptive bacterial foraging algorithm for optimum economic dispatch with valve-point effects and wind power[J].Iet Generation Transmission & Distribution,2010,4(9):989-999.

[10]Panigrahi B K,Pandi V R.Congestion management using adaptive bacterial foraging algorithm[J].Energy Conversion & Management,2009,50(5):1202-1209.

[11]王俊奇,李闖,董曄.Bishop 法的半解析解及其廣義數(shù)學(xué)模型[J].水利與建筑工程學(xué)報(bào),2015(6):123-128.

[12]Tang W J,Li M S,He S,et al.Optimal power flow with dynamic loads using bacterial foraging algorithm[C].Power System Technology,PowerCon 2006,International Conference on.IEEE,2006:1-5.

[13]Das S,Biswas A,Dasgupta S,et al.Bacterial foraging optimization algorithm:the oretical foundations, analysis,and applications[C]∥Foundations of Computational Intelligence Volume 3,Berlin/ Heidelberg: Springer,2009:23-55．

[14]李濤.計(jì)算機(jī)免疫學(xué)[M].北京:電子工業(yè)出版社,2004.