东北大学学报:自然科学版   2015, Vol. 36 Issue (5): 618-622   PDF (361 KB)    
一种基于反馈策略的自适应选择人工蜂群算法
刘婷婷, 张长胜, 张斌, 孙若男    
(东北大学 信息科学与工程学院, 辽宁 沈阳110819)
摘要:雇用蜂觅食策略对人工蜂群算法性能有较大影响,而单一的觅食策略难以适用于所有问题的搜索空间,并且算法运行的不同阶段所适合的搜索策略也不尽相同.因此,如何为一个给定的函数优化问题选择最佳的觅食策略尤为重要.针对这一问题,提出了一种基于反馈的觅食策略自适应人工蜂群算法SSABC,该算法能够在优化过程中为一个给定的优化问题自动选择最佳的觅食策略.实验表明,与经典ABC(artificial bee colony algorithm),PSO (particle swarm optimization),DE (differential evolution),GA(genetic algorithm) 算法相比,SSABC算法的寻优能力有较大提高.
关键词自适应     人工蜂群算法     反馈     函数优化     智能算法    
A Strategy Self-Adaptive Selection Bee Colony Algorithm Based on Feedback
LIU Ting-ting, ZHANG Chang-sheng,ZHANG Bin,SUN Ruo-nan    
(School of Information Science & Engineering, Northeastern University, Shenyang 110819, China. Corresponding author: ZHANG Bin, E-mail: zhangbin@ise.neu.edu.cn)
Abstract: Employed bee foraging strategies have a greater impact on the performance of artificial bee colony algorithm. The single foraging strategy is difficult to apply to all the search space of the problems. And the different stages of the algorithm performs differently by using different employed bee foraging strategies.How to choose the best foraging strategy is very important for the given function optimization problem. To solve this problem, a strategy self-adaptive selection colony algorithm was presented, based on feedback. The optimal foraging strategy could be automatically selected for the given problem during the optimization process using the praposed algorithm. Experimental results showed that compared with the ABC (artificial bee colony algorithm), the PSO (particle swarm optimization algorithm), the DE (differential evolution algorithm), and the GA (genetic algorithm), the optimization capability of the SSABC algorithm has been improved greatly.
Key words: self-adaptive     artificial bee colony algorithm     feedback     function optimization     intelligence algorithm    

人工蜂群算法由Karaboga于2005年首次提出[1],该算法源于对蜂群内部分工机制及其觅食行为的模拟.人工蜂群算法有别于传统算法的一个重要特质是它本质上是一种概率搜索,在问题求解过程中,不需要提供任何与问题相关的梯度信息,就可以解决各种复杂的问题.而与其他智能算法相比,人工蜂群算法又具有控制参数少、收敛速度快以及易于实现等优势,近年来受到越来越多的关注.而已有的人工蜂群算法处理问题的方式较为单一,无论是雇佣蜂还是观察蜂,都只采用了一种在整个优化过程中不变的搜索策略,而不同的优化问题其问题空间存在较大差异,从而导致单一雇佣蜂搜索策略对某些问题有效,而对其他问题求解效果却不是很理想.此外已有的算法没有有效利用优化过程中获得的即时信息来指导后序优化过程,具有一定的盲目性.

针对上述问题,本文提出一种基于反馈的策略自适应选择人工蜂群算法,将多种觅食策略有效融入到问题的求解过程中,并引入反馈机制使其能够根据优化过程中获取的信息及时指导觅食策略的选择.本文利用反馈已搜索信息的方式,自适应调整算法中各种策略使用的范围,随着算法迭代次数的增加,逐步加强算法与问题的适配性,最终找到一种针对某问题即时状态下适合的搜索策略,以获得更加优质的解.为证明新算法的有效性,将其与多种算法在不同测试问题上进行比较.

1 SSABC算法

与已有人工算法相同,SSABC算法也由发送雇佣蜂、形成新食物源、评价食物源、发送观察蜂和发送侦察蜂等几个部分组成.但为解决采用单一觅食策略带来的不足,在雇佣蜂觅食阶段融合了多种具有不同特性的搜索策略,并设计了一种基于反馈的自适应调整机制,基于求解过程中获取的信息对各种策略的适用性进行评价以实现雇用蜂对觅食策略的动态选择.具体过程如图 1所示.

图 1 SSABC算法流程图 Fig. 1 Flow chart of SSABC algorithm

