一种邻域搜索的人工蜂群算法

.作者:周新宇 吴志健 邓长寿 彭虎
.来源期刊:中南大学学报(自然科学版)2015年第2期
.中文关键字:全局优化;人工蜂群;邻域搜索;一般反向学习
.英文关键字:global optimization; artificial bee colony; neighborhood search; generalized opposition-based learning
.中文摘要:提出采用邻域搜索机制来改进人工蜂群算法的解搜索方程,从当前食物源的环形邻域拓扑结构中选择较优的邻居食物源进行开采,平衡算法的勘探与开采能力。此外,为保存侦察蜂的搜索经验,提出采用一般反向学习策略生成被放弃食物源的反向解,提高算法的搜索效率。在20个典型的benchmark函数上验证算法的性能,并与6种知名的改进算法进行对比。实验结果表明:本文算法在收敛速度和解的精度上均有较大优势。
.英文摘要:The neighborhood search mechanism was introduced to improve the solution search equation of artificial bee colony algorithm. In the ring neighborhood topology of current food source, the exploitation was focused on the best neighbor food source to balance the capabilities of exploration and exploitation. Moreover, in order to preserve search experience for scout bees, the generalized opposition-based learning strategy was utilized to generate opposite solutions of the discarded food sources, which helps enhance the search efficiency. Twenty classic benchmark functions were used to test the performance of our approach, and then the experimental results were compared with other six well-known algorithms. The results show that our approach has better convergence speed and solution accuracy.
详细信息展示

DOI: 10.11817/j.issn.1672-7207.2015.02.023

一种邻域搜索的人工蜂群算法

周新宇1, 2,吴志健1,邓长寿3,彭虎1

(1. 武汉大学 计算机学院,软件工程国家重点实验室,湖北 武汉,430072;

2. 江西师范大学 计算机信息工程学院,江西 南昌,330022;

3. 九江学院 信息科学与技术学院,江西 九江,332005)

摘要:提出采用邻域搜索机制来改进人工蜂群算法的解搜索方程,从当前食物源的环形邻域拓扑结构中选择较优的邻居食物源进行开采,平衡算法的勘探与开采能力。此外,为保存侦察蜂的搜索经验,提出采用一般反向学习策略生成被放弃食物源的反向解,提高算法的搜索效率。在20个典型的benchmark函数上验证算法的性能,并与6种知名的改进算法进行对比。实验结果表明:本文算法在收敛速度和解的精度上均有较大优势。

关键词:全局优化;人工蜂群;邻域搜索;一般反向学习

中图分类号:TP301.6             文献标志码:A         文章编号:1672-7207(2015)02-0534-13

Neighborhood search-based artificial bee colony algorithm

ZHOU Xinyu1, 2, WU Zhijian1, DENG Changshou3, PENG Hu1

(1. State Key Laboratory of Software Engineering, Computer School, Wuhan University, Wuhan 430072, China;

2. College of Computer and Information Engineering, Jiangxi Normal University, Nanchang 330022, China;

3. School of Information Science & Technology, Jiujiang University, Jiujiang 332005, China)

Abstract: The neighborhood search mechanism was introduced to improve the solution search equation of artificial bee colony algorithm. In the ring neighborhood topology of current food source, the exploitation was focused on the best neighbor food source to balance the capabilities of exploration and exploitation. Moreover, in order to preserve search experience for scout bees, the generalized opposition-based learning strategy was utilized to generate opposite solutions of the discarded food sources, which helps enhance the search efficiency. Twenty classic benchmark functions were used to test the performance of our approach, and then the experimental results were compared with other six well-known algorithms. The results show that our approach has better convergence speed and solution accuracy.

Key words: global optimization; artificial bee colony; neighborhood search; generalized opposition-based learning

