基于单纯形的改进精英人工蜂群算法

金 叶， 孙越泓,2， 王加翠， 王 丹

(1.南京师范大学 数学科学学院，江苏 南京 210023； 2.南京师范大学 江苏省大规模复杂系统数值模拟重点实验室，江苏 南京 210023)

0 引言

人工蜂群(artificial bee colony，ABC)[1]算法是模拟蜜蜂采蜜机制提出的群体智能随机搜索优化算法，该算法结构简单，设置参数少，不需要求解函数的梯度，易与其他算法结合，在函数优化[2]、工程优化[3]等方面得到了广泛应用.

近年来，已有不少专家学者对ABC算法进行了改进.文献[4]在雇佣蜂阶段提出了一种带有新的搜索算子的改进的人工蜂群算法(improved artificial colony algorithm，IABC)；文献[5]在跟随蜂阶段提出了一种新的选择策略(improved artificial colony algorithm，iABC)；文献[6]提出了受粒子群启发的多精英人工蜂群算法(particle swarm inspired muliti-elitist artificial bee colony，PS-MEABC).人工蜂群算法具有较好的全局搜索能力，但是文献[4-5]指出,ABC算法和其他群智能算法一样,在求解无约束优化问题时存在易早熟、局部搜索能力弱、寻优得到解的精度低等问题.笔者在受粒子群启发的多精英人工蜂群算法[6]的基础上，提出一种新的基于单纯形的改进精英人工蜂群(improved muliti-elitist artificial bee colony algorithm based on nelder-mead simplex method，NM-PS-MEIABC)算法：利用定向更新策略，改进了蜂群随机选取邻居的方式,建立新的跟随蜂选择概率公式,并利用单纯形方法局部搜索能力强的特点提高算法的局部寻优能力.8个基准函数上的数值实验表明，求解无约束优化问题时，本文新算法与ABC和PS-MEABC算法相比，求解精度和收敛速度都有较大改进.

1 基本人工蜂群算法

ABC算法[1]是通过模拟蜜蜂采蜜过程中的智能机制处理函数优化问题.人工蜂群算法描述如下:首先引入蜜源，它代表解空间中各种可能的解，函数优化过程中通过适应度值来衡量蜜源；再引入3种蜂，即雇佣蜂、跟随蜂和侦查蜂.雇佣蜂在蜂房附近搜索蜜源，侧重对蜜源的探测；跟随蜂接收其他蜜蜂分享的蜜源信息，主要负责开采蜜源；侦查蜂在食物源枯竭时，随机在蜂巢附近寻找新的蜜源.求解无约束优化问题(1)时，

minx∈Xf(x).

(1)

1.1 种群初始化

首先按照式(1)产生SN个个体的初始蜜源，得到初始种群：

(2)

产生初始种群后，通过式(2)计算蜜源的质量：

(3)

式中：fi为蜜源xi的目标函数值f(xi)；fiti为蜜源的适应度值,适应度值越大,表示该蜜源质量越优.

1.2 雇佣蜂阶段

雇佣蜂根据式(3)对每个蜜源进行一次邻域搜索,产生新蜜源：

vij=xij+φij(xij-xkj)，

(4)

式中：k∈{1,…,SN}，j∈{1,…,D},这两个数都是随机选取的,但k≠i；φij是[-1,1]上的随机数.在每次邻域搜索过程中随机更新一维(j)上的数值,然后评估vi的质量,利用贪婪选择策略更新蜜源.

1.3 跟随蜂阶段

跟随蜂阶段,雇佣蜂先将蜜源信息共享给观察蜂，然后跟随蜂依据蜜源质量,选择蜜源进行开采,每个蜜源的选择概率计算方式如下：

(5)

式中：Pi表示蜜源i的选择概率.当蜜源被选中之后,跟随蜂将按照式(4)对所选中的蜜源进行邻域搜索，并根据贪婪选择策略更新蜜源.

1.4 侦查蜂阶段

控制参数limit用来记录某个解未被更新的次数.假定某个解经过limit次循环之后都未得到改善，即表明这个解陷入了局部最优，应该被放弃，与这个解相对应的雇佣蜂也转变为侦查蜂,将按式(2)重新随机产生新蜜源.

