人工鱼群算法的现状与改进分析

人工鱼群算法的现状与改进分析王闯，薛婷，孙林燕大连海事大学，辽宁大连(116026)E-mail:[e-mail]摘要：本文首先对人工鱼群算法目前的发展情况进行了简单的综述。然后，通过分析人工鱼群算法的优点和缺点，提出了四种改进思路-改进参数、改进鱼群行为、高阶行为模式、与其它优化算法相融合，并用已有的改进算法加以论证。进而为人工鱼群算法的改进研究提供了新的便利。关键词：人工鱼群算法，优化算法，算法改进1.引言优化命题的解决存在于许多领域，对于国民经济的发展也有着巨大的应用前景。随着优化对象在复杂化和规模化等方面的提高，基于严格机理模型的传统优化方法在实施方面变得越来越困难。人工鱼群算法(ArtificialFish-swarmAlgorithm，AFSA)是一种基于模拟鱼群行为的优化算法，是由李晓磊等[1]于2002年提出的一种新型的寻优算法。AFSA是一种新型的思路，从具体的实施算法到总体的设计理念，都不同于传统的设计和解决方法，但同时它又能与传统方法相融合。因此，AFSA自提出以来，得到了国内外学者的广泛关注，对算法的研究应用已经渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问题。AFSA己经成为交叉学科中一个非常活跃的前沿性研究问题。2.研究现状在基本AFSA中，主要是利用了鱼群的觅食、聚群和追尾行为，从构造单条鱼的底层行为做起，通过鱼群中各个体的局部寻优，达到全局昀优值在群体中突现出来的目的。通过研究发现，AFSA具有以下特点[1]：l)算法只需要比较目标函数值，对目标函数的性质要求不高；2)算法对初值的要求不高，初值随机产生或设定为固定值均可以；3)算法对参数设定的要求不高，有较大的容许范围；4)算法具备并行处理的能力，寻优速度较快；5)算法具备全局寻优的能力，能够快速跳出局部极值点。从目前对AFSA的研究来看，绝大部分集中在如何应用AFSA解决实际问题，对于算法本身的研究和优化，见到的还不多。通过深入研究和实践发现，AFSA虽然具有很多优良的特性，但它本身也还是存在一些问题，如随着人工鱼数目的增多，将会需求更多的存储空间，也会造成计算量的增长；对精确解的获取能力不够，只能得到系统的满意解域；当寻优的区域较大，或处于变化平坦的区域时，收敛到全局昀优解的速度变慢，搜索效率劣化；算法一般在优化初期具有较快的收敛性，而后期却往往收敛较慢。这些算法本身存在的问题，在一定程度上也影响了算法的实际应用。因此，针对以上缺点，研究如何对人工鱼群算法进行优化、改进，解决算法本身存在的问题，提高算法求解各类优化问题的适应性，提高算法的搜索效率，具有比实际应用研究更重要的意义。的改进思路进行分析和总结。3.改进思路3.1算法参数的改进前面我们也提到，人工鱼群算法中的参数比较多，其中有人工鱼群的个体数目N，拥挤度因子δ，视野和步长，前面两个参数通常可以采用数值实验的方法来确定它的大致范围．后两个参数直接影响人工鱼运行的轨迹，因此对算法的效果有着更直接的影响，对于这两个参数的选择研究得更多一些。3.1.1基于视野的改进由于视野对算法中各行为都有较大的影响，因此，它的变化对收敛性能的影响也是比较复杂的。当视野范围较小时，人工鱼群的觅食行为和随机游动比较突出；视野范围较大时，人工鱼的追尾行为和聚群行为将变得较突出。总体来看，视野越大，越容易使人工鱼发现全局极值并收敛。因此对人工鱼的视野进行适当的改进，是提高人工鱼群算法优化性能的一种方法。YangYu等通过对人工鱼群算法的大量研究，发现鱼群的觅食行为在解决离散型优化问题时有很重要的作用。在鱼群觅食的过程中，其视野范围是固定不变的。当人工鱼逐渐逼近昀优解时，Xi仅仅有一个或两个变量不同于昀优解，因此人工鱼在昀优解附近以原始的视野进行觅食是盲目的。在这种情况下，try-number的试验次数会很大，这将增加算法的计算复杂性。另外，收敛速度的快慢和昀后寻优结果的质量都依靠视野值。如果视野范围太大，收敛速度将很慢；另一方面，如果视野范围太小，人工鱼群算法可能导致陷入局部昀优解。为了克服这些缺点，YangYu[2]等提出了如下的改进策略：在人工鱼群算法的初始阶段，每条人工鱼以一个大的视野寻找解，这样能扩大寻优的范围。随着算法的运行，鱼群的视野范围将适当的减小以加快收敛的速度。改变视野的变化函数定义为：1kkVDVDα+=，其中α是衰减因子，且(0,1)α∈。这里必须解释的一点是鱼群视野在聚群行为和追尾行为中仍然保持不变，仅在觅食行为中变换。3.1.2基于步长的改进在人工鱼群算法中，人工鱼个体的三个行为：觅食、聚群和追尾都依赖于一定的可视域和步长范围。为了进一步提高人工鱼群算法的寻优能力，一方面可以通过改进视野范围来施行；另一方面，也可以通过改进步长范围对原有算法进行了改进。Cui-ruWang等[3]提出了一种去除步长限制的人工鱼群算法，其基本思路就是将人工鱼群算法的实际步长改为参数定义域内的随机数，以保证更好的全局搜索能力。王西邓等[4]提出了两种对步长进行改进的鱼群算法，一种是移动步长缩减策略，另一种是移动步长动态调整策略。移动步长缩减策略就是通过缩减移动步长，限制普通种群人工鱼的随机跳动，对全局极值域进行更加精细的搜索，昀终获得全局极值。移动步长动态调整策略就是通过移动步长的动态调整，限制人工鱼的随机跳动，对全局极值域进行更加精细的搜索，昀终获得全局极值。3.1.3基于视野和步长的改进在鱼群模式所讨论的视野概念中，由于视点的选择是随机的，移动的步长也是随机的，这样，虽然能在一定程度上扩大寻优的范围，尽可能保证寻优的全局性，但是，会使得算法的收敛速度减慢，有大量的计算时间浪费在随机的移动之中。李晓磊等[5]又提出了一种取决于人工鱼当前所在的状态和视野中视点感知的状态的自适应步长的改进策略：对于人工鱼当前状态12(,,,)nXxxx=和所探索的下一个状态12(,,,)vvvvnXxxx=，其表示如下：(),()viixxVisualRandiRandn=+⋅=(3.1)1()vvnextvXXYXStepXXY−=⋅−⋅−求解极小问题或1()vnextvvXXYXStepXXY−=⋅−⋅−求解极大问题(3.2)式中，Rand函数为产生0到1之间的随机数，Step为移动步长，Yv为Xv状态的目标函数值，Y为X状态的目标函数值。即，本次移动步长的大小取决于当前所在的状态和视野中视点感知的状态。3.1.4基于步长和拥挤度因子的改进在使用固定步长条件下，步长越大越有利于前期收敛，但后期容易出现震荡现象，不利于快速收敛。小步长虽然有利于局部收敛，但寻找全局昀优较慢。我们可以考虑变尺度的步长方式，来解决上述问题。对于拥挤度因子，在求极大值问题中，01δ，它越大允许的拥挤程度越小，越有利于全局收敛，但精度相对较差；在求极小值问题中，1δ，它越小允许的拥挤程度越小，越有利于全局收敛，但精度相对较差。对于上述问题，我们同样可以考虑运用变尺度的方式来提高精度。JianmeiXiao等[6]提出了一种对步长和拥挤度因子进行适时的自行调整，以达到提高收敛精度的目的的自适应人工鱼群算法。在该算法中，运用昀优适应值变化率K和变化方差σ作为是否进行参数变化的衡量标准。其定义分别如下：()()()ftftnKftn−−=−；(3.3)其中f(t)表示t代时的昀优适应值；f(t-n)表示t-n代时的昀优适应值；K表示进化n代内的昀优适应值的相对变化率。((),(),(2))Dftftnftnσ=−−；(3.4)其中f(t)表示t代时的次优适应值；f(t-n)表示t-n代时的次优适应值；f(t-2n)表示t-2n代时的次优适应值；()D•表示求这些次优适应值的方差。根据以上两个判别准则，对步长和拥挤度因子作调整，表达式如下：(),(),,,stepfstepgfgKstepstepggKθσφθσφ==≤≤⎧⎨==⎩(3.5)其中f(Step)表示按一定规则对步长进行调整；f(g)表示对拥挤度因子作相应调整；θ，φ表示评价系数，根据具体问题给出不同的值，用来控制变步长的速度和迭代的进程。引入新参数从以上所述的算法参数的改进方法中，可以看出，通过对参数的改进进而可以有效地提高人工鱼群算法的求解精度、寻优成功率、收敛速度等。同理，引入新参数也可以有效的对鱼群算法进行改进。XiaojuanShan等[7]提出了一种引入一个新参数的人工鱼群算法，即觅食步长参数prey_step。引入觅食步长参数的目的，是在保留基本人工鱼群算法原有移动步长随机性的同时，根据觅食步长调整其移动的距离跨度。由于采用了移动和觅食两种步长，加快了算法的寻优速度，增强了人工鱼在离散解空间中邻域搜索的灵活性和有效性，也可降低陷入局部机制的可能性。但是，实际上这些研究也仅仅局限于部分问题的应用，无法推广到所有问题域。3.2基于鱼群行为的改进3.2.1基于基本鱼群行为的改进人工鱼群算法是模仿鱼类行为提出的一种基于动物自治体的优化方法，是一种昀优仿生优化算法，它主要是通过模拟鱼类的觅食、聚群、追尾等行为在搜索域中进行寻优，所以如果要对该算法进行改进，也可以从算法中的觅食行为、聚群行为、追尾行为着手，通过对这几方面进行改进，进而对算法进行改进。YangYu等[2]在采用自适应鱼群视野和昀优个体保留策略的基础上，通过将聚群行为和追尾行为分别与觅食行为相结合的方法，使算法的计算复杂度进一步降低。实验表明表明改进的人工鱼群算法具有寻优成功率高、收敛速度快等特点。范玉军等[8]通过对人工鱼群算法的研究，给出了改进的人工鱼群算法。采用昀优个体保留策略对觅食行为进行改进，防止群体中昀优个体的退化；给出加速个体局部搜索方法，改进算法中的聚群行为和追尾行为，使全局昀优值更快地突现出来；根据双射的定义和性质，在不影响昀终寻优结果的情况下对问题的搜索域进行“缩小”，从而加速了全局搜索。仿真结果表明改进的人工鱼群算法具有求解精度高、寻优成功率高、收敛速度快、算法稳定等优点。黄光球等[9]通过大量研究，昀后使用自适应δ变异算子、双算术交叉算子、峰跳操作算子等多种算子改进人工鱼的各种行为，得到了一种改进的人工鱼群算法。应用结果表明，该算法计算速度、可靠性和稳定性大幅度提高。3.2.2基于新增鱼群行为的改进从前一章所述的基本人工鱼群算法中，可以看出，当寻优的域较大或处于变化平坦的区域时，一部分人工鱼将处于无目的的随机移动中，这影响了寻优的效率，类似这种问题，除了可以对鱼群行为进行改进来解决，还可以通过引进新的鱼群行为来改进算法。李晓磊等[5]通过引入生存机制和竞争机制对人工鱼群算法加以改善。生存机制的描述如下：1::AF_move;1::AF_inithEhhTλ≥⎧=⎨⎩(3.6)式中h为生存指数；E为人工鱼当前所处位置的食物能量值；T为人工鱼的生存周期；K为消耗因子，即单位时间内消耗的能量值。即当人工鱼所处位置的食物能量足以维持其生命时，人工鱼将按照正常的行为寻优，否则，当此处的能量低于其生命的维持所需时，通常此时处于局部极值点或非极值点附近，寻优通常会没有结果，所以，强制该人工鱼初始化，例如，可以随机产生该人工鱼的位置，使其跳出该区域，这样就相当于利用相同的存储空间增加了寻优人工鱼的个数，从而提高了算法的效率。竞争机制就是实时地调整人工鱼的生存周期，其描述如下：maxETλ=∈(3.7)式中Emax为当前所有的人工鱼中所处位置的食物能量的昀大值；∈为比例系数。随着寻优的逐步进展，人工鱼的生存周期将被其中昀强的竞争者所提升，从而使得那些处于非全局极值点附近的人工鱼能有机会展开更广范围的搜索。JianweiMa等[3]提出了一种加入跳跃行为的人