人工蜂群(artificial bee colony, ABC)算法是近年来提出的一种较为新颖的全局优化算法[1-2],具有结构简单、控制参数少、易于实现等特点。该算法与粒子群优化(particle swarm optimization, PSO)算法[3]类似,都是通过模拟自然界生物的群体智能行为而设计的群智能优化算法。但与PSO算法不同的是,ABC模拟的是蜂群的智能采蜜行为,它根据不同种类蜜蜂的分工协作,实现整个蜂群采蜜量的最大化,即找到待优化问题的最优解[4]。Karaboga等[5]研究结果表明,ABC的性能要优于或者相当于差分演化(differential evolution,DE)算法、PSO算法和遗传算法。目前,ABC算法已成功地用于解决多种不同类型的实际优化问题,如参数优化[6]、符号回归[7]、神经网络[8-9]以及车辆路径问题[10]等。在标准ABC算法中,雇佣蜂(employed bee)和观察蜂(onlooker bee)共用一种解搜索方程(solution search equation)生成新的候选食物源,因而算法的性能主要依赖于该方程。然而,最近的研究[11-13]指出,这种解搜索方程侧重于算法的勘探(exploration)能力,而开采(exploitation)能力不足,易导致算法的收敛速度过慢和解的精度不高。针对此问题,受PSO算法的启发,Zhu等[11]提出了一种gbest引导的ABC算法,在解搜索方程中融入全局最优解的信息,用于提高算法的开采能力。类似地,Banharnsakun等[12]也在全局最优解的基础上,提出了改进的解搜索方程。Gao等[13]受DE算法的“DE/best/1”变异策略的启发,提出了一种“ABC/best/1”的改进解搜索方程,在该方法中同样也利用了全局最优解。这几种改进的ABC算法均利用了全局最优解信息来提高算法的开采能力。虽然使用全局最优解可增强开采能力,但在一定程度上也易导致算法陷入局部最优,特别是在优化多峰函数时。因此,为提高ABC算法的开采能力且不易于陷入局部最优,受局部版本的粒子群优化(local particle swarm optimization, LPSO)算法[14-15]的启发,本文提出一种邻域搜索的ABC(neighborhood search based artificial bee colony, NSABC)算法。LPSO是标准PSO算法[16]的一个改进版本,它采用粒子所在邻域的最优粒子代替标准PSO的全局最优粒子来指导粒子的速度更新。受此启发,在观察蜂阶段,采用邻域搜索机制从当前食物源的环形邻域拓扑结构中选择1个最优的食物源,在该食物源的邻域范围内搜索新的候选食物源,有助于增强算法的开采能力且不易于陷入局部最优。此外,为帮助侦察蜂(scout bee)保存搜索经验,提出采用一般反向学习策略来生成被放弃食物源的反向解,使得侦察蜂可以快速地找到新的优秀食物源。为验证本文算法的性能,在20个典型的benchmark函数(包括单峰、多峰以及偏移加旋转类型)上开展数值实验,并与6种不同类型的改进算法进行对比。

1  人工蜂群算法

在ABC算法中,人工蜂群包含了3种不同类型的蜜蜂:雇佣蜂、观察蜂和侦察蜂。雇佣蜂负责勘探食物源,并在蜂巢的舞蹈区通过摇摆舞的形式将食物源的相关信息分享给观察蜂[17],这些信息包括食物源的位置以及蜂蜜量。然后,观察蜂根据收到的信息以一定概率选择某一食物源继续开采,该食物源的蜂蜜量越多,被选中的概率就越高。若一个食物源被开采完,则相对应的雇佣蜂就转变为侦察蜂,再重新随机搜索一个新的食物源。值得说明的是:1个食物源的位置对应于待优化问题的1个候选解,食物源的蜂蜜量即指适应值;而雇佣蜂与食物源是一一对应的,同时雇佣蜂的数量和观察蜂相同。

类似于其他演化算法,ABC算法同样采用1个随机初始化的群体开始迭代搜索。设群体规模为SN,其中食物源Xi =(xi,1, xi,2, …, xi,D)代表1个候选解,i∈{1, 2, …, SN},D为待优化问题的维度。初始化之后,ABC算法根据蜜蜂的类型,将优化过程分为3个阶段。

1) 雇佣蜂阶段。在该阶段,每一只雇佣蜂在对应的食物源Xi处,采用解搜索方程生成1个新的食物源Vi =(vi,1,vi,2,…,vi,D)。若Vi的蜂蜜量更多即适应值更优,则就替换Xi。该方程如下:

             (1)

其中:为[-1, 1]间的随机数;k∈{1,2,…,SN}是随机选择的一个食物源,且k≠i;j∈{1,2,…,D}是随机选择的1个维度。

2) 观察蜂阶段。在所有雇佣蜂完成了勘探后,观察蜂根据接收到的信息随机选择一个食物源进一步开采。这种选择方式通常采用基于适应值的方法,如:轮盘赌机制。若观察蜂采用轮盘赌机制进行选择,则食物源Xi被选中的概率pi

                (2)

其中:fi为食物源Xi的适应值。从式(2)可以看出,食物源的适应值越大,被观察蜂选中的概率越高。

3) 侦察蜂阶段。当雇佣蜂对应的食物源的适应值连续limit次未更新,说明该食物源已被开采耗尽。这种情况下,雇佣蜂转变成侦察蜂,采用式(2)重新随机搜索1个新的食物源。

        (3)

