一种具有量子行为的细菌觅食优化算法

章国勇 伍永刚 谭宇翔

(华中科技大学水电与数字化工程学院 武汉 430074)

1 引言

细菌觅食优化[1](Bacterial Foraging Optimization, BFO)算法是由Passino在Breg等人的研究成果基础上，从微生物的行为机制出发，通过模拟大肠杆菌觅食行为提出的一种新的全局优化进化算法，现已成功应用于电力系统优化与控制[2]、函数优化[3]、图像处理[4]等中。相比Muller等人提出的基于单个细菌运动行为的细菌趋药性(BC)算法，BFO通过细菌群体的竞争与协作来实现优化，是一种基于群体的搜索技术。但Tang等人[5]的仿真实验指出，在现行的BFO群体感应机制下，细菌游动时不进行群体内通信时在收敛速度和精度上反而优于存在群体感应机制的BFO。同时，现有仿真实例表明，对于多维复杂优化问题，细菌的觅食机制容易引起算法早熟收敛[3]，较难获得全局最优。

为克服BFO算法的上述缺陷，学者们从算法参数和算法融合上进行了研究。针对趋化步长对算法搜索能力的影响，Mishra[6]提出用TS模糊机制选取最优步长的模糊细菌觅食算法；Das等人[7]提出一种随适应度值自适应变化的趋化步长控制策略；Chen等人[8]提出用自适应增量调制来控制趋向性步长；Tang等人[9]将PSO进化机制引入到BFO趋化操作中。在不增加算法复杂性的前提下，上述方法有效地提高了算法收敛速度。根据 Abraham 等人[10]对BFO中繁殖操作效果的数学分析表明，繁殖操作是算法的主要驱动因子，而现行BFO中采用的直接复制方法大大降低了种群的多样性。根据NFL(无免费午餐)定理，文献[11-13]分别结合差分进化、分布估计和免疫算法对BFO进行改善，结合各自算法的优点取得了不错的效果，但对于多峰高维函数的优化过程中表现出了寻优精度较低、成功率不高等缺陷。

从现行BFO的相关研究可以看出，细菌觅食机制侧重于个体的局部搜索而缺乏全局空间寻优能力[14]。Sun等人[15]从量子力学的角度出发，提出一种具有量子行为的粒子群(QPSO)算法。相比粒子群算法，QPSO基于群体信息建立了量子空间下概率分布模型，使得个体能以某一概率出现在整个可行搜索空间的任意位置，表现出了更强的全局搜索性能和更大的种群随机性。基于此，本文在细菌的繁殖阶段引入量子行为的概念，充分利用细菌群体的共享信息构建量子空间下细菌群的Delta势阱模型，通过蒙特卡罗随机采样完成对细菌群的繁殖；同时，针对细菌趋化步长提出了一种动态缩进控制策略，增加了种群的多样性和全局寻优几率。通过理论分析和仿真实验验证了所提出算法的有效性。

2 具有量子行为的细菌觅食优化算法设计

2.1 QBFO原理描述

由BFO算法的基本原理可知，细菌个体寻优由趋化、繁殖和迁移 3个操作通过 3层嵌套循环完成[16]。通过细菌的趋化操作实现个体自身较强的局部搜索能力，而细菌的繁殖算子相当于进化算法的选择操作，通过淘汰觅食能力差的个体最终实现算法的收敛。BFO中繁殖算子将提高细菌的收敛速度和精度[12]，但由于细菌移动步长过小、进化过程中个体间缺乏有效的信息共享机制等因素，采用直接个体复制的繁殖操作将导致种群多样性的缺乏，算法容易因此陷入局部最小区域。另外，在BFO趋化算子的游动和翻转中，细菌游动步长C是控制种群多样性和收敛性的重要参数。一般对于C的取值不应小于某一特定数值，这样能够有效避免算法过早收敛；但当C太大时会明显降低算法的收敛速度，丢失寻找到最优解的机会[16]。标准BFO中采用固定步长的控制方式，但实际操作中难以确定C的取值。

