基于细菌趋药性和当前最优解策略的人工蜂群算法

周长喜　毛　力　吴　滨　杨　弘　肖　炜

1(江南大学物联网工程学院　江苏 无锡 214122)

2(轻工过程先进控制教育部重点实验室　江苏 无锡 214122)

3(中国水产科学研究院淡水渔业研究中心　江苏 无锡 214081)



基于细菌趋药性和当前最优解策略的人工蜂群算法

周长喜1,2毛力1,2吴滨1,2杨弘3肖炜3

1(江南大学物联网工程学院江苏 无锡 214122)

2(轻工过程先进控制教育部重点实验室江苏 无锡 214122)

3(中国水产科学研究院淡水渔业研究中心江苏 无锡 214081)

摘要为了克服人工蜂群算法在求解函数优化问题中所存在的收敛精度低、收敛速度慢的缺点，提出一种基于细菌趋药性和当前最优解策略的人工蜂群算法。该算法将细菌觅食优化算法中的趋向性操作引入到雇佣蜂的局部搜索策略中，然后跟随蜂在当前最优解的基础上继续进行寻优，从而提高了人工蜂群算法的局部搜索能力。8个标准测试函数的仿真实验结果表明，与基本人工蜂群算法相比，改进后的人工蜂群算法在寻优精度和收敛速度上均有明显提高。

关键词人工蜂群算法当前最优解细菌趋药性局部搜索

0引言

人工蜂群ABC(Aartificial Bee Colony)算法[1]是Karaboga在2005年提出的一种模拟蜜蜂采蜜行为的仿生智能优化算法。ABC算法因其结构简单、易于实现、控制参数较少、计算简洁等优点历来备受国内外学者的广泛关注，成为群智能优化算法领域的研究热点之一。但文献[2-6]都已指出ABC算法和其他的群智能算法一样，在求解函数优化问题中也存在收敛精度低、收敛速度慢的缺点。针对该问题，许多学者纷纷提出改进方案。如文献[7]提出：利用当前全局最优解代替随机选取的邻域个体，并根据当前全局最优解的适应度调整邻域搜索步长，提高收敛精度和收敛速度；文献[8]提出：利用混沌序列的随机性、遍历性和规律性，设计一种混沌局部搜索算子，并将其嵌入蜂群算法框架中，以有效提高在当前最优解周围进行局部搜索的能力；文献[9]则提出了基于极值优化策略高效率的寻优机制重新设计ABC算法中跟随蜂的局部搜索方案，从而提高算法的寻优精度和收敛速度。由此可见，改进ABC算法的局部搜索能力，对提高算法的性能和扩大其适用范围具有重要的研究意义。

为了增强ABC算法的局部搜索能力，本文提出一种基于细菌趋药性和当前最优解策略的人工蜂群算法(BCABC)。该算法把细菌觅食优化算法中的趋向性操作引入到雇佣蜂的局部搜索策略中，然后跟随蜂在当前最优解的周围进一步进行局部搜索，从而有效提高了人工蜂群算法的局部搜索能力，使算法的收敛精度和收敛速度得到明显改善和提高。

1人工蜂群算法

人工蜂群算法在求解最小值优化问题Min(f(X))时，将优质蜜源的位置抽象成优化问题的可行解，人工蜂群寻找蜜源的过程就是算法搜寻最优解的过程。该算法把人工蜂群分为雇佣蜂、跟随蜂和侦查蜂三种角色，并让雇佣蜂、跟随蜂和蜜源数目相等且一一对应。而侦查蜂由进化停滞的雇佣蜂转化而来，蜜源的含蜜量则对应优化问题的适应度值。算法通过三种蜜蜂之间的相互协作来实现对最优蜜源的搜索过程。算法一次迭代过程的具体描述如下：

对于最小值优化问题Min(f(X))，其中f(X)为被优化的目标函数。假设初始种群含有SN个解(2SN个个体)，每个解Xi(i=1，2，…，SN)是一个D维向量，其中每个解与蜜源、雇佣蜂和跟随蜂一一对应。