其中:rand(0,1)为[0, 1]间的随机数;[aj, bj]为第j维变量的上下界。值得说明的是,除群体规模等公共参数外,limit是ABC算法中唯一的参数。

2  基于邻域搜索的ABC算法

2.1  邻域搜索机制

PSO算法模拟的是鸟群和鱼群的觅食行为[16]。在标准PSO算法中,粒子的速度更新受自身历史经验pbest和群体历史经验gbest的共同影响,如式(4)所示:

(4)

但Kennedy等[14-15]指出:标准PSO算法中的gbest在求解多峰函数时易出现早熟现象,为此提出了一种局部版本的PSO算法,即LPSO算法。在LPSO算法中,粒子的速度更新受自身历史经验pbest和邻域的最优粒子lbest的共同影响,即

(5)

受LPSO算法的启发,本文提出在观察蜂阶段采用邻域搜索机制来选择食物源进行开采,而不是直接利用全局最优解的信息。因而,在求解多峰函数时,能够利用邻域内较优的个体信息,而非全局最优解信息,有利于增加群体的多样性,避免算法陷入局部最优。此外,雇佣蜂阶段则保持原来的解搜索方程不变,这样有助于结合雇佣蜂的勘探能力和观察蜂的开采能力,充好利用和保持这两种能力的平衡,提高ABC的搜索性能。因此,对观察蜂而言,新食物源的搜索方式如下:

         (6)

其中:lbest(i)为当前食物源Xi所处邻域的最优食物源,设邻域半径为K,则lbest(i)∈{i-K,…,i-1,i,i+1,…,i+K}。r1∈{1,2,…,SN},r2∈{i-K,…,i-1,i,i+1,…,i+K},且满足r1,r2和i互不相等.

值得说明的是,邻域搜索的方式与群体的拓扑结构类型是相关的,依据Das等[18]的建议,本文采用效率较高的环形邻域拓扑结构。这种结构的特点是群体中个体是否相邻是由下标的关系确定,而不是搜索空间中的欧式距离。图1给出了式(6)采用的环形邻域拓扑结构示意图,其中K为邻域半径。

为更加直观地说明提出的邻域搜索机制与原解搜索方程的区别,以2维Shekel’s Foxholes函数为例,采用标准ABC算法和结合了邻域搜索机制的ABC(简记为ABC-NS)分别优化该函数,给出2种算法在不同演化代数下的群体分布情况。2维的Shekel’s Foxholes函数是多峰函数,有24个局部极值和1个全局极值f(-32,-32)=0.998 004,搜索空间的边界是[65.536, 65.536]2。该函数的具体定义可参考文献[19],图2所示为该函数的3-D图。对标准ABC算法和ABC-NS算法,采用相同的参数设置,SN=30,limit=100。而在ABC-NS算法中,按文献[18]的建议,取邻域半径K为群体规模的10%。

图1  环形邻域拓扑结构

Fig. 1  Structure of ring neighborhood topology

图2  2维Shekel’s Foxholes函数的3-D图

Fig. 2  3-D plot of Shekel’s Foxholes function of two-dimension

图3所示为标准ABC和ABC-NS算法在演化过程中的第1代、第15代和第30代的群体分布情况,实心圆点表示食物源,空心矩形是Shekel’s Foxholes函数在平面上的投影,即25个极值点。从图3可以看出,在第1代中由于随机初始化的作用,2种算法的群体分布无明显区别,均随机分散在搜索区域中。但随着演化代数的增加,2种算法的有效搜索区域都不断收缩,食物源也向各个极值点靠拢。但值得注意的是,ABC-NS算法的收缩速度要明显比ABC算法的快。特别地,在第30代时,ABC-NS算法的所有食物源都已收敛到全局极值点处,而ABC算法只有部分食物源到了该点。结果表明:采用邻域搜索机制可以有效地利用邻域中优良个体的信息,增强算法的开采能力,且不易于陷入局部最优。

2.2  一般反向学习策略

在标准ABC算法的侦察蜂阶段,一个食物源若超过limit次未更新,则认为该食物源被开采耗尽,对应的雇佣蜂转变为侦察蜂,并采用式(3)再重新随机搜索一个新的食物源。这种机制存在不足,即被放弃的食物源可能包含了有益的搜索信息,直接采用随机生成的新食物源来替换,则易导致这部分信息丢失。为此,本文提出采用一般反向学习策略生成被放弃食物源的反向解,充分利用这些食物源所含的有益信息,为侦察蜂提供更多的搜索经验,有助于进一步提高算法的搜索效率。

网站首页 | 把有色金属在线设为首页 |收藏有色通搜索 | 联系我们