基于最优个体指导单纯形法改进的人工蜂群算法及应用

赵旭芳 梁昔明 龙 文

1(北京建筑大学理学院 北京102600)2(贵州财经大学经济系统仿真贵州省重点实验室 贵州 贵阳 550025)

0 引 言

在过去的二十年来，全局优化算法发展迅速，为解决高度复杂的优化问题，众多受生物行为启发的优化算法相继被提出，这些方法通常简单且易于实现，例如：遗传算法、粒子群算法、蛙跳算法、人工鱼群算法、人工蜂群算法等。这些算法对优化问题研究结果表明群智能优化算法对解决复杂优化问题具有巨大的潜力和优势。人工蜂群算法ABC(Artificial bee colony algorithm)是由Karabogo在2005年提出的一种新型群体智能优化算法，全局探索能力强，能够有效解决复杂的高维度全局优化问题[1-2]。自提出以来，由于良好的全局优化能力且控制参数少、易于实现等优点，受到研究者的关注，并且适用于许多应用领域。然而，基本人工蜂群算法同样存在局部搜索缓慢和收敛精度低的缺点，且易陷入局部最优。为解决这些不足，研究人员提出一些改进算法，这些算法都有自己的特点和优势，并取得优异的结果。文献[3]利用微分算子的优势弥补基本人工蜂群算法的局限性，从而提高算法的收敛精度和加快其收敛速度；文献[4]受重力模型启发，提出一种基于对立学习的多节搜索方程和一种多方侦查的搜索策略来提高算法的性能；文献[5]提出在全局最优的指导下进行邻域搜索且采用精英蜜蜂随机选择的方法代替跟随蜂的概率选择方法，提高收敛精度和收敛速度；文献[6]提出基于混沌算子和相邻选择策略的改进算法，以平衡基本ABC算法的全局搜索和局部寻优能力；文献[7]提出一种全球侦查方案，通过对侦查蜂的搜索策略进行预测和选择来提高算法求解精度；文献[8]提出在全局最优和子集合最优共同指导下的搜索策略和独立的遗传搜索策略，用于提高算法的全局搜索能力。目前人工蜂群算法已在多方面得到应用，文献[9]将人工蜂群算法应用于应急调度优化问题中，使得所求出的非支配前沿解集更加多样性；文献[10]利用人工蜂群算法解决车辆路径规划问题，以减少总体的旅行距离或旅行时间，满足绿色物流的新要求；文献[11]对于双级交通网络设计问题，提出依靠人工蜂群算法来设计路线结构和下降的搜索方向，以确定给定路线结构的最佳频率设置。本文提出一种基于当前最优个体指导的人工蜂群算法，有效结合单纯形法精确的局部寻优能力和人工蜂群算法较强的全局搜索能力。经数值试验结果表明，所得改进后的人工蜂群算法具有更快的收敛速度和更高的收敛精度。

1 基本人工蜂群算法和单纯形法

对无约束连续优化问题：

minf(X)X∈RD

(1)

若X*∈RD满足f(X*)≤f(X),∀X∈RD，称X*为f(X)在全空间RD上的全局极小点或整体极小点。

1.1 ABC原理

人工蜂群算法是模拟蜜蜂采蜜行为提出的群智能优化算法，整个搜索过程可分为：引领蜂阶段、跟随蜂阶段和侦查蜂阶段。开始时所有的引领蜂在对应的食物源邻域随机搜索新的食物源，跟随蜂根据食物源的丰富程度进一步进行随机搜索。在搜索过程中，贪婪的选择机制被用于新旧食物源的选取，若经过给定迭代次数后食物源没有得到更新，那么引领蜂将转变为侦查蜂在搜索空间随机搜索替换。在搜索过程中，引领蜂、跟随蜂和侦查蜂都是重复迭代进行同样的工作，直到达到终止条件(最大迭代次数或给定的求解精度)。

ABC算法在求解优化问题时，NP表示食物源的数量，引领蜂和跟随蜂的个数等于食物源的数量；fiti是适应度函数值，表示食物源的丰富程度；limit是开采极限，引入计数traili。