基于上述问题, 本文将量子行为引入到细菌群繁殖算子中，形成具有量子行为的细菌觅食优化(QBFO)算法。QBFO 的设计思想是：在繁殖阶段通过利用细菌群共享信息建立量子空间下细菌个体的概率密度函数，由蒙特卡洛随机采样完成各细菌个体位置的更新，进而实现种群的繁殖操作，避免因直接复制导致的种群多样性丢失。由文献[15]对量子系统中个体的收敛分析可知，在QBFO中，需对群体建立一个量子化的势阱来束缚个体，使得群体具有聚集态，处于量子束缚态的个体能以一定的概率密度出现在空间任意点，且满足当粒子与中心的距离趋向无穷时概率趋近0。现假设在一个D维的搜索空间中，t时刻第i个体的位置表示为xi(t)=[xi1(t),xi2(t),…,xiD(t)]T，个体最好位置为Pi(t)=[Pi1(t),Pi2(t),…,PiD(t)]T，全局最好位置为Pg(t)=[Pg1(t),Pg2(t),…,PgD(t)]T，其中g为全局最优位置下标。根据Clerc等人[17]对个体运行轨迹的分析表明，要保证算法的收敛性，个体i第d维变量的位置必须收敛于其自身局部吸引子Pd，并满足以下条件：

其中Y=xid-Pd，表示个体所处位置xid与吸引子的距离。将其代入量子力学中Schrodinger方程(式3)，可得个体每一维的波函数ψ(Y,t)(式4)和概率密度函数Q(Y)(式5)，其中L为Delta势阱的特征长度。

其中参数β为收缩-扩张系数，必须满足β＜1.782以保证算法收敛[15]，通常采用随着进化代数t从β1线性改变至β2的方式(式8)；mbest为种群最好位置向量的平均值，如式(9)所示：

由QBFO的更新方程(式6)可知，细菌位置更新过程中的每一维变量xid服从一个以吸引子Pd为中心，L为范围的概率分布。细菌群位置在测量前没有既定的规程，采用概率分布函数更新细菌个体位置使其能以一定的概率分布出现在任意位置，达到全局搜索。相比传统进化算法，QBFO是统计理论与随机优化的结合，具有更大的随机性和更强的全局搜索能力。

2.2 QBFO执行步骤

针对标准BFO趋化操作中固定步长的缺陷，该文提出了一种动态缩进控制策略，在保证细菌收敛性的同时增大细菌个体寻优空间。据此，该文提出的QBFO算法具体实现步骤如下：

步骤 1参数初始化。包括细菌个体数s，迁移次数Ned，繁殖次数Nre，趋化次数Nc，游动次数Ns，迁移概率ped。

步骤 2 种群初始化。在解空间中随机生成s个独立的细菌个体向量xi。

步骤 3 计算各细菌个体适应度函数值J。

步骤 4 开始循环操作。迁移循环l=1 :Ned；繁殖循环k=1 :Nre；趋化循环j=1 :Nc。

步骤 5 执行趋化操作循环。forj=1 :Nc，对每个细菌i按如下步骤执行：

(a)翻滚：产生一个随机向量Δ∈Rn进行方向调整，向量Δ的每一个元素为区间[-1,1]的随机数。对个体变量xid(d=1,2,…,D)按式(10)更新细菌位置，其余的D-1个变量保持不变。

其中C(i,j)表示向前游动的步长单位，φ(i)表示旋转后选择的随机前进方向。

(b)游动：评价xi(j+1,k,l)适应度，若优于xi(j,k,l)，则将xi(j,k,l)替换为xi(j+1,k,l)，并按照此翻转的方向进行游动，直至适应值不再改善或者达到最大前进步数。

(c)d=d+1，若d=D转步骤5(d)，否则转步骤(a)继续对下一变量进行操作。

