人工鱼群算法综述.docx

人工鱼群算法综述.docx

《人工鱼群算法综述.docx》由会员分享，可在线阅读，更多相关《人工鱼群算法综述.docx（12页珍藏版）》请在冰点文库上搜索。

人工鱼群算法综述

人工鱼群改进算法研究综述

摘要：

人工鱼群算法源于对鱼群运动行为的研究，是一种新型的群体智能随机全局优化算法，人工鱼群算法（AFSA）起步较晚，还存在着许多不足之处。

因此本文主要通过阐述鱼群算法的基本理论的同时，对人工鱼群算法的改进方法进行文献综述，并根据这些改进方法指出了人工鱼群算法未来的改进与研究方向。

关键词：

人工鱼群算法算法改进综述

1.引言

1.1人工鱼群算法的基本概念

人工鱼群算法是李晓磊等[1]人于2002年提出的一种基于动物自治体[2-3]的优化方法,是集群智能思想[4]的一个具体应用，该算法根据水域中鱼生存数目最多的地方就是本水域中富含营养物质最多的地方这一特点来模拟鱼群的觅食行为而实现寻优。

它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工鱼个体的局部寻优行为,最终在群体中使全局最优值突现出来,有着较快的收敛速度[5]。

人工鱼群算法主要利用鱼的三大基本行为：

觅食、聚群和追尾行为，采用自上而下的寻优模式从构造个体的底层行为开始，通过鱼群中各个体的局部寻优，达到全局最优值在群体中凸显出来的目的[6]。

（1）觅食行为：

这是鱼趋向食物的一种活动，一般认为它是通过视觉或味觉来感知水中的食物两或食物浓度来选择行动的方向[6]。

（2）聚群行为：

大量或少量的鱼聚集成群，进行集体觅食和躲避敌害，这是它们在进化过程中形成的一种生存方式[6]。

（3）追尾行为：

当某一条鱼或几条鱼发现食物时，它们附近的鱼会尾随而来，导致更远处的鱼也会尾随过来[6]。

人工鱼群算法就是通过模拟鱼类的觅食、聚群、追尾等行为在搜索域中进行寻优的。

1.2人工鱼群算法的行为描述

觅食行为：

设置人工鱼当前状态，并在其感知范围内随机选择另一个状态，如果得到的状态的目标函数大于当前的状态，则向新选择得到的状态靠近一步，反之，重新选取新状态，判断是否满足条件，选择次数达到一定数量后，如果仍然不满足条件，则随机移动一步[6]。

聚群行为：

人工鱼探索当前邻居内的伙伴数量，并计算伙伴的中心位置，然后把新得到的中心位置的目标函数与当前位置的目标函数相比较，如果中心位置的目标函数优于当前位置的目标函数并且不是很拥挤，则当前位置向中心位置移动一步，否则执行觅食行为[6]。

追尾行为：

人工鱼探索周围邻居鱼的最优位置，当最优位置的目标函数值大于当前位置的目标函数值并且不是很拥挤，则当前位置向最优邻居鱼移动一步，否则执行觅食[6]。

根据所要解决的问题性质，对人工鱼当前所处的环境进行评价，从而选择一种行为。

较常用的评估方法是：

选择各行为中使得向最优方向前进最大的方向，也就是各行为中使得人工鱼的下一步状态最优的行为，如果没有能使下一个状态优于当前状态的行为，则采用随机行为。

1.3人工鱼群算法步骤[6]

Step1:

设定鱼群的参数，包括鱼群的规模m,最大迭代次数gen，人工鱼的感知范围Visual，最大移动步长step，拥挤度因子d等；

Step2:

在参数区间内随机生成m条人工鱼个体作为初始鱼群；

Step3:

计算每条鱼的食物浓度函数（目标函数），把最优的值放入公告板[7]中；

Step4：

对于每条人工鱼执行以下操作

（1）计算出追尾行为、聚群行为的值，采用行为选择策略，选择最优的行为作为鱼的移动方向，缺省行为是觅食行为。

