人工蜂群算法由Karaboga于2005年首次提出[1],该算法源于对蜂群内部分工机制及其觅食行为的模拟.人工蜂群算法有别于传统算法的一个重要特质是它本质上是一种概率搜索,在问题求解过程中,不需要提供任何与问题相关的梯度信息,就可以解决各种复杂的问题.而与其他智能算法相比,人工蜂群算法又具有控制参数少、收敛速度快以及易于实现等优势,近年来受到越来越多的关注.而已有的人工蜂群算法处理问题的方式较为单一,无论是雇佣蜂还是观察蜂,都只采用了一种在整个优化过程中不变的搜索策略,而不同的优化问题其问题空间存在较大差异,从而导致单一雇佣蜂搜索策略对某些问题有效,而对其他问题求解效果却不是很理想.此外已有的算法没有有效利用优化过程中获得的即时信息来指导后序优化过程,具有一定的盲目性.
针对上述问题,本文提出一种基于反馈的策略自适应选择人工蜂群算法,将多种觅食策略有效融入到问题的求解过程中,并引入反馈机制使其能够根据优化过程中获取的信息及时指导觅食策略的选择.本文利用反馈已搜索信息的方式,自适应调整算法中各种策略使用的范围,随着算法迭代次数的增加,逐步加强算法与问题的适配性,最终找到一种针对某问题即时状态下适合的搜索策略,以获得更加优质的解.为证明新算法的有效性,将其与多种算法在不同测试问题上进行比较.
1 SSABC算法与已有人工算法相同,SSABC算法也由发送雇佣蜂、形成新食物源、评价食物源、发送观察蜂和发送侦察蜂等几个部分组成.但为解决采用单一觅食策略带来的不足,在雇佣蜂觅食阶段融合了多种具有不同特性的搜索策略,并设计了一种基于反馈的自适应调整机制,基于求解过程中获取的信息对各种策略的适用性进行评价以实现雇用蜂对觅食策略的动态选择.具体过程如图 1所示.
可以看出该算法以迭代次数为阶段划分依据,将整个优化过程划分为K个阶段.在每个阶段结束后,根据所获取的该阶段运行信息,对搜索策略进行评价,同时根据评价结果自适应调整下一阶段的雇佣蜂搜索策略的分配.该算法融入了4种雇佣蜂觅食策略,其中:xij表示每个雇佣蜂携带的食物源信息;xmax表示当前整个蜂群获得的最好的食物源信息;Vij为新的食物源的信息;δ(xij)表示雇佣蜂的邻域;xkj表示从邻域中选出的食物源;Rij是自适应调整步长参数;Vijn表示第n段中产生的新食物源信息;Rl=xij-|xij-xkj|;R=2|xij-xkj|;N为设置的分段区间数,分段区间序号n∈{1,2,…,N}.
策略一[2]:对于每一个雇佣蜂,根据其自身获得的食物源xij信息及当前整个蜂群获得的有关食物源信息xmax进行觅食,以发现新的食物源Vij:
策略二[3]:雇佣蜂随机从它所在的邻域δ(xij)中选择一个食物源xkj,并利用食物源xij和xkj形成新的食物源Vij:
策略三[4]:在雇佣蜂邻域选择的范围中加入了自适应调整步长参数Rij,并利用食物源xij,共同形成新的食物源.新的位置更新公式为
策略四[5]:采用“分段搜索”的方式对食物源进行贪婪更新,即在更新某一维时,将搜索范围等分成若干个区间进行搜索,从中随机选取的区间代表值为
策略一适用于雇佣蜂搜索范围较大,食物源较分散的情况.策略二在雇佣蜂搜索范围较小,食物源较密集的情况下,搜索效果更理想.策略三为了提高算法的局部搜索能力,在位置更新公式中利用目标函数自适应调整步长,加强适应度对可行解的指导作用.策略四适合于食物源总体分散均匀,但各个局部搜索能力需要加强的情况.
在反馈机制中为每种策略设有相应的选择概率,算法运行过程中每隔N代根据使用每种策略所获得的食物源的适应度值对各策略的选择概率进行调整以实现雇佣蜂对各种觅食策略的动态选择.对于一个给定的策略e,其选择概率Pe为
其中:fe,i表示采用策略e的第i只雇佣蜂所对应的食物源的适应度值;ce表示采用策略e的雇佣蜂的数量;d表示算法中采用的雇佣蜂觅食策略的个数.
可见N是算法中控制策略调整频率的一个参数,每经过N代,进行一次雇佣蜂搜索策略的调整,即当算法达到kN次迭代后(k为自然数),计算策略e在kN+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也不尽相同.Rastrigin函数收敛后,无论N取值多少,适应度函数值都为0.测试问题Griewank中当N取5时,适应度最小;当N取1000和2000时,适应度最大. Rosenbrock中当N取1000时,适应度最小;当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取1000;Sphere中N取500;结果见表 2,图 2.其中的适应度值、方差为每个测试用例运行20次的结果.
Rastrigin测试问题中,以上各种算法都收敛于0.Griewank,Rosenbrock,Sphere中,SSABC算法得到的适应度函数值较其他算法更好,充分说明了算法的有效性.稳定性方面,SSABC算法在Rosenbrock中较其他算法更稳定;在Griewank与Sphere中,稳定性相对较差.从图 2中可以清晰地看到SSABC算法较其他算法而言,收敛速度是最快的.Rastrigin中,当迭代次数达到1100次左右时,各个算法都收敛于0.
2.3 与其他相关算法比较算法SSABC与算法DE,GA,PSO在4个测试用例上进行了对比分析.表 3给出了各种智能算法迭代10000次后的全局最优值的平均值、标准差,每个算法独立运行20次.
从表 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) |