1.1.1 初始化阶段

食物源的初始种群Xi=(xi1,xi2,…,xiD)(i=1,2,…,NP)按下式在搜索空间随机产生：

xi.j=Lmin,j+ψ(Umax,j-Lmin,j)

(2)

式中：j∈(1,2,…,D)，Umax,j和Umin,j分别表示第j维的上界和下界，ψ是(0,1)中的一个随机数。每个食物源的适应度函数值由下式计算：

(3)

式中：fi=f(Xi)。同时设置计数器traili(i=1,2,…,NP)为0。

1.1.2 引领蜂阶段

每一个引领蜂对应一个食物源，并在其周围按下式搜索得到一个新的食物源Vi，并计算其适应度值:

vi,j=xi.j+φ(xi,j-xk,j)

(4)

式中：i=1,2,…,NP，k是随机选择的一只人工蜂，k∈(1,2,…,NP)且k≠i，j∈[1,2,…,D]且是随机选择的一维，其余所有变量都将从旧食物源中继承，φ是(-1,1)中的一个随机数。比较两个食物源的适应度函数值，若新食物源的适应度值更大，则替换，同时计数器traili置0，否则保留旧食物源的位置且计数器加1。

1.1.3 跟随蜂阶段

跟随蜂根据引领蜂提供的信息，采用轮盘赌的选择机制选取需要更新的食物源，对每个食物源被选择的概率按下式计算：

(5)

r是选取的[0,1]中随机选取一个均匀分布的数，如果pi>r，那么跟随蜂在其对应的食物源周围按式(4)进行随机搜索产生新的食物源。贪婪选择机制被用于确定新旧食物源的去留，即新食物源的适应度值更大，则替换，同时计数器traili置0，否则保留旧食物源的位置且计数器加1。

1.1.4 侦查蜂阶段

在所有的引领蜂和侦查蜂完成搜索后，需要检查算法的计数器中是否有大于给定开采极限limit的值，若存在，则与之食物源对应的引领蜂就要转化为侦查蜂，在搜索空间按式(2)随机产生新的食物源Vi取代原有的，即：

(6)

式中：i=1,2,…,NP，j=1,2,…,D。

引领蜂、跟随蜂和侦查蜂阶段的搜索过程重复迭代直到达到给定的终止条件。通过以上过程可以看出，在基本ABC算法中，引领蜂分享信息的能力增强了蜂群之间的合作能力，跟随蜂选择适应度值大的食物源进行搜索可以提高算法的收敛速度，侦查蜂用于跳出局部最优解。但三种蜜蜂的搜索方案都是随机生成的，这样提高了搜索方案的多样性和全局探索的能力，但也弱化了算法的局部搜索能力。而且对于跟随蜂的搜索只是改变食物源其中的一维向量，探测能力有限，故本文针对这一现象对基本人工蜂群算法进行改进，在跟随蜂阶段引入单纯形法，且以当前最好的食物源作为指导。

1.2 单纯形法

单纯形法是由Hest和Himsworth于1962年提出的，是一种用于直接求解无约束优化问题的算法，具有良好的局部搜索能力。算法过程简单易于实现，通过对单纯体顶点目标函数值的比较，改良单纯体较劣顶点以逼近最优值。过程主要包括反射过程、扩张过程和收缩过程。以三个点为例，对函数值最小的顶点通过反射、扩张和收缩三种运算进行更新，得到更优的点。其求解流程如下：

Step1设置反射系数、扩张系数和收缩系数α、β、γ和ε，随机生成3个顶点X1、X2、X3。

Step2计算每个顶点的目标函数值，找到目标函数值最好的、第二差的和最差的分别为Xg、Xb、…、Xw。

Step4若f(Xn+3)

Step5若f(Xg)

Step6若f(Xb)

2 改进人工蜂群算法和单纯形法