（2）计算出每条鱼的食物浓度函数（目标函数），其最优值与公告板中的值进行比较，最终公告板中始终保持最优的值。

Step5:

判断是否满足结束条件，如果满足结束，否则转Step4。

最终公告板中的值就是最优值。

2.人工鱼群算法的改进

2.1初始化的改进

初始化种群是算法进行搜索的起点。

AFSA算法的初始种群生成是随机的，通常情况下可以保证初始鱼群分布均匀，但对于个体的质量不能保证，解群中有一部分远离最优解。

宋潇潇等[8]提出了基于极坐标编码的改进人工鱼群算法。

它通过设定编码规则，并将此编码方式运用到三种行为当中，计算出每一个编码母体获得的人工鱼的概率，选择大概率的母体作为算法初始化的起点，有效提高算法的收敛性。

曲良东等[9]利用混沌系统产生混沌变量，并在参数允许范围内随机产生各个人工鱼个体的初始状态。

陈广洲等[10]引入了免疫算法中的消亡算子，经算子运算更新，相互比较，摒弃非优个体，将其重新初始化，以此保持种群的多样性。

2.2算法参数的改进

王联国等[11]首先提出了一个全局版鱼群算法，并应用该算法对参数进行了详细的分析，实验表明步长step越小，求解精度越高，当step的值在1-6之间时，视野visual的值对于优化精度影响较小。

当step的值比较大时，随着visual值的增加，优化精度会震荡。

针对拥挤因子λ,实验表明该数值越小，鱼进行随机游动和觅食行为的几率较大，摆脱极值束缚的能力就会越强。

为了提高鱼群算法的求解能力和精度，王联国等[12-13]提出了一种动态参数调整的人工鱼群算法，使算法在早期能够进行较大范围的全局搜索，后期保证局部精细搜索。

文献提出的参数调整如公式如下：

实验证明引入该机制的鱼群算法，求解精度明显较原始鱼群算法有了较大的提高。

任彦军等[14]提出了在觅食行为过程中采用基于交换列表的排序法，在随机移动行为中采用自适应的小范围移动行为来改进人工鱼群算法，并应用在置换FlowShop调度，其仿真实验结果表明这种改进算法具有较强的全局搜索能力、更高的搜索效率。

李会等[15]依据学者韩江洪[16]在粒子群算法领域提出的自适应调整策略，将鱼群根据个体鱼适应值和鱼群平均适应值进行比较，根据比较结果将鱼群分为三组：

较优鱼群，一般鱼群和较差鱼群。

并由此提出了自适应调整人工鱼群算法参数的方法，该方法采用个体鱼适应值与整个鱼群的平均适应值作比较，将整个鱼群分为三组，再采用自适应调整每组鱼群的视野范围和步长的方法，对基本鱼群算法进行了优化和改进。

结果表明改进后的算法能够较快地收敛至全局较优解，并具有较好的寻优性能。

XiaoJianmei[17]采用另一种方法实现自适应参数调整，使步长step、视野visual、拥挤因子δ等参数随着计算的进行自动调整，以保证算法后期能够进行精细的局部搜索，提高算法的求解精度。

它运用适应值变化率和变化方差来决定是否进行参数的调整。

该文献将自适应鱼群算法（AAFSA）与原始鱼群算法、自适应粒子群算法、模拟退火粒子群算法进行了对比，其搜索范围和求解精度明显优于其它算法。

王冬冬等[18]提出了分段优化的思想，令食物浓度η为分界线，大于η时，为前期过程，采用较大的step和Visual，能使算法较快地得到一个相对较优的解;小于η时为后期过程，采用较小的step和Visual，得到一个精度更高的解。

黄华娟等[19]通过在人工鱼群的搜索过程中引进自适应的改变步长和拥挤度因子，其目的是加快算法的收敛速度，当寻优陷入平坦区时，对陷入的人工鱼以一定的概率对其变量加以扰动，使部分人工鱼改变状态，从而进入解空间的其他区域进行搜索，避免陷入局部最优。

2.3与其他算法结合的改进

