人工鱼群算法AFSA | 彩潭有鲤的札记

type

status

date

slug

summary

原理

人工鱼群算法(Artificial Fish Swarm Algorithm，AFSA)是Li Xiao-lei在2002年提出的(Yazdani, Toosi, & Meybodi, 2010)[1]，目的是模仿鱼类捕食、群集、跟随、移动等行为。AFSA是基于鱼类集体向某个目标运动，并受到自然的启发，是一种并行和随机搜索算法。与狮子和猴子不同，在像鱼类这种动物物种中没有领导者，每个成员都有自我组织的行为。鱼对它们的群体和环境一无所知，通过相邻成员之间的数据交换在环境中随意移动，这种交互作用为鱼群优化带来了更多的复杂性。一片水域中，鱼最多的地方就是水域中富含营养最多的地方，主要是依据这一特点来模仿鱼群的觅食、聚众、追尾等行为从而实现全局最优。它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工鱼个体的局部寻优行为,最终在群体中使全局最优值突现出来,有着较快的收敛速度。

人工鱼的结构模型

人工鱼对外的感知是依靠视觉来实现的，人工鱼的模型中使用如下方法实现人工鱼的虚拟视觉：

其中随机函数，产生0到1之间的随机数，为步长

人工鱼的视野:

人工鱼中封装的变量和函数

变量部分：人工鱼的总数、人工鱼个体的状态（其中为寻优的变量）、人工鱼移动的最大步长、人工鱼的视野、尝试次数、拥挤度因子、人工鱼个体之间的距离

函数部分：人工鱼当前所在位置食物浓度表示为（为目标函数值）、人工鱼各种行为函数（觅食行为、聚群行为、追尾行为、随机行为以及行为评价函数）

四种基本行为算法

觅食行为

这是鱼趋向食物的一种活动，一般认为它是通过视觉或味觉来感知水中的食物量或食物浓度来选择行动的方向。设置人工鱼当前状态，并在其感知范围内随机选择另一个状态，如果得到的状态的目标函数大于当前的状态，则向新选择得到的状态靠近一步，反之，重新选取新状态，判断是否满足条件，选择次数达到一定数量后，如果仍然不满足条件，则随机移动一步。

算法描述：人工鱼在其视野内随机选择一个状态

分别计算与的目标函数值与，如果发现比好，则向的方向移动一部：

否则，继续在其视野内选择状态，判断是否满足前进条件，反复尝试次后，仍没有满足前进条件，则执行随机行为。

聚群行为

大量或少量的鱼聚集成群，进行集体觅食和躲避敌害，这是它们在进化过程中形成的一种生存方式。人工鱼探索当前邻居内的伙伴数量，并计算伙伴的中心位置，然后把新得到的中心位置的目标函数与当前位置的目标函数相比较，如果中心位置的目标函数优于当前位置的目标函数并且不是很拥挤，则当前位置向中心位置移动一步，否则执行觅食行为。鱼聚群时会遵守两条规则：一是尽量向邻近伙伴的中心移动，二是避免过分拥挤

算法描述：人工鱼搜索当前视野内（）的伙伴数目和中心位置，若，则表明伙伴中心位置状态较优且不太拥挤，则朝伙伴的中心位置移动一步：

否则进行觅食行为

追尾行为

某一条鱼或几条鱼发现食物时，它们附近的鱼会尾随而来，导致更远处的鱼也会尾随过来。人工鱼探索周围邻居鱼的最优位置，当最优位置的目标函数值大于当前位置的目标函数值并且不是很拥挤，则当前位置向最优邻居鱼移动一步，否则执行觅食行为。

算法描述：人工鱼搜索当前视野内()的伙伴中函数最优伙伴，如果，表明最优伙伴的周围不太拥挤，则朝伙伴的中心位置移动一步：

否则执行觅食行为

随机行为

它是觅食行为的一个缺省行为，指人工鱼在视野内随机移动。当发现食物时，会向食物逐渐增多的方向快速的移动。

算法描述：人工鱼随机移动一步，到达一个新的状态：

人工鱼群算法描述

公告牌是记录最优人工鱼个体状态的地方。每条人工鱼在执行完一次迭代后将自身当前状态与公告牌中记录的状态进行比较，如果优于公告牌中的状态则用自身状态更新公告牌中的状态，否则公告牌的状态不变。当整个算法的迭代结束后，公告牌的值就是最优解。行为评价是用来反映鱼自主行为的一种方式，在解决优化问题时选用两种方式评价：一种是选择最优行为执行；另一种是选择较优方向。对于解决极大值问题，可以使用试探法，即模拟执行群聚、追尾等行为，然后评价行动后的值选择最优的来执行，缺省的行为为觅食行为。迭代终止条件：通常的方法是判断连续多次所得值得均方差小鱼允许的误差；或判断聚集于某个区域的人工鱼的数目达到某个比例；或连续多次所得的均值不超过已寻找的极值；或限制最大迭代次数。若满足终止条件，则输出公告牌的最优记录；否则继续迭代。

人工鱼群算法的步骤：

