一种双菌群细菌觅食优化算法

姜建国，周佳薇，郑迎春，2，周润生

1)西安电子科技大学计算机学院，西安710071;2)中国电子科技集团公司第五十四研究所，石家庄050081;3)渭南职业技术学院，陕西渭南714000

近年来，随着实际工程复杂性、约束性、多极值性和建模难等问题的日益突出，传统优化方法已无法满足复杂多变的实际需求［1］.群智能优化算法应运而生并迅速发展［2］，其中，新型仿生类智能优化算法的细菌觅食优化(bacterial foraging optimization，BFO)算法［3］因其群体并行性及局部搜索能力强等优点受到关注.有学者对其改进提出多种策略，根据无免费午餐(no free lunch，NFL)定理，Sun等［4］结合高斯分布和量子行为对BFO进行改进，刘小龙等［5］采用免疫算法中的克隆选择思想对精英细菌群体进行克隆和高频变异.虽然这两种思路对BFO均有改善，但在优化多峰高维函数时仍存在寻优精度不够高和收敛过程不够稳定等缺点.任佳星等［6］为增加菌群的多样性，在细菌进化过程中引入交叉算子和变异算子，但该方法易致群体中优秀个体的缺失.刘小龙等［7］将分布估计和差分进化思想引入繁殖算子，虽能部分提高搜索速度和精度，但在优化极易陷入早熟收敛的Schwefel等函数时效果并不理想.

由现行BFO的相关研究可知，细菌觅食机制仍有算法缺乏全局空间寻优能力［8］，收敛精度不高、速度不快［9］，且在求解高维多模态优化问题时易陷入局部最优，引起早熟收敛［10］等缺陷.为此，本研究改进了趋化操作中的步长与方向选择机制，在考虑精英细菌的同时在复制操作中引入杂交算子和变异算子，提出双菌群优化机制，借助菌群间的相互学习提升寻优能力，避免局部最优，同时提出一种双菌群细菌觅食优化算法(double flora bacteria foraging optimization algorithm，DFBFO)，仿真实验验证了该方法对优化效率的改进.

1 细菌觅食优化算法

Passino［3］提出的觅食优化算法可表述为:当优化某个问题时，根据其可行域确定细菌的觅食区域，该区域中的细菌构成一个独立觅食的细菌菌群.细菌通过翻转、游动向食物浓度高的位置行进，实现趋化操作;根据优胜劣汰机制，处于优势的一半细菌进行二分裂，而处于劣势的细菌消亡，完成复制操作;最后，为避免细菌陷入局部最优，对所有细菌进行随机性迁徙操作，更新菌群.

1.1 趋化操作

细菌通过趋化操作寻找丰富营养源，同时避开有害物质.BFO算法中菌群随机初始化公式为

其中，Xmin和Xmax分别为优化区间的最小值和最大值;X为细菌初始化位置;ζ为［-1，1］的随机数.

设细菌的种群规模为 S，P(i，j，k，l)为细菌 i在第j次趋向性操作，第k次复制操作和第l次迁徙操作后的位置，即细菌i在优化空间内的一个可行解.每次趋向性操作后细菌位置更新为

其中，C(i)为细菌i的趋化步长;φ(i，j)为细菌i翻转时的单位随机方向向量，φ(i，j)=θ(i)/［θT(i)，θ(i)］1/2，这里，i，j，k，l=1，2，…，N;θ(i)为［-1，1］内任意产生的随机方向向量.

1.2 复制操作

设S为菌群规模的大小，复制算子Sr为将被淘汰的细菌数目，经典BFO算法取Sr=S/2，从第0个细菌开始计数，i为循环数，则细菌复制操作流程如图1.

图1 BFO算法复制操作流程Fig.1 The flow chat of BFO algorithm's reproduction step

1.3 迁徙操作

对细菌执行迁徙操作，有利于细菌寻找新觅食区域，防止细菌扎堆.设Ped为迁徙概率，S为菌群规模大小，ζ为［-1，1］间的随机数，初始时设i=0，细菌迁徙操作流程如图2.