可以看出该算法以迭代次数为阶段划分依据,将整个优化过程划分为K个阶段.在每个阶段结束后,根据所获取的该阶段运行信息,对搜索策略进行评价,同时根据评价结果自适应调整下一阶段的雇佣蜂搜索策略的分配.该算法融入了4种雇佣蜂觅食策略,其中:xij表示每个雇佣蜂携带的食物源信息;xmax表示当前整个蜂群获得的最好的食物源信息;Vij为新的食物源的信息;δ(xij)表示雇佣蜂的邻域;xkj表示从邻域中选出的食物源;Rij是自适应调整步长参数;Vijn表示第n段中产生的新食物源信息;Rl=xij-|xijxkj|;R=2|xijxkj|;N为设置的分段区间数,分段区间序号n∈{1,2,…,N}.

策略一[2]:对于每一个雇佣蜂,根据其自身获得的食物源xij信息及当前整个蜂群获得的有关食物源信息xmax进行觅食,以发现新的食物源Vij

策略二[3]:雇佣蜂随机从它所在的邻域δ(xij)中选择一个食物源xkj,并利用食物源xijxkj形成新的食物源Vij

策略三[4]:在雇佣蜂邻域选择的范围中加入了自适应调整步长参数Rij,并利用食物源xij,共同形成新的食物源.新的位置更新公式为

策略四[5]:采用“分段搜索”的方式对食物源进行贪婪更新,即在更新某一维时,将搜索范围等分成若干个区间进行搜索,从中随机选取的区间代表值为

策略一适用于雇佣蜂搜索范围较大,食物源较分散的情况.策略二在雇佣蜂搜索范围较小,食物源较密集的情况下,搜索效果更理想.策略三为了提高算法的局部搜索能力,在位置更新公式中利用目标函数自适应调整步长,加强适应度对可行解的指导作用.策略四适合于食物源总体分散均匀,但各个局部搜索能力需要加强的情况.

在反馈机制中为每种策略设有相应的选择概率,算法运行过程中每隔N代根据使用每种策略所获得的食物源的适应度值对各策略的选择概率进行调整以实现雇佣蜂对各种觅食策略的动态选择.对于一个给定的策略e,其选择概率Pe

其中:fe,i表示采用策略e的第i只雇佣蜂所对应的食物源的适应度值;ce表示采用策略e的雇佣蜂的数量;d表示算法中采用的雇佣蜂觅食策略的个数.

可见N是算法中控制策略调整频率的一个参数,每经过N代,进行一次雇佣蜂搜索策略的调整,即当算法达到kN次迭代后(k为自然数),计算策略ekN+1至(k+1)N次迭代过程中采用策略e的选择概率.由于在算法执行之前很难判断哪种策略更适用于求解的问题,初始化阶段将各种策略的选择概率都设置为1/d.

2 实验评估

本文首先对引入的参数N对算法性能的影响进行讨论,为验证SSABC算法的有效性将其与采用单一觅食策略的4种ABC算法及GA,PSO,DE等相关算法[6, 7, 8, 9, 10]在多个测试问题上进行了比较.

2.1 参数调整

在总的迭代次数一定的前提下,N的大小不但决定了算法自适应调整的频度,而且也影响了算法的搜索能力,即搜索策略自适应调节能力的优劣,间接影响着算法的稳定性和鲁棒性.通过N的不同取值,得到的适应度值结果见表 1.

表 1 参数N对算法的适应度 Table 1 The fitness of N to algorithm

表 1可知,由于所处理的问题不同,最佳的雇佣蜂搜索策略自适应调节频率参数N也不尽相同.Rastrigin函数收敛后,无论N取值多少,适应度函数值都为0.测试问题Griewank中当N取5时,适应度最小;当N取1000和2000时,适应度最大. Rosenbrock中当N取1000时,适应度最小;当N取5时,适应度值最大.Sphere中当N取500时,适应度最小;当N取20时,适应度值最大.可以看出N的取值代表了搜索频率与自适应调整策略能力两个方面,并且两个方面相互制约.因此,N的取值根据不同问题解空间不同.

2.2 与采用单一觅食策略的ABC算法的比较

本节主要在4个测试问题中,分别对比SSABC算法与单一雇佣蜂搜索策略的算法ABC,SABC1,SABC2,SABC3在适应度计算次数相同的情况下的适应度值与方差.根据2.1节可知,不同的问题以及不同的解空间,最佳参数N的取值不唯一.因此,根据2.1节的结果,在下面的实验中N取值如下:Griewank中N取5;Rastrigin中N取5;Rosenbrock中N取1000;Sphere中N取500;结果见表 2图 2.其中的适应度值、方差为每个测试用例运行20次的结果.