2.3.1与模拟退火算法的结合改进

借鉴其他的智能算法的优点，进行优势互补是群体智能算法进行改进的一种有效手段。

张梅凤等[20]首先在AFSA中引进了变异算子，预先设置一个阈值beststep标记公告板上的最优值，如果在一定的迭代次数内，公告板上的最优值没有变化或者变化率极小，则在保留当前最佳个体的情况下，以一定的概率对于其它个体进行变异操作。

通过引入类似于遗传算法的变异操作之后，为了提高鱼群算法的求解精度，作者将鱼群算法的后期改为执行模拟退火（SA），利用低温下SA算法几乎概率1的收敛能力，进行精细解局部搜索。

该算法较原始人工鱼群算法有较好的跳出极值能力和较高的求解精度。

张梅凤等[21]针对人工鱼群算法求解多峰函数时难以发现全部最优的弱点，将小生境技术和模拟退火技术融入人工鱼群算法之中，同时加入变异算子和小生境半径自动生成机制，实验结果表明算法在求解多峰函数时非常有效；刘佳等借鉴模拟退火算法中的Metropolis判别准则改进了人工鱼的觅食行为，在利用人工鱼全局寻优的同时并利用模拟退火算子实施局部细化，提出了一种改进的人工鱼群优化算法（SA_IAFSA），保持了AFSA算法简单、易实现的特点，克服了人工鱼漫无目的随机游动以及容易陷入局部最优值的缺点，显著提高了算法的运行效率和求解质量。

2.3.2与遗传算法的结合改进

刘白等[22]针对人工鱼群算法（AFSA）在实际应用中出现的问题，提出了基于遗传算法的人工鱼群（AFSA）优化算法，当最优值连续无变化或变化不明显时采用遗传算法的交叉、变异操作，消除人工鱼漫无目的随机游动或大量聚集在非全局极值点附近的局限。

该算法不仅保持了人工鱼群算法（AFSA）简单、易实现的特点，而且提高了算法的运行效率和求解质量。

实验结果表明，该算法改善了人工鱼群算法（AFSA），且有效可靠，能够较好地解决优化问题。

Zi-xiaChen[23]等研究了将人工鱼群算法和遗传算法结合起来解决车辆调度问题，并发现组合的算法可以更快速的解决问题并保持性能的稳定等特征。

2.3.3与粒子群的结合改进

曲良东等[24]将进化策略和粒子群进化规则引入鱼群算法中，并通过理论证明了该算法的全局收敛性，同时通过Benchmark函数实验和应用于非线性参数估计问题中，证实了该算法收敛速度快，求解精度较高。

刘凌子等[25]通过研究文化算法和鱼群算法的机制，提出了一种将鱼群算法嵌入到文化算法框架内的混合鱼群文化算法该算法中包含两个空间，一个是种群空间内的鱼群算法，鱼群在进化过程中不断获取知识，将其组成一个知识空间，从而使知识空间与种群空间协同进化。

罗德相等[26]将种群分为两部分，一部分运用粒子群算法，一部分运用鱼群算法，将二者比较后的最优值赋予公告板，以此提高收敛速度。

其中的鱼群算法借鉴王联国等[12]的参数处理方式，通过5个Benchmark函数实验证明该算法的求解精度明显较原始粒子群算法和原始鱼群算法高。

Hsing-ChihTsai[27]等利用粒子群算法重新规划表示人工鱼群算法，并且将通信行为整合到人工鱼群算法中，从而形成新的人工鱼群参数公式。

因为visual和step支配这人工鱼群算法，然而它们又难以设置，因此利用粒子群算法重新规划修改鱼群算法可以使step更加自由，从而优化人工鱼群算法。

李亮等[28]通过邻域禁忌搜索，构造两点禁忌寻优算子对解空间进行无重复的搜索，以此来跳出局部最优点，确保算法的高效性。

2.3.4与蚁群算法的结合改进

高德芳等[29]提出鱼群－蚁群算法的概念，将蚁群算法融入ASFA中，并运用于模块化产品配置设计，混合鱼群-蚁群算法充分利用了各自的优势增强了算法在解空间的搜索能力和效率。

