基于混沌趋化行为的人工蜂群算法

孙晨骜，臧培荃，吴 滨，顾晓峰，周长喜

（江南大学 电子工程系 轻工过程先进控制教育部重点实验室，江苏 无锡214122）

0 引 言

人工蜂群 （artificial bee colony，ABC）算法［1］存在收敛精度低、容易早熟的缺陷。针对该问题已经有多种改进方案，例如，在蜂群的搜索方程中增加全局最优解，可提高算法的收敛精度和速度［2］；利用极值优化思想重新设计ABC算法中跟随蜂的搜索方程，可提高算法的局部搜索能力［3］；通过引入当前最优思想，蜂群在当前最优解的基础上进行搜索，可提高算法的收敛精度和速度［4］；根据领域蜜源质量动态调整信息共享程度，也能加快算法的收敛速度［5］。为进一步改善ABC算法的性能，提出一种基于混沌趋化行为的人工蜂群 （CCABC）算法。改进后的算法结合细菌觅食算法的趋化性和混沌理论的遍历性，克服标准ABC算法中随机搜索更优解的缺点，能更快地收敛到最优解。

1 标准人工蜂群算法

在标准ABC算法中，蜂群由雇佣蜂、跟随蜂和侦查蜂3组蜜蜂组成，其中蜂群、最小值优化问题中的可行解以及解的适应度值等的定义可参考文献 ［6］。雇佣蜂进行全局搜索，确定蜜源的信息并反馈给跟随蜂；跟随蜂选择其中一个蜜源并在其周围进行局部搜索，如果在设定的搜索次数limit内未搜索到更好的蜜源，则放弃该蜜源，同时雇佣蜂变为侦查蜂，并随机产生一个新的蜜源。

ABC算法的实现是一个迭代优化过程，具体描述如下：对于最小值优化问题，设f（x）是被优化的目标函数，且有SN 个解，每个解Xi＝ （xi1，xi2，…，xiD）为D 维向量。在算法初始化阶段，照式 （1）随机产生SN 个解；开始迭代搜索过程，雇佣蜂根据式 （2）进行全局搜索，产生一组新解；新解vi的适应度优于xi的适应度时更新解，否则保留xi；当所有雇佣蜂完成式 （2）计算后，跟随蜂按式 （3）选取部分优质解，并在其附近进行局部搜索

其中，M 和N 分别表示搜索空间的上下限；i，j均为随机选择；φ为 ［－1，1］的随机数，决定xi领域的生成范围；fiti为xi对应的适应度，可由式 （4）计算得到

在搜索过程中，如果解xi经过limit次迭代后仍未搜索到更好的解，则该解将被放弃；同时，对应的雇佣蜂变为侦查蜂，并按照式（1）在搜索空间随机产生一个新的解。

2 改进的人工蜂群算法CCABC

从式 （1）和式 （2）中可发现，ABC 算法中的搜索过程都是随机的，如果新个体优于原个体则更新，否则不更新。这样的随机搜索过程降低了算法的搜索效率和收敛精度，而且跟随蜂基于轮盘赌选择优质蜜源的方式可能会使算法陷入局部最优［7］。针对此问题，本文引入了细菌觅食算法中的趋化操作和混沌变量进行改进。

2.1 细菌趋化行为

细菌觅食优化 （bacteria foraging optimization，BFO）［8］算法是Passino基于大肠杆菌在肠道内吞噬食物的行为而提出的一种仿生类算法。BFO 算法包括趋化、复制和迁移3个步骤，其中细菌向营养丰富区聚集的行为称为趋化，趋化过程包括翻转和前进。细菌向任意方向移动单位步长称为翻转；如果翻转后细菌的适应度得到改善，则沿同一方向继续移动，直至适应度不再改善或达到预定步数Ns，此过程称为前进。细菌的趋化行为具体描述如下

综上可知，趋化行为可以提高算法的局部搜索能力，减小算法陷入局部最优的概率，因此在ABC 算法中引入BFO 算法的趋化行为，将式 （2）的搜索策略分解为两步

其中，式 （6）和式 （7）分别代表翻转和前进，Li表示翻转后过程的移动步长。

2.2 混沌优化

