基于参数优化的改进人工蜂群算法及其应用

王金金　丁茹茹　郑耿辉

摘要：针对基本人工蜂群算法（ABC）收敛速度较慢、容易陷入局部极值等不足，本文通过引入一个自适应控制参数，将基本ABC算法和一种改进的人工蜂群算法（EABC）进行混合，从而得出一种性能更加优良的改进人工蜂群算法——EFABC。将本文所提算法与混合前的两种算法应用于三维点云配准实验中，通過对点云库中的多个模型进行配准，结果表明本文所提算法不仅能提高收敛速度和精度，也可在一定程度上提高算法跳脱局部极值的性能。

关键词：群智能优化；人工蜂群算法；自适应控制参数；三维点云配准

1 引言

人工蜂群算法（Artificial bee colony algorithm， ABC）[1]是由Karaboga、Basturk等，于2005年提出的一种群体智能优化算法，该算法通过模拟蜜蜂采蜜的行为对问题进行优化求解，具有参数较少、优化精度高等优点。其与粒子群算法（Particle swarm optimization， PSO）[2]、差分进化算法（Differential evolution， DE）[3]等相比具有更好的优化求解性能[4]。人工蜂群算法能够在不需要知道问题的特殊信息情况下，对问题进行优劣的比较，通过蜜蜂个体的寻优行为，在整个群体中体现出全局的最优值，故该算法一经提出就受到了极大的关注。近年来吸引了国内外众多学者对其进行了研究、改进[5-8]以及应用，主要在于函数优化问题[9]、车辆路径问题[10]、经济负荷分配[11]、无线传感器网络动态部署[12]及人工神经网络[13]等领域。

但不可避免的是，人工蜂群算法在其具有较多优点的同时，也存在着一定的缺陷。它所具有的优良全局搜索能力，也导致了算法在寻优过程中开发能力较差，耗时较长等。为此，许多学者提出了一些相关的改进措施[14-18]，也取得了较好的效果。但由于多数学者过多的注重开发能力，致使改进后的人工蜂群算法容易陷入局部极值。为此，本文提出了一种新的改进措施，用一个自适应参数将基本人工蜂群算法和一种改进后的人工蜂群算法所分别具有的优异全局搜索能力和开发能力相结合，从而减少算法陷入局部极值的概率并降低求解时间。通过将本文

算法与ABC算法和EABC算法进行三维点云配准实验，结果表明本文提出的新改进人工蜂群算法效果更佳。

2三维点云配准

给定两片点云，一片为待配准点云 ，另外一片为目标点云 ，三维点云配准的目的是要获取这两片点云间的欧式变换矩阵 ，以此来解决多个传感器扫描得到的不同视角点云的配准问题。该变换矩阵包含6个待定参数，分别为沿三个坐标轴的平移量 以及绕三个坐标轴的旋转角 。在不考虑模型尺度伸缩的情况下，变换矩阵 的表达式为： 其中，

解决配准问题便可利用人工蜂群算法对该目标函数进行优化求解，从而得出欧式变换矩阵 ，完成配准。

3 人工蜂群算法

人工蜂群算法主要是模拟蜂群的智能采蜜行为。在ABC算法的模型中，主要包含三个基本的组成要素：食物源、被雇佣的蜜蜂以及未被雇佣的蜜蜂[19]。利用ABC算法求解优化问题时，食物源的位置被抽象成解空间中的点，蜜蜂采蜜的过程就是搜寻最优解的过程。被雇佣的蜜蜂也称采蜜蜂，采蜜蜂即已经发现食物源的蜜蜂，与其所发现的食物源一一对应，并储存着某一食物源的相关信息，例如相对于蜂巢的方向、距离以及食物源中花蜜的数量等，随后将这些信息以一定的概率与其他蜜蜂分享。未被雇佣的蜜蜂包括跟随蜂和侦察蜂。采蜜蜂完成工作后，跟随蜂会根据采蜜蜂传达回来的信息，通过一定的概率选择适应度值较高的食物源，提高算法的收敛速度。侦察蜂则是负责随机搜索蜂巢附近的食物源，增强算法跳出局部极值的能力。在采蜜的过程中，若采蜜蜂经过一定次数地循环搜索食物源后，食物源的质量仍然没有改善时，该食物源会被采蜜蜂所抛弃，然后该采蜜蜂变为侦察蜂，开始寻找新的食物源。

