一种混合蜂群算法的自适应细菌觅食优化算法

杜鹏桢，唐振民，孙 研

(南京理工大学计算机科学与工程学院，南京 210094)

1 概述

细菌觅食优化算法(Bacterial Foraging Optimization Algorithm,BFOA)[1]是一种模拟细菌觅食行为的群优化算法，现已成功运用于经济调度[2]、图像处理[3]等领域。BFOA在适当的趋化步长下，通过在解空间进行连续的翻转和泳动可以达到较高的精度，是一种精细型搜索算法。但由于其采用直接复制的繁殖方式，降低了种群的多样性，容易陷入局部最优[4]。为克服基本BFOA存在的缺点，各学者提出了很多改进方法，例如：文献[5]将量子行为引入细菌的繁殖操作，增强了BFOA的种群多样性，提高了算法的全局搜索能力；文献[6-7]采用自适应的趋化步长，提高了算法的整体性能；文献[8-9]分别将BFOA与其他算法相结合，改进了繁殖方式，大幅提高了算法的求解质量。

将多种算法进行混合，发挥每个算法的优点，是当前智能优化领域的研究热点之一。文献[10]研究表明，人工蜂群(Artificial Bee Colony,ABC)算法的寻优能力与粒子群优化(Particle Swarm Optimization,PSO)算法相当，强于差分进化，且在同等条件下，ABC的收敛速度可达PSO的2倍[11]，是一种比较有竞争力的新型智能优化算法。为克服BFOA的缺点，本文将ABC的部分机理引入到BFOA中，提出一种混合ABC算法的自适应BFOA算法(Bee Bacterial Foraging Optimization Algorithm,BBFO)。相比基本BFOA，BBFO有以下5点改进：(1)提出雇佣蜂式趋化，对解空间进行全局寻优；(2)改进BFOA原有趋化方式并自适应调节趋化步长，完成对解空间的局部调优；(3)依据对种群的多样性评价，完成2种趋化方式的自动切换；(4)提出基于t分布扰动的复制方式，提高种群多样性；(5)提出基于对立学习的侦察蜂式迁移，避免算法早熟。

2 细菌觅食优化算法

为方便描述，本文定义S个细菌组成的种群为：

其中，θi(j,k,l)表示第j次趋化，第k次复制，第l次驱散后的第i个个体。

BFOA把细菌觅食行为分解为趋化、聚群、复制和驱散4种算子。

(1)趋化算子模拟细菌向营养丰富区域移动的过程，包含翻转和泳动2种基本动作。个体i在n维解空间 ℝn按式(1)进行翻转，C(i)为趋化步长。如果翻转后细菌适应值得到改善，则沿当前方向φ(i)继续泳动预定步数Ns或泳动到适应值不再改善为止。

(2)聚群算子模拟个体间的相互影响，将个体间的吸引和排斥依式(3)计算为适应值Jcc，并与个体原适应值进行叠加，见式(4)。其中，dattract，wattract，h r epellant 和wrepellant为预先设定的吸引因子、吸引权重、排斥因子和排斥权重。

(3)复制算子模拟种群的繁殖。种群经过Nc次趋化后，依据适应值的累加和进行排序，较优的 Sr=S /2个细菌进行分裂繁殖，直接复制自身替换较差的Sr个细菌。

(4)驱散算子模拟种群的迁移。经过Nre次复制后，个体以概率Ped随机生成新个体，并替换原个体。

BFOA算法步骤如下：

步骤1初始化参数S,Nc,Ns,Nre,Ned,Ped,C(i),da,wa,hr和wr，在解空间 ℝn内随机初始化种群。

步骤2循环执行趋化算子Nc次，每次翻转操作后执行聚群算子。

步骤3执行复制算子，复制算子执行次数加1。若复制算子已执行Nre次，执行次数清0，转去执行步骤4，否则转去执行步骤2。

步骤4执行驱散算子，驱散算子执行次数加1。若驱散算子已执行Ned次，算法结束，否则转去执行步骤2。