混沌是自然界中普遍存在的一种非线性现象，具有随机性和遍历性等特点［10］。其基本原理为：通过混沌映射模型将需要优化的参数映射到混沌变量空间，在混沌变量空间中进行寻优搜索，最后将获得的最优解映射到原参数空间［11］。本文使用Logistic混沌映射模型，其迭代方程为

由于混沌的遍历性可以提高局部搜索能力，所以在趋化操作的翻转步骤中引入混沌变量，提出新的翻转公式

式中：ch（i）——Logistic混沌变量序列，itx 和itmax——当前和最大迭代次数，exp（－itx／itmax）——动态参数，使最优解搜索过程中，随着迭代次数的增加，搜索空间逐渐减小，从而进一步提高算法的性能。

2.3 CCABC的算法流程

步骤1 设定最大迭代次数itmax，趋化行为中最大移动步数Ns，判断雇佣蜂是否陷入停滞的参数limit，混沌序列长度K，解的维数D，解的数量SN。

步骤2 根据式 （8）生成Logistic混沌变量序列，根据式 （1）随机产生SN 个可行解。

步骤3 根据式 （4）计算每个解的适应度。

步骤4 对每个雇佣蜂根据式 （9）进行翻转操作，根据式 （7）进行前进操作，然后计算并比较适应度，如果得到改善则继续进行前进操作，直至适应度不再改善或达到最大前进步数Ns。

步骤5 对每个跟随蜂以式（3）计算概率，选择优质解，执行与步骤4中与雇佣蜂相同的操作，记录未更新次数。

步骤6 检查步骤5 中未更新次数是否达到设定值limit。若达到，则根据式 （1）产生一个新的解替代原来的解；若没有达到，则继续进行迭代运算。

步骤7 记录并更新最优解。

步骤8 检查当前迭代次数是否达到最大迭代次数itmax，若达到，则结束算法并输出最优解；否则返回步骤3。

3 仿真实验与分析

3.1 测试函数的选择

为了测试CCABC算法的性能，使用5个典型测试函数进行仿真实验，并与标准ABC 算法和文献 ［3］中的Bestso－far ABC算法进行比较。表1列出了测试函数的搜索范围和理论最优值。Sphere和Step函数为单峰函数，主要测试算法的搜索精度；Rastrgin和Ackley函数为非线性多峰函数，存在多个局部极值点，主要测试算法的全局搜索能力［12］；Rosenbrock为复杂函数，其最小值位于抛物线形的山谷中，但山谷内值的变化较小，找到最小值比较困难，所以该函数常用来测试算法的综合性能。

表1 测试函数

3.2 仿真结果与分析

在对标准ABC、Best－so－far ABC （表2 中简称 BABC）和提出的CCABC这3种算法的仿真实验中，设置最大迭代次数itmax＝1000，解的个数SN＝50，解的维度D＝30，最大前进步数Ns＝3，判断停滞控制参数limit＝10，混沌序列长度K＝40。为了获得可靠的实验结果，进行50次独立实验取其平均值，结果列于表2，适应度的进化曲线示于图1～图5，其中表2中的时间表示搜寻最优解过程达到稳定的收敛精度所需的时间。

从表2 可以看出，对于Sphere 和Rosenbrock 函数，CCABC算法的各项测试数据明显优于标准ABC 算法和Best－so－far ABC算法。最优值、最差值和均值的减小表明CCABC算法的收敛精度较高，方差的减小则表明CCABC算法的稳定性较好。对于比较简单的Step单峰函数，3种算法均能达到理论最优值，但从迭代时间和图2 可看出，CCABC算法迭代次数更少，收敛速度更快。对于多峰的Ackley和Rastrigin函数，搜索过程比较复杂，而CCABC算法中的前进操作增加了计算量，进而增加了迭代时间，但从均值中可以看出，其收敛精度得到了明显提高。此外，从图1～图5中也可以直观地发现，CCABC 算法的进化曲线最陡，迭代次数明显少于其它两种算法，平均适应度也显著优于其它两种算法。

表2 函数测试结果

图1 Sphere函数进化曲线

图2 Step函数进化曲线

4 结束语

图3 Rastrigin函数进化曲线

图4 Ackley函数进化曲线

