论文研究-人工鱼群算法的现状与改进分析 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.39M 资料格式：pdf 举报版权申诉

weixin_39840924-11558064-4744302543350404553.pdf-第1页.png

第1页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第2页.png

第2页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第3页.png

第3页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第4页.png

第4页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第5页.png

第5页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第6页.png

第6页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第7页.png

第7页 / 共8页

weixin_39840924-11558064-4744302543350404553.pdf-第8页.png

第8页 / 共8页

文本预览

人工鱼群算法的现状与改进分析 http://www.paper.edu.cn 王闯，薛婷，孙林燕大连海事大学，辽宁大连 (116026) E-mail: wch-7408549@163.com 摘要：本文首先对人工鱼群算法目前的发展情况进行了简单的综述。然后，通过分析人工鱼群算法的优点和缺点，提出了四种改进思路-改进参数、改进鱼群行为、高阶行为模式、与其它优化算法相融合，并用已有的改进算法加以论证。进而为人工鱼群算法的改进研究提供了新的便利。关键词：人工鱼群算法，优化算法，算法改进 1. 引言优化命题的解决存在于许多领域，对于国民经济的发展也有着巨大的应用前景。随着优化对象在复杂化和规模化等方面的提高，基于严格机理模型的传统优化方法在实施方面变得越来越困难。人工鱼群算法(Artificial Fish-swarm Algorithm，AFSA)是一种基于模拟鱼群行为的优化算法，是由李晓磊等[1]于 2002 年提出的一种新型的寻优算法。AFSA 是一种新型的思路，从具体的实施算法到总体的设计理念，都不同于传统的设计和解决方法，但同时它又能与传统方法相融合。因此，AFSA 自提出以来，得到了国内外学者的广泛关注，对算法的研究应用已经渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问题。AFSA 己经成为交叉学科中一个非常活跃的前沿性研究问题。 2. 研究现状在基本 AFSA 中，主要是利用了鱼群的觅食、聚群和追尾行为，从构造单条鱼的底层行为做起，通过鱼群中各个体的局部寻优，达到全局最优值在群体中突现出来的目的。通过研究发现，AFSA 具有以下特点[1]： l)算法只需要比较目标函数值，对目标函数的性质要求不高； 2)算法对初值的要求不高，初值随机产生或设定为固定值均可以； 3)算法对参数设定的要求不高，有较大的容许范围； 4)算法具备并行处理的能力，寻优速度较快； 5)算法具备全局寻优的能力，能够快速跳出局部极值点。从目前对 AFSA 的研究来看，绝大部分集中在如何应用 AFSA 解决实际问题，对于算法本身的研究和优化，见到的还不多。通过深入研究和实践发现，AFSA 虽然具有很多优良的特性，但它本身也还是存在一些问题，如随着人工鱼数目的增多，将会需求更多的存储空间，也会造成计算量的增长；对精确解的获取能力不够，只能得到系统的满意解域；当寻优的区域较大，或处于变化平坦的区域时，收敛到全局最优解的速度变慢，搜索效率劣化；算法一般在优化初期具有较快的收敛性，而后期却往往收敛较慢。这些算法本身存在的问题，在一定程度上也影响了算法的实际应用。因此，针对以上缺点，研究如何对人工鱼群算法进行优化、改进，解决算法本身存在的问题，提高算法求解各类优化问题的适应性，提高算法的搜索效率，具有比实际应用研究更重要的意义。 - 1 -