3 BBFO算法

3.1 趋化

BBFO算法采用2种趋化方式：雇佣蜂式趋化(Employed Bees Style Chemotaxis,EC)和改进的自适应步长趋化(Improved Chemotaxis,IC)。

3.1.1 雇佣蜂式趋化

为提高BBFO的全局搜索能力，EC借鉴ABC雇佣蜂更新蜜源的方式[10]，步长根据下式确定：

其中，Cec(i)表示个体i的趋化步长；rand(-1,1)表示–1与1之间的随机数；表示第k(k≠i)只细菌第j维的值，k和j均为随机生成。在EC中，无翻转操作，仅执行单维度泳动，个体i沿步长Cec(i)泳动，若适应值无改善，则退回原来位置。

3.1.2 改进的自适应步长趋化

基本BFOA对步长较为敏感，取值大则全局搜索能力强，但精度下降；取值小则局部调优能力强，但收敛速度下降，算法时间复杂度上升。在BBFO中，IC采用自适应步长，见式(6)，泳动依然采用式(1)。

其中，Cic(i,j)表示第i个个体第j次趋化后的步长；δ∈(0,0.95)为步长缩减因子；Cinit(i)表示第i个个体的初始步长；domxh为解空间定义域的右边界；domxl为解空间定义域的左边界；D为自然数。

3.2 种群多样性的评价及趋化方式的切换

算法初始时，种群分散在一个较大空间，多样性较强，此时适宜进行全局搜索，加快算法收敛。随着迭代次数的增加，种群不可避免地聚集在相对狭小的空间，此时更适宜进行局部调优，以提高求解精度。鉴于此，本文利用式(8)[12]评价种群多样性，同时引入阈值 Pc，当 diversity(P) ＞Pc时，采用雇佣蜂式趋化进行全局搜索并提高收敛速度，否则，采用改进的自适应步长趋化，提高求解精度。当 diversity(P)较小时，种群多样性较低，此时算法可能已经陷入局部最优，具体跳出局部最优的方法将在下文进行阐述。

3.3 基于t分布扰动的复制方式

复制是BFOA的主要进化操作[13]，为避免BFOA中直接复制所带来的多样性降低问题，BBFO采用基于t分布扰动的复制方式，具体见式(9)。

其中，θi为被替换个体；θk为被复制个体；t(υ)表示自由度为υ的t分布。

t分布又称学生分布，当υ趋向无穷大时，等同于标准高斯分布，当υ=1时，等同于柯西分布。本文将种群多样性作为t分布的自由度，见式(10)，当种群多样性较低时，t分布近似于柯西分布，具有较大的扰动，有利于跳出局部最优，增强全局搜索能力；当种群多样性较高时，t分布近似于标准高斯分布，扰动较小，更利于提高求解精度。

3.4 基于对立学习的侦察蜂式迁移

在ABC算法中，若蜜源一定次数内无法被改善，则抛弃该蜜源，由相应的侦察蜂重新对解空间进行随机搜索。BBFO借鉴侦察蜂方式，设立参数trails，若某个解连续trails次趋化无法被更新，则重新生成该解。由于BBFO是精细型搜索算法，为了避免在原位置附近进行无用的搜索，同时提高跳出局部最优的能力，本文采用对立学习的方法生成新解，迁移方式如下：

其中，θi为迁移个体；θio为θi的近似对立数；domxh为解空间定义域的右边界；domxl为解空间定义域的左边界。

3.5 算法流程

BBFO中不需要参数Ns，整个流程采用3层循环的框架，对大小为S的种群，需要 Ned×Nre×Nc次评价，其时间复杂度为O(Ned×Nre×Nc)，具体的流程如下伪码所示：

4 仿真分析

