基于改进搜索策略的狼群算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于改进搜索策略的狼群算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对狼群算法（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 constantly. 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 引言
Liu等[1]仿生自然界狼群捕猎行为提出了狼群算法（Wolf Colony Algorithm，WCA），该算法抽象出狼群搜索行为、围攻行为与狼群更新行为，仿真实验证明了WCA算法与粒子群优化（Particle Swarm Optimization，PSO）算法、遗传算法（Genetic Algorithm，GA）相比具有更高的求解精度、更快的收敛速度；并在此基础上，将WCA算法应用于机器人路径规划等问题。吴虎胜等[2]在分析狼群的协作捕猎活动特点的基础上提出与WCA算法搜索策略不同的狼群算法 （Wolf Pack Algorithm，WPA），该算法分析狼群捕食行为以及猎物分配的方式，抽象出游走、召唤、围攻3种行为，以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制，并基于马尔可夫链理论证明了算法以概率1收敛问题的全局最优解；最后通过实验说明了WPA算法与经典的鱼群算法（FishSwarm Algorithm，FSA）、PSO算法、GA算法相比具有较强的鲁棒性和全局寻优能力，尤其在处理多峰、高维复杂函数中效果明显。等[3]引入领导者策略，提出基于领导者策略的狼群算法（Wolf Colony search Algorithm base on the strategy of the Leader，LWCA），该算法通过竞争选出头狼，引领狼群不断进化。文献[4]通过定义运动算子，对人工狼位置、步长和智能行为进行了二进制编码，提出一种二进制狼群算法（Binary Wolf Pack Algorithm，BWPA），成功解决了01背包问题，具有较好的求解稳定性、收敛性和全局搜索能力，尤其在求解大规模01背包问题优势明显，拓展了狼群算法的应用。针对狼群算法（WPA）存在的收敛速度慢、易陷入局部最优、人工狼交互性不理想等不足，故本文提出一种改进搜索策略的狼群算法（Modified Wolf Pack Algorithm，MWPA）。
本文在基本WPA算法上，对狼群寻优策略进行了优化，对游走、召唤阶段提出了交互策略，增加狼群间信息的交流，促使狼群对搜索空间充分了解，使得全局探索更加精细，提高了算法的探索能力；对围攻行为提出了自适应的围攻策略，使得围攻行为随着算法的不断进化，攻击范围逐步减小，开采能力增强，收敛速度提高。
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 交互召唤行为
在召唤行为中，猛狼要不断地奔袭，直至dis
在猛狼奔袭过程中，猛狼间依然缺少必要的信息交互，不能及时了解“同伴”信息，限制了猛狼的搜索能力。文献[9]提出导向蜂群（Directed Bee Colony，DBC）算法，是依据蜜蜂寻找最优巢穴的快速与准确性提出的一种算法，该算法运用蜂群之间的交流快速找到最优解。群体算法中，群体间的交流是算法重要的一环，故本文在猛狼执行每一轮式（2）搜索时再进行一次式（6）的猛狼搜索过程，选取气味最浓的猎物且大于当前位置气味浓度Yi的方向前进，更新猛狼位置Xi，选取气味浓度Yi最大的狼作为头狼。
2.3 自适应围攻行为
围攻行为要求猛狼具有较强的局部寻优能力。猛狼按式（4）进行搜索，λ在[-1，1]内随机取值，具有随机性与不确定性，随着算法的不断进化，当前最优解越趋近全局最优解，猛狼开采能力应越强，使算法快速收敛全局最优解，式（4）不能很好地适应猛狼的局部寻优要求。文献[10]在ABC算法的基础上，加入PSO算法的搜索方式，指导蜂群进化；文献[11]对ABC算法的邻域搜索范围进行动态调整，使得算法具有调节作用，提高收敛速度；文献[12]在ABC的邻域搜索公式中利用目标函数自适应调整步长，并根据迭代次数非线性
减小侦查蜂的搜索范围，提高算法开采能力；文献[13]在ABC算法中加入混沌局部搜索算子，且随着算法的进化具备调节作用。由以上可知，在算法中加入调节机制是一种较好的改进方向，为了使围攻行为具备自适应的调节能力，本文将随机步长λ改为随着算法迭代次数t增加线性变化的自适应步长公式，如式（7）：
其中：ε为因子，取为（0，1）内随机数；υ，先用υ代替，问作者可否有其他符号替代，邮件问过作者，可用其他字母替代为{-1，1}内的随机整数。ε取值在（0，1）内的目的是为了保证在算法迭代后期避免υ（1-εt/tmax）趋近于零，导致寻优无变化；υ的作用是保证搜索范围不局限于Gkd-xkid的方向，能够更全面地搜索xid附近区域。若实施围攻行为后人工狼感知到的猎物气味浓度大于其原位置状态所感知的猎物气味浓度，更新人工狼的位置；否则，人工狼位置不变。
2.4 MWPA算法具体步骤
1）初始人工狼位置Xi及其数目N，迭代次数kmax，探狼比例因子α，游走次数Tmax，更新比例因子β。
2）选取最优人工狼为头狼，除头狼外最佳的S_num匹人工狼为探狼，执行交互游走行为，直到某匹探狼i侦察到的
猎物气味浓度Yi大于头狼所感知的猎物气味浓度Ylead或达到最大游走次数Tmax。
3）猛狼根据交互召唤行为向猎物奔袭，若途中感知的猎物气味浓度Yi>Ylead则Ylead=Yi，取代头狼发起召唤行为。
4）按式（7）对猛狼位置进行更新，执行围攻行为。
5）按“胜者为王”的头狼产生规则对头狼位置进行更新；再按照“强者生存”的狼群更新机制进行群体更新。
6）判断是否达到优化精度要求或最大迭代次数kmax，若达到则输出头狼的位置，即所求问题的最优解；否则转2）。
3 仿真实验
3.1 参数设置与测试函数
为了充分测试算法的性能和特点，与文献[3]的LWCA算法进行实验对比。实验设置最大迭代次数为1000，Tmax=15，初始狼群规模为200，LWPA探狼比例因子α=4，更新比例因子β=6，s=200；LWCA设置参见文献[3]。实验环境为Windows 7系统，4GB内存，Intel Core i3 M330。算法实现以Matlab R2012b用M文件编写。测试函数如表1；算法重复运行20次，实验结果如表2。
3.2 实验分析
用表1中的6个函数对2种算法进行测试，从平均值、标准差、最优值、最差值和平均耗时5个方面进行评估。Sphere、Rosenbrock函数为高维单峰函数，只有全局最优值，可以测试算法开采能力的强弱；Schaffer、Griewank、Rastrigin、Ackley函数为多峰函数，具有多个局部极值点，算法很容易陷入局部极值，可以测试算法探索能力的强弱。
首先，平均值和最优值可体现算法的收敛精度和寻优能力，由表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是一种有效求解函数优化问题的群体智能算法。狼群算法是一种较新的群体智能算法，如何将狼群算法与其他智能算法融合起来更高效地求解问题将是下一步的研究工作。
参考文献：
文献已查
[1]LIU C，YAN X，LIU C，et al. The wolf colony algorithm and its application [J]. Chinese Journal of Electronics，2011，20（2）： 212-216.
[2]WU H， ZHANG F， WU L. New swarm intelligence algorithm-wolf pack algorithm [J]. Systems Engineering and Electronics， 2013， 35（11）：
2430-2438.（吴虎胜，张凤鸣，吴庐山. 一种新的群体智能算法――狼群算法[J]. 系统工程与电子技术，2013，35（11）：2430-2438.）
[3]ZHOU Q，ZHOU Y. Wolf colony search algorithm based on leader strategy [J].Application Research of Computers，2013，30（9）：2629-2632.（，周永权. 一种基于领导者策略的狼群搜索算法[J]. 计算机应用研究，2013，30（9）：2629-2632.）
[4]WU H， ZHANG F， ZHAN R， et al. A binary wolf pack algorithm for solving 01 knapsack problem [J]. Systems Engineering and Electronics， 2014， 36（8）： 1660-1667.（吴虎胜，张凤鸣，战仁军，等. 求解01背包问题的二进制狼群算法[J].系统工程与电子技术，2014，36（8）：1660-1667.）
[5]WANG B. Improved artificial bee colony algorithm based on local best solution [J]. Application Research of Computers， 2014， 31（4）： 1023-1026.（王冰. 基于局部最优解的改进人工蜂群算法[J]. 计算机应用研究，2014，31（4）：1023-1026.）
[6]KARABOGA D， GORKEMLI B. A quick Artificial Bee Colony （qABC） algorithm and its performance on optimization problems [J]. Applied Sort Computing， 2014， 23（10）： 227-238.
[7]TSAI HC. Integrating the artificial bee colony and bees algorithm to face constrained optimization problems [J]. Information Sciences， 2014， 258（2）： 80-93.
[8]AKPINAR S，BAYKASOGLU A. Multiple colony bees algorithm for continuous spaces [J]. Applied Soft Computing，2014，24（网上查到的无期，核对是否有误9）：829-841。
[9]KUMAR R. Directed bee colony optimization algorithm [J]. Swarm and Evolutionary Computation， 2014， 17（网上查到的无期，请核实期数是否正确3）： 60-73.
[10]IMANIAN N， SHIRI M E， MORADI P. Velocity based artificial bee colony algorithm for high dimensional continuous optimization problems [J]. Engineering Applications of Artificial Intelligence， 2014， 36（核实期数11）： 148-163.
[11]CAO Y， CAI Z， SHAO Y. Improved artificial bee colony clustering algorithm based on Kmeans [J]. Journal of Computer Applications， 2014， 34（1）： 204-207， 217.（曹永春，蔡正琦，邵亚斌. 基于Kmeans的改进人工蜂群聚类算法[J]. 计算机应用，2014，34（1）：204-207，217.）
[12]ZHANG Y， TIAN X， CAO Y. Artificial bee colony algorithm with modified search strategy [J]. Journal of Computer Applications， 2012， 32（12）： 3326-3330.（张银雪，田学民，曹玉苹. 改进搜索策略的人工蜂群算法[J]. 计算机应用，2012，32（12）：3326-3330.）
[13]WANG X， LI Z， XU G， et al. Artificial bee colony algorithm based on chaos local search operator [J]. Journal of Computer Applications， 2012， 32（4）： 1033-1036， 1040.（王翔，李志勇，许国艺，等. 基于混沌局部搜索算子的人工蜂群算法[J]. 计算机应用，2012，32（4）：1033-1036，1040.）