基于交叉的全局人工蜂群算法的研究

张平华，李敬明，胡贤德，胡 俊

(1.安徽新华学院 信息工程学院，安徽 合肥 230088；2.合肥工业大学 管理学院，安徽 合肥 230009)

基于交叉的全局人工蜂群算法的研究

张平华1，李敬明2，胡贤德1，胡 俊1

(1.安徽新华学院 信息工程学院，安徽 合肥 230088；2.合肥工业大学 管理学院，安徽 合肥 230009)

人工蜂群(Artificial Bee Colony，ABC )算法在求解函数最优值时，存在后期收敛速度慢、易于陷入局部最优、疏于开发等问题.为了解决这些问题，对算法进行了深入研究，结合其他仿生智能优化算法的机制，提出了一种能有效提高收敛速度，增强算法开发性和全局寻优能力，并能有效避免种群个体陷入局部最优的算法——基于交叉的全局人工蜂群算法.选取7个标准测试函数进行实验仿真，结果表明，与ABC算法、全局最优人工蜂群算法(GABC)相比，基于交叉的全局人工蜂群算法(CGABC)的收敛速度及精度均有明显提高.

智能算法；交叉；全局；人工蜂群算法

近年来，国内外学者对基于智能优化规则的启发式算法做了大量的研究，各种先进的、智能的仿生群智能算法不断出现(如鱼群算法、蛙跳算法、禁忌搜索算法、遗传算法、蚁群算法、粒子群算法等)，并被逐步应用到组合优化和资源调度等各方面的问题求解中.仿生群智能是指众多简单的个体通过相互协同方式，表现出复杂的智能行为的过程和特性.群体智能算法主要有模拟蚂蚁觅食行为的蚁群算法[1](Ant Colony Optimization，ACO)、源于鸟群觅食行为的粒子群算法[2](Particle Swarm Optimization，PSO)、模拟真实鱼类觅食行为的人工鱼群算法[3](Artificial Fish Swarm Algorithm，AFSA)、模拟自然界中萤火虫成虫发光的生物学特性的萤火虫算法[4](Glowworm Swarm Optimization，GSO)以及模拟蜜蜂群体寻找优良蜜源的人工蜂群算法[5](Artificial Bee Colony，ABC)等.

1 人工蜂群算法及计算框架

1.1 人工蜂群算法概述

在对蜜蜂群体采蜜行为进行深入观察和研究后，受蜜蜂行为的启发，土耳其Erciyes大学的KARABOGA教授在一种虚拟蜜蜂(Virtual Bee Algorithm，简称VBA)算法的基础上，于2005年在文献[6]中系统地提出了一种新型群智能优化算法——人工蜂群觅食优化算法.

人工蜂群(简称ABC)算法在组合优化方面已经被证实比上述的智能算法具有更优越的性能[7].但与其他群智能计算算法一样，ABC算法也存在着缺乏全局最优值的记录和算法参与过程、后期收敛速度慢、易于陷入局部最优、疏于开发等问题.ZHU等[8]优化了蜜源产生位置的规则，在ABC算法中引入全局最优，提高了算法的开发能力；王伟等[9]将遗传算法的交叉算子引入了ABC算法中，提出了一种基于交叉算子的改进人工蜂群算法(MABC)，提高了算法的局部搜索能力，加快了收敛速度；在DE算法的变异策略启发下，GAO[10]等通过产生候选蜜源位置，改进了蜂群对蜜源的搜索能力，提出了GABC算法；刘三阳[11]等引入局部搜索算子，利用随机局部搜索算子对当前最优进行局部搜索，加快了算法的收敛速度；AKAY[12]等通过控制扰动频率来加快算法的收敛速度.

本文针对以上不足，结合文献[8]的优点，在全局最优的基础上引入交叉系数，提高局部优化能力，提出一种基于交叉的全局人工蜂群算法.