图2 BFO算法迁徙操作流程Fig.2 The flow chat of BFO algorithm's elimination and dispersal step

2 一种双菌群细菌觅食优化算法

本研究提出的双菌群细菌觅食优化算法从3方面来改进经典BFO算法:① 改进趋化操作，添加当前趋化周期内最优细菌对其他细菌在寻优方向上的指导，并设计新的趋化步长选取策略;② 改进复制操作，设计交叉算子与变异算子以保证精英细菌不缺失;③改进迁徙操作，提出双菌群优化机制，在菌群间实现细菌迁徙与学习过程.

2.1 趋化操作的改进

Das等［11］理论分析了使用变化步长对算法收敛性和稳定性的影响，证明步长的选取对细菌觅食速度和解的精度有直接影响.若算法的趋化步长较大，则易找到全局最优解，但解的精度不高，并可能伴有最优解附近的震荡现象(由于采用固定且较大的趋化步长，细菌在本身接近最优解的情况下，执行下一次趋化操作后可能越过最优解，此时需返回重新搜寻方向，即出现反复地重新搜方向现象)，增加了算法的复杂度;趋化步长较小固然能避免震荡现象，也会提高解的精度，但算法收敛速度慢，且可能陷入局部最优.因此，合理选择步长对算法局部搜索能力的改进尤为重要.

2.1.1 趋化步长改进

考虑到菌群周围环境对算法可能产生的影响，本算法赋予细菌感知菌群拥挤度的能力，分析菌群的平均距离，自适应改进BFO算法的趋化步长.

定义菌群密度函数因子为

其中，S为细菌群中的细菌数目;L为搜索空间对角线的最大长度;d为搜索空间的维度;X(m，t)为细菌t在搜索空间第m维的位置坐标;ˉXm为当前搜索空间内所有细菌在搜索空间里第m维的平均位置坐标.

结合菌群密度函数因子对原始固定趋化步长改进为

其中，A=(Cmax-Cmin)/(Dmax-Dmin);B=(DminCmax-DmaxCmin)/(Dmax-Dmin);Cmin与Cmax分别是最小和最大趋化步长，Cmin≤C(t)≤Cmax;Dmin与Dmax分别为菌群中的最小和最大细菌距离，Dmin≤D(t)≤Dmax.

2.1.2 趋化方向改进

BFO算法趋化过程中的方向选择机制带有随机性，无法体现细菌对食物浓度的信息感知，也无法体现细菌与细菌、细菌与环境之间的信息交流与反馈机制［12］.当优化问题的复杂性和搜索空间维度较大时，BFO算法的收敛性较差［13］.为此，本研究将趋化方向分为两个:一个方向用于控制细菌随机翻转［3］，另一个新增的方向则控制细菌向最优细菌学习.细菌在随机翻转的同时，也向着当前最优细菌的方向翻转.随机翻转方向记为φ(i)rand;细菌i向当前最优细菌学习的最优翻转方向为

其中，Pbest为当前迭代周期内最优细菌的位置矢量;Pi为细菌i的位置矢量.

将最优翻转方向与随机翻转方向相结合，则细菌i完成趋化操作时的翻转方向为

其中，α=c1(Nc-i)/Nc为细菌i随机翻转的学习因子;β=c2(i/Nc)为细菌i向最优细菌方向前进的学习因子;c1和c2为调节参数;Nc为趋化次数.

算法开始时φ(i)rand比重较大，趋化操作主要是细菌进行随机翻转.结合趋化步长，细菌在开始觅食时以较大步长随机翻转，实现优化初期向最优解的大步伐“勘探”.随着趋化次数的增加，φ(i)rand逐渐起指导作用，即在算法后期，细菌主要向着当前最优细菌的方向，以较小步伐进行精细搜索，这有利于算法快速找到最优解，避免算法陷入局部最优或在最优解附近出现震荡现象.