下面我们就已有的对 AFSA 的改进思路进行分析和总结。 http://www.paper.edu.cn 3. 改进思路 3.1 算法参数的改进前面我们也提到，人工鱼群算法中的参数比较多，其中有人工鱼群的个体数目 N，拥挤度因子 δ，视野和步长，前面两个参数通常可以采用数值实验的方法来确定它的大致范围．后两个参数直接影响人工鱼运行的轨迹，因此对算法的效果有着更直接的影响，对于这两个参数的选择研究得更多一些。 3.1.1 基于视野的改进由于视野对算法中各行为都有较大的影响，因此，它的变化对收敛性能的影响也是比较复杂的。当视野范围较小时，人工鱼群的觅食行为和随机游动比较突出；视野范围较大时，人工鱼的追尾行为和聚群行为将变得较突出。总体来看，视野越大，越容易使人工鱼发现全局极值并收敛。因此对人工鱼的视野进行适当的改进，是提高人工鱼群算法优化性能的一种方法。 Yang Yu 等通过对人工鱼群算法的大量研究，发现鱼群的觅食行为在解决离散型优化问题时有很重要的作用。在鱼群觅食的过程中，其视野范围是固定不变的。当人工鱼逐渐逼近最优解时，Xi 仅仅有一个或两个变量不同于最优解，因此人工鱼在最优解附近以原始的视野进行觅食是盲目的。在这种情况下，try-number 的试验次数会很大，这将增加算法的计算复杂性。另外，收敛速度的快慢和最后寻优结果的质量都依靠视野值。如果视野范围太大，收敛速度将很慢；另一方面，如果视野范围太小，人工鱼群算法可能导致陷入局部最优解。为了克服这些缺点，Yang Yu[2]等提出了如下的改进策略：在人工鱼群算法的初始阶段，每条人工鱼以一个大的视野寻找解，这样能扩大寻优的范围。随着算法的运行，鱼群的视野范围将适当的减小以加快收敛的速度。改变视野的变化函数定义为： VD VDα+ = 1k k ，其中α是衰减因子，且 (0,1) α∈ 。这里必须解释的一点是鱼群视野在聚群行为和追尾行为中仍然保持不变，仅在觅食行为中变换。 3.1.2 基于步长的改进在人工鱼群算法中，人工鱼个体的三个行为：觅食、聚群和追尾都依赖于一定的可视域和步长范围。为了进一步提高人工鱼群算法的寻优能力，一方面可以通过改进视野范围来施行；另一方面，也可以通过改进步长范围对原有算法进行了改进。 Cui-ru Wang 等[3]提出了一种去除步长限制的人工鱼群算法，其基本思路就是将人工鱼群算法的实际步长改为参数定义域内的随机数，以保证更好的全局搜索能力。王西邓等[4]提出了两种对步长进行改进的鱼群算法，一种是移动步长缩减策略，另一种是移动步长动态调整策略。移动步长缩减策略就是通过缩减移动步长，限制普通种群人工鱼的随机跳动，对全局极值域进行更加精细的搜索，最终获得全局极值。移动步长动态调整策略就是通过移动步长的动态调整，限制人工鱼的随机跳动，对全局极值域进行更加精细的搜索，最终获得全局极值。 3.1.3 基于视野和步长的改进在鱼群模式所讨论的视野概念中，由于视点的选择是随机的，移动的步长也是随机的， - 2 -

这样，虽然能在一定程度上扩大寻优的范围，尽可能保证寻优的全局性，但是，会使得算法的收敛速度减慢，有大量的计算时间浪费在随机的移动之中。李晓磊等[5]又提出了一种取决于人工鱼当前所在的状态和视野中视点感知的状态的自 http://www.paper.edu.cn 适应步长的改进策略：对于人工鱼当前状态 X = ( x x , 1 2 , 和所探索的下一个状态 , x )n X v = ( x x , v v 1 2 , ， x v n ) , = x v i 其表示如下： + X X x Visual Rand i Y v Y 1 ⋅ − X X − − X next = ⋅ v v (), i Rand n ( ) = (3.1) ⋅ Step ( 求解极小问题或 ) X next = X X v v − − X X 1 ⋅ − Y Y v ⋅ Step ( 求解极大问题 (3.2) ) 式中，Rand 函数为产生 0 到 1 之间的随机数，Step 为移动步长，Yv 为 Xv 状态的目标函数值， Y 为 X 状态的目标函数值。即，本次移动步长的大小取决于当前所在的状态和视野中视点感知的状态。 3.1.4 基于步长和拥挤度因子的改进在使用固定步长条件下，步长越大越有利于前期收敛，但后期容易出现震荡现象，不利于快速收敛。小步长虽然有利于局部收敛，但寻找全局最优较慢。我们可以考虑变尺度的步长方式，来解决上述问题。对于拥挤度因子，在求极大值问题中，0 1δ< < ，它越大允许的拥挤程度越小，越有利于全局收敛，但精度相对较差；在求极小值问题中， 1δ> ，它越小允许的拥挤程度越小，越有利于全局收敛，但精度相对较差。对于上述问题，我们同样可以考虑运用变尺度的方式来提高精度。 Jianmei Xiao等[6]提出了一种对步长和拥挤度因子进行适时的自行调整，以达到提高收敛精度的目的的自适应人工鱼群算法。在该算法中，运用最优适应值变化率K和变化方差σ 作为是否进行参数变化的衡量标准。其定义分别如下： K = f t ( ) f f t n ( − − t n ) ( − ) ； (3.3) 其中f(t)表示t代时的最优适应值；f(t-n)表示t-n代时的最优适应值；K表示进化n代内的最优适应值的相对变化率。 t n f ( ), − D f ( t ( ), f σ= 其中f(t)表示t代时的次优适应值；f(t-n)表示t-n代时的次优适应值；f(t-2n)表示t-2n代时； (3.4) − ( t n 2 )) 的次优适应值； ( )D • 表示求这些次优适应值的方差。根据以上两个判别准则，对步长和拥挤度因子作调整，表达式如下： ⎧ ⎨ ⎩ 其中f(Step)表示按一定规则对步长进行调整；f(g)表示对拥挤度因子作相应调整；θ，φ (3.5) , θσ φ ≤ , θσ φ > f step g ), ( g step g , = step step f g ( ) K K ≤ > = = = 表示评价系数，根据具体问题给出不同的值，用来控制变步长的速度和迭代的进程。 - 3 -

