一种基于“拥挤度”概念的人工蜂群算法改进*

王文国，吴宗月

（曲阜师范大学 信息科学与工程学院，山东 日照 276826）

一种基于“拥挤度”概念的人工蜂群算法改进*

王文国，吴宗月

（曲阜师范大学 信息科学与工程学院，山东 日照 276826）

为了弥补原始人工蜂群算法中执行效率低和收敛速度慢的缺点，提出了一种引入“拥挤度”概念的人工蜂群算法。当采蜜蜂进行邻域搜索时，通过拥挤度对采蜜蜂进行数量调控，避免过多的采蜜蜂在同一蜜源附近搜索；当拥挤度高时，增加侦查蜂的数量，从而有效提高算法的全局搜索能力，特别是加快算法后期的收敛。通过4个标准测试函数对改进后的算法进行可行性验证，结果表明改进的人工蜂群算法在执行效率和后期收敛速度上都优于原始的人工蜂群算法，可用于网络中组播QoS路由选择的优化过程。

人工蜂群算法；拥挤度；收敛速度；组播路由选择

0 引 言

现代多媒体通信对网络的带宽、延时、延时抖动、丢包率等参数提出了严格要求。而网络服务质量路由（QoSR）算法的目的是在网络中搜索最佳路由，该路由须满足带宽、延时、丢包率等条件。由于包含两个或两个以上不相关可加或可乘性参数的路由选择是一个NPC问题[1]，传统路由算法无法在有效时间内找到最优解，因而启发式搜索算法已成为解决多约束QoS路由问题的有效途径[2-4]。

基于群体智能优化的人工蜂群算法模拟了自然界不同类型蜜蜂的劳动分工，通过对食物源信息的某种共享，达到对食物源的最佳搜索与采集效果。最早提出的人工蜂群算法用于解决函数优化问题[1]。近年来，该算法凭借其工作原理简单、控制参数相对较少、算法过程易于实现的特点，而受到越来越多的关注。随着有关研究的不断深入，人工蜂群算法已经被成功应用于解决计算机网络的QoS单播或多播路由选择问题[4]。

许多研究者尝试对人工蜂群算法进行各种改进。Mezura等[5]使用一个新算子改善逼近可行域的方式，该算子允许生成偏离当前最优解的搜索方向，并将两种动态容错方法应用于约束处理机制，以便生成新的可行域；Lei等[6]对蜂群算法的邻域方程进行改进，使搜索具有了非线性下降特性，从而实现对搜索空间的压缩，同时在搜索方程中加入一个随机扰乱项，以提升优化结果的准确性和有效性；Tarun等[7]在搜索演化过程中使用种群规模下降机制来加强对算法的控制，同时使用等级选择策略来维持种群的多样性，以提高算法的性能；Saxena等[8]为了平衡算法中采集现有蜜源和搜索更好蜜源的能力，使用当前蜂的最优值与全局最优解比较以产生新解，从而给出一种新的搜索策略。

但是，上述各种人工蜂群算法中仍然存在执行效率低和收敛速度慢的缺点。为了克服此类缺陷，本文将针对采蜜蜂引入“拥挤度”的概念，即试图通过调控蜜蜂的空间分布密度，进一步优化人工蜂群算法的搜索性能。

1 人工蜂群算法

在人工蜂群算法中，把蜜蜂分为三类：观察蜂、侦查蜂和采蜜蜂。采蜜峰存储着蜜源的相关信息，且将这些信息以一定的概率在舞蹈区与观察蜂分享；观察蜂驻留在蜂巢的舞蹈区，通过采蜜蜂与之分享的蜜源信息选择蜜源；侦查蜂则进行随机搜索以发现新的蜜源。一般而言，各类蜜蜂的采蜜过程可用图1表示，其中S为侦查蜂，EF为采蜜峰，UF为观察蜂。

图1 蜜蜂采蜜过程示意

人工蜂群算法的主要流程如下：

（1）初始化；

（2）重复以下四个步骤：

①根据存储的食物源信息，采蜜峰确定最优食物源的位置；

②根据采蜜峰分享的食物源信息，观察蜂以一定的概率选择食物源；

③侦查蜂在搜索区域不断搜索，以发现新的食物源；

④存储目前最优的食物源信息。

（3）直到满足某种停止条件。

在上述算法中，假定蜜蜂的数量N等于食物源的数量。

初始化阶段，人工蜂群算法按照式（1）随机生成N个解决方案：

式中，i的取值范围是（1,2,…,N），j的取值范围是（1,2,…,D），N的大小与食物源相等，D是向量的维度，Xjmin和Xj