2 基于单纯形的改进精英蜂群算法

受精英人工蜂群算法[6]和Nelder-Mead单纯形方法[7]的启发，笔者提出了NM-PS-MEIABC算法.该算法的基本思想是在蜂群中建立精英解集，在雇佣蜂阶段借助精英个体引导蜜源搜索，并利用蜂群中蜜源的质量排序重新构造蜜源的选择概率公式.在跟随蜂阶段，选择种群最优蜜源引领蜂群，加强算法对全局最好解的局部开采能力，同时将随机选择邻居蜜源变为定向选择.最后,利用单纯形算法对精英解集进行再次更新，使得算法的局部寻优能力更强，从而达到提高求解精度的目的.而多精英人工蜂群算法和新算法的3个改进之处：多定向更新策略、基于蜜源目标函数值排序的选择概率公式和基于精英解集的单纯形局部搜索机制.

2.1 多精英蜂群算法

为了提高人工蜂群算法的求解精度，Xiang等[6]受粒子群算法[8]和文献[9]的启发，将蜂群中多个蜜源丰富的个体作为精英，构建了精英解集.雇佣蜂阶段通过轮盘赌从精英解集中随机选择一个精英，利用式(6)改进蜜源的更新：

vid=xid+φid(xid-xkd)+σid(xid-Elitistmd),

(6)

式中：i∈{1,…,SN}；d∈{1,…,D}；k∈{1,…,SN}；φid、σid是[-1,1]上的随机数；Elitistmd表示利用轮盘赌方法从精英种群中选出的第m个精英的第d维.同时,在跟随蜂阶段结合蜂群的最优蜜源信息，通过式(7)加强对优质蜜源的开采：

vij=xij+φij(xij-xkj)+θij(xij-gbestj)，

(7)

式中：i∈{1,…,SN}；j∈{1,…,D}；k∈{1,…,SN}；φij、θij是[-1,1]上的随机数；gbestj表示当代蜂群中的最优个体的第j维.

2.2 定向更新策略

Van den Bergh[10]等指出，在粒子群算法中，粒子更新会出现整体在优化，但是某一维却恶化的情况.对于ABC算法同样存在这种现象，由式(4)、(6)和(7)可知，无论是雇佣蜂阶段还是跟随蜂阶段，在进行蜜源更新时，邻居食物源xkj,k∈{1,…,SN} 均是随机从蜂群中选择的个体，k的随机选取可能会导致蜜源第j维更新朝着远离最优蜜源的方向.

图1 2维空间中蜜源搜索邻居的选取说明Fig.1 Illustration of how to select the neighbour sources in 2-D solution space

图1中,种群个体数目SN=5，维数D=2，gbest为当前种群中的最优解.对于第一维,种群中个体x2距离gbest最近;对于第二维,个体x4距离gbest最近,虽然它在第一维上是种群中距离gbest最远的个体.

对于优化问题minx∈Xf(x)而言,整个蜂群在寻优过程中不断寻找质量高的蜜源，也即函数值不断下降的解.然而函数的下降依赖于搜索过程中蜂群中个体不断趋向问题的解x*(x*∈X).最优定向策略应用于观察蜂阶段,通过Distj的大小来衡量种群中不同个体在第j维和gbest的距离.

通过上述过程,在更新第j维时,借助当前最优解的同时,将整个种群中的所有个体进行比较.一方面加强了个体间的信息交流,定向引导蜜源更新；另一方面随着迭代的进行,种群当前最优蜜源不断趋向问题的解x*,也保证了种群Foods={x1,x2,…,xSN}最终能够收敛到问题的最优解x*，文献[13]中有详细的收敛证明.

2.3 基于蜜源目标函数值排序的选择概率公式

基本的人工蜂群算法在跟随蜂阶段，利用式(5)计算每只蜂的跟随概率.在数值实验中发现，在迭代前期，整体蜜源的质量都不是很好，对应的选择概率也就相对较低，从而被跟随的可能性较小；到了迭代后期，蜜源的整体质量都很高，即fiti比较相近，蜜源的选择概率大部分接近1/SN.产生这一现象的主要原因是对于目标函数值小于一定数量级的蜜源，已经很难通过蜜源适应度值的计算公式(3)和概率计算公式(4)将这些蜜源加以区分.