初始化设置，包括种群规模、没条人工鱼的初始位置、人工鱼的视野、步长、拥挤度因子δ、重复次数；

计算初始鱼群各个体的适应值，取最优人工鱼状态及其值赋予给公告牌；

对每个个体进行评价，对其要执行的行为进行选择，包括觅食、聚群、追尾和随机行为；

执行人工鱼的行为，更新自己，生成新鱼群；

评价所有个体。若某个体优于公告牌，则将公告牌更新为该个体；

当公告牌上最优解达到满意误差界内或者达到迭代次数上限时算法结束，否则转步骤3

寻优原理

人工鱼群算法在寻优的过程中，可能会集结在几个局部最优解的周围，使人工鱼跳出局部最优解，实现全局寻优的因素主要有：

觅食行为中重复次数较少时，为人工鱼提供了随机移动的机会，从而可能跳出局部最优解；

随机步长使得人工鱼在前往局部最优解的途中，有可能转向全局最优解；

拥挤度因子 δ 限制了聚群的规模，使得人工鱼能够更广泛的寻优；

聚群行为能够促使少出陷于局部最优解的人工鱼趋向全局最优解的人工鱼方向聚集，从而逃出局部最优解；

追尾行为加快了人工鱼向更优状态游动。

各种参数对收敛性的影响

人工鱼群算法中，觅食行为奠定了算法收敛的基础；聚群行为增强了算法收敛的稳定性；追尾行为增强了算法收敛的快速性和全局性；其评价行为也对算法收敛的速度和稳定性提供了保障

人工鱼群算法有5个基本参数：群规模、人工鱼的视野、步长、拥挤度因子、重复次数

视野：由于视野对算法中个行为都有较大影响，因此，它的变化对收敛性能影响也比较复杂。当视野范围较小时，人工鱼的觅食行为和随机行为比较突出；视野范围较大时，人工鱼的追尾行为和聚群行为将变得比较突出，相应的算法的复杂度也会有所上升。总的来说：视野越大，越容易使人工鱼发现全局最优解并收敛

步长：对于固定步长，随着步长的增加，收敛的速度得到了一定的加速，但在超过一定的范围后，有使得收敛速度减缓，步长过大时会出现震荡现象而大大影响收敛速度。采用随机步长的方式在一定程度上防止了震荡现象的发生，并使得该参数的敏感度大大降低了，但最快的收敛速度还是最优固定步长的收敛速度，所以，对于特定的优化问题，我们可以考虑采用合适的固定步长或者变尺度方法来提高收敛速度。

群规模：人工鱼的数目越多，跳出局部最优解的能力越强，同时，收敛的速度也越快。当然，付出的代价就是算法每次迭代的计算量也越大，因此，在使用过程中，满足稳定收敛的前提下，应当尽可能的减少个图数目。

尝试次数：尝试次数越多，人工鱼的觅食行为能力越强，收敛的效率也越高。在局部极值突出的情况下，应该适当的减少以增加人工鱼随机游动的概率，克服局部最优解。

拥挤度因子：在求极大值问题中，；在求极小值问题中，。其中α为极值接近水平，为期望在该邻域内聚集的最大人工鱼数目。拥挤度因子与相结合，通过人工鱼是否执行追尾和聚群行为对优化结果产生影响。以极大值为例（极小值的情况正好与极大值相反），δ越大，表明允许的拥挤程度越小，人工鱼摆脱局部最优解的能力越强；但是收敛速度会有所减缓，这主要因为人工鱼在逼近最优解的同时，会因避免过分拥挤而随机走开或者受其他人工鱼的排斥作用，不能精确逼近极值点。可见，虽然δ的引入避免了人工鱼过度拥挤而陷入局部最优解，但是另一方面，该参数会使得位于极值点附件的人工鱼之间存在相互排斥的影响，而难以想极值点精确逼近。所以，对于某些局部极值不是很严重的具体问题，可以忽略拥挤的因素，从而在简化算法的同时也加快算法的收敛速度和提高结果的精确程度

人工鱼群算法的特点

只需比较目标函数值，对目标函数的性质要求不高；

对初值的要求不高，随机产生或设置为固定值均可，鲁棒性强；

对参数设定的要求不高，容许范围大；

收敛速度较慢，但是具备并行处理能力；

具备较好的全局寻优能力，能快速跳出局部最优点；

对于一些精读要求不高的场合，可以用它快速得到一个可行解；

不需要问题的严格机理模型，甚至不需要问题的精确描述，这使得它的应用范围得以延伸

代码

调库实现AFSA

AFSA输入参数

入参	默认值	意义
func	-	目标函数
n_dim	-	目标函数的维度
size_pop	50	种群规模
max_iter	300	最大迭代次数
max_try_num	100	最大尝试捕食次数
step	0.5	每一步的最大位移比例
visual	0.3	鱼的最大感知范围
q	0.98	鱼的感知范围衰减系数
delta	0.5	拥挤度阈值，越大越容易聚群和追尾

AFSA输出参数

afsa.best_x 最优函数值

afsa.best_y 最优函数值对应的输入值