南京邮电大学学报自然科学版
主办单位:江苏省教育厅
国际刊号:1673-5439
国内刊号:32-1772/TN
学术数据库优秀期刊 《中文科技期刊数据库》来源期刊
       首 页   |   期刊介绍   |   新闻公告   |   征稿要求   |   期刊订阅   |   留言板   |   联系我们   
  本站业务
  在线期刊
      最新录用
      期刊简明目录
      本刊论文精选
      过刊浏览
      论文下载排行
      论文点击排行
      
 

访问统计

访问总数:11202 人次
 
    本刊论文
基于精英蜂群搜索策略的人工蜂群算法

 摘要:针对人工蜂群(ABC)算法存在收敛速度慢、求解精度不高、容易陷入局部最优等问题,利用蜂群觅食过程中先由侦察蜂进行四处侦察食物,并利用蜂群搜索构建精英群体指导蜂群觅食寻优。据此,提出了一种模拟侦察蜂侦察觅食行为的基于精英蜂群搜索策略的连续优化算法。算法利用构建精英蜂群策略、改进侦察蜂搜索机制以及基于目标函数值选择寻优三个主要策略加强算法的搜索机制。数值实验表明,所提算法不仅寻优精度和寻优率非常高,且收敛速度快,并能适于高维空间的优化问题。 