依据文献[6]中的描述及摇摆舞(如图1所示)和采蜜过程(如图2所示)可知，ABC算法主要由4个基本组成元素：蜜源(食物源，Food Sources)、引领蜂(又称采蜜蜂或雇佣蜂，Employed Foragers，EF)、跟随蜂(又称观察蜂Onlookers或非雇佣蜂，Unemployed Foragers，UF)、侦察蜂(Scouts).其中引领蜂和跟随蜂用来开采蜜源, 即寻找最优解, 而侦查蜂用来观察是否陷入局部最优[13]；两种基本的智能行为模式为：(1)招募(Recruit)行为：采蜜蜂在蜂巢跳舞区传递蜜源信息，招募待工蜂(观察蜂)；(2)放弃(Abandon)行为：某个食物源被持续开采极限(Limit)次后，采蜜蜂放弃该蜜源成为侦察蜂.

蜜源即待求解问题的可行解，在算法中用“适应度”又称“适应值”来描述蜜源(可行解)质量的好坏.

引领蜂也称作雇佣蜂或采蜜蜂，在算法中其数量与已知的蜜源数量一致，占整个蜂群规模的一半.它具有记忆功能，存储着蜜源的相关信息，它会将蜜源的相关信息在舞蹈区分享给观察蜂(待工蜂)，并依据蜜源情况不断更新自身位置选取更好的蜜源，提高了解的质量.

图1 摇摆舞

图2 蜂群采蜜过程图

侦察蜂主要在蜂巢周围搜索潜在的食物源，一旦找到新的食物源，则变为雇佣蜂即采蜜蜂.参考实验数据和文献[6]，侦察蜂数量在算法中大约占蜂群数量的5%～20%；跟随蜂占整个蜂群规模的一半，主要是在舞蹈区观察引领蜂(雇佣蜂)的摇摆舞(如图1所示)，按蜜源与适应度值比例的概率，选择自己认为满意的蜜蜂进行跟随.

招募行为：引领蜂在指定的区域内随机搜索新蜜源，并计算适应度值大小，以此来判断是否更新当前的食物源，并存储蜜源相关信息.引领蜂回到蜂巢跳舞区通过摇摆舞来传递蜜源信息给跟随蜂，跟随蜂采用贪婪算法并以一定的概率选择一只引领蜂跟随，成为引领蜂.

放弃(Abandon)行为：当某个蜜源经历了Limit次迭代后仍没有改进时，则被强制放弃，其对应的引领蜂转变为侦查蜂，重新随机搜寻一个新的蜜源.

1.2 人工蜂群算法框架描述

根据求解组全优化问题的分析，可以建立利用ABC算法求解智能优化问题的数学模型，即

(1)

式中：D为优化问题的维数；f(x)为优化的目标函数；G为可行解的解空间的(可以用上下界来表示，如[lb,ub]).

在ABC算法中，蜜源亦即优化问题的解，通常用一个N维向量来表示；蜜源的优劣用优化函数的适应度值来衡量.算法框架描述如下.

1.2.1 初始化阶段

初始化人工蜂群的规模(SN)、最大迭代次数(maxCycle)、最大开采次数(limit)；初始化SN/2个D维的可行解xi(xi1,xi2,…,xiD)T(i=1,2,…，SN).

(2)

1.2.2 引领蜂阶段

引领蜂依据(2)式进行邻域搜索，并采用贪婪算法或轮盘赌算法依据(3)式计算初始适应度值(fitness(xi))，并按(4)式求出对蜜源选择的概率.

(3)

式中：f(x)为待优化的函数；fitness(xi)为函数的适应度值.

f(x)通常是一个在实数域内连续的函数，其值也是对应于实数域中的适应度值fitness(xi).从式(2)可以明显看出，适应度值fitness(xi)越大，对应的目标函数值就越小.因此，标准ABC算法中fitness(xi)的最大值，即对应为求解式(1)的最小化问题.反之如果要求解优化问题的最大值，只需求出适应度值fitness(xi)的最小值.以上分析可用图3所示的二维曲线图[7]来描述.