修春波等[30]分析了蚁群和鱼群两种优化算法的寻优机理，通过类比揭示了两种优化算法中寻优个体在寻优过程中所遵循的运动规律的差异。

并将鱼群算法中拥挤度的作用引入到蚁群算法中，提出了一种新的混合优化算法。

在优化过程中拥挤度的指导作用逐渐减弱，既克服了蚁群算法初期可能出现的早熟等现象，增强了算法遍历寻优的能力，又使得算法具有较快的收敛速度，提高了算法的寻优性能。

2.3.5与聚类算法的结合改进

刘薇等[31]针对传统K-means聚类算法存在的缺陷，引进人工鱼群算法，提出了一种基于改进鱼群和K-means的混合聚类算法。

聚类样本中心点初始化时，人工鱼各维参数随机选择在对应属性两个极值之间，同时为了降低计算复杂度，提高收敛效率，寻找全局最优，首先对随机选取的一小部分人工鱼进行K-means操作，然后对全体人工鱼的追尾算子引入粒子群策略，引导其学习，模拟人工鱼的行为。

WangFei[32]等将人工鱼群算法结合K-means算法用于机场容量聚类分析解决随机模型问题，从而证实了人工鱼群算法的可行性。

WeilingZhu[33]将人工鱼群算法和模糊C-mean算法结合起来用于聚类分析，发现者能够提高聚类的效率，使结果更加精确和稳定。

并且发现人工鱼群算法的参数在很大的程度上影响着效率，人工鱼群算法参数的效率将是以后研究的一个热点。

LiXiao[34]YongmingCheng[35]等也研究了将聚类算法和人工鱼群算法结合起来进行改进。

2.4与其他技术结合的改进

YazdaniD[36]将模糊理论与人工鱼群算法融合提出了一种模糊自适应的人工鱼群算法。

黄光球等[37]利用有限马尔科夫链理论分析了鱼群算法的进化过程，得出结论鱼群算法是全局渐进收敛的。

张红霞[38]在鱼群算法的后期每隔一定的代数，引入一次单纯形算子，替换掉原来大量聚集在非极值点附近的人工鱼个体，有效提高了局部搜索精度，提高了解质量。

曲良东等[39]文针对基本人工鱼群算法的不足，提出了一种基于单纯形的双群人工鱼群算法，在该算法中，两个不同的子群并行游动，通过子群重组进行子群问的信息交换，实现鱼群在解空间的探索和搜索能力，然后通过单纯形进行局部再搜索,表明该算法收敛速度快、精度高，具有更好的性能。

戴上平等[40]提出了一种多鱼群协同的人工鱼群算法，并用于实现对连续空间变量的分类规则提取问题。

班晓娟等[41]在基于认知的人工鱼行为模型的基础上，增加实现鱼群个体问通信及鱼群与环境交互的互操作行为模块，建立面向群体行为的人工鱼体系结构与模型。

提出了一种基于多Agent的人工鱼群自组织行为的研究方法：

将基于这种体系结构的人工鱼作为Agent，其能感知环境信息，产生意图，规划行为。

但是只考虑到影响个体鱼集群的几个因素，事实上还有很多生理、心理、遗传等因素需要考虑，同时人工鱼群作为整体，还存在着个体间通信、合作捕食关系等。

GenrangZheng[42]等将第一启发式算法和人工鱼群算法结合来形成混合人工算法用于解决组合拍卖的赢家决策问题，并且发现混合人工鱼群算法在赢家决策问题上是一种快速且有效的算法。

同时也发现和蚁群算法相比，混合人工鱼群算法性能更好，应用也更加广泛。

YongquanZhou等[43]也提出也一种将人工鱼群算法Hooke-Jeeves方式结合起来的基于变异算子的混合人工鱼群算法，用于解决非线性方程组问题。

实验结果表明，该混合算法在效果和效率方面显著优于经典的数值方法和标准的人工鱼群算法。

2.5增加群体多样性的改进

