第7章--鱼群算法基本理论.ppt

7.1鱼群算法的概述7.1.1鱼群算法的概念7.1.2鱼群算法的的发展7.1.3鱼群算法的特点7.1.4鱼群算法的分类7.2鱼群算法的基本原理7.2.1鱼群觅食的几种典型行为7.2.2鱼群算法的机理7.3鱼群算法的应用,第7章鱼群算法基本理论,7.1鱼群算法概述7.1.1鱼群算法的概念鱼群算法是根据鱼类的活动特点,提出了一种基于动物行为的自治体寻优模式。【注】自治体：指生物体在不同时刻和不同环境中，能够自主地选择某种行为，而无需外接的控制与指导。鱼群算法的基本思想：在一片水域中，鱼往往能够自行或尾随其他鱼找到营养物质多的地方，因此鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法就是根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为，从而实现全局寻优。,7.1鱼群算法概述,7.1.2鱼群算法的发展鱼群算法是浙江大学系统工程研究所李晓磊博士等在系统工程理论与实践2002年第11期发表的“一种基于动物自治体的寻优模式：鱼群算法”中首次提出。之后，引起广泛关注，提出多种改进算法。,7.1鱼群算法的概述,7.1.3鱼群算法的特点李晓磊博士论文描述李晓磊博士在“一种基于动物自治体的寻优模式：鱼群算法”一文中描述鱼群算法的特点主要是“五性”：并行性：多个人工鱼并行进行搜索；简单性：算法中仅使用了目标问题的函数值；全局性：算法具有很强的跳出局部极值的能力；快速性：算法中虽然有一定的随机因素，但总体是在步步向最优搜索；跟踪性：随着工作状况或其他因素的变更造成的极值点的漂移，本算法具有快速跟踪变化的能力。,7.1鱼群算法的概述,综述特点只需比较目标函数值，对目标函数的性质要求不高。对初值的要求不高，随机产生或设定固定值均可。对参数设定的要求不高，容许范围大。具备并行处理能力，寻优速度较快。具有全局寻优能力，能快速跳出局部极值点。具有较快的收敛速度，可以用于解决有实时性要求的问题。对于一些精度要求不高的场合，可以快速得到一个可行解。不需要问题的严格机理模型。,7.1鱼群算法的概述,7.1.4鱼群算法的分类,7.1鱼群算法的概述,7.2鱼群算法的基本原理7.2.1鱼群觅食的几种典型行为随机行为：单独的鱼在水中通常都是随机游动的，这是为了更大范围地寻找食物点或身边的伙伴。觅食行为：当鱼发现食物时，会向食物逐渐增多的方向快速游去。聚群行为：鱼在游动过程中，为了保证自身的生存和躲避危害会自然地聚集成群。追尾行为：当鱼群中的一条或几条鱼发现食物时，其临近的伙伴会尾随其快速到达食物点。,7.2鱼群算法的基本原理,7.2鱼群算法的基本原理,7.2鱼群算法的基本原理,7.2.2鱼群算法的机理人工鱼的结构模型人工鱼是真实鱼的一个虚拟实体，用来进行问题的分析和说明。人工鱼主要由感知系统、行为系统和运动系统三部分组成。可以通过感官来接收环境的刺激信息，并通过控制尾鳍活动来做出相应的应激动作。,7.2鱼群算法的基本原理,感知系统：主要靠视觉来实现。设其当前状态为X，视野范围为Visual，状态Xv为其某时刻视点所在的位置，若该位置的状态优于当前状态，则考虑向该位置方向前进一步，到达状态Vnext。若状态Xv不比当前状态更优，则继续巡视视野内的其他位置。巡视的次数越多，对视野的状态了解越全面，有助于做出相应的判断和决策。其状态变化可表示为式中，Rang（）函数为产生01之间的随机数；Step为移动步长。,7.2鱼群算法的基本原理,行为系统：主要包括觅食行为、群聚行为、追尾行为和随机行为。鱼类通过对行为的评价，选择一种当前最优的行为进行执行，以到达食物浓度更高的的位置。运动系统：即参数系统，主要包括变量和函数两部分。变量有人工鱼的总数、人工鱼个体状态、人工鱼移动的最大步长、人工鱼的视野、尝试次数、拥挤度因子、人工鱼个体之间的距离等。函数包括人工鱼当前所在位置的食物浓度（即目标函数）、人工鱼的各种行为函数（觅食行为、群聚行为、追尾行为、随机行为）以及评价函数。,人工鱼的四种基本行为函数觅食行为这是人工鱼的一种趋向食物活动。一般通过视觉或味觉来感知水中的食物量或浓度来选择趋向。设人工鱼i的当前状态为Xi，在其感知范围内随机选择一个状态Xj，则若，则否则，重新随机选择Xj，判断是否满足前进条件，尝试Try-number次后，若还不满足，则随机前进一步,7.2鱼群算法的基本原理,群聚行为这是鱼群生存和躲避危害的一种生活习性。在鱼群算法中，一般规定两条，一是尽量向邻近伙伴的中心移动，二是避免过分拥挤。设人工鱼当前状态为Xi，探索当前邻域内的伙伴数目nf及中心位置Xc。若，表明伙伴中心有较多食物且不太拥挤，则朝伙伴的中心位置方向前进一步，即否则，执行觅食行为。,7.2鱼群算法的基本原理,追尾行为鱼群在游动过程中，当其中一条鱼或几条鱼发现食物时，其邻近的伙伴会尾随其快速到达食物点。即追尾行为是一种向邻近的有最高适应度的人工鱼追逐的行为，在寻优算法中可理解为向附近最优伙伴靠近的过程。设人工鱼i的当前状态为Xi，探索当前邻域内所有伙伴中Xj的Yj最大，则超Xj的方向前进一步，即随机行为鱼在水中自由游动，表面看是随机的，实际是在为更大范围觅食做准备，即在视野内随机选择一个状态，然后向该方向移动。,7.2鱼群算法的基本原理,7.2鱼群算法的基本原理,人工鱼群算法的参数选取视野（Visual）：由于视野对算法中各行为都有较大的影响，因此其变化对收敛性能的影响也是比较复杂的。当视野范围较小时，人工鱼群的觅食行为和随机游动比较突出；视野范围较大时人工鱼的追尾行为和聚群行为将变得较突出。总体来看，视野越大，越容易使人工鱼发现全局极值并收敛。因此对人工鱼的视野进行适当的改进，是提高人工鱼群算法优化性能的一种方向。步长（step）：随着步长的增加，收敛速度加快，但超过一定范围后收敛速度减慢，甚至出现振荡。因此，采用随机步长可在一定程度上防止振荡，可利用合适的固定步长和变步长来提高收敛速度和精度。,7.2鱼群算法的基本原理,人工鱼的数目（N）：人工鱼数目越多，鱼群的群体智能越突出，收敛速度越快，精度越高，跳出局部极值的能力也越强，但迭代计算量增大。因此，实际应用中，在满足稳定收敛的前提下，应尽量减少人工鱼的数目。尝试次数（Try-number）：尝试次数越多，人工鱼执行觅食行为的能力越强，收敛效率越高，但在局部极值突出的情况下，易错过全局极值点，即人工鱼摆脱局部极值的能力越弱。因此，在一般优化中，可适当增加尝试次数，以加快收敛速度；在局部极值突出的情况下，应减少尝试次数，增加人工鱼随机游动的概率。拥挤度因子（）：拥挤度因子的引入是为了避免过度拥挤而陷入局部极值。,7.2鱼群算法的基本原理,拥挤度因子的定义：对于极大值问题：对于极小值问题：式中，分别为极值接近水平和期望在该邻域内聚集的最大人工鱼数目。拥挤度因子对算法的影响（以极大值为例）：拥挤度因子越大，表明允许拥挤的程度越小，摆脱局部极值的能力越强，但收敛速度减缓。对于某些局部极值不严重的问题，往往可以忽略拥挤的因素，既简化算法，又加快算法收敛速度，提高结果的精确程度。,7.2鱼群算法的基本原理,7.2.3鱼群算法的步骤初始化设置：包括种群规模N，每条人工鱼的初始位置，人工鱼的可视域Visual，步长step，拥挤度因子，重复次数Try-number。计算初始鱼群各个体适应值，取最优人工鱼状态及其值赋予公告牌。对每个个体进行评价，对其要执行的行为进行选择，包括觅食、聚群、追尾和随机行为。执行人工鱼的行为，更新自己，形成新鲜鱼。评价所有个体，若谋个体优于公告牌，则将公告牌更新为该个体。当公告牌最优解达到满意误差界内时，算法结束。否则转步骤。,7.2鱼群算法的基本原理,7.2鱼群算法的基本原理,公告牌：用来记录最优人工鱼个体的状态。各人工鱼个体在寻优过程中，每次行动完毕就检验自身状态与公告牌的状态，如果自身状态优于公告牌状态，就将公告牌的状态改写为自身状态，这样就使公告牌记录下历史最优的状态。当整个算法结束后，输出公告牌记录的值。迭代终止条件：连续多次所得值的均方误差小于允许误差；聚集于某个区域的人工鱼数目达到某个比率；连续多次所获得的均值不超过已找到的极值；达到规定的最大迭代次数。,7.3鱼群算法的应用,7.3鱼群算法的应用人工鱼群算法虽然没有蚁群算法、粒子群算法得到广大学者的关注，但国内在电力系统、神经网络、通风系统、油田定位、信号处理、模糊控制器设计、非线性复杂函数优化等方面得到了初步应用，并取得了较好的应用效果。此外，人工鱼群算法在灌区优化配水、多用户检测、数据挖掘、路由优化、湖泊富营养综合评价、任务调度和数字图像处理等方面也有初步应用。,7.4鱼群算法的研究方向,7.4鱼群算法的研究方向算法的理论基础薄弱。到目前为止，人工鱼群算法的收敛性只从实验角度进行了分析，没有从数学方面进行分析和证明。因此，对AFSA算法模型研究和收敛性的分析对AFSA的研究十分有益。AFSA的实施过程与它采用的参数取值有较大关系，这些参数的选取仍然是一个亟待解决的问题。通常认为，对不同的问题选取相应的参数