2.2 复制操作的改进

复制操作是算法的主要驱动因子［14］.经典BFO算法采用一个周期内的适应度函数值之和作为复制的判断条件，同时直接消灭健康度差的细菌，但它可能扼杀精英细菌，且会降低菌群的多样性.本研究保留了当前趋化周期内的最优细菌作为精英细菌，设计一种杂交算子和变异算子，在记录当前搜索到的有用信息的同时，可提高种群的多样性和解的精度.

为使精英细菌在进化过程中能起到正引导作用，本研究引入交叉算子，令适应度较差的一半细菌向优秀细菌学习，并与当前优秀细菌个体进行杂交，充分利用已搜索到的有用信息改善健康度较差的细菌;同时引入变异算子，对当前搜索到的有较优适应度函数值的半数细菌在其邻域内进行微小的位置扰动，防止细菌进化停滞不前，使早熟细菌跳出局部最优，同时提高菌群的多样性.

交叉算子设置为

其中，λ为［0，1］间均匀分布的随机数;best为目前为止菌群搜索到的最优细菌的标号，则X(best)为最优细菌的位置矢量.

变异算子设置为

其中，Y服从标准正态分布N(0，1).

2.3 双菌群的提出

大肠杆菌在觅食过程中会出现群聚现象，群与群之间保持一定距离的同时又通过某种方式交换有用信息.这种相互通信扩大了细菌对周围环境的了解，增加了细菌存活几率.鉴于此，本研究提出一种双菌群优化机制:两个菌群并行且各自独立运行，其中一个菌群采用改进的趋化操作，其复制操作与BFO算法的复制操作相同.另一个菌群采用固定步长的趋化操作及改进过的复制操作.第1个子菌群为探测子菌群，重在优化算法的局部搜索能力，在优化初期保持较高的收敛速度，通过强化搜索加快细菌寻找极值点的能力;第2个子菌群重在优化算法的全局搜索能力，提高解的精度.每次复制操作周期结束后，两个菌群相互学习:用各自菌群中一定量的最优细菌替换另一个菌群中等量的最差细菌，由此促进算法收敛.其中，替换学习的细菌数取黄金分割率的平方即0.6182.

2.4 DFBFO算法设计

本研究提出的双菌群的细菌觅食优化算法主要操作步骤为:

1)初始化参数.包括菌群规模S、搜索空间的维度d、趋化操作中在某一方向上的最大游动次数NS、趋化次数Nc、复制次数Nre、学习次数Ned、最大趋化步长Cmax和最小趋化步长Cmin.

2)初始化菌群位置.采用随机初始化方法按照式(1)在d维空间初始化2S个点作为初始菌群XS，其中随机选取S个细菌作为菌群X1，剩余S个细菌作为菌群X2.

3)设置循环变量.趋化循环变量j从1增至Nc、复制循环变量k从1增至Nre、学习循环变量l从1增至Ned;

4)进入趋化循环，进行趋化操作.对菌群X2按照经典BFO算法的趋化操作对每个细菌进行趋化，对菌群X1用改进后的趋化操作对每个细菌进行以下两步操作:①翻转.按式(3)和式(4)计算细菌的趋化步长，并按照式(6)计算翻转方向，细菌根据步长与方向按照式(2)翻转，同时计算新位置上的适应度函数值;②游动.若细菌在新位置的适应度函数值有改善，则按照该方向游动，直到适应度函数值不再改善或达到预设的最大游动次数Ns.

5)进入复制循环，进行复制操作.对菌群X1按照经典BFO算法执行复制操作，对菌群X2按照如下步骤进行改进过的复制操作:①计算所有细菌的适应度函数值并自小至大排序，选出当前最优细菌作为精英细菌;②对当前适应度函数值较差的半数细菌按式(7)与复制循环环节里①中挑选出来的精英细菌进行杂交，生成S/2个新细菌并与未进行交叉操作的S/2个细菌构成新子细菌群X″2;③对当前适应度函数值较好的半数细菌按式(8)实施变异操作，生成S/2个细菌并与未变异的S/2个细菌构成新的子细菌群X'2;④从子细菌群X'2与子细菌群X″2中挑选出适应度函数值最好的前S个细菌替换原细菌群X2.