为了解决这一问题，笔者受文献[14]的启发，在构造选择概率公式时，不采用蜜源的适应度值，而是直接利用蜜源目标函数值从大到小排序后的序标，借助式(8)重新定义：

(8)

式中：a=0.1；b=0.9；c为常数；j为第i个蜜源在整个蜂群中按照目标函数值从大到小排序得到的序标.第i个蜜源越好，它的序标j将越大，通过式(8)计算得到的选择概率Pi也就越接近1.

2.4 精英解集Nelder-Mead单纯形局部搜索机制

单纯形法(nelder-mead simplex method, NM-SM)[7]是一种局部搜索算法，具有较强的局部搜索能力.近年来，单纯形法被用于一些全局优化算法中来增强局部搜索能力.单纯形法和人工鱼群算法[15]、头脑风暴算法[16]等优化算法都做过结合.单纯形算法的基本思想是：对于D维优化问题，利用D+1个点作为顶点构成凸包，即单纯形.在已有单纯形的基础上通过反射、扩张和收缩去寻找一个目标函数值更小的点.如果得到这样的点就可以用该点作为顶点构造新的单纯形，否则将已有单纯形缩小.具体算法流程见文献[17].

在单纯形算法每次迭代过程中，反射系数、扩张系数、收缩系数分别为α、γ、β，定义如下：

单纯形算法的大致过程如下：

步骤2对最差的点进行反射，得到反射点xα.

步骤3若f(xα)

步骤4若f(xα)

步骤5若f(xh)>f(xα)>f(xp)，执行收缩操作得到收缩点xw;若f(xw)

人工蜂群算法虽然全局搜索能力不错，但是存在着局部搜索能力差、在接近最优解时搜索效率下降、求解复杂问题时容易陷入局部最优而停滞不前的缺点[18]，而单纯形法具有很强的局部搜索能力，它和人工蜂群算法的全局搜索能力互补，如果将两者结合必然相得益彰.

因此，为了进一步加强算法对蜜源的开采能力，将更新后的精英解集在侦查蜂阶段之后结合当前全局最优蜜源，利用D+1个蜜源构成初始单纯形，初始单纯形的构造具体如下.

(1)若SN>D,则对更新后的精英解集按照函数值从小到大排序,利用前D个精英蜜源和全局最优蜜源构成初始单纯形.

(2)若SN

vi=elitesi+φ(xi-xk),

(9)

式中：i∈{1,…,D-SN}；k∈{1,…,SN}；φ是[-1,1]上的随机数.然后利用Nelder-Mead单纯形法进行局部搜索，加快算法的收敛.单纯形方法的迭代次数和食物源数目保持一致，取为SN.

2.5 NM-PS-MEIABC算法步骤

步骤1参数设置.设置蜂群规模NP,雇佣蜂数SN=NP/2,跟随蜂数SN=NP/2.迭代步数计数器t=0,最大函数计算次数,蜜源停留最大限制次数limit,初始化密源停留次数trial=0.

步骤2初始化种群.按式(2)随机产生SN个蜜源.利用式(3)对蜜源质量进行评价.并记录下此时的全局最优蜜源gbest,并利用初始种群初始化精英解集.

步骤3精英个体引导雇佣蜂搜索.利用轮盘赌方法,随机从精英解集中选取一个精英个体Elitistm,利用式(6)对蜜源进行搜索.对超出搜索范围的解直接利用精英Elitistm代替,接着利用贪婪选择决定是否更新蜜源, 更新gbest和密源停留次数trial.

步骤4选择概率计算.将所有蜜源按照目标函数值从大到小排列.蜜源xi质量越高,序标j越大.利用式(8)计算跟随蜂选择蜜源xi的概率Pi.

步骤6侦查蜂更新.若蜜源的停留次数trial>limit成立，则该蜜源转为侦查蜂，用式(2)重新随机产生新的蜜源将其更新.

步骤7精英解集的更新.如果种群中全局最优蜜源优于轮盘赌选出的最差精英个体，则将其替换从而更新精英解集，保持精英蜜源个数为SN.