图3 目标函数与适应度转化曲线图

1.2.3 跟随蜂阶段

跟随蜂依据(3)式计算跟随概率Pi，搜索蜜源，并计算适应度值，选择相关蜜源.

(4)

1.2.4 侦察蜂阶段

侦察蜂在其邻域范围内随机地搜索新的蜜源.当蜜源经过限定的最大开采次数(limit)后，如果仍然没有改进，则在此采蜜的引领蜂就放弃此蜜源，并变为侦查蜂，从而重新按(2)式随机选取新的蜜源，产生新蜜源位置.

2 基于交叉的全局人工蜂群算法

2.1 交叉操作

在ABC算法中，算法的效率及收敛的关键是如何设计好适应度函数、种群的更新过程和如何避免陷入局部最优.在ABC算法中，引领蜂从其阾域中随机选取一个食物源进行迭代更新，这种方式更新得到的新的食物源，在算法中不能保证它就是一个质量较好的解，可能导致算法局部搜索能力的下降.为了更好地提高算法的全局和局部搜索能力，本文将遗传算法中种群的交叉算子引入到GABC(全局最优解引导的人工蜂群算法)算法中，提出一种基于交叉的全局人工蜂群算法(Crossover of the Global Artificial Bee Colony，CGABC).

交叉操作是将种群的父代个体基因中优秀的基因遗传给子代，通过配对方式进行基因交换重组，重新结合成新个体，在一定程度上充分提高了蜂群的多样性，提高了算法整体的优化能力.

交叉操作常见的方式有指数交叉和二项交叉两种[14].交叉操作是将选择出的两个个体作为父个体，将二者的部分码值按位进行交换.设有两个8位个体P1和P2，如图4所示.

图4 P1，P2个体

现随机产生一个在1到7之间的数c=3，则依据交叉原理可将P1和P2的低三位交换后，得到一个新的个体.其交换过程如图5所示.

图5 交叉操作示意图

在交叉操作中，对于二项交叉，对每一个分量都随机地产生一个0～l之间的随机数rand，若rand

(5)

式中：交叉算子cr一般取值为0.3～0.6；β的取值在0～1.5.

为进一步提高算法的探索和开发能力，在文献[8]CABC算法思想启发下，通过全局引导来加快算法的收敛速度和算法搜索能力，具体邻域搜索公式改变如下：

k≠i

(6)

式中：β的取值在0～1.5；α∈[-1,1]之间的随机值.

2.2 CGABC算法框架

基于交叉的全局人工蜂群算法(CGABC)借鉴了DE算法的基本思想和CABC算法的思想，在CABC的基础上引入交叉算子[15]，提高了算法种群的多样性和变异更新能力，达到了提高算法的开发能力和整体寻优能力效果.算法流程图如图6所示.CGABC算法步骤如下：

S1:算法各种参数和种群的初始化；

S2: 引领蜂(采蜜蜂)依据(6)式进行邻域搜索，依据(3)式计算初始适应度值(fitness(xi))并记录全局最优值(GlobalValue)和全局最优解向量(GlobalMin)；

S3:进入采蜜阶段，引领蜂根据蜜源情况，采蜜蜂进行邻域搜索，依据(6)式更新食物源，产生新的候选位置，并进行交叉操作.具体过程如下：

