基于改进搜索策略的狼群算法
摘要:针对狼群算法(WPA)存在的收敛速度慢、易陷入局部最优、人工狼交互性不理想等不足,提出一种基于改进搜索策略的狼群(MWPA)算法。对游走行为以及召唤行为引入交互策略,促使人工狼之间进行信息交流,提升狼群对全局信息的掌握,ϟ增强狼群的探索能力;对围攻行为提出自适应围攻策略,使算法具有调节作用,随着算法的不断进化,狼群围攻范围不断减小,算法开采能力不断增强,从而提高算法收敛速度。通过优化问题中6个典型复杂函数的仿真实验表明,与基于领导者策略的狼群搜索(LWCA)算法相比,改进搜索策略的狼群算法求解精度更高、收敛速度更快,更加适合函数优化问题的求解。
关键词:狼群算法;交互策略;函数优化;自适应;搜索策略
中图分类号: TP301.6 文献标志码:A
Abstract:Aiming at the shortcomings of Wolf Pack Algorithm (WPA), such as slow convergence, being easy to fall into local optimum and unsatisfactory artificial wolf interactivity, a wolf pack algorithm based on modified search strategy was proposed, which named Modified Wolf Pack Algorithm (MWPA). In order to promote the exchange of information between the artificial wolves, improve the wolves grasp of the global information and enhance the exploring ability of wolves, the interactive strategy was introduced into scouting behaviors and summoning behaviors. An adaptive beleaguering strategy was proposed for beleaguering behaviors, which made the algorithm have a regulatory role. With the constant evolution of algorithm, the beleaguered range of wolves decreased constantly and the exploitation ability of algorithm strengthened consta Üntly. Thus the convergence rate of algorithm was enhanced. The simulation results of six typical complex functions of optimization problems show that compared to the Wolf Colony search Algorithm based on the strategy of the Leader (LWCA), the proposed method obtains higher solving accuracy, faster convergence speed and is especially suitable for function optimization problems.
英文关键词
Key words:Wolf Pack Algorithm (WPA); interactive strategy; function optimization; adaptive; search strategy
0 引言
1 基本狼群算法
基本狼群系统分为头狼、探狼和猛狼。头狼是狼群的首领;探狼负责搜寻猎物;猛狼负责围攻猎物。狼群的整个捕猎活动抽象为3种智能行为(游走行为、召唤行为、围攻行为)以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制。
1) 头狼产生规则:初始搜索空间中,具有最优目标函数值的人工狼为头狼,记为Ylead。头狼不执行3种智能行为而直接进入下次迭代,直到它被其他更强的狼替代。
5)“强者生存”的狼群更新机制:猎物按照“由ฅ强到弱”的原则进行分配,即在算法中去除目标函数值最差的R匹狼,同时随机产生R匹狼。这里R取[n/(2×β),n/β]内的随机整数,β为群体更新比例因子。
2 改进搜索策略的狼群算法
2.1 交互游走行为
WPA算法中,探狼向h个方向进行探索,h越大,探索越精细,寻优精度越高,但算法寻优速度将会下降,易陷入局部寻优;h过小,探狼搜索过于粗糙,造成算法寻优不精确,甚至出现不收敛的情况。本文分析,出现上述情况的原因在于探狼间缺少必要的信息交互,探狼根据式(1)对探索空间进行搜索,不能及时了解“同伴”的信息,影响探狼的全局搜索能力。文献[5]在改进人工蜂群(Improved Artificial Bee Colony,IABC)算法中引入当前局部最优解,增强了算法的开采能力;文献[6]引入邻域半径r来更好地确定观察蜂的邻居,使得观察蜂能更好地掌握邻居的信息;文献[7]融合人工蜂群(Artificial Bee Colony,ABC)算法与蜂群(Bee Colony,BC)算法,增强了混合算法的探索与开采能力;文献[8]采用一种积极反馈机制促使不同蜂巢的蜜蜂进行信息交流,增强了蜂群的交互性。为了增加探狼间的交互性及提高寻优能力,本文采用文献[5]提出的搜索方式,如式(6):
其中:φi,d为[0,1]的随机数,ฒi,d为[-1,1]的随机数,k≠i≠j。式(6)前半段增强了狼群的局部寻优能力,后半段增强了狼群的全局搜索能力,很好地平衡了狼群的全局搜索能力与局部寻优能力,既体现了狼群头狼的领导能力,又保持了狼群间信息的密切交流。
游走行为中,探狼i根据式(1)进行一次游走之后,随机选择探狼k、j。根据式(6)得到新的猎物Vi,随后探狼i感知搜索到的食物源的气味浓度Y′i[h+1](一次游走共探寻到h个猎物源和一次交互探寻到的猎物源Vi),选取气味最浓的且大于当前位置气味浓度Yi的方向前进一步,更新探狼位置Xi,重复以上游走行为直到某匹探狼j感知到的猎物气味浓度Y′j>Ylead,则探狼j成为新的头狼并发起召唤行为,否则,探狼继续下一轮游走直至游走次数T达到最大游走次数Tmax。
2.2 交互召唤行为
在召唤行为中,猛狼要不断地奔袭,直至disYlead则Ylead=Yi,取代头狼发起召唤行为。
4)按式(7)对猛狼位置进行更新,执行围攻行为。
5)按“胜者为王”的头狼产生规则对头狼位置进行更新;再按照“强者生存”的狼群更新机制进行群体更新。
6)判断是否达到优化精度要求或最大迭代次数kmax,若达到则输出头狼的位置,即所求问题的最优解;否则转2)。
3 仿真实验
3.1 参数设置与测试函数
3.2 实验分析
首先,平均值和最优值可体现算法的收敛精度和寻优能力,由表2可知,无论是平均值还是最优值,MWPA算法均要优于LWCA算法。对Sphere单峰函数寻优接近理论最优值,精度达到10-16,说明MWPA算法具有良好的开采能力,这得益于自适应围攻行为,随着迭代次数的增加,狼群围攻范围逐渐减小,搜索越精细,算法开采能力越强,收敛速度越快。MWPA对Schaffer、Griewank、Ackley等多峰函数优化效果较好,Schaffer、Griewank函数已寻到理论最优解,Ackley函数精度达到10-11,说明MWPA具有良好的探索能力,这得益于交互游走行为与交互召唤行为,两种改进行为使得狼群能够更好地掌握全局信息,降低算法陷入局部极值的概率,提升了算法探索能力。
其次,标准差与最差值则体现了算法的鲁棒性和对抗局部极值的能力。由表2标准差可以看出,除Rosenbrock函数外,MWPA标准差始终处于1E-03级别以下,Sphere等函数达到1E-17级别,同时,MWPA的最差值几乎与最优值处于同一级别,可见MWPA在寻优运算中能保持良好的鲁棒性。
最后,平均耗时可以体现算法的复杂程度。由表2平均耗时可以看出,MWPA与LWCA处于同一级别,说明MWPA在提升性能的基础上并没有明显增加运行时间,是一种高效的改进狼群算法。
为了更直观地说明MWPA的优越性,给出上述6个标准函数图像进行分析,如图1。由图1可以看出,MWPA无论在求解精度还是收敛速度均要优于LWCA算法,再次验证了MWPA的优势。
4 结语
本文在基本WPA算法上,针对搜索策略进行了改进。对游走行为以及召唤行为,提出了交互策略,使得狼群交互性强,全局探索更加精ฎ细,提高了算法的探索能力;对围攻行为,提出了自适应的围攻策略,使得围攻行为随着算法的不断进化,攻击范围逐步减小,开采能力越强,收敛速度加快。实验验证了MWPA带来的性能提升,表明MWPA是一种有效求解函数优化问题的群体智能算法。狼群算法是一种较新的群体智能算法,如何将狼群算法与其他智能算法融合起来更高效地求解问题将是下一步的研究工作。
参考文献:
文献已查
[2]WU H, ZHANG F, WU L. New swarm intelligence algorithm-wolf pack algorithm [J]. Systems Engineering and Electronics, 2013, 35(11):
[9]KUMAR R. Directed bee colony optimization algorithm [J]. Swarm and Evolutionary Computation, 2014, 17(网上查到的无期,请核实期数是否正确3): 60-73.