基本人工鱼群算法

基本人工鱼群算法摘要人工鱼群算法（ArtificialFish-SwarmAlgorithm，AFSA）是由李晓磊等在2002年提出的，源于对鱼群运动行为的研究，是一种新型的智能仿生优化算法。它具有较强的鲁棒性、优良的分布式计算机制易于和其他方法结合等优点。目前对该算法的研究、应用已经渗透到多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问题。人工鱼群算法已经成为交叉学科中一个非常活跃的前沿性学科。本文主要对鱼群算法进行了概述，引入鱼群模式的概念，然后给出了人工鱼的结构，接下来总结出了人工鱼的寻优原理，并对人工鱼群算法的寻优过程进行仿真，通过四个标准函数选取不同的拥挤度因子进行仿真实验，证实了利用人工鱼群算法进行全局寻优确实是有效的。关键词：人工鱼群算法；拥挤度因子；寻优0引言动物在进化过程中，经过漫长的优胜劣汰，形成了形形色色的觅食和生存方式，这些方式为人类解决生产生活中的问题带来了不少启发和灵感。动物不具备复杂逻辑推理能力和综合判断等高级智能，但他们通过个体的简单行为和相互影响，实现了群体的生存和进化。动物行为具有以下几个特点。（1）适应性：动物通过感觉器官来感知外界环境，并应激性的做出各种反应，从而影响环境，表现出与环境交互的能力。（2）自治性：在不同的时刻和不同的环境中能够自主的选取某种行为，而无需外界的控制或指导。（3）盲目性：单个个体的行为是独立的，与总目标之间没有直接的关系。（4）突现性：总目标的完成是在个体行为的运动过程中突现出来的。（5）并行性：各个个体的行为是并行进行的。人工鱼群算法是根据鱼类的活动特点提出的一种基于动物行为的自治体寻优模式。1鱼群模式描述1.1鱼群模式的提出20世纪90年代以来，群智能（swarmintelligence，SI）的研究引起了众多学者的极大关注，并出现了蚁群优化、粒子群优化等一些著名的群智能方法。集群是生物界中常见的一种现象，如昆虫、鸟类、鱼类、微生物乃至人类等等。生物的这种特性是在漫长的进化过程中逐渐形成的，对其生存和进化有着重要的影响，同时这些方式也为人类解决问题的思路带来不少启发和鼓舞。因此，近年来有不少科学家对生物行为进行了广泛研究，并逐渐形成了一种基于生物行为的人工智能模式。这种基于生物行为的人工智能模式与经典的人工智能模式是不同的，它不是采取自上而下的设计方法，而是采取自下而上的设计方法：首先设计单个实体的感知、行为机制，然后将一个或一群实体放置于环境中，让它们在与环境的交互作用中解决问题。它是内嵌的、物化的、自治的、突现的。一个集群通常定义为一群自治体的集合，他们利用相互直接或间接的通信，从而通过全体的活动来解决一些分布式难题。在这里，自治体是指在一个环境中具备自身活动能力的一个实体，其自身力求简单，通常不必具有高级智能。但是，它们的集群活动所表现出来的则是一种高级智能才能达到的活动，这种活动可以称为集群智能。动物自治体通常指自主机器人或动物模拟实体，它主要用来展示动物在复杂多变的环境中能够自主产生自适应的智能行为的一种方式。自治体的行为受到环境的影响同时每一个自治体又是环境的构成因素。环境的下一个状态是当前状态和自治体活动的函数，自治体的下一个刺激是在环境的当前状态和其自身活动的函数，自治体的合理架构就是能在环境的刺激下做出最好的应激活动。将动物自治体的概念引入鱼群优化算法中，采用自下而上的设计思路，应用基于行为的人工智能方法，形成一种新的解决问题的模式，因为是从分析鱼类活动而出发的，所以称为鱼群模式。该模式用于寻优中，形成人工鱼群算法。在一片水域中，鱼生存数目最多的地方一般就是该水域中富含营养物质最多的地方，依据这一点来模仿鱼群的觅食、群聚、追尾等行为，从而实现全局寻优，这就是人工鱼群算法的基本思想。1.2人工鱼的结构模型人工鱼（artificialfish，AF）是真实鱼的一个虚拟实体，用来进行问题的分析和说明。人工鱼的结构模型和行为描述可以借助面向对象的分析方法，如图1.1所示。可以认为人工鱼就是封装了自身数据和一系列行为的实体，可以通过感官来接收环境的刺激信息，并通过控制尾鳍来做出相应的应激活动。图1.1人工鱼的结构人工鱼所在的环境主要是问题的解空间和其人工鱼的状态，它在下一刻的行为取决于目前自身状态和目前环境状态，并且它还通过自身活动来影响环境，进而影响其他同伴的活动。人工鱼对外界的感知是靠视觉来实现的。生物的视觉是极其复杂的，为了实施的简单有效，在人工鱼的模型中应用如下方法实现虚拟人工鱼的视觉。如图1.2所示，一条虚拟人工鱼当前状态为X，Visual为其视野范围状态vX为其某时刻视点所在的位置，若该位置的状态由于当前状态，则考虑向当前位置方向前进一步，即到达状态nextX；若状态vX不比当前状态更优，则继续巡视视野内的其他位置。巡视的次数越多，对视野的状态了解的越全面，从而对周围的环境有一个全方位立体的认知，这有助于做出相应的判断和决策。当然，对于状态多状态无限的环境也不必全部遍历，允许人工鱼具有一定的不确定性的局部寻优，从而对寻找全局最优是有帮助的。StepVisualXXnextX2X1Xv图1.2人工鱼视觉的概念其中，状态nxxxX...,,,21，状态nvvvVxxxX...,,,21，则该过程可以表示如下：()RandVisualXXv()XXXXvvnextRandStepXX式中，Rand()函数为产生0到1之间的随机数；Step为移动步长。由于环境中同伴的数目是有限的，因此在视野中感知同伴（如图1.2中X1，X2等）的状态，并相应的调整自身状态，方法与上式类似。通过模拟鱼类的四种行为——觅食行为、聚群行为、追尾行为和随机行为，来使鱼类活动在周围的环境。这些行为在不同的条件下会相互转换。鱼类通过对行为的评价，选择一种当前最优的行为进行执行，以达到食物浓度更高的位置，这是与鱼类生存有着密切关系的。算法采用面向对象的技术重构人工鱼的模型，将人工鱼封装成变量和函数两部分。变量部分包括人工鱼的总数N、人工鱼个体的状态nxxxX...,,,21（其中nixi,...,2,1为欲寻优的变量）、人工鱼移动的最大步长Step、人工鱼的视野Visual、尝试次数Try_number、拥挤度因子、人工鱼个体i,j之间的距离jiijXXd。函数部分包括人工鱼当前所在位置的食物浓度)(YXf（Y为目标函数值）、人工鱼的各种行为函数（觅食行为Prey()、聚群行为Swarm()、追尾行为Follow()、随机行为Move()以及行为评价函数Evaluate()）。通过这种封装，人工鱼的状态可以被其他同伴所感知。2人工鱼的四种基本行为算法描述鱼类不具备人类所具有的复杂逻辑推理能力和综合判断能力等高级智能，它们的目的是通过个体的简单行为或通过简单行为而达到或突现出来的。这里，对人工鱼定义了四种基本行为。1.觅食行为这是人工鱼的一种基本行为，也就是趋向食物的一种活动，一般可以认为它是通过视觉或味觉来感知水中的食物量或浓度进而来选择趋向的，因此前面讲到的视觉概念可以应用于该行为。行为描述：设人工鱼i当前状态为iX，在其感知范围内随机选择一个状态jX()RandVisualiXXj（2.1）式中，Rand()是一个介于0和1之间的随机数，如果在求极大值问题中，jYiY，则向该方向前进一步()1RandStepXXXXXXtijtijttii（）（2.2）反之，再重新随机选择状态jX，判断是否满足前进条件，反复尝试Try_number次后，若仍不满足前进条件，则随机移动一步()X1RandVisualXtiti（2.3）伪代码描述如下：FloatArtificial_fish::AF_prey(){For(i=0;itrynumber;i++){Xj=Xi+Rand()*Visual;if(YiYj)ijjiinextXXXXStepRandX()X/i;ElseStepRandXinext()X/i}ReturnAF_fooodconsistence(nexti/X);}2聚群行为鱼在游动过程中会自然的聚集成群，这也是为了保证群体的生存和躲避危害而形成的一种生活习性。鱼群的形成也是一种突现的生动实例，一般认为鸟类和鱼类聚群的形成并不需要一个领头者，只需每只鸟或每条鱼遵循一些局部的相互作用规则，然后集群现象作为整体模式从个体的局部相互作用中突现出来。行为描述：自然界中鱼在游动过程中为保证群体的生存和躲避危害，会自然的聚集成群。在人工鱼群算法中对每条人工鱼做如下规定：一是尽量向邻近伙伴的中心移动；二是避免过分拥挤，设人工鱼当前状态为iX，探索当前领域内Visualdij的伙伴数目fn及中心位置oX。若ifYn/Yc，表明伙伴中心有较多食物且不太拥挤，则朝伙伴中心位置方向前进一步()X1RandStepXXXXXtictictiti（2.4）否则执行觅食行为。伪代码描述如下：FloatArtificial_fish::AF_swarm(){;0;0cfXnfor(j=0;jfriend_number;j++){If(Visualdji,){fn++;jcXX}fnnXcX;If(ifYncY);iciinextXXXXStepRandXc/i()X;elseAF_prey();}ReturnAF_foodconsistence(nexti/X);}3.追尾行为鱼群在游动过程中，当其中一条鱼或几条鱼发现食物时，其邻近的伙伴会尾随其快速达到食物点。行为描述：追尾行为是一种向邻近的有着最高适应度的人工鱼追逐的行为，在寻优算法中可以理解为是向附近的最优伙伴前进的过程。设人工鱼i当前状态为iX，探索当前邻域内Visualdij的伙伴中jY为最大值的伙伴jX。若ifYn/Yj，表明伙伴jX的状态具有较高的食物浓度并且其周围不太拥挤，则朝jX的方向前进一步()Xj1RandStepXXXXXtijtititi(2.5)否则执行觅食行为。伪代码描述如下：FloatArtificial_fish::AF_follow(){maxY；for(j=0;jfriend_number;j++){If(Visualdji,&&maxjYY){jjXXYmaxmax;Y}fn=0；For（j=0;jfriend_number;j++）If(Visualdmax){fn++;}If(ifYnmaxY);iiinextXXXXStepRandXmaxmax/i()X;elseAF_prey();}ReturnAF_foodconsistence(nexti/X);}4.随机行为平时会看到鱼在水中自由地游来游去，表面看是随机的，其实它们也是为了在更大范围内寻觅食物或同伴。行为描述：随机行为的描述比较简单，就是在视野中随机选择一个整体，然后向该方向移动，其实它是觅食行为的一个缺省行为。这四种行为在不同的条件下会相互转换，鱼类通过对行为的评价选择一种当前最优的行为进行执行，以达到食物浓度更高的位置，这是鱼类生存习惯。对行为的评价是用来反应鱼自主行为的一种方式。咋解决优化问题中，可以选用两种简单的评价方式：一种是选择最优行为进行执行，也就是在当前状态下，哪一种行为向最优的方向前进最大，就选择哪一行为；另一种是选择较优方向前进，也就是任选一种行为，只要能向优的方向前进即可。3人工鱼群算法的寻优原理通过以上人工鱼的行为描述可知，在人工鱼群算法中，觅食行为奠定了算法收敛的的基础，群聚行为增强了算法收敛的稳定性，追尾行为则增强了算法收敛的快速性和全局性，行为分析为算法收敛的速度和稳定性提供了保障。人工鱼群算法寻优过程中，人工鱼可能会集结在几个局部极值域的周围。使人工鱼逃出局部极值域，实现全局寻优的因素主要有以下几点：（1）觅食行为中重试次数较少时，为人工鱼提供了随机游动的机会，从而能跳出