max分别是解空间的下限和上限。

采蜜蜂阶段，计算每种解决方案的适应性，然后每个蜜蜂在当前位置附近按照式（2）产生新的解决方案：

式中，k的取值范围是（1,2,…,N），且k≠i，j是随机产生的，而rand()是介于-1与1之间的随机数。新位置的产生与之前的位置有关，且是在附近随机选择的。新位置New_的适应度将按照式（3）计算，然后通过贪婪选择机制与之前的位置进行比较，以便选取适应度更好的位置。

在观察蜂阶段，主要是根据采蜜蜂提供的食物源相关信息，以一定的概率选择食物源。适应度的计算公式是：

食物源被选择的概率如下：

式中，fiti是第i个位置的适应度。对于观察蜂来说，它们使用轮盘赌选择法挑选食物源，以确保适应度较好的蜜源被选择的概率更大。观察蜂确定食物源后，开始并行执行任务。在某个食物源附近搜索时，如果食物源的适应度一直得不到改善，那么达到预先设定的循环次数limit的食物源就会被放弃。放弃蜜源后的采蜜峰变成侦查蜂，开始在整个搜索空间中随机搜索新的解决方案，搜索到蜜源之后侦查蜂又转变成采蜜峰。

最后，系统存储到目前为止适应度最佳的蜜源，然后重复搜索过程直至终止条件满足。比如，到达预先设定的最大周期数或者搜索结果小于预先设定的误差等。

2 改进的人工蜂群算法

在上述基本人工蜂群算法的搜索机制中，不难看出适应度高的食物源附近会有大量的采蜜峰进行邻域搜索，而局部汇聚大量蜜蜂将导致其他区域的搜索能力下降，其结果会降低该算法的收敛速度和搜索效率。

图2展示了一般情况下蜂群可能遇到的蜜源分布情形。

图2 一种假设的蜜源分布情况

如图2所示，假设x1是采蜜蜂的当前位置，而系统在搜索过程中，一个新的蜜源将会在x1的邻域空间出现。例如，图中的x2是一个局部的最优值，但是算法在执行过程中会在x1附近不断发现比x1优秀的解，从而吸引大量的采蜜峰在临近区域搜索，因此算法往往会在局部最优位置的邻域空间来回摆动，容易陷入局部收敛。采蜜峰的大量聚集必然会影响到x3、x4等优秀蜜源的发现效率，导致算法运行后期的收敛速度相对较慢。为了避免这种不利情况出现，引入“拥挤度”这一概念，以限制采蜜峰的数量：当拥挤度低时，蜂群不需要进行任何的调整，当拥挤度高时，适当减少采蜜蜂的数量，同时增加侦查蜂的数量来扩大对解空间的全局搜索。这样就能在一定程度上帮助算法避免早熟现象，同时在后期提高算法的收敛速度。

定义crowd为拥挤度参数，表示解空间中采蜜蜂与其邻域空间中其他个体之间的接近程度。crowd的值越大，表示该区域内的采蜜蜂越少。

观察蜂选择食物源的概率相应修改为：

此外，原始人工蜂群算法初始化时，蜜蜂的群体会被分为采蜜峰和观察蜂，观察蜂在蜂巢中被动等待采蜜峰带回的蜜源信息。本文的另一个改进思路是假设蜂群中侦查蜂一直存在，一般使其比例保持在蜂群总数的5%～10%左右，这样会迫使部分观察蜂转变为侦查蜂，以便继续保持对解空间的不断搜索，进而有利于提高算法后期的收敛速度。

3 仿真测试和分析

人工蜂群算法作为一种仿生学的智能算法，在搜索过程中会表现出很强的随机性。按照上节引入拥挤度的改进蚁群算法，具体实现方案包含三个步骤：第一步，在采蜜峰阶段所获得的解将按照适应值的优劣进行降序排列；第二步，观察蜂对排序后的解以一定的概率进行选择；第三步，跟踪优势解的分布情况，及时调整蜂群的多样性及搜索方向，当拥挤度高时，对采蜜峰的数量进行限制。

为了测试上述改进蚁群算法的性能，在Intel(R) Pentium E6500、CPU主频2.93 GHz、2 GB内存、Windows 7操作系统下，运用MATLAB 7.8进行仿真试验。所采用的4个测试函数及其值域范围罗列在表1中。

实验中，主要关注两种人工蜂群算法的优化曲线和算法执行时间，从而比较其收敛速度和执行效率。实际测试中的参数设置如下：测试函数维度D=5，解空间中蜜源的数量NP=100、limit=50、maxCycle=500。由于算法在执行过程中存在随机性，本次实验选取的数据取算法随机执行50次后所得的平均值。