基本ABC算法中，依靠蜂群之间信息分享共同完成搜索新食物源的任务，但由于引领蜂和侦查蜂的随机搜索机制导致算法随机性大，故算法有强的全局探索能力，但局部探索性能差。因此针对此缺陷，提出一种基于最优个体指导单纯形法改进的人工蜂群算法(BABC),在跟随蜂的局部搜索引入以当前最优个体作为指导的单纯性法且在侦查蜂阶段加入保优策略。基本ABC算法中的局部搜索每次只改变一维的变量，而单纯形法同时可以改变多个变量，便于加大搜索范围，更快地找到最优值。具体更新规则为：在跟随蜂阶段选取当前最优个体Xg，次优个体Xb和需要更新个体Xw作为初始顶点代入单纯形法，且令α=1.4，β=0.5，γ=0.4，用单纯形算法求得的Xi取代Xw。接着进行侦查蜂阶段的保最优个体策略，即首先判断达到开采极限的是否为当前最优个体，若是，则保留；若不是，按基本ABC算法的搜索机制进行，最后判断是否达到终止条件，若达到，输出当前最优个体。在侦查蜂阶段加入的选取机制，能够有效避免侦查蜂跳出最优值，增强算法的收敛速度和精度。改进后的人工蜂群算法流程如下：

(1) 初始阶段，随机初始化NP个食物源，分别设置参数最大迭代次数max、食物源开采极限limit和精度tol；

(2) 计算适应度函数值，执行引领蜂阶段，即引领蜂在各自的食物源周围进行随机搜索，记录新食物源的适应度函数值且与旧食物源的进行比较，保留丰富的食物源(适应度函数值大的)；

(3) 执行跟随蜂阶段，即根据引领蜂分享食物源丰富程度的信息(适应度函数值的大小)，跟随蜂以轮盘赌的方式选择搜索的食物源，然后通过以最优个体指导的单纯形法进行搜索，并记录新食物源的适应度值，采用贪婪选择机制确定留下的食物源；

(4) 执行侦查蜂阶段，即所有的引领蜂和跟随蜂完成搜索任务后，检测计算器traili(1,2,…,NP)中是否有大于开采极限limit，若大于开采极限则需再次判断是否为当前最优个体，若是，则保留，反之引领蜂转化为侦查蜂，在空间随机搜索食物源取代；

(5) 所有的蜜蜂完成搜索任务后，判断是否达到终止条件(终止条件是达到最大迭代次数或达到目标精度)，如果满足终止条件，则输出最优解，算法终止，否则转步骤(2)。

BABC算法流程图如图1所示。

图1 BABC算法流程图

3 实验结果与分析

为了验证所提出的改进人工蜂群算法的性能，使用以下五个典型的无约束极小化问题进行数值试验，具体如表1所示。

表1 五个典型的无约束优化问题

3.1 ABC算法、GABC算法和BABC算法的比较

对目标函数f1～f5，将BABC算法与基本ABC算法及文献[12]中GABC算法在固定迭代次数下进行比较分析。GABC算法以当前最好的食物源位置作为引领蜂搜索方式的指导，以提高搜索精度。试验中，具体参数设置如下：食物源NP取30，测试目标函数设置维数D为100，最大迭代次数2 000次，开采极限limit=300。采用MatlabR2014a实验平台进行数值试验，为减少偶然性的影响，每个算法对每个测试问题进行30次独立试验，取试验所得目标函数值的平均值、标准差、最大值和最小值进行对比。试验结果统计如表2所示，且图2-图7分别是三种算法对不同目标函数的平均最优值进化曲线。

表2 目标函数测试结果

续表2

从表2可以看出，与ABC算法和GABC算法相比，BABC算法无论在稳定性还是所得目标函数值的精度上都有较大的提升。对目标函数f1～f6，ABC算法和GABC算法均得不到最优目标函数值，且其求解精度也不高。而BABC算法对目标函数f1、f2、f5和f6，都有较高的求解精度，且目标函数值平均值、最小值和最大值相差不是很大，说明算法稳定性很好。对目标函数f3，BABC算法求得理论最优目标函数值0；对目标函数f4，虽求得的目标函数值精度提升不大，但求的最小值达2.45e-12。

图2 目标函数f1平均值进化曲线

