基于免疫算法的BFA优化研究

王家兰

(池州职业技术学院信息技术系，安徽池州 247100)

BFA(Bacterial Foraging Algorithm，细菌觅食算法)是一种新兴的寻优智能优化算法[1-2]，在2002年由K M Passino提出[3]。时至今日，BFA被广泛应用于最优化问题求解之中，但是传统意义的BFA算法的搜索能力能收敛精度有待提高[4-8]。

鉴于此，国内外学者针对BFA的优化问题进行了大量研究。Farhat I A将BFA和粒子群算法相融合，对BFA的群体感应机制做出些许改变，一定程度上改善了BFA的搜索能力，但是仍然无法获得较好的收敛精度[9]；Panigrahi B K利用粒子的移动替代了BFA中的趋向性操作环节，但是却大大降低了BFA寻优的速度[10]，尤其是容易陷入局部最优的陷阱；李闯利用解析解的思想对BFA进行了部分优化，提高了BFA的收敛精度和寻优速度，但是李闯针对的是特定问题，没有系统探讨BFA，更没有涉及BFA的搜索能力[11]；Tang W J[12]将繁殖算子的思想融合进入BFA，提高了BFA的寻优能力，但是却牺牲了精度和寻优的速度。

现有的针对BFA的研究成果往往针对BFA的寻优能力和搜索能力进行优化，无法兼顾寻优速度和收敛精度。在BFA算法的复制操作环节、趋向性操作环节和迁移操作环节基础上，融合免疫算法(generate and test)的相关思想，一种比BFA更优化的算法GBFA(Generate Bacterial Foraging Algorithm)应用而生，具体表现：在趋向性操作环节中由原来固定步长变为非固定步长，并在计算过程中随时可以改变，而趋向性操作步长的动态更新机制也被建立起来；而后，BFA的复制操作环节被免疫算法(generate and test)所替代，我们将对细菌群落一一比较择优，挑选出适应度相对高的细菌去替代适应度相对低的细菌；在最后迁移操作这一步中，适应度最高的个体很少被驱散。我们可以通过一些实例，去检验GBFA算法的寻优速度和收敛精度。

1 GBFA的基本思想

这样，我们就用这组细菌前m部分的细菌取代原来整个细菌群落，从而大大增强整个细菌群落的觅食能力。而后，我们按照下面的方法对细菌群落进行变异和繁衍。

(1)择优选出适应度高的细菌，记为clone群体A；

(2)将clone群体A繁衍为群体B,

其中，Round为取舍数学函数；S为细菌群落的细菌个数；A(i)为计算的克隆群体A的个数；i为计算次数；α为克隆的系数。简化计算，我们把适应度F标准化。

这里，max是取最大值数学函数。

(3)变异群体B操作，生产群体C,

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

这里，random为随机函数；B(i)为计算的克隆群体B的个数；β为变异概率，计算方法为：

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

其中，适应度和变异概率之间关系成正比例。

交叉方法为：

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

其中，x1,x2,x3,x4为克隆群体A中4个不同的细菌标本。把两个群体B和C融合到一起，形成群体D。

D=B+C.

(4)把群体D里前m部分的细菌克隆n次，剩下全部删除。

在这里，将BFA算法和GBFA算法进行对比一下。

BFA算法思路：首先预设一个迁移概率Ped，假如Ped比随机数大，则细菌被迁移。优点解决细菌跃出局部最优解的陷阱，缺点是Ped没有经过筛选，也没有考虑适应度，这样所有细菌随时都可能被迁移。

GBFA算法改进之处在于在迁移操作这一步骤中，若某细菌的适应度是最高的，则不被驱散,这样大大提高了搜索的速度。

依据此思想，绘制出算法流程图——GBFA算法，如图1所示。

2 GBFA的收敛性

在此之前，DASGUPTA对传统BFA算法的收敛性进行了研究[13]，但由于BFA算法的局限性，本文研究GBFA算法融合了免疫算法，笔者认为有必要在此重新论证一下GBFA的收敛性。

图1 算法流程图——GBFA算法

依据李涛的研究[14]，抗体种群A0，抗体空间几何为I*，v(A(k))为计算所得最优解的个数，B*为最优解的个数，

经过整理得到

由此可见，该算法收敛到最优解集的概率为1，即当算法运行到一定数量时，定会收敛的。

而本文的GBFA融入了免疫算法，在抗体种群A0不变的情况下，有

这里，Ai(k)表示细菌i在第k次操作时所在的位置，而Ai(k)是由Ai(k-1)经过克隆、变异而得。

简化表述记为：

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}.

因为

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}.

又因为

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).

又因为

所以

最后

结合以上所述，GBFA的收敛概率为1。

3 GBFA的性能分析

选取Sphere函数f1(x1)、Griewank函数f2(x2)、Rastrigrin函数f3(x3)作为测试函数：

图2 Sphere函数的寻优曲线

图3 Griewank函数的寻优曲线

图4 Rastrigrin函数的寻优曲线

在图2中，对于Sphere函数的寻优曲线，GBFA仅仅需要12次迭代便可以寻找出最优值，而传统BFA需要22次迭代才可以寻找出最优值，迭代次数为GBFA的2.67倍；Griewank函数具有很强的震荡性质，一般无法找到它们的最优解。根据图3可以看出，传统BFA无法找到Griewank函数的最优解，但GBFA搜索到的最优解为0，这说明GBFA的搜索能力远大于传统BFA。在图4中，对于Rastrigrin函数的寻优曲线，GBFA仅仅需要23次迭代便可以寻找出最优值，而传统BFA需要53次迭代才可以寻找出最优值，迭代次数为GBFA的2.30倍。简而言之，GBFA的搜索能力和搜索速度远大于传统BFA。

表1是GBFA和传统BFA收敛精度的比较。

表1 GBFA和传统BFA收敛精度

根据表1，对于Sphere函数f1(x1)、Griewank函数f2(x2)、Rastrigrin函数f3(x3)，GBFA的精度远大于传统BFA，寻优能力更强。并且，GBFA的方差均小于传统BFA的方差，说明GBFA的稳定性更好。

4 结论

本文针对BFA算法的3个操作环节(复制操作环节、趋向性操作环节和迁移操作环节)，融合免疫算法的相关思想，提出BFA的一种优化算法GBFA。并利用Sphere函数f1(x1)、Griewank函数f2(x2)、Rastrigrin函数f3(x3)作为实例进行验证，发现GBFA的搜索能力和搜索速度远优于传统BFA，寻优能力更强，稳定性更好。

[1]张荣沂.一种新的集群优化方法——粒子群优化算法[J].黑龙江工程学院学报,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 法的半解析解及其广义数学模型[J].水利与建筑工程学报,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]李涛.计算机免疫学[M].北京:电子工业出版社,2004.