While(iter

采蜜蜂将邻域搜索后的解与迭代产生的最优解按(5)式进行交叉操作，计算新的适应度值，根据贪婪算法选择更优的蜜源.

按(4)式计算观察蜂跟随概率，并转为采蜜蜂进行邻域搜索，然后按(5)式交叉操作，按照贪婪算法选择新的蜜源，并保留全局最优值；

侦察蜂随机寻找新蜜源替换超过邻域搜索限制次数的蜜源；

记录全局最优解；

End while

图6 算法流程图

3 数值实验仿真与分析

为了充分测试提出的基于交叉的全局人工蜂群(CGABC)算法的优越性，在此选取了单模和多模函数共计7个(如表1所示)，分别进行实验仿真，并与标准ABC算法和全局ABC算法的实验结果进行比较.其中，只有Sphere 为单模态函数，其余都是多模态函数，它们的理论最优值(最小值)都是0，在实验中，蜂群大小BN=50，采蜜蜂数量=观察蜂的数量=BN/2=25，所有优化函数维度D=30，最大迭代次数maxCycle=3 000，最大开采次数limit=300，交叉系数cr=0.3；实验针对每个测试函数在上述参数设置下独立运行10次，记录其最优值、平均值、最劣值和标准差.表2给出了CGABC算法、ABC算法和GABC算法对表1中的7个测试函数进行仿真寻优结果的比较.图7～图13为7个测试函数的优化收敛比较图.

表1 测试函数

编号函数名模式函数表达式取值范围全局极小值F1Sphere单模fx()=∑Di=1x2i[-100,100]f0→()=0F2Rosenbrock多模fx()=∑D-1i=1100[(xi+1-x2i)2+(xi-1)2][-2.048,2.048]f1→()=0F3Schaffer多模fx()=0.5+sin2 ∑Di=1x2i()-0.5(1+0.001(∑Di=1x2i))2[-100,100]f0→()=0F4Schwefel多模fx()=D*418.9829-∑Di=1x2isin( xi)[-500,500]f420.96→()=0F5Ackley多模 fx()=-20e-0.2 1D∑Di=1x2i()-e1D∑Di=1cos2πxi()+20+e[-32,32]f0→()=0F6Rastrigin多模fx()=∑D-1i=1x2i[-10cos2πxi()+10][-5.12,5.12]f0→()=0F7Griewank多模fx()=14000∑Di=1x2i-∏Di=1cosxi i()+1[-600,600]f0→()=0

表2 测试函数优化结果对比表

函数名算法全局极小值最劣值平均值标准差SphereABC4.55409×10-167.50686×10-165.72005×10-169.38136×10-17GABC2.63053×10-165.5108×10-165.0541×10-168.50722×10-17CGABC2.38339×10-163.28075×10-162.97085×10-162.65856×10-17RosenbrockABC0.1293804673.4995705431.2340769940.989323071GABC0.0029668641.7454077920.6157354010.613216816CGABC0.0585532680.4356478390.1964641660.109650872SchafferABC0.2276901410.3732906940.3404386050.045531083GABC0.1782223040.373290650.3036420660.051266344CGABC0.2727410960.3455094940.3097199320.032563777SchwefelABC0.0003818270.0003818270.0003818279.795557710-13GABC3.8182699×10-43.8182699×10-43.8182699×10-48.335656610-13CGABC3.8182699×10-43.8182699×10-43.8182699×10-40AckleyABC3.9968×10-144.35207×10-144.17444×10-141.77636×10-15GABC2.93099×10-144.35207×10-143.89022×10-144.21861×10-15CGABC2.930988×10-143.9968029×10-143.6415315×10-143.5527137×10-15RastriginABC05.68434×10-141.13687×10-142.27374×10-14GABC0000CGABC0000GriewankABC1.1102230×10-164.4408921×10-161.5543122×10-161.0175362×10-16GABC1.1102230×10-162.2204460×10-161.2212453×10-163.3306691×10-17CGABC1.1102230×10-161.1102230×10-161.1102230×10-160

图7 Sphere函数收敛图

图 8 Rosenbrock函数收敛图

图9 Schaffer函数收敛图

图 10 Schwefel函数收敛图

图11 Ackley函数收敛图

图12 Rastrigin函数收敛图

图13 Griewank函数收敛图

从表2和图7～13的寻优收敛曲线图可以看出，不管是单模态还是多模态的函数，CGABC算法性能优于标准ABC算法和GABC蜂群算法，它能更快速地收敛于最优值点，效果有了明显的提升.

4 结束语

人工蜂群算法是一种新型的群体智能优化算法，因特有的劳动分工、自组织、贪婪选择和协作机制，算法灵活，不依赖于问题的梯度而具有广泛的适用性.本文利用交叉算子对全局优化算法进行改进，通过对函数的测试，表明该算法在求解多模态函数的全局优化问题时，在收敛速度、优化精度、收敛成功率和稳定性等方面的性能更优于标准人工蜂群算法.改进后的算法可在多目标优化问题及相关工程领域广泛应用.

[1] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]// Varela F J, Bourgine P. Proceedings of the First European Conference on Artificial Life. Second Printing Edition. Paris：Elsevier,1992:134-142.