为了验证BBFO的性能，本文选取10个Benchmark函数进行测试，所有函数均为30维，理论最小值均为0，详见表1。其中，f1～f7为单峰函数，用于测试算法的求解精度和收敛速度，f8～f10为多峰函数，用于测试算法的搜索能力和跳出局部最优的能力。测试所引入的对比算法有：基本BFOA[1]，ABC[10]，BSA[7]，QBFO[5]和EDABFO[6]，相关参数参照相应文献。由于BBFO将ABC引入BFOA，因此本文将其与ABC和BFOA进行纵向比较，同时，从混合型算法的角度出发，本文将BBFO与BSA、EDABFO和QBFO进行横向比较。BBFO参数设置如下：种群大小S=100，切换阈值 Pc=0.08，缩减因子 δ=0.08，定义域划分数D=50，迁移次数 Ned=10，复制次数Nre=8，趋化次数Nc=40，总迭代次数为Ned·Nre·Nc= 320 0。仿真平台CPU 2.9 GHz，内存2 GB，VS2010编译套件。

表1 测试函数

4.1 寻优性能比较

针对表1函数，ABC、BFOA和BBFO各运算30次，每次进行3200次迭代，所得统计结果见表2。BFOA是一种精细型搜索算法，全局搜索能力较弱，在测试中效果不理想，相应的，其局部寻优能力强的优点并未得到体现。ABC具有较强的全局搜索能力，也获得了较为理想的效果，但与BBFO相比，还有较大的局部调优空间。最优值可以衡量算法的精度，平均值衡量算法的性能，标准差衡量算法的稳定性。BBFO在各方面均优于ABC和BFOA，兼具两者优点。最优值和平均值的比对表明，BBFO在具有较高的全局寻优能力的同时，保持了较高的局部调优能力。标准差的对比结果表明BBFO具有较强的稳定性。

表2 寻优性能纵向对比

为进一步验证BBFO的有效性，将其与BSA、EDABFO和QBFO进行了横向比对。其中，BBFO进行1000次迭代，由于BBFO的2种趋化依据多样性进行自动切换，因此切换阈值更改为Pc=0.15，结果见表3。可以看出，BBFO的平均值和标准差均优于对比算法，表明BBFO具有较高的全局搜索能力，同时具有较强的鲁棒性。

表3 寻优性能横向对比

4.2 收敛速度比较

收敛速度是衡量算法的重要指标之一，为对BBFO的收敛速度进行验证，本文选取Rosenbrock函数和Schwefel 1.2函数进行测试。Rosenbrock函数在最优值附近存在陡峭区域，易陷入局部最优，相关算法在测试中效果并不理想，Schwefel 1.2函数最优值存在于一个狭小区域，比较考验算法的局部调优性能。结合4.1节寻优性能的比对实验，可对算法进行较为全面的测试。由图1可见：(1)BFOA收敛速度曲线整体比较平缓；(2)迭代早期BBFO收敛速度与ABC相当；(3)在某一迭代区间，BBFO开始高速收敛。BFOA全局搜索能力较弱，在2个测试中均未搜索到全局最优区域，仅在局部最优区域进行调优，因而整体效果较差。BBFO存在2种趋化方式，迭代早期种群多样性较高，采用雇佣蜂式趋化，寻优性能与ABC相当。但从某个迭代区间开始，BBFO依据种群多样性自动切换为改进的自适应步长趋化，在图中表现为曲线的急速下降。从整体效果看，BBFO明显优于ABC和BFOA，充分证明了本文算法的有效性。

图1 收敛速度比较

4.3 多样性分析