图3、图4、图5和图6分别为Sphere、Griewank、Rastrigin和Rosebrock函数的优化曲线对比。从中可以看出，改进后的蜂群算法之收敛速度明显优于原始的人工蜂群算法。

表2则是改进后的蜂群算法与原始算法在执行时间上的对比。从表2中可以看出，在相同的寻优精度和相同的参数设置情况下，改进后的算法在运行时间上减少了35%以上，明显地提高了算法的寻优效率。

表1 仿真所用的四个测试函数

图3 Sphere优化曲线

图4 Griewank优化曲线

图5 Rastrigin优化曲线

图6 Rosenbrock优化曲线

表2 改进的蜂群算法与原始算法的运行时间对比

4 结 语

本文从人工蜂群算法的搜索机制出发，通过引入拥挤度参数对采蜜蜂数量进行调控，以避免过多的采蜜蜂在同一蜜源附近搜索，同时保持侦查峰占蜂群总数的比例为5%～10%左右。仿真测试结果表明，改进后的蜂群算法能够有效提高算法的收敛速度和执行效率。下一步工作是把本文改进的蜂群算法用于解决网络中组播QoS路由选择的优化问题。

[1] Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization[R].TR06.Kayseri Erciyes University,2005.

[2] Wang Z,Crowcroft J.Quality-of-Service for Routing Supporting Multimedia Applications[J]. IEEE Journal of Selected Areas in Communicatio ns,1996,14(07):1228-1234.

[3] 刘洋,王文国.差异化密集蚁群算法与网络QoS路由选择[J].通信技术,2015,48(08):949-953. LIU Yang,WANG Wen-guo.Differentiated Dense Ant Colony Algorithm and Network QoS Routing Selection[J]. Communications Technology,2015,48(08):949-953.

[4] 杨原.基于群智能优化算法的QoS组播路由算法研究[D].西安:西安科技大学,2014. YANG Yuan.Research on QoS Multicast Routing Algorithm based on Swarm Intelligence Optimization Algorithm[D].Xi'an:Xi'an University of Science and Technology,2014.

[5] Mezura M E,Damian A M,Cetina D O.Smart Flight and Dynamic Tolerances in the Artificial Bee Colony for Constrained Optimization[C]. Barcelona: Proceedings of 2010 IEEE Congress on Evolutionary Computation,2010:1-8.

[6] Lei X J,Huang X,Zhang A D.Improved Artificial Bee Colony Algorithm and Its Application in Data Clustering[C]. Changsha:Proceedings of IEEE 5th International Conference on Bio-Inspired Computing,2010:514-521.

[7] Tarun K S,Millie P.Some Modifications to Enhance the Performance of Artificial Bee Colony[C]. Brisbane:Proceedings of IEEE Congress on Evolutionary Computation,2012:1-8.

[8] Saxena S,Sharma K,Shiwani S,et al.Best Artificial Bee Colony Using Structured Swarm[C]. Gurgaon: Proceedings of IEEE International Advanced Computing Conference,2014:1354-1360.

王文国（1960—），男，博士，教授，主要研究方向为网络与信息安全；

吴宗月（1990—），男，硕士研究生，主要研究方向为计算机网络。

Improved Artificial Bee Colony Algorithm based on Congestion concept

WANG Wen-guo, WU Zong-yue
(Dept. of Info. Science & Engineering, Qufu Normal University, Rizhao Shandong 276826, China)

In order to overcome shortcomings of low efficiency and slow convergence in original ABC(artificial bee colony) algorithm, a new concept of "congestion degree" is introduced into the basic ABC procedure. The proposed congestion concept is used mainly in employed bee, and when many employed bees search in adjacent domains, these bees would affect each other; by limiting the number of employed bees working in the same area and increasing the number of scouts, the global searching ability and speed of convergence of the algorithm would be enhanced. The feasibility and performance of the improved ABC algorithm is verified with four standard testing functions, and the results show that the improved ABC algorithm outperforms the basic algorithm in both execution efficiency and speed of convergence. This new algorithm could be used to optimize QoS multicast routing protocol.

artificial bee colony algorithm; congestion; speed of convergence; multicast routing protocol

National high level talents attracting program of China（No.200461）

TP311

A

1002-0802(2016)-07-0867-05

10.3969/j.issn.1002-0802.2016.07.014

2016-03-10;

2016-06-20 Received date:2016-03-10;Revised date:2016-06-20

国家人事部高层次留学人员回国工作资助项目（No.200461）)