Rastrigin测试问题中,以上各种算法都收敛于0.Griewank,Rosenbrock,Sphere中,SSABC算法得到的适应度函数值较其他算法更好,充分说明了算法的有效性.稳定性方面,SSABC算法在Rosenbrock中较其他算法更稳定;在Griewank与Sphere中,稳定性相对较差.从图 2中可以清晰地看到SSABC算法较其他算法而言,收敛速度是最快的.Rastrigin中,当迭代次数达到1100次左右时,各个算法都收敛于0.

2.3 与其他相关算法比较

算法SSABC与算法DE,GA,PSO在4个测试用例上进行了对比分析.表 3给出了各种智能算法迭代10000次后的全局最优值的平均值、标准差,每个算法独立运行20次.

表 2 算法内部比较 Table 2 Interior compare in algorithm

图 2 算法内部比较 Fig. 2 Interior compare in algorithm
(a)—Griewank; (b)—Rastrigin; (c)—Resenbrock; (d)—Sphere.

表 3 与其他智能算法比较 Table 3 Compare with the other intelligence algorithm

表 3中看出,SSABC算法在处理各种问题时,都可以得到一个为较理想的适应度值;并且就收敛效果来看,其他算法易陷入早熟与停滞,而SSABC算法能改进这一缺点.Rosenbrock问题中,找到相对理想的适应度值的有效办法是沿着局部极值搜索的过程中,加入有较大分量的搜索方向.SSABC算法由于加入反馈机制,从而自适应调整搜索策略,使之与问题匹配,因此得到了较好的搜索效果.而GA算法在迭代开始不久就陷入了局部最优值.Rastrigin问题中,SSABC与ABC算法的效果较明显,都收敛于0.SSABC算法不仅寻优精度高而且其稳定性也较其他智能算法高.

3 结语

本文提出了一种基于反馈的策略自适应选择蜂群算法,在此基础上应用改进后的蜂群算法在多个测试用例上进行了求解,从多个角度对算法进行了分析,并与经典的ABC,PSO,DE,GA算法进行了比较.结果表明,改进后的蜂群算法,在解决问题时,寻优效果不但优于经典的蜂群算法,而且较其他经典算法而言,搜索精度以及寻优效果也都比较好.未来的研究工作主要集中在多目标优化问题中基于反馈的策略自适应算法的改进和有效性验证上.

参考文献
[1] Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Technical Report-tr06,Erciyes University,Engineering Faculty,Computer Engineering Department,2005.(1)
[2] Akay B,Karaboga D.A modified artificial bee colony algorithm for real-parameter optimization[J].Information Sciences,2012,192:120-142.(1)
[3] Gao W,Liu S.A modified artificial bee colony algorithm[J].Computers & Operations Research,2012,39(3):687-697.(1)
[4] Gao W,Liu S,Huang L.A global best artificial bee colony algorithm for global optimization[J].Journal of Computational and Applied Mathematics,2012,236(11):2741-2753.(1)
[5] 罗钧,肖向海,付丽,等.基于分段搜索策略的改进蜂群算法[J].控制与决策,2012,27(9):1402-1410.(Luo Jun,Xiao Xiang-hai,Fu Li,et al.Modified artificial bee colony algorithm based on segmental-search strategy[J].Control and Decision,2012,27(9):1402-1410.)(1)
[6] Yildiz A R.A new hybrid artificial bee colony algorithm for robust optimal design and manufacturing[J].Applied Soft Computing,2013,13(5):2906-2912.(1)
[7] Khorsandi A,Hosseinian S H,Ghazanfari A.Modified artificial bee colony algorithm based on fuzzy multi-objective technique for optimal power flow problem[J].Electric Power Systems Research,2013,95:206-213.(1)
[8] Gao T,Xu Y,Xu T X,et al.A GA algorithm based on niche and discrete[J].Applied Mechanics and Materials,2013,380/381/382/383/384:1546-1549.(1)
[9] Karaboga D,Akay B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation,2009,214(1):108-132.(1)
[10] Karaboga D,Gorkemli B,Ozturk C,et al.A comprehensive survey:artificial bee colony (ABC) algorithm and applications[J].Artificial Intelligence Review,2014,42(1):21-57.(1)