(1) 雇佣蜂负责全局搜索：依次对雇佣蜂中每个个体进行更新操作，即随机选择个体Xi中任意的一维分量按式(1)进行变异，产生新个体。

(1)

Xi=X'i f(X'i)

(2)

(3)

(2) 跟随蜂在部分优质蜜源附近作局部搜索：跟随蜂依据概率从种群中选择部分适应度值较好的蜜源Xi，由式(4)和(5)可知，拥有较优适应度值的蜜源被选中的概率也较大。首先，根据式(4)计算Xi的适应度函数fiti；然后，根据适应度函数，利用式(5)计算Xi的选择概率Pi；最后，针对选中的Xi执行与雇佣蜂相同的变异与选择操作。

fiti=11+fi fi≥01+|fi| fi<0{

(4)

(5)

其中，fi是蜜源Xi对应的被优化的目标函数f(Xi)的适应度值，fiti是蜜源Xi对应的适应度值变换后的适应度函数值。

(3) 侦查蜂处理进化停滞的个体：如果某个解Xi经过指定的limit次循环没有得到改善，则该解对应的雇佣蜂转变为侦查蜂，通过式(6)产生一个新解来代替该解[10]。

Xi=Xmin+φ×(Xmax-Xmin)

(6)

式中，φ表示区间[0，1]内的随机数，Xmax和Xmin是解空间的上、下边界。

2改进人工蜂群算法

ABC算法每次迭代过程中都通过雇佣蜂和侦察蜂执行全局搜索，在式(1)和式(6)中：xkj是随机选择的任一个体的一维分量，R和φ也是随机数，由此可知该算法的全局搜索能力很强。但该算法中，雇佣蜂和跟随蜂都是随机地选择一维分量经过变异来执行局部搜索，而雇佣蜂变异后的新个体的适应度值是不确定的：可能比原来个体优秀，也可能比原来个体差。然后根据式(2)来更新个体，如果新个体比原来个体优秀则更新，否则不更新，所以式(1)所示的雇佣蜂在邻域的局部搜索能力较差；同理，跟随蜂也因为盲目地选择一维变量进行变异，从而降低了产生更优秀个体的概率，使个体不被更新的可能性变大，增加了无效搜索次数，进而致使其局部搜索效率下降。综上，这一系列问题导致该算法出现寻优精度不高、收敛缓慢的弊端。

2.1基于细菌觅食算法中的趋药性的局部搜索策略

细菌觅食优化BFO(Bacteria Foraging Optimization)算法[11]是Passino在2002年根据人类大肠杆菌觅食行为提出的一种仿生学算法。该算法把细菌的觅食行为抽象为趋向性、复制和迁移三个操作。其中，趋向性操作包括翻转和向前移动两个过程，将细菌向任意方向移动单位步长定义为翻转，而每当细菌完成一次翻转后，就检查其适应度值是否改善，若适应度值得到改善，细菌将沿同一方向继续移动，如此循环直至适应度不再改善，或达到预定的移动步数Ns，此过程被定义为向前游动。BFO算法中的趋向性操作实质上是一种局部搜索策略，细菌按式(7)更新位置：

(7)

式中，θi(j,k,l)为第i个细菌在第j次趋向性操作、第k次复制操作、第l次迁移操作后的位置；C(i)表示细菌i向前翻转的步长；Δ(i)表示随机翻转方向。

为了有效地提高雇佣蜂的局部搜索能力，把具有良好局部搜索性能的细菌趋向性操作引入到ABC算法中，使该算法具有较快的收敛速度和较高的寻优精度。其具体思路是：将式(1)中的个体变异部分R×(xij-xkj)视为细菌的翻转，式(1)整体视为细菌向前游动，这样ABC算法中的雇佣蜂就具有像细菌一样的趋药性行为。为了进一步提高雇佣蜂在邻域的搜索效率，让蜜蜂在D维空间中逐维尝试翻转和游动，在适应度值有所提高时，让蜜蜂继续在该有利的维度上向前移动。

2.2基于当前最优解的跟随蜂局部搜索策略

当前最优蜜源的位置对改善ABC算法的收敛性能是一项极为有用的信息，跟随蜂可以根据雇佣蜂所传来的蜜源信息来比较蜜源的优劣，进而选择当前的最优蜜源并在其周围进行搜索。为了加快跟随蜂的收敛速度，令其在雇佣蜂最优解[12]的基础上进一步进行寻优，并且在每次迭代中逐维更新蜜源每一维度的值，以增加该可行解在搜索空间中的多样性。因此本文提出了基于当前最优解引导的搜索策略公式：

(8)

与基本ABC算法中的搜索策略不同，本文所采用的是跟随蜂在当前最优解的引导下在自身周围进行局部搜索的策略。fb的值可以适时调节步长，有助于跟随蜂寻找新位置，调高寻优性能。在迭代初期，由于fb的值较大，有效地扩大了领域的搜索范围，提高了算法的局部搜索能力；而随着迭代次数的增加，fb的值逐渐变小，有效的缩小领域的搜索范围，将有助于算法进行深度寻优并能快速寻找到最优解。

2.3基于细菌趋药性和当前最优解策略的ABC算法流程

对于最小值优化问题Min(f(X))，改进后的人工蜂群算法实现的具体步骤如下：

1) 初始化算法参数，随机产生SN个解，每个解Xi=(xi1,xi2,…,xiD)是一个D维向量，最大迭代次数MCN、最大移动步数Ns、并指定侦察蜂用于判断个体是否陷入停滞的控制参数limit的值。