(d)j=j+1 ，按式(13)动态缩进策略改变细菌个体游动步长，其中A为动态缩进系数。

步骤6基于量子行为的细菌繁殖操作。经过一个完整的趋化循环后，更新当前群体的个体最好位置和全局最优位置。根据式(9)计算种群的平均最好位置向量mbest，并按照式(6)更新群体位置。

步骤7细菌迁徙。将所有细菌按照能量进行排序，对适应度较低的部分细菌(s·Ped)按照随机初始化的方法进行迁徙。

步骤8循环结束判断，满足则结束。

3 算法特性及收敛性说明

在 BFO 算法中，细菌趋化操作对应细菌觅食过程中的游动和方向调整策略，决定了BFO的收敛性。为了提高细菌趋化行为的效率和种群多样性，本文提出一种动态缩进步长控制策略。将趋化初始步长取变量最大寻优范围，随着趋向迭代运行动态缩进，逐步对趋化步长进行缩小，在保证细菌收敛性的同时拓宽了细菌个体寻优空间，增强了细菌个体全局寻优能力。在细菌的趋化循环完成后，进入繁殖阶段，QBFO结合了量子空间下种群的概率进化机制，利用细菌群共享信息建立各细菌个体概率密度函数，通过蒙特卡洛随机采样完成对细菌群的繁殖，使其能以一定概率对整个空间进行搜索，将有效避免算法陷入早熟收敛。

针对 BFO的收敛性分析，Das等人[7]做了相应的证明，本文在他的基础上从Solis等人[18]提出的收敛准则入手，给出QBFO的收敛性说明。对于最小化问题，给定一个目标函数f,S是f(x)的解空间(S∈ℜn)，假如算法在最优化区域Rε={z∈S|f(z)＜φ+s}找到了一点z，则这个点即为被找到的全局最小值的一个可接受近似值。现在需考虑一个算法是否能够在搜索空间中到达最优化区域。

假设1对于S的任意Borel子集A，若其测度v|A|＞0，则有

其中μt[A]是由测度μt得到A的概率。这表明对于测度大于0的任意一个集合A而言，如果采用随机取样的方法，则其无穷多次重复错过集合A的概率必定为0。由Solis准则, 可得到下面的定理：

定理1假定算法在每一步都有最优解，且目标函数f是可测函数，区域S是ℜn的可测子集，且满足假设1，设 {zk}k∞=0表示算法生成的空间位置向量，则可得

其中P[zk∈Rε]表示第k步算法生成的解θk∈Rε的概率。

4 仿真实验结果与分析

4.1 仿真设计

本节的仿真中，引入了 5个标准函数来测试QBFO的总体性能(见表1)。这些函数理论最小值均为 0，由于其全局最优解通常在一个狭小的地带，采用常规的优化方法较难获取最优值，且优化的难度随着函数维数的增加而急剧上升。对于单峰低维函数，BFO可以得到满意的优化结果，但对于多峰高维函数，其优化效果难以令人满意。因此，本文测试函数的维度均设置为30维。文中设计了6组算法对比测试实验，包括标准BFO[1]及几种改进算法：EDA-BFO[12], IBFO[13], BSO[9], DEBFO[11]和GAQPSO[19]，算法参数参照相应文献。本文提出的QBFO 算法中种群个数取 40；收缩-扩张系数：β1=1,β2=0.5；迁移概率0.25；迁移次数Ned=2；繁殖Nre=5；趋化Nc=30；游动Ns=4；动态缩进系数A=0.7。考虑到 Schwefel函数寻优空间较复杂，Ned取 3,Nc取 20。算法趋化操作迭代总次数MAXIER=Ned·Nre·Nc为300次。

4.2 仿真结果及分析