[2] KENNEDY J. Particle Swarm Optimization[M]. New York: Spring US，2011:760-766.

[3] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践，2002(11):32-38.

[4] KRISHNANAND K N, GHOSE D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]// Symposium I S I .Proceedings 2005 IEEE Swarm Intelligence Symposium. Pasadena: IEEE,2005:84-91.

[5] KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1): 687-697.

[6] KARABOGA D. An idea based on honey bee swarm for numerical optimization: Technical report-tr06[R].Kayseri: Erciyes University,2005.

[7]张伟. 人工蜂群混合优化算法及应用研究[D]. 杭州：浙江大学, 2014.

[8]ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3 166-3 173.

[9]王伟,龙文.基于交叉算子的改进人工蜂群算法[J].兰州理工大学学报，2015,41(1):101-106.

[10] GAO W, LIU S. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3): 687-697.

[11] 刘三阳,张平,朱明敏.基于局部搜索的人工蜂群算法[J].控制与决策，2014,(1):123-128.

[12] AKAY B, KARABOGA D. A modified artificial bee colony algorithm for real-parameter optimization[J]. Information Sciences, 2012, 192: 120-142.

[13]宁爱平,张雪英.人工蜂群算法的收敛性分析[J].控制与决策，2013(10):1 554-1 558.

[14]乔艳霞,邹书蓉,张洪伟.基于K-means的改进差分进化聚类算法[J].四川理工学院学报( 自然科学版)，2014,27(5):64-67.

[15] 邱剑锋,谢娟,汪继文.基于交叉突变算子的人工蜂群算法及其应用[J].计算机应用研究，2014(5):1 336-1 341.

(编辑：郝秀清)

Research on global artificial bee colony algorithm based on crossover

ZHANG Ping-hua1，LI Jing-ming2，HU Xian-de1，HU Jun1

(1.School of Information Engineering, Anhui Xinhua University, Hefei 230088, China;2.School of Management, Hefei University of Technology, Hefei 230009, China;)

The shortcomings of artificial bee colony algorithm include slow convergence speed，easily falling into local optimum value，neglect of development and other issues. In order to overcome these problems,referencing the mechanism of other bionic intelligent optimization algorithms, a new algorithm of global artificial bee colony algorithm based on crossover is proposed, which can effectively improve the convergence rate, enhance the development of the algorithm and the global optimization ability, and the algorithm can effectively avoid the local optimum. Finally,seven standard test functions are selected to carry out the experiment and simulation. The results show that the convergence speed and accuracy of the proposed algorithm (CGABC) are significantly improved compared with other algorithms such as ABC algorithm, GABC algorithm and so on.

intelligent algorithm; cross; global; artificial bee colony algorithm

2016-09-07

国家自然科学基金项目(71271071);安徽省自然科学基金项目(KJ2016A304，KJ2016A308)

张平华，男，zphpinganye@qq.com

1672-6197(2017)05-0006-06

TP301.6； TP18

A