http://www.paper.edu.cn 3.1.5 引入新参数从以上所述的算法参数的改进方法中，可以看出，通过对参数的改进进而可以有效地提高人工鱼群算法的求解精度、寻优成功率、收敛速度等。同理，引入新参数也可以有效的对鱼群算法进行改进。 Xiaojuan Shan等[7]提出了一种引入一个新参数的人工鱼群算法，即觅食步长参数 prey_step。引入觅食步长参数的目的，是在保留基本人工鱼群算法原有移动步长随机性的同时，根据觅食步长调整其移动的距离跨度。由于采用了移动和觅食两种步长，加快了算法的寻优速度，增强了人工鱼在离散解空间中邻域搜索的灵活性和有效性，也可降低陷入局部机制的可能性。但是，实际上这些研究也仅仅局限于部分问题的应用，无法推广到所有问题域。 3.2 基于鱼群行为的改进 3.2.1 基于基本鱼群行为的改进人工鱼群算法是模仿鱼类行为提出的一种基于动物自治体的优化方法，是一种最优仿生优化算法，它主要是通过模拟鱼类的觅食、聚群、追尾等行为在搜索域中进行寻优，所以如果要对该算法进行改进，也可以从算法中的觅食行为、聚群行为、追尾行为着手，通过对这几方面进行改进，进而对算法进行改进。 Yang Yu等[2]在采用自适应鱼群视野和最优个体保留策略的基础上，通过将聚群行为和追尾行为分别与觅食行为相结合的方法，使算法的计算复杂度进一步降低。实验表明表明改进的人工鱼群算法具有寻优成功率高、收敛速度快等特点。范玉军等[8]通过对人工鱼群算法的研究，给出了改进的人工鱼群算法。采用最优个体保留策略对觅食行为进行改进，防止群体中最优个体的退化；给出加速个体局部搜索方法，改进算法中的聚群行为和追尾行为，使全局最优值更快地突现出来；根据双射的定义和性质，在不影响最终寻优结果的情况下对问题的搜索域进行“缩小”，从而加速了全局搜索。仿真结果表明改进的人工鱼群算法具有求解精度高、寻优成功率高、收敛速度快、算法稳定等优点。黄光球等[9]通过大量研究，最后使用自适应δ变异算子、双算术交叉算子、峰跳操作算子等多种算子改进人工鱼的各种行为，得到了一种改进的人工鱼群算法。应用结果表明，该算法计算速度、可靠性和稳定性大幅度提高。 3.2.2 基于新增鱼群行为的改进从前一章所述的基本人工鱼群算法中，可以看出，当寻优的域较大或处于变化平坦的区域时，一部分人工鱼将处于无目的的随机移动中，这影响了寻优的效率，类似这种问题，除了可以对鱼群行为进行改进来解决，还可以通过引进新的鱼群行为来改进算法。李晓磊等[5]通过引入生存机制和竞争机制对人工鱼群算法加以改善。生存机制的描述如下： h = E Tλ ; h 1 ::AF_move ≥⎧ ⎨ h 1 ::AF_init < ⎩ (3.6) 式中h为生存指数；E为人工鱼当前所处位置的食物能量值；T为人工鱼的生存周期；K为消耗因子，即单位时间内消耗的能量值。即当人工鱼所处位置的食物能量足以维持其生命时，人工鱼将按照正常的行为寻优，否则，当此处的能量低于其生命的维持所需时，通常此时处于局部极值点或非极值点附近， - 4 -