人工蜂群算法中，蜂群采蜜的过程其实就是寻找优化问题中最优解的过程。食物源的位置则对应着优化问题中的可行解，每个食物源的花蜜量则代表相关解的质量（适应度fit），采蜜蜂的数量就等于食物源的数量。在初始化阶段，人工蜂群算法首先生成一个随机分布的初始种群（食物源位置），其中 表示食物源的数量。利用公式（3-1）随机生成食物源：

其中， 为食物源位置 的适应度值。适应度值越优的食物源被选择的概率越大。

当采蜜蜂在某个食物源的位置处搜索超过一定的次数后，该食物源没有得到改善时，采蜜蜂会变成侦察蜂，通过公式（3-1）产生新的食物源。

4 EABC算法

人工蜂群算法一经提出，就有大批学者进行研究和改进。提高人工蜂群算法性能的关键，就在于平衡和提高该算法的探索性能和开发性能。探索性能通常表现为优化过程中算法跳脱局部极值的能力，而开发性能则体现为算法的收敛精度和速度。在原始的人工蜂群算法中，采蜜蜂和跟随蜂的位置更新搜索方程完全一致，较不利于算法性能的平衡和提高。高卫峰等[20]于2014年，研究并提出了一种改进的人工蜂群算法（Enhancing artificial bee colony algorithm， EABC），该算法在采蜜蜂和跟随蜂阶段引入了不同的搜索方程，该改进后的算法性能优良。其在采蜜蜂阶段引入的搜索方程如公式（4-1）：

5 使用自适应参数控制的改进人工蜂群算法——EFABC

人工蜂群算法的优化效果较好，但由于初始的人工蜂群算法的搜索方程更加偏向于探索，故其在处理复杂的优化问题时往往收敛速度较慢，耗时较长。而大部分改进的人工蜂群算法则直接将算法偏向于开发性能，提高算法的收敛速度，但在节约了较多时间的同时也使得算法较为容易陷入局部极值。改进的EABC算法较于基本ABC算法性能优异，提高了开发能力，收敛速度较快，但是该算法同样容易陷入局部极值。因此，为了更好地提高算法的求解性能，本文提出了另一种改进的人工蜂群算法：EFABC（Enhancing faster artificial bee colony algorithm）。该算法在基本ABC算法和EABC算法的基础上，引入了一个能够随着迭代次数改变的自适应参数 ，使算法既具有良好的探索性能又同时具备较好的开发能力。在解决最优化问题时，首先进行全局搜索，在找到较多的疑似最优解的位置后再对其进行开发，通过这样的搜索过程会取得更佳的结果。引入本文所提自适应参数 后改进的搜索方程，如公式（5-1）、（5-2）所示。

6实验结果以及分析

为了验证提出的改进算法的性能，本文选取了被广泛认可的点云配准实验模型，包括SAMPL点云库的Bird、Tele、Frog模型和斯坦福实验室的Bunny模型进行配准实验。为了体现本文提出改进算法的优良性能，本文将EFABC算法与ABC算法、EABC算法进行了对比实验。仿真环境为Windows 7操作系统，Intel i5处理器，2.20GHz，4G内存。仿真软件为MATLAB R2014a。为保证实验结果数据的可靠性，我们对每个模型均进行了20次独立配准实验取平均值。在配准完成后，根据由式（2-5）得出的目标函数值评价各算法的优劣。在实验中Bird、Tele、Frog点云模型采用的是0度视角和40度视角的两片点云，同时为了凸显算法对于不同模型的适用性，对Bunny点云模型采用的是0度视角和45度视角的两片点云。在所有的配准实验中，均以0度视角的点云为静态点云，另一片点云作为动态点云进行配准。

实验配准完成的标准是以最后得出的两片点云间对应点欧式距离的中值（误差中值）进行核定的。在经过大量论文查询和实验的观察比较后，确定了适用于本文实验中的四种模型的误差中值的标准精度。具体精度数值如表1所示：

在实验中分别采用ABC算法、EABC算法以及本文所提出的EFABC算法对Bird、Tele、Frog以及Bunny等四种点云模型进行配准。配准完成后，各算法取得的误差中值最小值、平均值以及标准差如表2所示：

由表2中可明显看出，本文改进后的算法EFABC在对四个不同点云模型的配准实验中，均取得了最小的配准误差平均值和标准差，明显优于ABC算法和EABC算法。特别的，对于配准误差最小值，仅在对Bird模型进行配准得出的实验结果中，较EABC算法大，但差异极小。特别要说明的是对于Bunny点云模型，由于其点云密度比另外三个点云模型大得多，因此其数据精度对比其他模型要高。

此外，本文在设定运行次数和进化代数后，对不同算法用于各模型配准完成后的成功率及所用时间进行了记录整理及对比分析。实验结果如表3所示：