在一般情况下，较高的种群多样性，表示算法有更大的可能跳出局部最优，可以有效避免早熟。但当已经搜索到全局最优区域时，过高的种群多样性反而表示算法收敛速度较低，局部调优能力不足。BBFO中2种趋化方式的切换和t分布扰动都基于种群多样性。为验证BBFO中种群多样性的重要性，对BFOA、ABC和BBFO进行仿真比对，结果见图2，从中可以看出，ABC一直保持较高的种群多样性，具有较强的全局搜索能力，但结合图1可见，在迭代后期，ABC的收敛速度明显下降，表明ABC局部调优能力不足。基本BFOA以固定概率进行随机迁移，很大程度上提高了种群的多样性，但其繁殖方式导致多样性迅速下降，所以多样性曲线以固定迭代代数波动。BBFO在迭代早期拥有较强的全局搜索能力，相应多样性保持在一个较高的水平上，在迭代后期，随着趋化方式的改变，算法侧重于局部调优，种群多样性迅速下降。特别的，图2(a)中BBFO的多样性曲线在迭代后期出现了剧烈的波动，原因是基于t分布扰动的复制方式在起作用，随着多样性的降低，t分布近似于柯西分布，可以产生较大的扰动。整体来看，BBFO依据多样性进行趋化方式自动切换的理念是合理可行的，效果非常明显。

图2 种群多样性比较

5 结束语

在对细菌觅食优化算法进行研究的基础上，本文提出一种混合蜂群算法的自适应细菌觅食优化算法(BBFO)。通过设计新的雇佣蜂式趋化方式提高了全局搜索能力，同时改进BFOA原有趋化中的固定步长为自适应步长，充分发挥了BFOA局部调优能力强的优点。在此基础上，引入种群多样性评价，并依据评价结果完成2种趋化方式的自动切换。提出基于t分布扰动的复制方式，有效提高了算法的收敛速度和求解精度。此外，还将种群多样性作为t分布的自由度，使扰动强度可以自适应调节。为避免算法早熟，提出基于对立学习的侦察蜂式迁移，在跳出局部最优的同时提高了种群的多样性。实验结果表明，本文算法在寻优能力、求解精度和收敛速度方面均优于对比算法，并具有较强的稳定性。下一步工作是利用该算法解决更高维复杂的工程问题，并应用于相关收敛性理论的研究。

[1]Passino K M.Biomimicry of Bacterial Foraging for Distributed Optimization and Control[J].IEEE Control Systems,2002,22(3):52-67.

[2]Pandit N,Tripathi A,Tapaswi S,et al.An Improved Bacterial Foraging Algorithm for Combined Static/Dynamic Environmental Economic Dispatch[J].Applied Soft Computing,2012,36(12):3500-3513.

[3]Sathya P D,Kayalvizhi R.Modified Bacterial Foraging Algorithm Based Multilevel Thresholding for Image Segmentation[J].Engineering Applications of Artificial Intelligence,2011,24(4):595-615.

[4]Chatzis S P,Koukas S.Numerical Optimization Using Synergetic Swarms of Foraging Bacterial Populations[J].Expert Systems with Applications,2011,38(12):15332-15343.

[5]章国勇,伍永刚,谭宇翔.一种具有量子行为的细菌觅食优化算法[J].电子与信息学报,2013,35(3):614-621.

[6]王雪松,程玉虎,郝名林.基于细菌觅食行为的分布估计算法在预测控制中的应用[J].电子学报,2012,38(2):333-339.

[7]Tang W J,Wu Q H,Saunders J R.A Bacterial Swarming Algorithm for Global Optimization[C]//Proceedings of CEC’07.Singapore:IEEE Press,2007:1207-1212.

[8]刘小龙,赵奎领.基于免疫算法的细菌觅食优化算法[J].计算机应用,2012,32(3):634-637.

[9]刘小龙,李荣钧,杨 萍.基于高斯分布估计的细菌觅食优化算法[J].控制与决策,2011,26(8):1233-1238.

[10]Akay B,Karaboga D.A Modified Artificial Bee Colony Algorithm for Real-parameter Optimization[J].Information Sciences,2012,192(6):120-142.

[11]El-Abd M.Performance Assessment of Foraging Algorithms Vs.Evolutionary Algorithms[J].Information Sciences,2012,182(1):243-263.

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

[13]Abraham A,Biswas A,Dasgupta S,et al.Analysis of Reproduction Operator in Bacterial Foraging Optimization Algorithm[C]//Proceedings of CEC’08.Hong Kong,China:[s.n.],2008:1476-1483.