http://www.paper.edu.cn 寻优通常会没有结果，所以，强制该人工鱼初始化，例如，可以随机产生该人工鱼的位置，使其跳出该区域，这样就相当于利用相同的存储空间增加了寻优人工鱼的个数，从而提高了算法的效率。竞争机制就是实时地调整人工鱼的生存周期，其描述如下： T =∈ maxE λ (3.7) 式中Emax为当前所有的人工鱼中所处位置的食物能量的最大值；∈为比例系数。随着寻优的逐步进展，人工鱼的生存周期将被其中最强的竞争者所提升，从而使得那些处于非全局极值点附近的人工鱼能有机会展开更广范围的搜索。 Jianwei Ma等[3]提出了一种加入跳跃行为的人工鱼群算法，目的是加大目标函数值跳出局部极值、到达全局最优的可能性。跳跃行为的主要思想是当整个人工鱼群连续迭代M1次最优目标函数值未发生明显变化时，在鱼群中按概率P (0

_ fish http://www.paper.edu.cn // // // ′ ′ AF s position AF slast position theever good positionof AF class Artificial { public : float AF X n _ [ ]; float last AF X n _ [ ]; _ float evergood AF X n _ _ [ ]; }; 这样，人工鱼就记忆着曾经的最好状态和上一次的状态，从而为下一次的行为作出更加合理的行为评价。 3.4 混合优化方法鱼群模式提供了一种解决问题的架构，其中自然可以应用传统的一些相对成熟的计算方法，而面向对象的方法使得将其他计算方法与鱼群算法的有机融合提供了良好的基础。例如，如果问题的模型比较熟知，并且目标函数的非线性程度不是非常严重，则可以在觅食行为中使用单纯行法等传统方法来代替在视野中的随机搜索方法，这样，在提高收敛速度的同时，能适当提高收敛的精度，并且还能在一定程度上克服局部极值的问题。算法在优化过程初期虽然具有较快的收敛品质，但在后期却往往收敛较慢，或者无法达到要求的精度，因此，与其他算法相结合，在合适的时候与它们互相切换，实现各算法之间的优缺点互补，也是一种解决问题的常用方法。李晓磊等[11]针对复杂大系统的优化问题中方程数多、变量维数高等特点，描述了一种基于分解协调思想的人工鱼群优化算法。并以换热器系统为例进行了计算，结果表明，该算法具有较好的收敛性、初值不敏感性和参数不敏感性等特点。 Xiaojuan Shan等[7]提出了一种改进的人工鱼群算法，引入禁忌表，增强了人工鱼群算法的全局寻优和邻域搜索能力，避免限于局部最优解。实验结果显示改进的算法具有较好的全局寻优能力。李亮等[10]构造了一种两点禁忌寻优算子以避免寻优过程中的迂回搜索，并用它模拟鱼群中单条鱼的追寻历史最优鱼、追尾、群聚三种行为，采用遗传算法中非均匀变异算子模拟单条鱼的觅食行为，鱼群中各个体通过这四种行为进行交流、合作从而形成了一种禁忌鱼群算法。将该算法应用于两个复杂土坡的最小安全系数搜索中，并同基本鱼群算法的计算结果进行了比较，结果证明禁忌鱼群算法具有搜索高效、适于约束优化问题求解等特点。张梅凤等[12]在分析人工鱼群算法存在不足的基础上，提出了基于变异算子与模拟退火混合的人工鱼群优化算法。该算法保持了人工鱼群算法简单、易实现的特点，克服了人工鱼漫无目的随机游动或在非全局极值点的大量聚集，显著提高了算法的运行效率和求解质量。通过函数和实例测试验证，表明了该算法是可行和有效的。黄光球等[13]通过引入网格划分策略和禁忌搜索算法，对基本人工鱼群算法进行了改进，减少了迂回搜索的无用计算，同时也使人工鱼可以在解空间内进行更为全面的搜索，提高了搜索效率，加快了系统满意解域的确定；通过对变量空间进行网格划分，提供了获取系统最优解的方法，而且加强了对鱼群公告板信息的使用。实验表明，与基本人工鱼群算法相比，该方法具有明显的优越性。 - 6 -

http://www.paper.edu.cn 高德芳等[14]提出了融合鱼群算法及蚁群算法的优化模型求解方法，并以铁路客车内装模块化配置设计为应用，验证了该求解方法的可行性和有效性。宋志宇等[15]根据混沌(CHAOS)的遍历性和随机性等特点，将混沌系统和人工鱼群算法相结合形成了一种新的融合优化算法-混沌人工鱼群算法(CAFSA)。经算例分析表明，与人工鱼群算法相比较，混沌人工鱼群算法具有收敛快、效率高和结果精度高等优点。从而为解决类似的系统优化和参数识别问题提供了一种新的方法。程晓荣等[16]针对人工鱼群算法的这些不足，引入了改进的模拟退火算法和精英选择的思想对人工鱼群算法进行改进。然后通过对具体实例的仿真实验，比较了人工鱼群算法改进前后进行优化的结果，同时验证了该方法的可行性和有效性。对上述研究工作简单总结可看出这些混合优化方法主要有两大类： (1)全局优化算法与局部优化算法混合； (2)全局优化算法与全局优化算法混合。 4. 结论人工鱼群算法从具体的实施算法到总体的设计理念，都不同于传统的设计和解决方法，同时它又具有与传统方法相融合的基础。它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，有着较快的收敛速度。该算法还具有良好的克服局部极值、取得全局极值的能力，并且算法的实现无需目标函数的梯度值等特性，对搜索空间具有一定的自适应能力。相信通过本文提出的四种改进思路,不断改进完善该算法，鱼群算法将有着更良好的应用前景。 - 7 -