2) 对种群中每个雇佣蜂Xi在D维度空间中利用式(1)逐维进行翻转，并用式(2)对其更新。如果翻转后适应度值得到改善，则继续按照翻转的方向向前移动，直至适应度值不再改善或达到设定的最大移动步数Ns为止。

3) 记录此次迭代中雇佣蜂的最优解Xb，以供式(8)使用。

4) 根据式(4)计算Xi的适应度函数值fiti，再利用式(5)计算Xi的选择概率Pi。

5) 跟随蜂依据概率Pi选择部分适应度较好的蜜源，然后每个跟随蜂再根据式(8)在它的邻域附近逐维进行局部搜索，并用式(3)记录其未更新次数triali。

6) 侦查蜂检查是否存在连续limit次迭代都没有更新的个体，若存在则按式(6)产生一个新解代替原来的陷入局部最优的解。

7) 记录到目前为止的最优解。

8) 判断是否达到最大迭代次数MCN，若满足，则输出最优解，否则转到步骤2。

3仿真实验及分析

为了评估BCABC算法的性能，本文使用了8个典型的测函数[13]对BCABC算法与ABC算法[14]以及文献[7]中提出的改进ABC(Best-so-far ABC)算法进行对比试验，进而比较三种算法的稳定性、寻优精度和收敛速度。

3.1测试函数选择

表1列出了8个测试函数的搜索范围和理论最优值。其中：f1-f3是单模态函数，在定义域内只有一个极值点，主要用来测试算法的寻优精度和收敛速度；f4-f7是非线性多模态函数，存在多个局部极值点，用来测试算法的全局寻优性能和避免早熟的能力；f8被称作变态函数，该函数的变量之间具有很强的关联性，并且理论最优值位于一个弯曲的、平滑路径上的谷底，由于该函数较特殊，通常用来评价优化算法的性能。

表1　测试函数的搜索范围和理论最优值

续表1

Sphere函数：

Step函数：

Schwefel’s函数：

Rastrigin函数：

Ackley函数：

f5(x)= -20exp-0.21n∑ni=1x2iæèçöø÷-

Griewank函数：

Levy函数：

Rosenbrock函数：

3.2实验结果与分析