图3 目标函数f2平均值进化曲线

图4 目标函数f3平均值进化曲线

图5 目标函数f4平均值进化曲线

图6 目标函数f5平均值进化曲线

图7 目标函数f6平均值进化曲线

从图2、图3和图6可以看出，BABC算法在大约1 200次迭代后趋于平缓且解达到较高精度，而ABC算法和GABC算法在迭代2 000次仍只得到精度较低的解；从图4可以看出，BABC算法很快达到理论最优值，图上基本显示不出它的变化曲线，而ABC算法和GABC算法在迭代500次趋于平缓且求解精度很低；从图5和图7可以看出，BABC算法在迭代2 000次达到较高精度且仍在向最优解靠近。

3.2 指定精度下的迭代次数

为了进一步比较三种算法的性能，在给定精度tol=10-6下每个算法对每个测试问题进行30次独立试验，统计每个算法的成功率、平均迭代次数、最小迭代次数和最大迭代次数，其中成功率表示算法在30次独立试验中达到给定精度的次数和30的比值，维数D=100。表3为迭代次数的对比结果。

表3 迭代次数的对比结果

从表3中可以看出，在给定精度的情况下，ABC算法和GABC算法对目标函数f1～f6，迭代2 000次均没有得到指定精度的解，成功率为0，而BABC算法除目标函数f4外，成功率为1。且所用迭代次数更少，尤其对复杂目标函数f3，平均迭代次数只需3次便得到给定精度的解，对于其他目标函数，其最小迭代次数均是两位数，平均迭代次数均为三位数。以上结果说明，在给定精度下，BABC算法不论是成功率、稳定性还是计算效率均比其他两种算法有很大的提升。

3.3 改变参数的优化结果

种群数目、迭代次数和开采极限是影响算法性能的主要参数，对参数的取值不同，算法的寻优效率也会有变化。为了能够进一步了解算法的性能，设置了在不同开采极限下不同种群数在不同维度和不同最大迭代次数下的试验。取种群数分别为20、40、60、80、100和150，开采极限为100、200和300，分别对应最大迭代次数1 000、2 000和3 000，维数取30和50，对六个测试问题进行30次独立试验求取目标函数的平均值，测试结果如表4所示。

表4 不同参数下算法寻优效果

续表4

从表4中可以看出，当最大迭代次数增加和开采极限改变时，BABC算法对目标函数的求解精度有所提高，当NP≥40时，BABC算法优化结果相对稳定且收敛精度较高。计算中增加迭代次数和加大群体规模更有助于算法的寻优效果，但计算量也随之增加。因此，对一些优化问题的求解过程中，太多的迭代次数和太大的群体规模是不必要的，要选取适量的迭代次数和群体规模，在取得精度较高解的同时减少计算量，从而减少运算时间。

3.4 与其他算法求解结果对比

对六个目标函数，BABC算法与GABC算法、COABC算法[13]、ABC-best-1算法[14]、ABC-best-2算法[15]进行比较,维数取30，其他参数设置与文献[8]一致且表中数据除BABC算法均来自文献[16]。COABC算法通过应用前一个最佳方案来指导新的候选方案，从而提高算法的性能；ABC-best-1算法为提高算法的收敛精度生成初始种群时采用了混沌系统和基于队里的学习方法；ABC-best-2算法在搜索中引入选择性机制来提高算法的全局寻优速度。表5为不同改进算法寻优结果对比。

表5 不同改进算法寻优结果对比

从表5中可以看出，BABC算法对目标函数f1虽然没有得到最优值0，但其精度很高；对目标函数f2，其目标函数值精度较ABC-best-1算法和ABC-best-2算法有很大的提升；对目标函数f3，只有BABC算法取得理论最优值0，而且其他算法求解精度均不是很高；对目标函数f4，除ABC-best-1算法外，其他四种算法均求得理论最优值；对目标函数f5，其他四种算法求解精度均很低，只有BABC算法得到精度较高的解；对目标函数f6，五种算法均得到理论最优值0。

4 改进算法在参数优化问题中的应用