6)进入学习循环，进行学习操作.对菌群X1与菌群X2中的细菌按适应度函数值排序，并从菌群X1的前a=0.618S个细菌中按轮盘赌法选择出b=0.618a个细菌，与菌群X2中适应度函数值较差的b个细菌进行交换;再随机初始化a个细菌，与从菌群X1中交换来的b个细菌组成新菌群X2;

7)判断.若循环结束，则比较两个菌群分别找到的精英细菌，选择较好的一个作为全局最优解并输出结果，算法结束;否则，转4).

3 算法仿真结果与分析

3.1 仿真设计

本研究采用10个高维测试函数对BFO及DFBFO的性能分别进行对比测试(表1).这些函数的全局最优解通常在一个狭小地带，采用常规优化方法难以获取最优值，且优化难度随函数维数的增加而骤升［14］.

测试参数设置如下:设置函数维度为30维，运行DFBFO算法20次.菌群中的细菌总数S=40，迁徙概率0.25;趋化次数Nc=40;单向最大游动次数NS=5;迁徙次数Ned=5，复制次数Nre=5，学习参数 a=0.618S，b=0.382S.

表1 标准测试函数Table1 Benchmark functions

3.2 仿真结果与分析

表2给出了固定迭代次数下BFO算法及DFBFO算法的寻优精度对比.其中，算法测试20次，最优解(最差解)指20次中得到的最接近(最远离)全局最优解的值，固定迭代次数为Nc×Nre×Ned=1 000.

表2 固定迭代次数下的寻优精度对比结果Table2 The comparison results for optimization accuracy under the fixed number of iterations

由表2可见，对用于测试寻优精度的Sphere函数和Griewank函数，本研究算法得到的寻优解比经典BFO算法提高了6个数量级，全局寻优精度较高，且最优解与最差解差距不大，说明DFBFO算法在优化简单高维函数时性能稳定，这取决于本研究对菌群密度函数因子的引入，细菌被赋予感知菌群的能力并随着菌群拥挤程度自适应调整步伐大小，由于趋化方向上的改进，寻优不再盲目，进一步避免了细菌在最优解附近出现振荡现象，增进了算法稳定性.对于较难获得全局最优解的Rastrgin函数，DFBFO算法也取得了较佳效果，突破了BFO算法的局部早熟现象，且寻优精度接近理论最优值0.在优化极易陷入早熟收敛的Rosenbrock函数时，DFBFO算法效果不甚理想，虽然最优解较BFO算法有一定改进，但并未达到数量级的提高，说明DFBFO算法对于最优解附近存在陡峭区域的函数，它跳出早熟收敛的能力有待提高，变异算子及双菌群对于多样性的改善作用都有待加强.但DFBFO算法对于复杂Schwefel函数的收敛结果有较好改进，Schwefel函数的理论最优值为-12 569.5，DFBFO算法能较快收敛到-8 000左右，且20次测试结果显示平均解接近最优解，性能较稳定.对于其他测试函数，DFBFO算法也能取得较理想的结果.

表3在固定寻优阈值的情况下，对BFO算法及DFBFO算法进行了对比测试.其中，算法测试20次，最大和最小代数分别指20次测试中收敛到给定阈值所需代数的最大值和最小值.参数调整为:趋化次数Nc=30，单向最大游动次数Ns=5，复制Nre=5，迁徙次数Ned=8，其余参数设置同上.若迭代次数超过1 000仍未收敛到给定阈值，则认为算法陷入局部最优.