5个测试函数分别运行20次所得的目标函数最优解的均值和标准差如表 2所示，可以看出，针对函数f2,f3和f4，现有的一些改进算法基本上能获得较好的寻优结果但精度不高，本文提出的QBFO算法较其他大多数改进算法能获得较高的收敛精度，且在提高精度的同时保持最优解的标准差较小，表现出了较好的稳定性。由于上述函数最优值所在区域较平坦，在进化后期不需要优化算法对解空间进行大范围的探索，本文求解精度较文献[13]中的IBSO稍低。但从表2中可以看出，QBFO已达到较高的全局收敛精度且性能稳定，而对于IBFO，由于进化后期群体多样性较小，细菌个体在较小区域进行集中搜索以达到较高的收敛精度，但当函数最优值所在区域较狭窄时将可能导致算法陷入早熟收敛，其对函数f1和f5的测试结果充分说明了这点。同时，通过调整QBFO中控制趋化步长的动态层进系数可以增大算法对该类问题的求解精度，关于不同参数下算法性能的比较在本文4.5节有详细分析。

针对函数f1和f5而言，由于最优值附近存在陡峭区域，极易发生早熟收敛，要求种群具有较大的搜索空间。相关改进算法在上述函数中测试结果并不理想，有些算法或者不针对f5进行比较，而已有改进算法大都是通过增加迭代次数来提高算法获取全局最优的概率，其优化结果通常表现为最优解较好、平均值较差，算法寻优成功率不高。从表2中可以看到QBFO在f1和f5上的随机测试中平均最优值均在1.0e-4数量级，相比其他改进算法具有非常高的收敛精度，且在20次的测试中，函数最优值的标准差较小，每次的测试结果均在1.0e-4附近，充分体现了其较强的的稳定性和全局收敛能力。

表1 标准测试函数

表2 标准函数算法测试的平均最优值及标准差

4.3 算法性能评价

为进一步评估不同算法的时间复杂度，本文采用固定进化代数下算法最优解收敛过程以及到达确定阈值的平均进化代数、成功率两项来评价不同优化算法的优化性能。前者在一定程度上反映出算法的收敛速度，而平均进化代数体现出算法的进化速度，成功率可以体现算法的可靠性[14]。表 3给出了在给定阈值下不同算法的成功率及平均进化代数，函数设置同上。计算迭代次数中将细菌游动次数记为4，当迭代次数达到1000代而仍未满足给定值则认为算法已陷于局部最优解。从表 3可以看出，由于文中选取的函数在整个取值区间内均有无数局部极值点，QPSO和BSO算法成功率不高，但QBFO算法均能达到100%的成功率。对于函数f3和f4, QPSO和BSO算法也取得了一定成功率，但算法达到成功的进化代数均明显增多，且成功率较低，算法可靠性不高。针对函数f1和f2而言，由于函数最优值附近有陡峭的区域，极易发生早熟收敛，而函数f5的复杂性取决于远离全局最优解的局部最优解， QPSO和BSO算法很难搜索到函数的全局极值，难以实现函数优化目标。因此，本文认为QBFO针对该类多峰高维问题具有较高的适用性且能够较稳定地获得全局最优。

算法的收敛性也是检测算法性能的重要指标，图1给出了QBFO迭代过程中函数最优值和种群平均值的收敛曲线。可以看出，基于量子行为概率分布的繁殖算子使得种群平均值与最优值之间保持了较大的距离，尤其是在对函数f1和f5的求解过程中，QBFO保持了较高的种群多样性，使得细菌群能够对整个空间进行搜索。同时，动态缩进游动步长控制策略使得细菌个体在每次迭代开始时都能从一个较大的寻优空间进行搜索，继而进行动态缩进，保证了算法较好的搜索精度和较快的收敛速度。因此，从总体上看，QBFO算法借助上述机制在全局收敛性、进化代数和寻优结果质量上均优于其他2种算法。

表3 运行20次寻优成功率与平均迭代次数

图1 算法收敛测试曲线

4.4 算法种群多样性分析