马勇杰等[44]研究表明采取一定的策略保持种群多样性是提高算法求解能力的重要途径。

王培崇等[45]提出了一种小生境人工鱼群算法，针对K-Means算法对于初始k值较敏感和容易过早收敛的问题，提出基于人工鱼群机制的K-Means聚类算法（NAFS）。

首先，利用先验知识随机产生待求解问题的若干个聚类中心，组成一个鱼群环境；其次，利用鱼群个体的协作、竞争机制寻找满意的结果。

鉴于人工鱼群算法后期容易陷入局部最优，根据鱼群聚集度引入小生境算法，改善种群的多样性，提高了算法的求解精度。

王培崇等[46]为了克服人工鱼群算法容易收敛于局部最优和解精度不高的缺点，提出了一种新的小生境人工鱼群算法（NAFS）。

在算法后期根据鱼群聚集程度引入小生境排挤机制，维持种群的多样性。

利用压缩映射定理从理论上证明了该算法的全局收敛性，证明该算法的解精度比原始人工鱼群算法有较大的提高。

刘凌子等[25]提出一种基于人工鱼群和文化算法的新型混合全局优化算法，该混合算法的思想是将人工鱼群嵌入文化算法框架中，作为种群空间的一个进化过程；通过从进化种群中获得的知识组成知识空间，两空间具有各自群体并独立并行演化，从而实现增加人工鱼群的群体多样性。

黄华娟[47]提出一种基于变异算子的人工鱼群混合算法，其中Hooke-Jeeves的强局部搜索能力提高了人工鱼群混合算法的局部收敛速度,变异算子的引入增加了群体的多样性,避免人工鱼群混合算法陷入局部最优。

3.总结与展望

作为一个前沿性的热点研究领域，人工鱼群算法已引起越来越多国内研究者的关注，但因人工鱼群算法（AFSA）起步较晚，与遗传算法、神经网络、蚁群算法、粒子群算法和免疫算法相比，人工鱼群算法理论还不完善、不成熟，研究处于初步阶段，在今后的工作中，还有很多方面有待进一步的探索和研究：

（1）人工鱼群算法的理论研究

人工鱼群算法的理论研究还存在许多问题需要进一步解决，比如初始化参数

选择问题、收敛速度问题等，这些均带有经验性和直觉性，至今没有经过严格的

数学论证。

今后人工鱼群算法的收敛性证明和理论分析仍然是一个非常具有挑战性的研究方向。

（2）人工鱼群算法的改进研究

人工鱼群算法因处于初步阶段，因此其算法的改进仍是目前研究的一大重要方向。

根据目前的研究可知对人工鱼群算法在初始化、参数、与其他方法的结合和群体多样化方面的改进仍需积极探索与完善。

特别是研究人工鱼群算法与其他智能算法和的融合技术，能够提高算法优化性能，因此研究人工鱼群算法与模拟退火算法、遗传算法、粒子群算法、蚁群算法等智能优化算法的融合技术，对智能算法的研究具有重要意义。

参考文献

[1]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:

鱼群算法[J].系统工程理论与实践,2002,22（11）:

32-38.

[2]MAESP.Fromanimalstoanimats4:

Proceedingsofthefourthinternationalconferenceonsimulationofadaptivebehavior[M].TheMITPress,1996.

[3]DEANJ.Animatsandwhattheycantellus[J].TrendsinCognitiveSciences,1998,2

（2）:

60-67.

[4]BONABEAUE,THRAULAZG.Swarmsmarts[J].ScientificAmerican,2000,282（3）:

72-79.

[5]李晓磊,钱积新.人工鱼群算法自下而上的寻优模式[C][J].过程系统工程年会论文集,2001,82（

[6]李晓磊.一种新型的智能优化方法-人工鱼群算法[D][D];杭州:

浙江大学,2003.

[7]李晓磊,路飞,田国会,etal.组合优化问题的人工鱼群算法应用[J].山东大学学报:

工学版,2004,34（5）:

64-67.