http://www.paper.edu.cn 参考文献 [1] 李晓磊,邵之江, 钱积新.一种基于动物自治体的寻优模式:鱼群算法［J ］. 系统工程理论与实践, 2002,22(11):32-38. [2] Yu Yang, Tian Yafei,Yin Zhifeng.Multiuser Detector Based on Adaptive Artificial Fish School Algorithm ［J］.Communications and Information Technology,2005. ISCIT 2005.IEEE International Symposium on Volume 2,12-14 Oct.2005:1480-1484. [3] Wang Cuiru,Zhou Chunlei,Ma Jianwei.An Improved Artificial Fish-swarm Algorithm and its Application in Feed-forward Neural Networks［J］.Proceedings of the Fourth International Conference on Machine Learning and Cybernetics,2005:2890-2894. [4] 王西邓.人工鱼群算法的改进研究［D］.西安:西安建筑科技大学,2007. [5] 李晓磊.一种新型的智能优化方法-人工鱼群算法［D］.杭州:浙江大学,2003. [6] Xiao Jianmei,Zheng Xiaoming,Wang Xihuai etal.A Modified Artificial Fish- Swarm Algorithm［J］. Proceedings of the 6th World Congress on Intelligent Control and Automation, 2006:3456-3460. [7] Shan Xiaojuan,Jiang Mingyan,Li Jingpeng.The Routing Optimization Based on Improved Artificial Fish Swarm Algorithm［J］. Proceedings of the 6th World Congress on Intelligent Control and Automation, 2006:3658-3662. [8] 范玉军,王冬冬,孙明明.改进的人工鱼群算法［J］.重庆师范大学学报(自然科学版),2007,24(3): 23-26. [9] 黄光球, 姚玉霞, 任燕. 用鱼群算法求解多级递阶物流中转运输系统优化问题［J ］. 计算机应用, 2007,27(7):1732-1736 转 1743. [10] 李亮,迟世春,林皋.禁忌鱼群算法及其在边坡稳定分析中的应用［J］.工程力学,2006,23(3):6-10. [11] 李晓磊,钱积新.基于分解协调的人工鱼群优化算法研究［J］.电路与系统学报,2003,8(1):1-6. [12] 张梅凤 , 邵诚 , 甘勇等 . 基于变异算子与模拟退火混合的人工鱼群优化算法［ J ］ . 电子学报 , 2006,34(8):1381-1385. [13] 黄光球,王西邓,刘冠.基于网格划分策略的改进人工鱼群算法［J］.微电子学与计算机,2007, 24(7):83-86 转 90. [14] 高德芳,赵勇,郭杨等.基于混合鱼群-蚁群算法的模块化产品配置设计［J］.设计与研究,2007, 34(1):7-10. [15] 宋志宇,李俊杰,汪红宇.混沌人工鱼群算法在重力坝材料参数反演中的应用［J］.岩土力学,2007, 28(10):2193-2196 转 2202. [16] 程晓荣,张秋亮,王智慧等.基于人工鱼群算法的配电网网架优化规划［J］.继电器,2007, 35(21):34-38. A survey of Artificial Fish-swarm Algorithm and its Improve Technique Wang Chuang, Xue Ting, Sun Linyan Dalian Maritime University, Dalian (116026) Abstract In this paper, firstly, we make a simple survey of AFSA for its developing situation. Then through analyzing AFSA’s advantage and disadvantage to propose four improve technique, which are improving parameter, improving the behavior of fish-swarm, the mode of high-level behavior, amalgamation with other optimization algorithm. And we prove them with foregone algorithm. Finally, we make it more convenience for improving AFSA. Keywords: artificial fish-swarm algorithm, optimization algorithm, improve technique - 8 -

分享到：

赞收藏

资料库

论文研究-人工鱼群算法的现状与改进分析 .pdf

相关推荐

开发技术

热门标签

最新资料