人工鱼群算法

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,人工鱼群算法,目录,1 引言,2 鱼群模式概论,3 人工鱼群的四种根本行为算法描述,4 人工鱼群算法的寻优原理,5 参数设置性能,6 拥挤度因子对优化的影响,7 人工鱼群算法的特点,1,引言,动物在进化的过程中，经过优胜劣汰，形成了各种觅食和生存方式。他们不具备复杂逻辑能力和综合判断能力等高级技能，但他们通过个体的简单行为和相互影响，实现群体的生存和进化。动物行为具有以下特点：,1适应性：动物通过感觉器官来感知外界环境，并应激性的做出各种反响，从而影响环境，表现出与环境交互的能力。,2自治性：在不同的时刻和环境中能够自主地选取某种行为，而无需外界的控制和指导。,3盲目性：单个个体的行为是独立的，与总目标之间没有直接关系。,4突现性：总目标的完成是在个体行为的运动过程中突现出来的,5并行性：各个个体的行为是并行的,人工鱼群算法是根据鱼类的活动特点提出的一种基于动物行为的自治寻优模式。,2,鱼群的模式概论,2.1,鱼群模式的提出,20,世纪,90,年代以来，群智能的研究引起了众多学者的极大关注，出现了蚁群优化、粒子群优化等一些著名的群智能方法。,基于生物行为的人工智能模式：,采用自下而上的设计方法，首先设计单个实体的感知、行为机制，然后将一个或一群实体放置环境中，让它们在环境的交互作用中解决问题。,人工鱼群算法(artificial fish-swarm algorithm，AfSA)描述,在一片水域中，鱼存在的数目最多的地方就是本水域中富含营养物质最多的地方，依据这一特点来模仿鱼群的觅食，聚群，追尾等行为，从而实现全局最优，这就是鱼群算法的根本思想。,鱼类的活动中，觅食行为，聚群行为，追尾行为和随机行为与寻优命题的解决有较密切的关系，如何利用简单有效的方式来构造实现这些行为将是算法实现的主要问题。,2.2 人工鱼的构造模型,人工鱼是真实鱼的一个虚拟的实体，用来进展问题的分析和说明。,人工鱼就是一个封装了自身数据和一系列行为的实体，可通过感官来承受环境的刺激信息，并通过控制尾鳍来做出相应的应激活动。,人工鱼所在的环境主要是问题的解空间和其他人工鱼的状态，它在下一刻的行为取决于目前自身的状态和环境的状态，并且他还通过自身的活动来影响环境，进而影响其他同伴的活动。,图1 人工鱼的构造,感知行为,参数数据,行为评价执行,人工鱼对外的感知是靠视觉来实现的，人工鱼的模型中应用如下方法实现虚拟人工鱼的视觉。,其中,Rand(),函数为产生,0,到,1,之间的随机数；,Step,为步长,图2 人工鱼视觉的概念,人工鱼封装成变量局部和函数局部,变量局部：人工鱼的总数N、人工鱼个体的状态X=(x1,x2,xn)其中xii=1,2n为欲寻优的变量、人工鱼移动的最大步长Step、人工鱼的视野Visual、尝试次数Try-number、拥挤度因子、人工鱼个体i,j之间的距离,函数局部：人工鱼当前所在位置的食物浓度表示为Y=f(X)Y为目标函数值、人工鱼各种行为函数觅食行为Prey()、聚群行为Swarm()、追尾行为Follow()、随机行为Move()以及行为评价函数Evaluate(),3 人工鱼的四种根本行为算法描述,1觅食行为Prey()：指鱼循着食物多的方向游动的一种行为，人工鱼Xi在其视野内随机选择一个状态Xj，,分别计算它们的目标函数值进展比较，如果发现Yj比Yi优，那么Xi向Xj的方向移动一步；,否那么，Xi继续在其视野内选择状态Xj，判断是否满足前进条件，反复尝试Try-number次后，仍没有满足前进条件，那么随机移动一步使Xi到达一个新的状态。表达式如下：,2聚群行为Swarm()：鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群 。,鱼聚群时所遵守的规那么:一是尽量向临近伙伴的中心移动；二是防止过分拥挤。,人工鱼Xi搜索当前邻域内dij Yi，说明伙伴中心位置状态较优且不太拥挤，那么Xi朝伙伴的中心位置移动一步，,否那么执行觅食行为。,3追尾行为Follow():指鱼向其可视区域内的最优方向移动的一种行为。,人工鱼Xi搜索当前邻域内 dij Yi,说明最优伙伴的周围不太拥挤，那么Xi朝此伙伴移动一步:,否那么执行觅食行为。,4,随机行为,Move(),：指人工鱼在视野内随机移动，它是觅食行为的一个缺省行为。当发现食物时，会向食物逐渐增多的方向快速的移动。,4,人工鱼群算法的寻优原理,人工鱼群算法在寻优的过程中，可能会集结在几个局部极值域的周围，使人工鱼逃出局部极值域，实现全局寻优的因素主要有：,觅食行为中重复次数较少时，为人工鱼提供了随机移动的时机，从而可能跳出局部极值域,随机步长使得人工鱼在前往局部极值的途中，有可能转向全局极值,拥挤度因子限制了聚群的规模，使得人工鱼能够更广泛的寻优,聚群行为能够促使少数陷于局部极值的人工鱼趋向全局极值的人工鱼方向聚集，从而逃出局部极值,追尾行为加快了人工鱼向更优状态游动。,1公告牌,是记录最优人工鱼个体状态的地方。每条人工鱼在执行完一次迭代后将自身当前状态与公告板中记录的状态进展比较，如果优于公告板中的状态那么用自身状态更新公告牌中的状态，否那么公告牌的状态不变。当整个算法的迭代完毕后，输出公告板的值，就是我们所求的最优值。,2行为评价：是用来反映鱼自主行为的一种方式。在解决优化问题时选用两种方式评价，一种是选择最优行为执行；另一种是选择较优方向。对于解决极大值问题，可以使用试探法，即模拟执行聚群、追尾等行为，然后评价行动后的值选择最优的来执行，缺省的行为方式为觅食行为。,3迭代终止条件,通常的方法是判断连续屡次所得值的均方差小于允许的误差；或判断聚集于某个区域的人工鱼的数目到达某个比率；或连续屡次所获得的均值不超过已寻找的极值；或限制最大迭代次数。假设满足终止条件，那么输出公告牌的最有记录；否那么继续迭代。,人工鱼群算法的步骤：,1初始化设置，包括种群规模N、每条人工鱼的初始位置、人工鱼的可视域Visual、步长step、拥挤度因子、重复次数Try-number,2计算初始鱼群各个体适应值，取最优人工鱼状态及其值赋给公告牌,3对每个个体进展评价，对其要执行的行为进展选择，包括觅食、聚群、追尾和随机行为,4执行人工鱼的行为，更新自己，生成新鱼群。,5评价所有个体。假设某个体优于公告牌，那么将公告牌更新为该个体。,6当公告牌上最优解到达满意误差界内，算法完毕，否那么转步骤3。,5.1 人工鱼群算法的收敛根底,在人工鱼群算法中，觅食行为奠定了算法收敛的根底；聚群行为增强了算法收敛的稳定性；追尾行为增强了算法收敛的快速性和全局性；其行为评价也对算法收敛的速度和稳定性提供了保障。,5.2 各种参数对收敛性的影响,人工鱼群算法有5个根本参数：群规模N，人工鱼的视visua、 步长step、拥挤度因子、重复次数Try-number,1.视野：由于视野对算法中各行为都有较大的影响，因此，它的 变化对收敛性能的影响也是比较复杂的。当视野范围较小时，人工鱼的觅食行为和随机游动比较突出;视野范围较大时，人工鱼的追尾行为和聚群行为将变得较突出。总体来看，视野越大，越容 易使人工鱼发现全局极值并收敛。,2.步长：对于固定步长，随着步长的增加，收敛的速度得到了一定的加速，但在超过一定的范围后，又使得收敛速度减缓，步长过大时，有时会出现振荡现象而大大影响收敛的速度。采用随机步长的方式在一定程度上防止了振荡现象的发生，并使得该参数的敏感度大大降低了，但最快的收敛速度还是最优固定步长的收敛速度，所以，对于特定的优化问题，我们可以考虑采用适宜的固定步长或变尺度方法来提高收敛的度。,3.人工鱼的个体数目：人工鱼的数目越多，跳出局部极值的能力越强，同时，收敛的速度也越快，当然，付出的代价就是算法每次迭代的计算量也越大了，因此，在使用过程中，满足稳定收敛的前提下，应尽可能的减少个体的数目。,4.尝试次数：尝试次数越多，人工鱼的觅食行为能力越强，收敛的效率也越高。在局部极值突出的情况下，应该适当的减少以增加人工鱼随机游动的概率，抑制局部极值。,5.拥挤度因子：,6,拥挤度因子,对优化的影响,定义：,在求极大值问题中,:,=1/(n,max,), (0,1,其中,为极值接近水平，,n,max,为期望在该邻域内聚集的最大人工鱼数目。,在求极小值问题中：,=n,max, (0,1,拥挤度因子的作用机理,拥挤度因子与,nf,相结合，通过人工鱼是否执行追尾和聚群行为对优化结果产出影响,对追尾行为的描述,图中,af0,为人工鱼,af1-5,在各自视野内的最优人工鱼，其实物浓度为,Yj,C1,为以,af0,为圆心，以视野为半径的圆，即能探知,af0,的最远距离，人工鱼越靠近,af0,，状态越优,图3 对追尾行为的描述,极大值情况下：当nf 1时，所有人工鱼af1-5都执行追尾行为，向af0游动；当nf 1时，假设C2的食物浓度为Yj/nf 的等浓度食物圈，那么C2与C1间的人工鱼af1、af2、af3执行追尾行动，向af0游动，人工鱼af4、af5执行觅食行为。此时nf 越大执行追尾行动的人工鱼越少，反之越多。,拥挤度因子的影响,以极大值为例(极小值的情况正好和极大值相反)， 越大，说明允许的拥挤程度越小，人工鱼摆脱局部极值的能力越强;但是收敛的速度会有所减缓，这主要 因为人工鱼在逼近极值的同时，会因防止过分拥挤而随机走开或者受其它人工鱼的排斥作用，不能准确逼近极值点。可见，虽然的引入防止了人工鱼过度拥挤而陷入局部极值，另一方面，该参数会使得位于极值点附近的人工鱼之间存在相互排斥的影响，而难以向极值点准确逼近，所以，对于某些局部极值不是很严重的具体问题，可以忽略拥挤的因素，从而在简化算法的同时也加快了算法的收敛速度和提高结果的准确程度。,7,人工鱼群算法的特点,1只需比较目标函数值，对目标函数的性质要求不高。,2对初值的要求不高，随机产生或设为固定值均可。,3对参数设定的要求不高，容许范围大。,4具备并行处理能力，寻优速度较快。,5具备全局寻优能力，能快速跳出局部极值点。,6具有较快的收敛速度，可以用于解决有实时性要求的问题；,7对于一些精度要求不高的场合，可以用它快速的得到一个可行解；,8不需要问题的严格机理模型，甚至不需要问题的准确描述，这使得它的应用范围得以延伸,综上所述，该算法是一种基于集群智能的新型的高效寻优方法,谢谢大家！,