0 引言
群体智能(swarm intelligence，SI)算法来源于自然界生物的觅食行为或进化过程的模拟，是一类新型的进化算法，主要特点是群体搜索策略和群体之间的信息交换.典型的群体智能算法包括蚁群优化算法(ant colony optimization，ACO)[1]、粒子群优化算法(particle swarm optimization，PSO)[2]和人工蜂群算法(artificial bee colony，ABC)[3]等.蚁群算法在求解性能上有很强的鲁棒性，但算法收敛速度慢，容易陷入局部最优，一般需要较长的搜索时间，而且该算法容易出现停滞现象，不利于发现更好的解.粒子群算法具有相当快的逼近最优解的速度，其个体可以充分利用自身经验调整自身状态，缺点是容易产生早熟收敛，局部寻优能力较差.
人工蜂群算法(artificial bee colony，ABC)是D.Karaboga[4]在2005年将蜜蜂的觅食行为应用到函数优化问题中而提出的，该算法计算简单、便于实现、鲁棒性强，在复杂组合优化问题中有明显的优势[5]，目前已经成功应用到模糊聚类[6]、人工神经网络[7]、传感器网络[8]等多个领域中.与其他群体智能算法一样，ABC算法也存在收敛速度慢、易陷入局部最优解等问题[9].针对以上问题，已有学者提出了相应的改进算法，这些改进算法在一定程度上提高了算法的收敛速度、寻优精度，改善了算法的性能，但是很难实现在避免算法早熟收敛的同时加快算法的收敛速度.目前，大多数关于ABC算法的改进都是基于单一种群模型，没有考虑算法在基于多种群模型改进时相较于原始算法的优势.
聚类(clustering)[10]是把所有数据对象划分到若干个子集的过程，每个子集是一个簇(cluster)，主要指导思想是尽量使相同簇内对象具有最大相似度.在众多聚类方法中，K均值算法[11]是一种非常重要的聚类算法，主要思想是依据参数k将给定数据集划分成k个簇，从而让各聚类中心的数据对象到其对应的中心点的距离平方和最小，该算法原理简单、易于实现.
笔者在原始人工蜂群算法的基础上，利用K均值算法的思想将蜂群划分为多个子蜂群，提出一种多种群人工蜂群算法(multi-swarm artificial bee colony，MABC).子种群将全局通信模式和局部通信模式相结合，基于局部通信的适应度函数扩展了解方案的多样性，基于全局通信的蜜源位置更新方式加速算法收敛，避免算法陷入局部最优.在Matlab编程环境下选取6个标准测试函数对算法进行测试，证明了该算法能显著提高ABC算法的收敛速度和寻优精度.
1 原始人工蜂群算法(ABC)
人工蜂群算法是模拟蜜蜂的采蜜行为提出的一种智能优化算法，由蜜源，被雇佣蜂(引领蜂)和未被雇佣蜂(跟随蜂、侦查蜂)3项基本元素构成.同时，引入3种基本的行为模式：搜索蜜源、招募蜜源和放弃蜜源.其中，蜜源的位置代表优化问题的可行解；蜜源的质量对应解的适应度.
最优蜜源的搜索过程如下:首先，算法随机产生含有N个侦查蜂的初始种群，初始时所有蜜蜂都为侦查蜂，同时也是蜜源的数量，每个解Xi是一个d维向量，Xi={xi1,xi2,…,xid}.计算解对应函数值，设定一个临界值，将大于临界值的解作为蜜源位置.一个引领蜂与一个蜜源是相对应的，与第i个蜜源相对应的引领蜂依据式(1)寻找新的蜜源.
Vij=Xij+Rij(Xkj-Xij),
(1)
式中：i=1,2,…,N，Vij代表更新后的蜜源;j代表蜜源更新的维度，j=1,2,… d；k代表学习的蜜源位置，k≠i，k，j都是随机选择的，并且k≠j；R为[-1,1]的随机数.跟随蜂采用轮盘赌策略选择蜜源，蜜源选择的概率公式如下:
(2)
式中：pi代表第i个蜜源被选择的概率；fitnessi代表第i个蜜源的质量，即第i个解的适应度值，计算公式如式(3)所示；N代表解的个数.
(3)
式中：fi是第i个解的目标函数值，每个蜜源被选择的概率与适应度成正比.
所有引领蜂和跟随蜂经过一次邻域搜索后，检查蜜源未更新的次数Limit，如果一个蜜源经过Limit次循环后没有得到改善，则该蜜源将会被放弃，它所对应的引领蜂转为侦查蜂，侦查蜂通过公式(4)搜索新的蜜源Vij[12].
(4)
式中：rij是区间[0,1]上的随机数；j代表蜜源更新的维度，
和
分别是第j维的上界和下界.
原始人工蜂群算法具有控制参数少、计算简单、便于实现等优点，已经被越来越多的研究者关注.但是该算法存在收敛速度慢、容易陷入局部最优解等缺点，需要在收敛速度和寻优精度等方面加以改进.
2 多种群人工蜂群算法(MABC)
2.1 种群分割
首先，从蜜源Xi={x1,x2,…,xi,…,xN}中随机选取
取整数)个蜜源作为初始聚类中心C，令
然后，利用基于K均值算法中基于欧氏距离的方式将剩余蜜源划分到每个聚类中心，即对于蜜源xi按照min{Dij(xi,Cj)}的规则将人工蜂群划分为
个子种群，Dij代表蜜源xi到聚类中心Cj的距离.根据ABC算法思想，种群分割后的蜂群蜜源个数和引领蜂个数均为
种群分割的具体步骤如下:
步骤1随机初始化
个聚类中心；
步骤2将蜜源按照基于欧氏距离的方法依次划分到每个聚类中心；
步骤3重新计算每类中所有节点的算数平均值，得到更新后的个簇的中心点；
步骤4分别计算当前所有蜜源到相应的聚类中心的均方差之和；
步骤5如果当前迭代次数的均方差之和与前次相同，结束蜜源聚类，转到步骤6，否则转到步骤2；
步骤6输出蜜源聚类结果，即种群分割结果.
假设在边长为300 cm×200 cm的空间中蜜源数量为100，按照本文的种群分割方法将其划分为10个子种群，其中相同颜色的个体为同一个子种群，划分结果如图1所示.
图1 种群分割结果
Fig.1 The result of population segmentation
2.2 蜜源位置更新方式
ABC算法利用原始的位置更新公式(1)时，引领蜂缺乏与整个蜂群的信息交流和共享，算法易陷入局部最优.种群分割之后，提出基于全局通信的新蜜源位置更新公式(5):
Vij=Xij+Rij(Xkj-Xij)+θij(XCbest,j-Xij),
(5)
式中：Vij代表更新后的蜜源；θij∈[0,1]是一个随机数；XCbest,j代表蜜源丰富度最高的子种群的聚类中心.
公式(1)只能权衡自己所在位置和历史最优位置的食物源的丰富度.公式(5)基于全局通信方式加入引导因子XCbest,j-Xi,j，使引领蜂能够参考所有子种群中当前最优的位置，有很好的方向性.
2.3 适应度函数
种群分割之后以子种群
为单位进行引领蜂的选取和角色转换，同一种群内样本对象相似度最高.引领蜂被跟随蜂选择的概率公式(2)更改为公式(6)：
(6)
式中：pc,i代表第c组中第i个引领蜂被选择的概率，因为将人工蜂群划分为个子种群，所以
代表第c组中第i个蜜源的质量，即第c组中第i个解的适应度值;cn代表第c组中蜜源的数量.
基于局部通信的适应度函数由式(7)代替ABC算法中式(3)：
(7)
改进的目标函数值Fi计算公式如式(8)所示:
Fi=∑Xi∈CjD(Xi,Cj)/NumCj,
(8)
式中：∑Xi∈CjD(Xi,Cj)代表种群Cj中所有蜜源到聚类中心的距离之和；NumCj代表种群Cj中蜜源的数量.
公式(7)中的适应度函数同时考虑了子种群中的蜜源数量和距离，提高了算法的鲁棒性.
2.4 MABC算法步骤
步骤1根据ABC算法初始化蜂群，包括种群规模N，最大迭代次数MaxCycle，适应度阈值Limit，维度Dim等.
步骤2利用K均值聚类算法中基于欧氏距离的方法对人工蜂群进行种群分割，得到C个子种群，其中
每个子种群中分别独立运行.
步骤3根据公式(7)分别计算Cj个子种群中蜜蜂的适应度值，适应度值高的一半作为引领蜂，剩余的作为跟随蜂.
步骤4Cj中的引领蜂根据公式(5)搜索蜜源，根据公式(7)计算蜜源适应度值，若适应度值提高，则更新蜜源，否则保留原蜜源不变.
步骤5引领蜂提供蜜源丰富度信息，跟随蜂根据公式(6)选择引领蜂，并采用公式(5)进行邻域蜜源搜索.
步骤6更新Cj状态，迭代次数加1，若迭代次数达到Limit后仍有未更新的蜜源，由侦查蜂根据公式(4)产生一个新蜜源.
步骤7迭代次数达到最大迭代次数MaxCycle时，算法结束；否则，返回步骤3.
3 实验仿真及分析
实验中采用操作系统是Windows 10，处理器是Intel(R)Core(TM)i5-6300HQ CPU @2.30 GHz，内存4 GB的计算机，编译软件为Matlab-R2016a.
笔者使用6个典型的测试函数[5]对MABC算法、ABC算法[14]及文献[15]中改进ABC(CSABC)算法的鲁棒性、收敛速度和寻优精度进行对比试验.
3.1 测试函数
为了测试本文MABC算法在函数优化问题中的性能，选择6个常用的函数作为测试函数，见表1.其中，f1～f3是单峰函数，主要用来测试算法的收敛速度和寻优精度；f4～f6是多峰函数，主要用来测试算法的全局寻优能力和避免早熟的能力.
表1 测试函数
Tab.1 Testing functions
函数名称搜索空间最小值f1Sphere[-100,100]0f2Rosenbrock[-30,30]0f3Schwefel[-100,100]0f4Rastrigin[-5.12,5.12]0f5Ackley[-32,32]0f6Griewank[-600,600]0
测试函数f1～f6表达式如下：
f2(x)=
f5(x)=
3.2 测试结果对比分析
MABC、ABC和CSABC 3种算法对比试验参数设置如下：种群规模N=100，其中引领蜂和跟随蜂的数目均为50，最大迭代次数Max-
Cycle=1 000，适应度阈值Limit=50，维度Dim=50.
3种算法对每个测试函数分别独立进行50次实验，得到对应的最优值、最差值、平均值和方差，测试结果见表2.其中，最优值和最差值反映算法的质量，平均值反映算法的收敛速度和寻优精度，方差反映算法的稳定性和数据的离散程度.
表2 函数测试结果对比
Tab.2 Comparison of functions test results
函数算法最优值最差值均值方差ABC9.233 71.150 7E+021.186 0E+012.978 1E+02SphereCSABC7.697 1E-027.771 33.124 7E-011.513 3E-01MABC1.985 6E-064.874 42E-043.744 5E-056.452 3E-05ABC7.092 0E+042.147 7E+051.207 3E+044.695 3E+02RosenbrockCSABC4.141 4E+035.702 8E+056.724 2E+041.456 3E+02MABC1.691 43.700 7E+027.566 31.142 5E-01ABC-7.092 0E+03-2.147 7-1.207 3E+014.695 3E+03SchwefelCSABC-4.141 4E+3.5-5.702 8E+02-6.724 2E+031.456 3E+02MABC-1.691 4E+05-3.700 7E+03-7.566 3E+041.142 5ABC1.085 7E+039.433 8E+064.736 9E+058.204 6E+06RastriginCSABC7.401 4E+023.330 6E+051.184 2E+041.407 2E+04MABC1.333 82.378 1E+028.166 77.243 8E+01ABC9.233 7E+011.150 01.186 0E+012.978 19AckleyCSABC7.697 1E-017.771 3E+013.124 71.513 3MABC1.985 6E-044.874 4E-023.744 5E-043.744 5E-03ABC1.480 31.691 4E+014.033 96.523 7E+01GriewankCSABC3.700 7E-011.920 64.159 67.043 8MABC5.341 1E-053.588 7E-037.332 8E-052.824 3E-03
图2 测试函数结果
Fig.2 The results of test functions
通过表2可以看出，笔者提出的MABC算法在单峰函数和多峰函数测试中均有较高的寻优精度.算法的最优值、最差值与ABC算法和CSABC算法相比有明显的提升，说明MABC算法稳定性更高；在相同的迭代次数下，MABC算法在各测试函数上均得到了最小均值和最小方差，表明其收敛速度更快，寻优精度更高，性能明显优于ABC算法和CSABC算法.
图2中给出了MABC算法、ABC算法和CSABC算法独立运行50次的平均适应度值进化曲线.由图2(a)、(b)可以看出，MABC算法达到稳定收敛的次数远小于ABC算法和CSABC算法；由图2(c)可以看出，ABC算法和CSABC算法在搜索过程中陷入局部极值，种群分割策略使MABC算法分组寻优，收敛值明显小于其他两种算法；由图2(d)可以看出，ABC算法和CSABC算法收敛较快，迭代次数较少，但过早停滞，寻优精度不如MABC算法；由图2(e)、(f)可以看出，MABC算法在搜索后期表现出较强的优势，而ABC算法和CSABC算法则容易陷入局部最优.
由以上分析可以看出，MABC算法达到稳定收敛时的寻优精度远高于ABC算法和CSABC算法，尤其对单峰函数而言收敛速度更加明显.
4 结束语
笔者针对原始人工蜂群算法存在的收敛速度慢、易陷入局部最优解等不足，提出了一种基于种群分割的多种群人工蜂群算法(MABC)，该算法利用K均值聚类算法中基于欧氏距离的方式对人工蜂群进行种群分割，将大的种群划分为多个子种群，每个子种群分别独立运行，在子种群中引入基于全局通信的蜜源位置更新方式加速算法收敛，同时引入基于局部通信的适应度函数扩展解方案的多样性.通过6组标准测试函数的仿真实验结果可知，笔者提出的MABC算法比ABC算法及CSABC算法收敛速度快、寻优精度高、鲁棒性高、适应度好.
在未来的工作中，我们计划进一步提高算法的性能，并通过更加多样性的测试问题进行验证，比如最优点不在原点或者各维度最优点不一样的测试函数进行测试，以证明没有偏差.另外笔者计划下一步将本文的MABC算法有效地应用到实际工程问题中，并采用数学方法使其表现出更多的价值.
[1] SAM
M, PELLEGRINI P, D′ARIANO A, et al. Ant colony optimization for the real-time train routing selection problem[J]. Transportation research, part B, 2016, 85:89-108.
[2] 梁静,宋慧,瞿博阳,等.基于改进粒子群算法的路径优化问题研究[J].郑州大学学报(工学版),2014,35(1):34-38.
[3] 胡珂，李迅波，王振林.改进的人工蜂群算法性能[J].计算机应用，2011，31(4):1107-1110.
[4] KARABOGA D，OZTURK C. A novel clustering approach: artificial bee colony (ABC) algorithm[J]. Applied soft computing journal, 2011, 11(1): 652-657.
[5] NSEEF SK, ABDOLLAH S, TURKY A, et al. An adaptive multi-population artificial bee colony algorithm for dynamic optimisation problems[J]. Knowledge-based systems, 2016, 104:14-23.
[6] KARABOGA D，OZTURK C. Fuzzy clustering with artificial bee colony algorithm[J]. Scientific research & essays, 2010, 5(14):1899-1902.
[7] 王允霞. 蜂群算法的研究及其在人工神经网络中的应用[D]. 广州：华南理工大学理学院， 2013.
[8] OZTURK C，KARABOGA D， GORKEMII B. Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm[J]. Sensors, 2011， 11(6):6056-6065.
[9] 徐斌，刘弘.融合社会力与人工蜂群的人群疏散仿真方法[J].小型微型计算机系统，2016， 37(8):1725-1729.
[10] 胡燕,朱晓瑛,马刚.基于K-Means和时间匹配的位置预测模型[J].郑州大学学报(工学版),2017,38(2):17-20.
[11] KHANMOHAMMADI S, ADIBEING N, SHANEHBANOY S.An improved overlapping k-means clustering method for medical applications[J]. Expert systems with applications, 2016, 67:12-18.
[12] DERVIS D. Artificial bee colony algorithm[J]. Scholarpedia， 2010， 5(3):6915.
[13] 刘雷，王洪国，邵增珍，等.一种基于蜂群原理的划分聚类算法[J]. 计算机应用研究，2011， 28(5):1699-1702.
[14] 秦全德,程适,李丽,等.人工蜂群算法研究综述[J].智能系统学报,2014,9(2):127-135.
[15] 毛力，周长喜，吴滨，等.一种高效的求解函数优化问题的人工蜂群算法[J].小型微型计算机系统， 2016， 37(1):152-156.