[8]宋潇潇,孙棣华,解佳.基于极坐标编码的改进人工鱼群算法[J].系统工程与电子技术,2010,32（10）:

[9]曲良东,何登旭.一种混沌人工鱼群优化算法[J].计算机工程与应用,2010,46（022）:

40-42.

[10]陈广洲,汪家权,李传军,etal.一种改进的人工鱼群算法及其应用[J].系统工程,2009,27（12）:

105-110.

[11]王联国,施秋红.人工鱼群算法的参数分析[J].ComputerEngineering,2010,36（24）:

[12]王联国,洪毅,赵付青,etal.一种简化的人工鱼群算法[J].小型微型计算机系统,2009,30（8）:

1663-1667.

[13]王联国,洪毅,赵付青,etal.一种改进的人工鱼群算法[J].

[14]任彦君,黎冰,顾幸生.改进的人工鱼群算法在置换FlowShop调度中的应用[J].华东理工大学学报（自然科学版）,2010,1（019.

[15]李会,张天丽,陶佰睿,etal.动态分组方案的自适应人工鱼群算法[J].计算机工程与应用,2013,8）:

[16]韩江洪,李正荣,魏振春.一种自适应粒子群优化算法及其仿真研究[J][J].系统仿真学报,2006,18（10）:

2969-2971.

[17]XIAOJ,ZHENGX,WANGX,etal.Amodifiedartificialfish-swarmalgorithm;proceedingsoftheIntelligentControlandAutomation,2006WCICA2006TheSixthWorldCongresson,F,2006[C].IEEE.

[18]王冬冬,李哲,梁丽,etal.基于改进人工鱼群算法求解多元非线性方程组;proceedingsofthe2009年中国智能自动化会议论文集（第一分册）,F,2009[C].

[19]黄华娟,周永权.改进型人工鱼群算法及复杂函数全局优化方法[J].广西师范大学学报:

自然科学版,2008,26

（1）:

194-197.

[20]张梅凤,邵诚,甘勇,etal.基于变异算子与模拟退火混合的人工鱼群优化算法[J].电子学报,2006,34（8）:

1381-1385.

[21]张梅凤,邵诚.多峰函数优化的生境人工鱼群算法[J].控制理论与应用,2008,25（4）:

773-776.

[22]刘白,周永权.基于遗传算法的人工鱼群优化算法[J].计算机工程与设计,2008,29（22）:

5827-5829.

[23]CHENZ-X,LUY-M.ResearchonVehicleRoutingProblembasedonhybridartificialfish-schoolandgeneticalgorithm;proceedingsoftheComputerApplicationandSystemModeling（ICCASM）,2010InternationalConferenceon,F,2010[C].IEEE.

[24]曲良东,何登旭.混合变异算子的人工鱼群算法[J][J].计算机工程与应用,2008,44（35）:

50-52.

[25]刘凌子,周永权.一种基于人工鱼群和文化算法的新型混合全局优化算法倡[J].计算机应用研究,2009,26（12）:

[26]罗德相,周永权,黄华娟.粒子群和人工鱼群混合优化算法[J].计算机与应用化学,2009,26（10）:

1257-1261.

[27]TSAIH-C,LINY-H.Modificationofthefishswarmalgorithmwithparticleswarmoptimizationformulationandcommunicationbehavior[J].AppliedSoftComputing,2011,11（8）:

5367-5374.

[28]李亮,迟世春,林皋.禁忌鱼群算法及其在边坡稳定分析中的应用[J][J].工程力学,2006,23（3）:

6-10.

[29]高德芳,赵勇,郭杨,etal.基于混合鱼群-蚁群算法的模块化产品配置设计[J].机械,2007,34

（1）:

9-12.

[30]修春波,张雨虹.基于蚁群与鱼群的混合优化算法[J].计算机工程,2008,34（14）:

206-207.

[31]刘薇,刘柏嵩,王洋洋.基于改进鱼群和K-means的混合聚类算法[J].ComputerEngineeringandApplications,2013,49（22）:

[32]FEIW,XIAO-HAOX,JINGZ.Applicationof