步骤8基于精英解集的单纯形局部搜索机制.用更新后的精英解集和全局最优蜜源构造初始单纯形，接下来采用Nelder-Mead单纯形进行局部再开采，最后利用输出的单纯形更新对应的精英个体.若单纯形最优解优于蜂群最差个体，则替换蜂群最差个体，将利用单纯形进行局部搜索得到的最优蜜源信息传递给蜂群.

步骤9记录全局最优.单纯形开采后的最优蜜源和gbest进行比较，记录较优的蜜源作为当前全局最优蜜源.

步骤10停止准则.判断是否达到最大函数计算次数FES,若满足则输出全局最优解，否则转步骤3.

3 数值仿真实验结果

3.1 测试函数

为了验证NM-PS-MEIABC算法的有效性，笔者进行了数值实验，将其与ABC算法[1]和PS-MEABC[6]算法,NMABC[18]作比较.实验设备为：台式电脑HP LV2011，CPU为Intel Core2 Duo CPU E7500 2.93 GHz, 2 012 MB内存，实验仿真软件Matlab2012b.所有用于比较的算法的种群大小SP=100，食物源数目SN=50，最大限制次数limit=100，决策变量维数为30维，函数计算次数(maximum function evaluations,MFE)为300 000次.参照基于精英蜂群搜索策略的人工蜂群算法[19], 笔者选取8个基本测试函数，如表1所示.

表1 测试函数Tab.1 Test functions

新算法在构建好的精英解集上引入了Nelder-Mead单纯形局部搜索机制,以增强人工蜂群的局部寻优能力.单纯形中反射系数、扩张系数以及收缩系数的不同取值,在不同问题中对算法影响程度不同.通常反射系数α=1,扩张系数1<γ≤2,收缩系数0<β<1[20].接下来对反射系数和收缩系数设置不同取值,进行实验分析,测试中选取单峰函数f1,多峰函数f4、f7.在30维上进行30次模拟,最大函数计算次数为300 000.

表2给出了取定单纯形收缩系数β=0.5时，扩张系数γ不同取值下在3个测试函数上的实验结果.由表2得知，扩张系数γ=2时，算法在选取的测试函数上效果最差；γ=1.2时，效果一般；动态变化γ从2递减至1.2时，效果最好.综上，将γ的取值设在2～1.2变化，随着迭代的进行，在算法后期减小对单纯形的扩张，实验得到的结果是最好的.故新算法中，γ=2～1.2.

表2还给出了取定单纯形扩张系数γ=1.2时，收缩系数β取值不同时的实验结果.收缩系数β=0.2时，算法在3个给定函数上的结果最差，可知局部寻优的单纯形收缩过小容易导致算法陷入局部最优.当β=0.8时，算法的效果最好，故在新算法NM-PS-MEIABC中取β=0.8.

表2 算法NM-PS-MEIABC关于扩张系数γ的不同取值(β=0.5)和关于收缩系数β的不同取值(γ=1.2)Tab.2 The different values of the expansion coefficient and contraction coefficient

3.2 实验结果

由表3可以看出，当函数计算次数相同时，很明显NM-PS-MEIABC 算法具有较好的寻优性能，比ABC算法、PS-MEABC、NMABC算法有更高的求解精度.

表3 本文算法与其他人工蜂群算法在30维上结果比较Tab.3 The comparison results with ABC variants

图2、图3分别给出了ABC算法、PS-MEABC算法、NMABC算法和NM-PS-MEIABC算法对于30维f1(Sphere)函数和f5(Griewank)函数，在独立运行30次时取平均最优值的收敛情况.从图2～图3可以看出，笔者算法在收敛速度和搜索精度上要优于其余3种算法.

图2 Sphere函数收敛情况Fig.2 The convergence of Sphere function

图3 Griewank函数收敛情况Fig.3 The convergence of Griewank function

4 结束语

笔者提出了一种基于单纯形的改进精英人工蜂群算法，算法利用单纯形算法加强对解的局部寻优，并提出了新的邻域搜索方法和跟随概率的计算公式.数值实验结果表明，新算法与ABC、PS-MEABC、NMABC算法相比，求解精度和收敛速度均有显著提高，寻优性能也更加稳定，未来可以进一步做ABC算法的应用以及综述.