一种应用于函数优化问题的多种群人工蜂群算法

王守娜， 刘 弘， 高开周

(1.山东师范大学 信息科学与工程学院，山东 济南 250014； 2.山东师范大学 山东省分布式计算机软件新技术重点实验室，山东 济南 250358； 3.南洋理工大学 海事研究所，新加坡 639798)

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)

原始人工蜂群算法具有控制参数少、计算简单、便于实现等优点，已经被越来越多的研究者关注.但是该算法存在收敛速度慢、容易陷入局部最优解等缺点，需要在收敛速度和寻优精度等方面加以改进.

2 多种群人工蜂群算法(MABC)

2.1 种群分割

种群分割的具体步骤如下:

步骤2将蜜源按照基于欧氏距离的方法依次划分到每个聚类中心；

步骤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 适应度函数

(6)

基于局部通信的适应度函数由式(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等.

步骤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

测试函数f1～f6表达式如下：

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

图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算法有效地应用到实际工程问题中，并采用数学方法使其表现出更多的价值.