在仿生优化算法的研究中，为了避免算法的过早收敛，许多学者提出了通过控制种群的多样性来提高算法总体性能。为比较BFO和QBFO算法中种群多样性的变化过程，本文选取Sphere(单峰函数)和Griewank(多峰函数)进行优化求解，采用平均粒距来评价D维函数的种群多样性[19]。

式(16)中L为变量搜索空间范围，M为种群大小，xij为个体i第j维变量，为细菌种群第j维变量的平均值。式(16)表明，种群的多样性值越小说明种群聚集在一个狭小的空间，此时可提高算法收敛精度但容易陷入局部最优；相反，种群的多样性越大时细菌群分散在较大的寻优空间，但此时算法收敛速度较慢。两种算法分别独立运行20次，变量维数为 30，趋化迭代总次数MAXIER=Ned·Nre·Nc约250次，其他设置同上。记录每次迭代的div(x)，其随算法迭代次数变化的曲线如图2所示。可以看出，BFO通过复制来完成繁殖操作将使得种群的平均粒距迅速下降，一旦种群中部分个体得到改善，其他较差个体受复制操作的影响将被替代，种群的多样性大大减少。对于单峰 Sphere函数而言，寻优过程较简单，BFO和QBFO中种群的平均粒距最终均较小，有利于提高算法收敛精度。而对于多峰Griewank函数，其全局最优解较难找到，平均粒距过小将导致算法过早陷入局部最优。相比标准BFO, QBFO通过对种群的概率分布模型进行蒙特卡洛随机采样使得处于量子束缚态的个体以一定的概率密度出现在空间任意点，保持了种群的多样性，增加了算法全局寻优的几率。

4.5 算法参数灵敏度分析

图2 BFO和QBFO种群多样性比较

对于标准 BFO 和收缩-扩张系数β的参数分析在相关文献已有讨论[16,20]，本文重点讨论动态缩进系数A对算法性能的影响。A越小，搜索步长缩减越快，游动步长越小，此时可提高趋化操作后期的收敛精度，但算法会因此过快陷入小范围局部寻优，且算法的时间复杂度也随之增加；反之，A较大可使细菌趋化操作步长衰减速度较慢，细菌个体保持较大的寻优空间，但也将因此降低算法的收敛精度。本文选择不同动态缩进系数分别进行20次优化，函数的维度均为30，优化结果如表4所示。可以看出，对于求解过程较简单的函数f3和f4，借助BFO自身较强的局部寻优能力，取A=0.60左右时较为理想，此时算法能获取较高的收敛精度，且保证算法具有较强的稳定性。而对于较复杂的函数f1,f2和f5，由于全局最优的范围较狭窄，且距离局部最优值很远。当A较小时，搜索步长缩减较快，算法难以跳出局部最优值所在区域；而当A较大时细菌游动步长一直保持较大值，个体将因此而跳过最优解区域，导致算法难以收敛到最优解区域附近。

表4 动态缩进系数敏感性分析

综合上述，通常取0.60-0.70时优化结果较为理想，此时算法能找出测试函数的全局最优且性能稳定，函数最优平均适应度值较好，在实际工程问题可根据具体情况适当调整参数以获取最优解。

5 结束语

本文将细菌个体放在量子空间中描述，充分利用量子空间下种群概率进化机制的全局搜索性能及细菌觅食行为机制的局部优化能力，提出了一种具有量子行为的细菌群觅食优化算法。文中引入了基于细菌群信息的量子概率分布模型进行种群繁殖操作，同时提出一种动态缩进的细菌游动步长控制策略，使得个体能够在局部寻优的基础上对整个空间进行搜索。仿真结果表明，对于多峰高维函数，QBFO较其他改进算法具有更高的适用性且能够较稳定地获得全局最优。后续研究主要是探讨不同势阱模型下的收敛情况，并将该方法应用于解决高维复杂工程的相应优化问题。