中国论文网 http://www.xzbu.com/8/view-6136203.htm
  关键词:侦察蜂;精英蜂群;人工蜂群算法;全局侦察;函数优化 
  中图分类号: TP18 
  文献标志码:A 
  Abstract: There are some problems in the Artificial Bee Colony (ABC) algorithm, such as the slow convergence speed, low solution precision and easy to fall in local optimum. In this paper, the scout bees firstly explored the food source by a random motivation. Along with the process of colony bee foraging behavior, the elite swarm was constructed to guide the colony bee to achieve better solutions. Hence, the paper proposed a continuous optimization algorithm based on elite swarm search strategy, which simulated the foraging behavior of scout bees. The search mechanism of the algorithm was enhanced by constructing elite swarm strategy, improving the scout bee search mechanism and selecting the best solution based on the objective function value. The numerical experiment results show that the proposed algorithm has high searching precision, success rate and fast convergence speed. It is also suitable for solving highdimensional space optimization problems. 
  Key words: scout bee; elite swarm; Artificial Bee Colony (ABC) algorithm; global reconnaissance; function optimization 
  0引言 
  人工蜂群(Artificial Bee Colony, ABC)算法是一种模拟蜜蜂采蜜行为的随机搜索优化算法[1],算法采用蜂群觅食的方式来生成问题的解,从而解决现实生活中的诸多问题。该算法具有独特的角色分配机制,能快速地搜索到优化问题的解。同时,该算法利用蜂群的劳动分工、协作机制以及正反馈机制,使得算法更加灵活,全局寻优能力强,有较好的搜索性能,易与其他技术结合来提高原算法的效率,以解决连续优化以及求解组合优化问题,具有广泛的适用性。随后,Karaboga等进一步将其发展并与遗传算法(Genetic Algorithm, GA)、粒子群优化(Particle Swarm Optimization, PSO)算法、粒子群进化算法(Particle Swarm Inspired Evolutionary Algorithm, PSEA)、差分进化(Differential Evolution, DE)算法、进化算法(Evolutionary Algorithm, EA)等进行了性能比较[2-3],与其他群智能算法相比,ABC算法表现出控制参数少,有其独特的优越性[4]。目前,该算法不仅在离散优化领域中得到了较广泛的应用,也能成功地应用到各类问题[5],并取得了良好的优化效果,如:函数优化问题[6]、神经网络训练[7]、滤波器设计[8]、聚类分析[9-11]、约束优化问题[12-13]、可靠性冗余分配问题[14]、作业车间调度问题[15]、约束车辆路径问题[16]和优化二元结构性问题[17]等。 
  ABC算法是一个最早用来求解函数优化问题的数学模型,由于函数优化是一个连续域优化问题,因而求解复杂,求解精度要求较高。但是,与其他全局优化算法一样,传统ABC算法也存在着早熟收敛、后期收敛速度变慢易陷入局部最优解的缺点。为此,为了进一步探索ABC算法进行连续函数优化的方法,一些学者研究了用ABC算法与其他算法杂交混合的搜索策略,例如IABC(Improved Artificial Bee Colony)[18]、RABC(Rosenbrock Artificial Bee Colony)[19]、HHSABC(Hybrid Harmony Search with Artificial Bee Colony)[20]等。其中:IABC利用一个参数q控制ABC/best/1和ABC/rand/1两种搜索模式;RABC算法结合Rosenbrock旋转方向的方法局部优化,利用ABC进行全局搜索;HHSABC则是结合和声搜索和蜂群的混合算法,来达到良好的全局搜索性能。另外,一些学者用ABC算法进行函数优化的另一途径则是对最初的ABC算法进行搜索机制的局部改进使其能较好地应用于连续空间优化问题。例如:Zhu等[21]提出GABC(Gbestguided Artificial Bee Colony),利用全局最好解(gbest)指导搜索;Banharnsakun等[22]提出一种改进跟随蜂的搜索机制来提高搜索精度;MABC(Modified Artificial Bee Colony)[23]则利用混沌初始化,DE变异操作加强搜索,并取消概率选择和侦察蜂搜索机制;Akay等[24]提出采用频率和幅度扰动两个新的搜索模式提高收敛的改进的蜂群优化算法;PSABC(Prediction and Selection Artificial Bee Colony)[25]则是改进雇佣蜂和跟随蜂的搜索机制,提出利用全局最好解、惯性权重、加速系数的IABC(Improved Artificial Bee Colony)算法,并提出混合三种搜索机制进行预测和选择的PSABC算法;NABC(New Artificial Bee Colony)[26]改进雇佣蜂和跟随蜂的搜索机制,构建候选解池存储当前蜂群的较好解;MFABC(Modified Foraging Artificial Bee Colony)[27]改进跟随蜂的搜索机制,从而增加食物源的多样性。   为了改进算法的性能,一些新的改进算法也在不断地产生。以上这些研究取得了显著的成果,但如何提高寻优率和寻优精度并提高收敛速度仍需进一步探索,特别是对高维空间问题的优化精度和速度更有待提高。这些研究都取得了很大成就,但由于这些算法大都是在原始模型基础上的改进,因而收敛速度和精度都还没有达到更理想的程度。 
  虽然ABC算法有较好的全局搜索能力,但是,其局部搜索能力相对较差,求解精度仍有待提高,不断探索优化精度更高、收敛速度更快、性能更优的优化算法是不断追求的目标。为此,本文受已有算法的启发,并根据真实蜂群的研究[28],提出了一种基于精英蜂群搜索策略的人工蜂群(Elite Searchbased Artificial Bee Colony, ESABC)算法。该算法初始化种群分布后,利用一组侦察蜂进行大步长全局搜索,并逐步构建精英蜂群,指导引领蜂和跟随蜂的局部优化,从而加速收敛,提高求解精度。该算法具有算法简单、收敛速度快、精度高,且适用于高维空间等特点。仿真实验结果表明,本文算法求解速度快,寻优率和精度高,效果十分令人满意。 
  1基本的人工蜂群算法 
  ABC是建立在蜜蜂自组织模型和蜂群智能基础上的一种非数值优化的随机搜索方法。蜜蜂根据各自不同的分工进行相互协作,并实现蜂群信息的共享与交流,从而搜寻到最优的食物源(蜜源)。人工蜂群算法模型中包括3类蜂群:雇佣蜂、跟随蜂和侦察蜂。雇佣蜂也被称为引领蜂,其在蜂房附近搜索蜜源,记录与其对应蜜源的相关信息,并将信息与其他蜜蜂按一定的概率分享;跟随蜂主要任务为开采蜜源,其在舞蹈区域等待雇佣蜂以舞蹈的方式与其分享信息从而寻找收益度更高的蜜源;侦察蜂在ABC算法中是一只虚拟蜂,当某个食物源枯竭时候,相应的雇佣蜂角色转变为侦察蜂在蜂巢附近寻找新的蜜源,对整个蜂群的觅食有全局的侦察引导作用。 
  3.2参数设置 
  本文算法中,为了与其他蜂群优化算法比较,在相同的机器下,相同的VC6.0++环境下进行程序实现。设置总蜂群规模数m、侦察蜂系数alf、早熟系数limit分别为100,0.05和100,根据侦察蜂系数,可知侦察蜂数ms为5,根据NABC算法[26]中对参数的设置,为0.1,wmax和wmin分别为1和0.2,为了与其他蜂群优化算法测试的公平性,算法在最大迭代次数MCN为1000和4000的情况下分别进行了测试,维数分别为30和60,测试结果如表2~4所示。 
  3.3实验结果 
  用表1所示的测试函数对本文ESABC算法进行了最大迭代次数分别为1000和4000次,维度分别为30和60的测试。为了验证基于目标函数值选择寻优的效果,本文将基于适应度函数值选择寻优的方法表示为ESABC0,直接基于目标函数值选择寻优的方法表示为ESABC。实验中同时测试了相同环境下基本ABC算法的测试结果。实验中优化过程的精度要求固定为0,实验中分别独立运行30次。取平均误差值(Mean),标准方差(Standard Deviation, SD),平均收敛迭代次数(average of Convergence Iteration, CI)。表中粗体部分表示最优结果。 
  表2中,本文测试了最大迭代次数为1000和4000次,维度分别为30和60维。从1000次的实验数据来看,ESABC算法的测试结果优势明显,很好地验证了基于目标函数值选择寻优的有效性。同时,可以看到基于适应度函数值选择寻优ESABC0算法也比基本ABC算法优越,反映出本文构建精英蜂群策略和改进侦察蜂搜索机制使得算法性能提高显著。 
  当最大迭代次数为4000次时可的测试结果来看看出,ESABC0和ESABC算法分别在不同的函数上都表现出优异的寻优能力和搜索精度。可以看出,随着迭代次数的增加,ESABC算法能表现出很好的求解精度和寻优能力。 
  为了进一步验证本文算法的效果,将ESABC算法与有代表性的和新发表的蜂群连续优化算法进行了实验比对。与蜂群连续优化算法的实验比较,主要比较了ABC算法、GABC算法和MABC算法,结果如表3所示。表4中,本文算法与NABC算法在维度为30的情况下进行了比较。表3和表4中的符号意义同表2,其中Max.FE表示最大评价次数,表3中GABC和MABC算法的实验数据结果分别摘自文献[23],而本文算法在多数函数中测试性能上优于这些算法。同时,部分测试结果与最新提出的蜂群连续优化算法性能相当,说明本文算法具有很好的搜索性能。 
  从整体上来看,ESABC算法具有较好的综合搜索性能,比ABC算法、MABC和NABC算法更具优势,显示出本文算法较好的性能。图1~4分别给出了基本ABC算法、NABC算法和本文ESABC算法对于30维的Sphere、Griewank、Penalized和Quartic with noise函数在30次独立运行下取平均误差值的收敛情况,进一步验证了本文算法有更好的全局搜索能力与求解精度。 
  4结语 
  本文提出了一种基于精英蜂群搜索的连续优化算法,算法中模拟侦察蜂侦察食物再与其他蜂群协作共享信息,并在迭代搜索的过程中逐步构建精英蜂群指导搜索寻优。尽管这种模拟可能还不完美,有待改进,但实验结果表明,该算法寻优率、求解精度都非常高,效果显著。与当前的多种先进算法比,收敛速度有所加强,寻优精度也有大幅提高,且对高维空间问题有一定的优势。 
  参考文献: 
  [1]KARABOGA D. An idea based on honey bee swarm for numerical optimization, TR06 [R]. Kayseri: Erciyes University, Faculty of Engineering, 2005. 
  [2]KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm [J]. Journal of Global Optimization, 2007, 39(3): 459-471.   [3]KARABOGA D, BASTURK B. Artificial Bee Colony (ABC) optimization algorithm for solving constrained optimization problems [C]// IFSA07: Proceedings of the 12th International Fuzzy Systems Association World Congress on Foundations of Fuzzy Logic and Soft Computing. Berlin: SpringerVerlag, 2007: 789-798. 
  [4]KARABOGA D, AKAY B. A comparative study of artificial bee colony algorithm [J]. Applied Mathematics and Computation, 2009, 214(12): 108-132. 
  [5]KARABOGA D, AKAY B. A survey: algorithms simulating bees warm intelligence [J]. Artificial Intelligence Review, 2009, 31(1/2/3/4): 61-85. 
  [6]KARABOGA D, BASTURK B. On the performance of Artificial Bee Colony (ABC) algorithm [J]. Applied Soft Computing, 2008, 8(1): 687-697. 
  [7]KARABOGA D, AKAY B, OZTURK C. Artificial Bee Colony (ABC) optimization algorithm for training feedforward neural network [C]// MDAI07: Proceedings of the 4th International Conference on Modeling Decisions for Artificial Intelligence. Berlin: SpringVerlag, 2007: 318-319. 
  [8]KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR filters [J]. Journal of the Franklin Institute, 2009, 346(4): 28-348. 
  [9]ZHANG C, OUYANG D, NING J. An artificial bee colony approach for clustering [J]. Expert Systems with Applications, 2010, 37(7): 4761-4767. 
  [10]KARABOGA D, OZTURK C. Fuzzy clustering with artificial bee colony algorithm [J]. Scientific Research and Essays, 2010, 5(14): 1899-1902. 
  [11]KARABOGA D, OZTURK C. A novel clustering approach: Artificial Bee Colony (ABC) algorithm [J]. Applied Soft Computing Journal, 2011, 11(1): 652-657. 
  [12]MEZURAMONTES E, VELEZKOEPPEL R E. Elitist artificial bee colony for constrained realparameter optimization [C]// CEC 2010: Proceedings of the 2010 IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press, 2010: 2068-2075. 
  [13]KARABOGA D, AKAY B. A modified Artificial Bee Colony (ABC) algorithm for constrained optimization problems [J]. Applied Soft Computing Journal, 2011, 11(3): 3021-3031. 
  [14]YEH W C, HSIEH T J. Solving reliability redundancy allocation problems using an artificial bee colony algorithm [J]. Computers and Operations Research, 2011, 38(11): 1465-1473. 
  [15]LI J Q, PAN Q K, XIE S X, et al. A hybrid artificial bee colony algorithm for flexible job shop scheduling problems [J]. International Journal of Computers, Communications and Control, 2011, 6(2): 286-296. 
  [16]SZETO W Y, WU Y, HO S C. An artificial bee colony algorithm for the capacitated vehicle routing problem [J]. European Journal of Operational Research, 2011, 215(1): 126-135.   [17]KASHAN M H, NAHAVANDI N, KASHAN A H. DisABC: a new artificial bee colony algorithm for binary optimization [J]. Applied Soft Computing, 2012, 12(1): 342-352. 
  [18]GAO W, LIU S. Improved artificial bee colony algorithm for global optimization [J]. Information Processing Letters, 2011, 111(17): 871-882. 
  [19]KANG F, LI J, MA Z. Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions [J]. Information Sciences, 2011, 181(16): 3508-3531. 
  [20]WU B, QIAN C, NI W, et al. Hybrid harmony search and artificial bee colony algorithm for global optimization problems [J]. Computers and Mathematics with Applications, 2012, 64(8): 2621-2634. 
  [21]ZHU G, KWONG S. Gbestguided artificial bee colony algorithm for numerical function optimization [J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173. 
  [22]BANHARNSAKUN A, ACHALAKUL T, SIRINAOVAKUL B. The bestsofar selection in artificial bee colony algorithm [J]. Applied Soft Computing Journal, 2011, 11(2): 2888-2901. 
  [23]GAO W F, LIU S Y. A modified artificial bee colony algorithm [J]. Computers and Operations Research, 2012, 39(3): 687-697. 
  [24]AKAY B, KARABOGA D. A modified artificial bee colony algorithm for realparameter optimization [J]. Information Sciences, 2012, 192(1): 120-142. 
  [25]LI G, NIU P, XIAO X. Development and investigation of efficient artificial bee colony algorithm for numerical function optimization [J]. Applied Soft Computing, 2012, 12(1): 320-332. 
  [26]XU Y F, FAN P, YUAN L. A simple and efficient artificial bee colony algorithm [J]. Mathematical Problems in Engineering, 2013, 2013: 1-9. 
  [27]SHARMA T K, PANT M, DEEP A. Modified foraging process of onlooker bees in artificial bee colony [C]// BICTA 2012: Proceedings of Seventh International Conference on BioInspired, Computing: Theories and Applications, Advances in Intelligent Systems and Computing. Berlin: SpringVerlag, 2013: 479-487. 
  [28]SEELEY T D. The wisdom of the hive the social physiology of honey bee colonies [M]. Cambridge: Harvard University Press, 1996. 
  [29]ZHU Q B, YANG Z J, MA W. A quickly convergent continuous ant colony optimization algorithm with scout ants [J]. Applied Mathematics and Computation, 2011, 218(5): 1805-1819. 
  [30]CHOI C, LEE J. Chaotic local search algorithm [J]. Artificial Life and Robotics, 1998, 2(1): 41-47.

特别说明:本站仅协助已授权的杂志社进行在线杂志订阅,非《南京邮电大学学报自然科学版》杂志官网,直投的朋友请联系杂志社。

版权所有 © 2009-2021《南京邮电大学学报自然科学版》编辑部  (权威发表网)   苏ICP备12048821号-1   --