图5 Rosenbrock函数进化曲线

通过在ABC算法中引入细菌觅食算法中的趋化操作和混沌变量，提出了一种基于混沌趋化行为的CCABC 算法。改进的算法将蜂群随机搜索的过程分解为翻转和前进两步，并在翻转过程引入混沌变量和动态参数，使蜂群在优质蜜源区能进行更细致的搜索。利用5个典型测试函数进行了仿真实验，结果表明CCABC算法提高了局部搜索能力，具有更好的收敛精度和收敛速度。

［1］Akay B， Karaboga D. A modified artificial bee colony algorithm for real－parameter optimization ［J］.Information Sciences，2012，192：120－142.

［2］Zhu Guopu，Kwong Sam.Gbest－guided artificial bee colony algorithm for numerical function optimization ［J］.Applied Mathematics and Compution，2010，217 （7）：3166－3173.

［3］GE Yu，LIANG Jing，WANG Xueping.Improved artificial bee colony algorithms based on ectremal optimization strategy［J］.Computer Science，2013，40 （6）：247－251 （in Chinese）.［葛宇，梁静，王学平.基于极值优化策略的改进的人工蜂群算法 ［J］.计算机科学，2013，40 （6）：247－251.］

［4］Banharsakun A，Achalakul T，Sirrinaovakul B.The best－sofar selection in artificial bee colony algorithm ［J］.Applied Soft Computing，2011，11 （2）：2888－2901.

［5］WANG Hui.Improved artificial bee colony algorithm ［J］.Computer Engineering and Design，2011，32 （11）：3869－3872（in Chinese）.［王辉.改进的蜂群算法 ［J］.计算机工程与设计，2011，32 （11）：3869－3872.］

［6］LI Shuang，LI Wenjing，YANG Wen，et al.Research and implementation of parallel random perturbation artificial bee colony algorithm based on multi－core PC ［J］.Microelectronics and Computer，2012，29 （9）：63－66 （in Chinese）. ［李双，李文敬，杨文，等.基于多核PC的人工蜂群并行算法的研究与实现 ［J］.微电子学与计算机，2012，29 （9）：63－66.］

［7］WANG Xin，TAN Huazhong，JIANG Hua.Vedio watermark scheme based on improved artificial bee colony algorithm ［J］.Computer Engineering and Design，2014，35 （6）：2095－2099（in Chinese）.［王鑫，谭华忠，蒋华.基于改进人工蜂群算法的视频水印［J］.计算机工程与设计，2014，35 （6）：2095－2099.］

［8］Passino KM.Bacterial foraging optimization ［J］.International Journal of Swarm Intelligence Research，2010，1 （1）：1－16.

［9］WU Bo，HE Chunmei.Task scheduling of multi－core processor system based on improved bacteria foraging optimization algorithm ［J］.Microelectonics and Computer，2013，30 （3）：143－147 （in Chinese）.［吴波，赫春梅.细菌觅食优化算法在嵌入式系统多任务调度中的应用 ［J］.微电子学与计算机，2013，30 （3）：143－147.］

［10］FENG Bin，WANG Zhang，SUN Jun.Niche quantum－behaved particle swarm optimization with chaotic mutation operator［J］.Computer Applications and Software，2009，26（1）：50－52 （in Chinese）.［冯斌，王璋，孙俊.基于混沌变异算子的小生境量子粒子群算法 ［J］.计算机应用与软件，2009，26 （1）：50－52.］

［11］LIU Daohua，YUAN Sicong，LAN Yang，et al.Method of particle swarm optimization based on the chaos map ［J］.Journal of XiDian University，2010，37 （4）：764－769 （in Chinese）.［刘道华，原思聪，兰洋，等.混沌映射的粒子群优化方法［J］.西安电子科技大学学报，2010，37 （4）：764－769.］

［12］ZHANG Xueyin，TIAN Xuemin，CAO Yuping.Artificial bee colony algorithm with modified search strategy ［J］.Journal of Computer Applications，2012，32 （12）：3326－3330 （in Chinese）.［张雪银，田学民，曹玉苹.改进搜索策略的人工蜂群算法［J］.计算机应用，2012，32 （12）：3326－3330.］