由表3可以看出，本文新提出的改进EFABC算法与EABC算法较原始的ABC算法相比，在时间和成功率上都有较大的提升。但在Bunny点云模型的实验中，对EABC和ABC算法数据进行对比分析后，虽然EABC的运行时间比ABC算法短，但是成功率却低于ABC算法，这是因为EABC算法比ABC算法雖提高了开发能力，但相应的探索能力较弱，更加容易陷入局部极值，节约运行时间的同时降低了配准的精度与成功率。而本文改进的EFABC算法在减少了时间成本的情况下依然保证了较高的配准精度。在Bird、Frog、Tele这三个点云模型中，EFABC算法在节省时间成本和提高精度方面明显优于ABC算法和EABC算法。

综上所述，本文引入自适应控制参数优化搜索方程后的改进人工蜂群EFABC算法，在三维点云配准的误差精度和成功率方面都有了明显的突破与提高，同时降低了运行时间。

7结束语

本文针对人工蜂群算法收敛速度较慢、容易陷入局部极值的缺陷，结合一种改进的人工蜂群算法，引入一个自适应控制参数优化其搜索方程，从而得到了一种新的改进人工蜂群算法——EFABC。本文所提改进算法兼顾了全局搜索和开发能力，提高了算法的性能。通过将本文EFABC算法与ABC算法、EABC算法应用于三维点云配准实验，可以发现，本文EFABC算法不仅提高了配准的精度，而且大大缩短了配准完成所用的时间。由此可见，EFABC算法是一种性能优良的改进算法。

参考文献：

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

[2]He L H， Yao N， Wu J H， et al. Application of modified PSO in the optimization of reactive power[C]. Proc. Of the Chinese Control and Decision Conference， 2009：3493-3496.

[3] Storn R P K. Differential evolution a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization， 1997， 11（4）：341-359.

[4]Karaboga D， Basturk B. On the performance of artificial bee colony （ABC） algorithm [J]. Applied Soft Computing， 2008， 8（1）：687-697.

[5]暴励， 曾建潮. 自适应搜索空间的混沌蜂群算法[J]. 计算机应用研究， 2010， 27（4）：1331-1335.

[6]罗钧， 樊鹏程. 基于遗传交叉因子的改进蜂群优化算法[J]. 计算机应用研究， 2009， 26（10）：3751-3753.

[7]Alatas B. Chaotic bee colony algorithms for global numerical optimization [J]. Expert Systems with Applications， 2010， 37（8）：5682-5687.

[8] 丁海军， 冯庆娴. 基于Boltzmann选择策略的人工蜂群算法[J]. 计算机工程与应用， 2009， 45（31）：53-55.

[9] Karaboga D， Basturk B. A comparative study of artificial bee colony algorithm [J]. Applied Mathematics and Computation， 2009， 214（1）108-132.

[10]于晓东， 廉莲. 人工蜂群算法在单时间窗车辆路径问题中的应用[J]. 科技创新与应用， 2016（19）：64-64.

[11]胡欣. 改进的人工蜂群算法及其在经济负荷分配中的应用[D]. 武汉理工大学， 2015.

[12]贺培玉. 人工蜂群算法及其在无线传感器网络动态部署中的应用[D]. 山东大学， 2014.

[13] 冷昕，张树群， 雷兆宜. 改进的人工蜂群算法在神经网络中的应用[J]. 计算机工程与应用， 2016， 52（11）：7-10.

[14]李彦苍， 彭扬. 基于信息熵的改进人工蜂群算法[J]. 控制與决策， 2015， 30（06）：1121-1125.

[15]毕晓君， 王艳娇. 改进人工蜂群算法[J]. 哈尔滨工程大学学报， 2012， 33（01）：117-123.

[16]王冰. 基于局部最优解的改进人工蜂群算法[J]. 计算机应用研究， 2014， 31（04）：1023-1026.

[17]王生生， 杨娟娟， 柴胜. 基于混沌鲶鱼效应的人工蜂群算法及应用[J]. 电子学报， 2014， 42（09）：1731-1737.

[18] 臧明相， 马轩， 段奕明. 一种改进的人工蜂群算法[J]. 西安电子科技大学学报， 2015， 42（2）：65-70.

[19]Nurhan K. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute， 2009， 346（4）：328-348.

[20]Gao W F， Liu S Y， Huang L L. Enhancing artificial bee colony algorithm using more information-based search equations[J]. Information Sciences， 2014， 270（1）： 112-133.

基金项目：2016年国家级大学生创新创业训练计划项目“基于群智能计算的纹理图像拼接技术研究”（201610069021）