在做BCABC、ABC和Best-so-far ABC三种算法求解函数最小值优化问题的对比实验时，参数设置如下：种群规模SN=100，最大移动步数Ns=4，判断是否陷入停滞的控制参数limit=300，维度D=30，最大循环次数MCN的值为1000。

为了测试算法的性能，分别使用以上三种算法对每个测试函数在30维的条件下进行30次独立实验。测试结果如表2所示，得出其所对应的最优值、最差值、平均值、标准差和平均时耗，其中，平均时耗指的是三种算法分别对8个测试函数在各自独立运行30次达到收敛稳定精度所需要时间的平均值；同时，图1—图8还分别给出了三种算法对8个测试函数在各自独立运行30次的平均适应值的进化曲线。

表2中的数据表明：基本ABC算法的稳定性较差、收敛速度慢而且收敛精度不高。Best-so-far ABC算法利用当前最优解及其对应的适应度值改进跟随蜂的邻域搜索方式，从而增强了该算法的局部搜索能力，也在一定程度上提高了算法的求解质量。BCABC算法则把细菌觅食优化算法里的趋向性操作加入到了雇佣蜂局部搜索策略中，然后跟随蜂在当前最优解的周围进一步进行局部搜索，显著提高了该算法的局部搜索能力，并进而使算法的性能得到明显提高。

表2　30维函数测试结果的比较

从表2中可以看出，BCABC算法的最优值和最差值的精度与基本ABC算法和Best-so-far ABC算法相比明显得到提高，并且BCABC算法对各测试函数均具有较高的寻优精度。对除f2以外的所有测试函数，BCABC算法的均值和方差都优于另外两种算法，而且存在数量级级别的提升，这说明BCABC算法稳定性较高，具有较好的鲁棒性。

另外，从表2中可知，BCABC算法的平均时耗小于基本ABC算法和Best-so-far ABC算法，虽然BCABC算法在每次迭代过程中都在雇佣蜂搜索阶段尝试在各个方向上进行游动增加了计算量，从而增加了每次迭代的运行时间，但是从图1—图8可以看出，BCABC算法达到稳定收敛精度所需要的迭代次数远小于基本ABC算法和Best-so-far ABC算法，特别是对函数f2、f4和f6在迭代几十次就收敛到理论最优值。显然，BCABC算法表现出比基本ABC算法和Best-so-far ABC算法更高的收敛精度和更快的收敛速度，并且在进化中BCABC算法始终保持向最优解进化的趋势。这表明BFO算法中趋向性操作的局部搜索策略和基于当前最优解策略的跟随蜂局部搜索策略明显的改善了基本ABC算法中存在的一些不足之处，并能有效地提高算法的寻优精度和收敛速度，防止早熟收敛现象的出现。

图1　Sphere函数的收敛曲线

图2　Step函数的收敛曲线

图3　Sehwefel’s函数的收敛曲线

图4　Rastrigin函数的收敛曲线

图5　Ackley函数的收敛曲线

图6　Griewank函数的收敛曲线

图7　Levy函数收敛曲线

图8　Rosenbrock函数的收敛曲线

4结语

本文在对算法分析的基础上，指出基本ABC算法中存在的雇佣蜂和跟随蜂局部搜索能力较差的问题，并提出了具体的改进方案，即把BFO算法中的趋向性操作加入到基本ABC算法中雇佣蜂的局部搜索策略中，跟随蜂再在当前最优解的引导下进一步进行局部搜索。而仿真实验结果也表明，在求解函数最小值优化问题时，本文给出的改进基本ABC算法取得了较好的效果, 具有较强的鲁棒性，并能有效避免算法陷入局部最优，使算法具有更高的寻优精度和更快的收敛速度。

参考文献

[1] Karaboga D. An idea based on honey bee swarm for numerical optimiz- ation[R]. Technical Report-TR06.Kayseri: Erciyes Unversity, Engineer- ing Faculty, Computer Engineering Department, 2005.