近年来，智能优化算法求解模型参数优化问题越来越受到人们的关注，本文选用登革病毒传播模型，利用BABC算法对模型参数进行优化，并与文献[16]中选取的参数得到的模型输出结果进行对比，结果表明BABC算法求解的参数使模型输出和实际观测数据之间拟合效果更好, 均方根误差更小。

传统登革病毒传播模型将所有人Nh分为三部分：易感人群Sm(t)，感染人群Ih(t)，拥有抗体人群Rh(t)。所有的雌蚊Nm被分为两部分：易感染雌蚊Sm(t)和已感染雌蚊Im(t)。模型由如下五个方程描述，考虑五个独立变量Sh、Ih、Rh、Sm、Im：

(7)

(8)

(9)

(10)

(11)

式中：μh代表人患病后的平均死亡率，μm代表雌蚊患病后的平均死亡率，βh代表易感人群被已感染雌蚊叮咬后被传染的概率，βm代表易感染雌蚊叮咬感染人群后被传染的概率，b代表人被雌蚊叮咬的概率，γ代表感染人群的恢复率。

登革病毒传播模型需要顾及六个参数μh、μm、βh、βm、b、γ，各个参数的搜索区间分别为：1e-5≤μh≤1e-4，0≤μm≤0.5，0≤βh≤1，0≤βm≤1，0≤b≤1，0≤γ≤1。

利用Caputo分数阶导数：

(12)

对传统登革病毒传播模型进行改进，得到在Caputo分数阶导数定义下的分数阶非线性登革病毒传播模型[16]：

(13)

(14)

(15)

(16)

(17)

在Caputo分数阶导数定义下的分数阶非线性登革病毒传播模型需要估计六个参数μh、μm、βh、βm、b、γ以及两个Caputo分数阶导数αh和αm，它们的搜索区间分别为:1e-5≤μh≤1e-4，0≤μm≤0.5，0≤βh≤1，0≤βm≤1，0≤b≤1，0≤γ≤1，0≤αh≤1，0≤αm≤1。

为了估计登革病毒传播模型中的参数，我们利用佛得角岛上2009年登革热疫情的实际数据作为已知数据，初始条件为：Sh(0)=55 784，Ih(0)=216，Rh(0)=0，Sm(0)=168 000，Im(0)=0，时间t=90天。

文献[16]选取参数为μh=1/71.365，μm=0.1，βh=0.36，βm=0.36，b=0.7，γ=1/3，αh=1，αm=0.77，此时分数阶非线性登革病毒传播模型输出结果与实际数据的均方根误差为581。

当参数为μh=1/71.365，μm=0.1，βh=0.36，βm=0.36，b=0.7，γ=1/3时，利用BABC算法对αh和αm进行优化，求解结果为式(13)中αh= 0.999 1，式(14)中αh= 0.726 8，式(15)中αh= 0.752 4，式(16)中αm= 0.979 8，式(17)中αm= 0.915 4。此时分数阶非线性登革病毒传播模型的输出结果与实际数据的均方根误差为323，利用BABC算法所得参数与文献[16]中选取参数对应的模型输出与实际数据之间的拟合情况如图8所示。

图8 优化所得参数对应的模型输出结果与实际数据的对比

BABC算法求解在Caputo分数阶导数定义下的分数阶非线性登革病毒传播模型中的参数，所得参数对应的模型输出比文献[16]选取的模型输出与实际数据的均方根误差都小。

5 结 语

本文提出了一种基于最优个体指导单纯形法改进的人工蜂群算法(BABC)，应用于跟随蜂阶段，以平衡算法的开发和探测能力，并且在侦查蜂阶段加入一个保优策略，避免跳出全局最优，以加快收敛速度。经过6个目标测试函数的实验数据表明，所提出的改进算法是有效的，能够增强基本ABC算法的局部搜索能力，使得算法具有更高的求解精度。利用改进后的算法对参数进行优化，所得模型参数对应的模型输出与实际数据拟合很好，结果表明BABC算法对这类模型参数优化问题求解的有效性。