人工鱼群算法及其在一维下料问题中的运用

人工鱼群算法及其在一维下料问题中的应用Contents4鱼群模式概论123人工鱼群算法算法实际应用总结鱼群模式概论1●视觉一虚拟人工鱼实体的当前状态为X，Visual为其视野范围，状态Xv为其在时刻视点所在的位置，如果该位置的状态优于当前状态，则考虑向该位置方向前进一步，即到达状态Xnext；如果状态Xv不比当前状态更优，则继续巡视视野内的其它位置。巡视的次数越多，则对视野内的状态了解更全面，从而对周围的环境有一个全方面立体的认知，这有助于做出相应的判断和决策。当然，对于状态多或无限状态的环境也不必全部遍历，允许一定的不确定性对于摆脱局部最优，从而寻找全局最优是有帮助的。其中，初始状态X=（x1,x2,…,xn），随机状态Xv=(x1v,x2v,…,xnv)则该过程可以表示如下：上式中，Rand函数为产生0到1之间的随机数，Step为移动步长。由于环境中同伴的数目是有限的，因此在视野中感知同伴的状态，并相应的调整自身状态的方法与上式类似。●鱼群行为分析鱼类与我们的关系相当密切，也较为我们所熟知，通常我们可以观察到如下的鱼类行为:觅食行为:这是生物的一种最基本的行为，也就是趋向食物的一种活动;一般可以认为它是通过视觉或味觉来感知水中的食物量或浓度来选择趋向的，因此，以上所述的视觉概念可以应用于该行为。聚群行为:这是鱼类较常见的一种现象，大量或少量的鱼都能聚集成群，这是它们在进化过程中形成的一种生存方式，可以进行集体觅食和躲避敌害。追尾行为:当某一条鱼或几条鱼发现食物时，它们附近的鱼会尾随其后快速游过来，进而导致更远处的鱼也尾随过来。随机行为:鱼在水中悠闲的自由游动，基本上是随机的，其实它们也是为了更大范围的寻觅食物或同伴。●人工鱼人工鱼是真实鱼个体的一个虚拟实体，用来进行问题的分析和说明。借助于面向对象的分析方法，可以认为人工鱼就是一个封装了自身数据信息和一系列行为的一个实体，可以通过感官来接收环境的刺激信息，并通过控制尾鳍来作出相应的应激活动。人工鱼所在的环境主要是问题的解空间和其他人工鱼的状态，它在下一时刻的行为取决于目前自身的状态和目前环境的状态（包括问题当前解的优劣和其他同伴的状态），并且通过自身活动影响环境，进而影响其他同伴的活动。●问题的解决问题的解决是通过自治体在自主的活动过程中以某种形式表现出来的。在寻优过程中，通常会有两种方式表现出来：一种形式是通过人工鱼最终的分布情况来确定最优解的分布，通常随着寻优过程的进展，人工鱼往往会聚集在极值点的周围，而且，全局最优的极值点周围通常能聚集较多的人工鱼；另一种形式是在人工鱼的个体状态之中表现出来的，即在寻优的过程中，跟踪记录最优个体的状态。2人工鱼群算法（AFSA,ArtificialFishSwarmAlgorithm）在一片水域中，鱼往往能自行或尾随其它鱼找到营养物质多的地方，因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法就是根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为，从而实现寻优。●基本思想●人工鱼模型(AF-artificialfish)算法采用了自下而上的设计方法，所以，首先着重构造人工鱼的模型。这里主要采用了面向对象的技术，并用C++语言的伪代码形式来说明。通常，人工鱼的模型可以用如下的类来描述:●行为描述①相关定义人工鱼个体的状态可表示为向量X=（x1,x2,…,xn），其中Xi（i=1,…,n）为欲寻优的变量；人工鱼当前所在位置的食物浓度表示为Y=f(X)，其中Y为目标函数值；人工鱼个体的距离表示为di,j=//Xi-Xj//；Visual表示人工鱼的感知距离；Step表示人工鱼的最大步长；δ为拥挤度因子。②觅食行为设人工鱼的当前状态为Xi在其感知范围内随机选择一个状态Xj，如果在求极大问题中，YiYj(或在求极小问题中，YiYj，因极大和极小问题可以互相转换，所以以下均以求极大问题讨论)，则向该方向前进一步;反之，再重新随机选择状态Xj，判断是否满足前进条件;这样反复尝试try-number次后，如果仍不满足前进条件，则随机移动一步。③聚群行为设人工鱼当前状态为Xi，探索当前邻域内（即di,jVisual）的伙伴数目nf及中心位置Xe，如果，表明伙伴中心有较多的食物并且不太拥挤，则朝伙伴中心位置方向前进一步，否则执行觅食行为。④追尾行为设人工鱼当前状态为Xi，探索当前邻域内（即di,jVisual）的伙伴中Yj为最大的伙伴Xj，如果，表明伙伴中心有较多的食物并且不太拥挤，则朝伙伴中心位置方向前进一步，否则执行觅食行为。⑤随机行为随机行为的实现比较简单，就是在视野范围内随机选择一个状态，然后向该方向移动。⑥公告板在算法中设立一个公告板，定义为一条人工鱼，用于记录最优人工鱼的状态。每条人工鱼在每次行动后，将自身的当前状态与公告板的状态进行比较，如果自身状态优于公告板，则用自身状态取代公告板状态。●算法描述鉴于以上描述的人工鱼模型及其行为，每个人工鱼探索它当前所处的环境状况(包括目标函数的变化情况和伙伴的变化情况)，从而选择一种行为，最终，人工鱼集结在几个局部极值的周围，一般情况下，在讨论求极大问题时，拥有较大的AF_foodconsistence值的人工鱼一般处于值较大的极值域周围，这有助于获取全局极值域，而值较大的极值区域周围一般能集结较多的人工鱼，这有助于判断并获取全局极值。满意解域S就是所获取的全局极值域，再根据该域的特性来获取较精确的极值，如通常情况下，可以选择域内各人工鱼的重心作为极值。算法示意图算法流程图3算法实际应用——求解一维下料问题●问题描述及模型的建立●编码方法●初始群体的建立●对于解一维下料问题的人工鱼群算法的一些定义定义一：定义二：定义三：●数值试验算法中，使人工鱼逃逸局部极值实现全局寻优的因素主要有以下几种：觅食行为中try_number的次数较少时，为人工鱼提供了随机游动的机会，从而能跳出局部极值的邻域;随机步长的采用，使得在前往局部极值的途中，有可能转而游向全局极值，当然，其相反的一面也会发生的，就是在去往全局极值的途中，可能转而游向局部极值，这对一个个体当然不好判定他的祸福，但对于一个群体来说，好的一面往往会具有更大的机率:拥挤度因子的引入限制了聚群的规模，只有较优的地方才能聚集更多的人工鱼，使得人工鱼能够更广泛的寻优。聚群行为能够促使少数陷于局部极值的人工鱼向多数趋向全局极值的人工鱼方向聚集，从而逃离局部极值;追尾行为加快了人工鱼向更优状态的游动，同时也能促使陷于局部极值的人工鱼向趋向全局极值的更优人工鱼方向的追随而逃离局部极值域。4总结try_number越大，人工鱼摆脱局部极值的能力就越弱，算法收敛到全局最优的进化代数就会越大。但较大的try_number又可以减少人工鱼的随机游动从而提高收敛效率。当视野较小时，人工鱼的觅食行为和随机行为比较突出，这样就很容易进入局部极值中；而当视野较大的时候，人工鱼的追尾行为和聚群行为将变得比较突出，降低算法的收敛速度。它的大小决定了算法的收敛速度和最终解的质量。在基本的人工鱼群算法的觅食行为中，视野大小是固定不变的。应该考虑使得视野随着尝试次数的增大而逐渐减小。在算法的初始阶段，各条人工鱼在较大的视野范围内寻优，这样就能扩展算法的搜寻范围；随着算法的进行，自适应地减小人工鱼的视野范围，从而提高算法的收敛速度。如果步长为固定步长，随着步长的增加，收敛速度也在逐渐加快，但当步长过大的时候又会减缓速度，甚至出现振荡现象而影响收敛速度。因此为了减少收敛过程中的振荡现象，这里采用随机步长进行寻优。这样能够使得该参数的敏感度大大降低了，但是当步长为最优固定步长时，算法的收敛速度是最快的，所以，对于特定的优化问题，还是可以考虑用有效的固定步长来提高收敛的速度。人工鱼群算法的特点并行性:多个AF并行地进行搜索;简单性:算法中仅使用了目标问题的函数值;全局性:算法具有很强的跳出局部极值的能力;快速性:算法中虽然有一定的随机因素，但总体是在步步向最优搜索;跟踪性:随着工作状况或其他因素的变更造成的极值点的漂移，本算法具有快速跟踪变化的能力。由以上的研究可以看出，本算法仅仅获取的是系统的满意解域，对于精确解的获取还需借助于一些策略，如分阶段寻优和变参数寻优等。Thankyou!