[2] 杨建卫. 一种采用蜂群全局引导搜索策略的入侵杂草优化改进算法[J]. 计算机应用与软件, 2014,31(4):161-164.

[3] Rajasekhar A, Abraham A, Pant M. Levy mutated artificial bee colony algorithm for global optimization[C]//IEEE International Conference on Systems, Man and Cybernetics, 2011: 655-662.

[4] Wu B, Fan S H. Improved artificial bee colony algorithm with chaos[M]//Computer Science For Environmental Engineering and Ecoinformatics, Berlin: Springer, 2011: 51-56.

[5] 张鹏, 刘弘, 王爱霖. 基于人工蜂群算法的疏散运动仿真[J]. 计算机工程, 2013, 39(7): 261-264.

[6] Gao Weifeng, Liu Sanyang. Improved artificial bee colony algorithm for global optimization[J]. Information Processing Letters, 2011,111(17):871-882.

[7] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-so-far selection in artificial bee colony a1gorithm[J]. Applied Soft computing, 2011,11(2):2888-2901.

[8] 王翔, 李志勇, 许国艺. 基于混沌局部搜索算子的人工蜂群算法[J]. 计算机应用, 2012,32(4):1033-1036, 1040.

[9] 葛宇, 梁静, 王学平. 基于极值优化策略的改进的人工蜂群算法[J]. 计算机科学, 2013,40(6):247-251.

[10] Kang Fei, Li Junjie, Ma Zhenyue. Rosenbrock artificia1 bee colony algorithm for accurate global optimization of numerical functions[J]. Information Sciences, 2011,181(16):3508-353l.

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

[12] Gao Weifeng, Liusanyang, Huang Ling-ling. A global best artificial bee colony algorithm for global optimization[J]. Journal of Comput-ational and Applied Mathematics, 2012, 236(11):2741-2753.

[13] 张银雪, 田学民, 曹玉苹. 改进搜索策略的人工蜂群算法[J]. 计算机应用, 2012, 32(12): 3326-3330.

[14] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm[J]. Journal of Global Optimization, 2007,39(3):459-471.

ARTIFICIAL BEE COLONY ALGORITHM BASED ON STRATEGY OF BACTERIAL CHEMOTAXIS BEHAVIOUR AND CURRENT OPTIMAL SOLUTION

Zhou Changxi1,2Mao Li1,2Wu Bin1,2Yang Hong3Xiao Wei3

1(SchoolofInternetofThings,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(KeyLaboratoryofAdvancedProcessControlforLightIndustry(MinistryofEducation),Wuxi214122,Jiangsu,China)3(FreshwaterFisheriesResearchCenterofChineseAcademyofFisherySciences,Wuxi214081,Jiangsu,China)

AbstractWe proposed an artificial bee colony (ABC) algorithm in this paper which is based on the strategy of bacterial chemotaxis behaviour and current optimal solution in order to overcome the drawbacks of low convergence accuracy and slow convergence rate the conventional ABC algorithm has in solving function optimisation problem. This algorithm introduces the chemotaxis operation in bacterial foraging optimisation algorithm into local search policy of employed bees, and then the onlooker bees continue to search for the optimal solution based upon the present optimal solution, therefore the local search capability of ABC algorithm is enhanced. It is indicted by the results of simulation experiments on eight standard test functions that the improved ABC algorithm gains significant improvement on optimisation accuracy and convergence rate compared with basic ABC algorithm.

KeywordsArtificial bee colony (ABC)Current optimal solutionBacterial chemotaxis behaviourLocal search

中图分类号TP18

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.01.065

收稿日期：2014-06-26。国家青年科学基金项目(F030204)；轻工过程先进控制教育部重点实验室开放课题资助(江南大学)项目(APCLI1004)；现代农业产业技术体系专项(CARS-49)。周长喜，硕士生，主研领域：智能算法。毛力，副教授。吴滨，讲师。杨弘，研究员。肖炜，助理研究员。