由表3可见，本算法对于寻优速度有了较大幅度地改善，在优化多峰高维函数时DFBFO算法表现稳定，基本在前300代内寻得全局最优解.由此可知，对于较低维度的测试函数，经典BFO算法可得到满意的优化结果，但当函数趋于复杂且易陷入局部最优时，BFO算法的寻优效果并不理想，容易引起算法的早熟收敛［15］.对于多峰函数Schwefel及Rastrgin，BFO算法无法在1 000代以内收敛至给定阈值，且测试结果表明，1 000代以后BFO算法寻优解的值变化缓慢，在3 200代时仍无法达到给定阈值.而DFBFO算法虽然在1 000代以内优化Rosenbrock函数只能得到最优解26.656 0，但对于其他高维多峰复杂函数，收敛代数均有大幅减小.在仿真过程中发现，每当DFBFO算法趋化循环结束，开始进行复制及迁徙操作时，寻优解的值会有大幅度的，甚至若干数量级的改善，这得利于本研究的改进措施:复制操作保护精英细菌，迁徙阶段不再随机抽取细菌进行灭亡与初始化操作，而是充分利用当前已搜索到的有用信息改善较差细菌，根据细菌的适应度值区别采取措施，同时两个菌群侧重点不同，并行寻优且相互学习与交流，从而本研究算法有效加快了寻优速度，能在较少的迭代次数内收敛至给定的寻优精度值.

表3 固定寻优阈值下的迭代次数对比结果*Table3 The comparison results for iterations under the fixed optimal threshold

综上，本研究提出的DFBFO算法可改善算法陷入局部早熟现象，提高全局搜索能力.不同函数的测试结果表明，DFBFO算法的解的精度和收敛速度均优于BFO算法，对某些复杂高维函数改善效果尤显，故DFBFO算法提高了细菌觅食机制的优化效率.

3.3 参数选取

本研究提出的算法涉及多个控制参数.在实际使用中，参数取值直接影响算法的寻优结果，故针对参数取值设计仿真实验.以Cmax和Cmin为例，它们在相同测试环境下对Griewank函数进行优化的收敛曲线如图3.

Cmax及Cmin的取值组合为

1)Cmax=0.1，Cmin=1×10-3;

2)Cmax=5×10-2，Cmin=1×10-4;

3)Cmax=3×10-2，Cmin=1×10-5;

4)Cmax=1×10-2，Cmin=1×10-6.

其余参数设置同上并在仿真过程中保持不变.

由图3可知，第4组取值组合对应的寻优解精度最大.当Cmax和Cmin取值继续减小时，寻优解精度的提高幅度趋于平缓，且由于其趋化步长过小，导致寻优速度降低.由此可见，Cmax和Cmin取值分别定为1×10-2及1×10-6.

同理，对其他控制参数进行仿真实验，最终确定本研究的主要控制参数取值为:Dmax=0.25，Dmin=0.01，c1=0.25，c2=0.05.

图3 Cmin和Cmax参数选取对比结果Fig.3 The comparison results for parameterselection between Cminand Cmax

结 语

本研究分析了BFO算法的优化原理，并从趋化操作、复制操作和迁徙操作3方面对经典BFO算法进行改进.引入菌群密度函数因子，将固定步长改进为随菌群拥挤程度自适应变化的趋化步长，并添加最优细菌对其他细菌的寻优方向指导，避免了在最优解附近出现震荡现象，加快寻优速度;根据遗传算法的交叉变异思想，提出一种交叉算子和变异算子，在保护精英细菌的同时增加菌群的多样性，促进早熟细菌跳出局部最优;受群聚现象的启发，提出双菌群优化机制，加强菌群间相互学习交流的程度，提高算法的局部搜索能力，有效抑制了算法的退化现象.仿真实验结果表明，本研究提出的双菌群细菌觅食优化算法，既提高了解的精度，又加快了算法收敛速度，能改善算法全局收敛能力，避免陷入局部早熟现象.

/References:

［1］Li Jin.The Research and Application of the Niche Shuffled Frog Leaping Algorithm ［D］.Xi'an:Xidian University，2012.(in Chinese)李 锦.小生境混合蛙跳算法研究与应用［D］.西安:西安电子科技大学，2012.

［2］Wang Yanfei.The Particle Swarm Optimization and Its Application［D］.Wuhan:Huazhong University of Science and Technology，2008.(in Chinese)王雁飞.粒子群优化算法及其应用［D］.武汉:华中科技大学，2008.

［3］Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.Control System Magazine，2002，22(3):52-67.

［4］Sun J，Fang W，Palade V，et al.Quantum-behaved particle swarm optimization with Gaussian distributed local attractor point［J］.Applied Mathematics and Computation，2011，218(7):3763-3775.

［5］Liu Xiaolong，Zhao Kuiling.Bacterial foraging optimization algorithm based on immune algorithm ［J］.Journal of Computer Applications，2012，32(3):634-637.(in Chinese)刘小龙，赵奎领.基于免疫算法的细菌觅食优化算法［J］.计算机应用，2012，32(3):634-637.

［6］Ren Jiaxing，Huang Jinying.An optimized bacterial foraging algorithm to solve the problem of global optimization ［J］.Science and Technology Information，2012(2):44-45.(in Chinese)任佳星，黄晋英.一种优化的细菌觅食算法用以解决全局最优化问题［J］.科技信息，2012(2):44-45.

［7］Liu Xiaolong，Li Rongjun，Yang Ping.Bacterial foraging optimization algorithm based on estimation of distribution［J］.Control and Decision，2011，26(8):1233-1238.(in Chinese)刘小龙，李荣钧，杨 萍.基于高斯分布估计的细菌觅食优化算法 ［J］.控制与决策，2011，26(8):1233-1238.

［8］Wang Xuesong，Cheng Yuhu，Hao Minglin.Estimation of distribution algorithm based on bacterial foraging and its application in predictive control［J］.Acta Electronic Sinica，2010，38(2):333-339.(in Chinese)王雪松，程玉虎，郝名林.基于细菌觅食行为的分布估计算法在预测控制中的应用 ［J］.电子学报，2010，38(2):333-339.

［9］Liu Xiaolong.The Improvement and Application of Bacterial Foraging Optimization Algorithm ［D］.Guangzhou:South China University of Technology，2011.(in Chinese)刘小龙.细菌觅食优化算法的改进及应用 ［D］.广州:华南理工大学，2011.

［10］Li M S，Ji T Y，Tang W J，et al.Bacterial foraging algorithm with varying population ［J］.BioSystems，2010，100(3):185-197.

［11］Das S，Biswas A，Dasgupta S，et al.Bacterial foraging optimization algorithm:theoretical foundations，analysis and applications［J］.Foundations of Computer Intelligence，2009，3:23-55.

［12］Xu Xin，Liu Yanheng，Wang Aimin，et al.Optimization algorithm of bacterial swarm based on the collection ［J］.Journal of Jilin University Engineering and Technology Edition，2012，42(6):1491-1497.(in Chinese)许 鑫，刘衍珩，王爱民，等.基于集合的细菌群优化算法 ［J］.吉林大学学报工学版，2012，42(6):1491-1497.

［13］Dasgupta S，Das S，Abraham A，et al.Adaptive computational chemotaxis in bacterial foraging optimization:an analysis［J］.IEEE Transactions on Evolutionary Computation，2009，13(4):919-941.

［14］Zhang Guoyong，Wu Yonggang，Tan Yuxiang.Bacterial foraging optimization algorithm with quantum behavior［J］.Journal of Electronics ＆ Information Technology，2013，35(3):614-621.(in Chinese)章国勇，伍永刚，谭宇翔.一种具有量子行为的细菌觅食优化算法［J］.电子与信息学报，2013，35(3):614-621.

［15］Chatzis S P，Koukas S.Numerical optimization using synergetic swarms of foraging bacterial populations ［J］.Expert Systems withApplications，2011，38(12):15332-15343.