[1]Passino K M. Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine,2002, 22(3): 52-67.

[2]Saber A Y. Economic dispatch using particle swarm optimization with bacterial foraging effect[J].Electrical Power and Energy Systems, 2012, 34(1): 38-46.

[3]Chatzis S P and Koukas S. Numerical optimization using synergetic swarms of foraging bacterial populations[J].Expert Systems with Applications, 2011, 38(12): 15332-15343.

[4]Verma P O, Hanmandlu M, Kumar P,et al.. A novel bacterial foraging technique for edge detection[J].Pattern Recognition Letters, 2011, 32(8): 1187-1196.

[5]Tang W J, Wu Q H, and Saunders J R. Bacterial foraging algorithm for dynamic environment[C]. Proceedings of IEEE Conference on Evolutionary Computation, Canada, 2006:4467-4473.

[6]Mishra S. A hybrid least square-fuzzy bacteria foraging strategy for harmonic estimation[J].IEEE Transactions on Evolutionary Computation, 2005, 9(1): 61-73.

[7]Das S, Biswas A, Dasgupta S,et al.. Bacterial foraging optimization algorithm: theoretical foundations, analysis,and applications[J]. FoundationsofComputational Intelligence, 2009, 203: 23-55.

[8]Chen H N, Zhu Y L, and Hu K Y. Adaptive bacterial foraging optimization[J].Abstract and Applied Analysis, 2011, 2011(1):1-27.

[9]Tang W J and Wu Q H. A bacterial swarming algorithm for global optimization[C]. Proceedings of IEEE Conference on Evolutionary Computation, Singapore, 2007: 1207-1212.

[10]Abraham A, Biswas A, Dasqupta S,et al.. Analysis of reproduction operator in bacterial foraging optimization algorithm[C]. Proceedings of IEEE Congress on Evolutionary Computation, Hong Kong, 2008: 1476-1483.

[11]Biswas A, Dasgupta S, Das S,et al.. A synergy of differential evolution and bacterial foraging algorithm for global optimization[J].Neural Network World, 2007, 17(6): 607-626.

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

Liu Xiao-long, Li Rong-jun, and Yang Ping. Bacterial foraging optimization algorithm based on estimation of distribution[J].Control and Decision, 2011, 26(8): 1233-1238.

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

Liu Xiao-long and Zhao Kui-ling. Bacterial foraging optimization algorithm based on immune algorithm[J].Journal of Computer Applications, 2012, 32(3): 634-637, 653.

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

Wang Xue-song, Cheng Yu-hu, and Hao Ming-lin. Estimation of distribution algorithm based on bacterial foraging and its application in predictive control[J].Acta Electronic Sinica,2010, 38(2): 333-339.

[15]Sun J, Feng B, and Xu W B. Particle swarm optimization with particles having quantum behavior[C].Proceedings of the IEEE Congress on Evolutionary Computation, USA,2004: 325-331.

[16]周雅兰. 细菌觅食优化算法的研究与应用[J]. 计算机工程与应用, 2010, 46(20): 16-21.

Zhou Ya-lan. Research and application on bacteria foraging optimization algorithm[J].Computer Engineering and Applications, 2010, 46(20): 16-21.

[17]Clerc M and Kennedy J. The particle swarm: explosion,stability, and convergence in a multi-dimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002, 6(1): 58-73.

[18]Solis F J and Wets R J B. Minimization by random search techniques[J].Mathematics of Operations Research, 1981,6(1): 19-30.

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

[20]方伟, 孙俊, 谢振平, 等. 量子粒子群优化算法的收敛性分析及控制参数研究[J]. 物理学报, 2010, 59(6): 3686-3694.

Fang Wei, Sun Jun, Xie Zhen-ping,et al.. Convergence analysis of quantum-behaved particle swarm optimization algorithm and study on its control parameter[J].Acta Physica Sinica, 2010, 59(6): 3686-3694.