一种基于自适应能力改进的 AFSA 算法研究
摘要：文章在分析基本人工鱼群算法（AFSA）的基础上，提出了一种基于自适应能力的改进人工鱼群算法，在不明显增加算法计算复杂性的前提下，引入自适应移动和 visual、step 参数自适应调整策略，这对于克服算法优化后期收敛速度慢，感知和移动距离随机性大、寻优精度低等缺点具有显著效果。仿真测试表明，改进后的人工鱼群算法在很大程度上摆脱了局部极值吸引的能力，寻优精度明显提高。
关键词：基本人工鱼群算法；人工鱼群改进算法；自适应移动；自适应调整中图分类号：TP18 文献标识码：A 文章编号：1673-1131（2015）10-0047-03.
1 基本人工鱼群算法
基本人工鱼群算法（AFSA）是 2002 年由李晓磊博士提出[1,2]
的，通过观察鱼群，他提取了鱼的几种典型行为：觅食、聚群、追尾、随机行为，建立起了一种自下而上的寻优模式，即人工鱼群算法。
1.1 人工鱼模型
人工鱼是真实鱼的一个虚拟实体，通过感知周围环境，结合自身状态做出相应的应激行为。其感知模型[3]如下。 如图 1 所示，一条人工鱼的当前位置为 X，visual 代表人工鱼的感知距离，Xv 为此人工鱼在某时刻感知到的点。若 Xv食物浓度优于 X，则向该点方向前进一步，到达位置 Xnext ；否则，继续感知区域内其他点。感知过程可用如下式表示：
（1）
其中，rand() 函数的功能是产生 [0,1]区间内的随机数，step为人工鱼一次移动最大步长。 为 Xv 和 X 之间的距离。
感知次数越多，对周围环境越了解，越利于判断和决策下一步位置。当然，也不必遍历所有位置，允许人工鱼进行一定的不 确定性的局部寻优，对全局寻优是有利的。
1.2 人工鱼的基本行为
假设人工鱼个体的位置为 X=(x1，x2，…，xm) ，其中 xi(i=1，2，…，m)为寻优变量；人工鱼数量为N；人工鱼所在位置X的食物浓度为 Y=f(X)，食物浓度Y 即目标函数值；人工鱼i 和 j之间的距离 ；visual为人工鱼的感知距离；step为人工鱼一次移动的最大步长；try_count为人工鱼觅食行为最多尝试次数；为拥挤度因子。则人工鱼的基本行为可进行如下描述[4]。
（1）觅食行为。觅食行为是鱼类通过某些器官感知水中的食物浓度，进而选择趋向。设人工鱼的当前位置和对应食物浓度分别为 Xi 和 Yi=f(Xi) ，在感知区域内随机选择一个位置Xj ，若 Yj>Yi ，则向该方向前进一步；否则，再从感知区域内随机选择一个位置，判断食物浓度是否更优；随机选择 try_count次后，若仍找不到更优点，则随机移动一步。
（2）聚群行为。为了躲避敌害和保证生存，鱼在游动过程中会自然地聚集成群。AFSA 中规定人工鱼在向中心位置移动时，既要尽量向邻近伙伴的中心移动，又要避免过分拥挤。
设人工鱼当前在位置 Xi，感知范围内的同伴数目 n 及中心位置 Xc。若 Yc/n> · Yi 表明同伴中心位置食物浓度较高且不太拥挤，则朝该方向移动一步；否则，执行觅食行为。
（3）追尾行为。当一条鱼发现食物时，其附近的伙伴会快速游过来尾随其后。设人工鱼的当前位置 Xi，以及感知范围内所在位置食物浓度最高的同伴 Xj。若 Yj/n> · Yi，表明同伴Xj置食物浓度较高且不太拥挤，则朝该方向移动一步；否则，执行觅食行为。
（4）随机行为。鱼在水中游动时，时而前行，时而调转方向，可以认为这种随机行为是为了寻找伙伴或食物。随机行为其实是觅食行为的缺省行为，其算法描述非常简单，即感知区域内随机选择一个位置，并朝该方向移动一步。
1.3 算法流程 通过对人工鱼行为的分析可知，觅食行为是算法收敛的基础，聚群、追尾行为改善了算法收敛的速度和稳定性，随机移动则有助于算法跳出局部极值实现全局寻优。其流程图如下： 基本 AFSA 的执行过程可描述如下：
（1）初始化设置，包括设置算法的 visual 、step 、try_coun、等参数，确定人工鱼的数量 ，随机初始化人工鱼的状态；（2）初始化公告牌，将其状态设为初始人工鱼群的最优状态；（3）对每条人工鱼依次进行行为分析和评价，选择最优行为执行，并更新状态信息；（4）如果个体状态优于公告牌，更新公告牌信息为该个体状态；（5）判断是否满足终止条件，是则停止迭代输出寻优结果；否则转而执行步骤（3），继续下一次迭代。
2 自适应改进的人工鱼群算法
基本AFSA中visual、step 都是固定的，人工鱼的搜索范围取决于 visual 值，而 step 取值对算法收敛速度和寻优精度影响显著。在一定范围内，visual 、step 值越大，AFSA 在优化初期收敛速度越快，克服局部极值能力越强；但这也会在很大程度上造成算法优化后期收敛速度变慢，加上感知和移动距离的随机性，使得寻优精度大打折扣。针对这一问题，文章在不明显增加算法计算复杂性的前提下，引入自适应移动 0 和 visual、step 参数自适应调整 0 策略，提出了自适应的人工鱼群算法。
2.1 自适应移动
在基本 AFSA 中，采用随机移动方式，即步长为 step ·rand() ，会影响算法收敛速度和寻优精度。在此引入如式（2）所示的自适应移动策略。 式中，X 、Y 分别为人工鱼当前位置和对应食物浓度；Xv 、Yv 分别为目标位置和对应食物浓度。如此一来，人工鱼就会根据当前自身位置和目标位置的状态差异自适应地调整移动距离。两点间的状态差距，在不超过 step 的前提下，人工鱼移动距离越大，该策略对于算法初期加快收敛和后期精确寻优 具有明显改善。
2.2 自适应感知
通过改进，赋予人工鱼更多的智能，使其可以随着鱼群整体状态的变化自适应地调整自身的感知距离 visual 和移动步长 step 参数，使参数取值在前期收敛速度和后期寻优精度之间取得平衡，从而算法性能得到明显改善。具体改进思路如下：
（1）每次移动前，根据鱼群的状态，人工鱼自适应地获取visual；（2）引入视步系数确定步长，即step= ·visual （0 ＜ ≤1），为视步系数；（3）忽略对拥挤度的考虑，仅就食物浓度进行比较。
根据上述思想，AFSA 的参数由五个变为三个，感知距离visual 的获取转移到算法中，由人工鱼自行计算。0 算法优化初期，人工鱼散布在定义域中，彼此距离较远，此时较大的 visual 有助于加快收敛，并克服局部极值的束缚；而随着鱼群不断向极值点靠拢，彼此距离变近，此时减小 visua l有利于更快地找到全局极值点，提高寻优效率。
基于这一现象，对每条人工鱼，在尝试各种行为之前，先计算它到其它鱼的距离的平均值，以此作为它的 visual。基于平均距离 visual 的 Java 伪代码描述如图 3。
图 3 基于平均距离的代码描述
2.3 改进 AFSA 算法流程
引入自适应感知和移动策略[7]后，每条人工鱼被赋予了更多的对环境感知和应激的能力。在进行行为评价前，根据环境状态动态调整感知距离；在行为执行时，根据环境状态动态调整移动距离。改进的 AFSA 算法流程图如图 4 所示。 3 仿真测试为验证改进的 AFSA 的全局寻优性能，文章选取了三个标准测试函数基于 MATLAB 平台进行了实验。
（1）F1 函数：
（3）
图 5 F1 仿真结果三维效果图
从上图可以看出，函数在处取得全局极大值 1，且在定义域内散布着一些不是很突出的局部极值。
（2）F2 函数：
（4）
图 6 F2 仿真结果三维效果图
从上图可以看出，F2 函数是一个更为典型的多极值问题，在[0，0] 处有全局极小值 0，有无数多个局部极值。
在鱼群规模和迭代次数IT 相同的情况下，取系数 =1 ，尝试次数 try_count=1 ，分别利用 AFSA（visual=5, step=2 ）、AFSA1 运行 100 次，通过 100 次优化结果的最优值、最劣值、平均值、平均耗时以及收敛到阈值平均迭代次数对比各算法性能差异，实验结果如表 1 所示。实验中将采用基于平均距离的 visual 的 AFSA 标记为 AFSA1 从表中的数据可以看出，改进的 AFSA，在寻优精度上明显高于基本 AFSA，改进的 AFSA 具有很强的摆脱局部极值吸引的能力，寻优精度明显优于基本 AFSA。对于各参数对 AAFSA 的影响，经过多次实验验证和分析，得出如下规律：
（1）人工鱼数量 N ：由于个体智能的加强，N 的增加，对算法的寻优能力提高很大，但算法耗时的增加也十分明显。
（2）视步系数 ：引入该参数是为了抑制局部极值的影响。实验中， 取值等于或略小于 1，可保证算法性能稳定。
（3）尝试次数 try_count ：对于一般问题，适当增加 try_count ，有利于快速收敛和精确寻优，但对于局部极值突出的情况，则不利于人工鱼逃脱局部极值。
4 结语
文章从模型、原理、流程、优缺点等方面对基本人工鱼群进行了阐述和分析，针对基本人工鱼群算法的缺点，文章提出了感知距离和移动步长随算法的执行自适应调整，旨在解决算法后期收敛速度慢、寻优精度低的问题。经过测试函数的多次实验，设计和改进之后的自适应感知和移动的鱼群算法，具有很强的摆脱局部极值吸引的能力，寻优精度明显优于基本 AFSA。
参考文献：
[1] 邹康,刘婷，鲍韦韦.人工鱼群算法研究综述[J].研究与探讨,2012(2).
[2] 曲良东,何登旭.基于自适应高斯变异的人工鱼群算法[J].计算机工程,2009(8).
[3] 李晓磊.一种新型的智能优化方法——人工鱼群算法[D]杭州: 浙江大学,2003.
[4] 王宗利,刘希玉,王文平.一种改进的人工鱼群算法[J].信息技术与信息化,2010(3).
[5] 李跃松,樊金生,张巧迪.用改进的人工鱼群算法求解 TSP问题[J].石家庄铁道大学学报（自然科学版）,2011(6): 24.2.
[6] 马建伟,张国立,谢宏.利用人工鱼群算法优化前向神经网络[J].计算机应用,2004(10).
[7] 刘彦君.鱼群算法及在无线传感器网络覆盖优化中的应用[D].济南: 山东大学, 2009.
