分组进化人工鱼群算法

李辉

（福建水利电力职业技术学院 公共基础部数学教研室，福建 永安 366000）

分组进化人工鱼群算法

李辉

（福建水利电力职业技术学院 公共基础部数学教研室，福建 永安 366000）

针对人工鱼群算法搜索性能较差的缺陷，结合粒子群、蛙跳和人工鱼群算法的优点，文章提出了一种分组进化人工鱼群算法，该算法将人工鱼群算法简化后，仿照蛙跳算法进行分组进化，并加入粒子群算法的更新机制对个体位置进行更新，以便充分利用种群信息.实验证明，该算法有较强的寻优能力，且稳定性好，实用性强.

分组进化；拥挤度；觅食行为；寻优性能

优化算法是一种以数学为基础，求解各类实际问题最优值的技术.随着计算机技术的不断进步，优化技术得到了长足发展，已被广泛地应用到了众多领域.近年来，模拟生物行为的智能优化算法渐渐被众多学者所关注，智能优化算法较多，如粒子群算法、蛙跳算法、人工鱼群算法、蚁群算法、遗传算法等等.智能优化算法作为一种随机搜索算法，由于对初始值、梯度等信息没有过多要求，因而可以较好地解决具有复杂性、约束性、非线性、多极值等特点的工程问题，且这类算法容易与实际问题结合，应用领域非常广泛，如生产调度、系统控制、人工智能、模式识别和计算机工程等多种领域，如林智华[1]等利用粒子群算法研究数据中心网络流量调度，杨薪冉等[2]将蛙跳算法应用于船舶电力系统励磁控制，取得了良好的效果.

粒子群算法是Kennedy和Eberhart[3]于1995年提出的，它在每次迭代时记录群体最优和当前种群极优，并结合个体自身信息、历史最优个体信息和当前迭代中极优个体的信息对个体进行位置更新.算法在搜索过程中有极高的搜索速度，但算法在搜索后期容易陷入局部极值，特别是对于高维问题容易陷入“维度灾难”，无法搜索到最优值.针对该算法，很多学者进行了改进和应用研究：李胜等[4]将轨迹扰动因子引入粒子群算法，提高了算法的性能；冯浩等[5]采用自适应的惯性权重，改善了粒子群算法的搜索性能.粒子群算法是目前优化算法的研究热点之一.

人工鱼群算法是由李晓磊等[6]学者模拟鱼类行为提出的一种智能优化算法，它是群体智能思想的一个具体应用.人工鱼群算法模拟鱼群觅食行为，通过追尾行为、聚群行为和觅食行为对问题进行寻优，并利用拥挤度因子选择其中一种行为对个体进行位置更新，这种有针对性地选择个体行为的机制，有效地避免了算法陷入局部极值的缺陷.该算法由于其新颖的寻优机制，在提出后受到了很多学者的关注，但基本算法搜索机制相对复杂，搜索性能较差，特别对高维问题，寻优效果非常差，因而很多学者对算法的改进进行了研究：李小培等[7]在觅食、聚群、追尾行为中用历史全局最优人工鱼的位置和感知区域内较优位置的和向量，代替感知区域内较优位置，提高了算法的全局寻优能力；易新兵[8]采用具遍历性的组合映射产生复合混沌的局部搜索方法来跳出局部最优，取得了较好的效果；吴昌友[9]引入自适应步长和变异策略帮助算法跳出局部最优，提高了算法的性能；黄美华等[10]使用自适应步长代替原算法中的固定步长，提高了算法的收敛速度，并将改进算法应用到多目标背包问题中，取得了良好的效果；王丽等[11]通过引入视野递减反馈策略改进人工鱼群算法，平衡了算法的全局搜索和局部搜索能力，提高了算法的搜索精度；易正俊等[12]在算法每次迭代中不断加入新个体，并动态调整拥挤度因子的上限值，提高了算法的整体性能，等等.

蛙跳算法是由Eusuff和Lansey[13]在2003年提出的，它是模拟青蛙觅食的一种基于群体智能的启发式算法，它根据群体中个体的适应度大小，将种群分为若干小组，每个小组中的个体都按照从优到劣的顺序排列，每次迭代时，只对组内最差个体进行位置更新.由于蛙跳算法的搜索分组进行，相当于引入了并行搜索机制，因而有较高的搜索效率；同时经过若干次搜索后又将所有个体重新分组，整合了各小组之间的信息，体现了群体的协同工作性，因而有较快的搜索速度；但蛙跳算法每次只更新组内最差个体，未充分体现群体中每个个体的价值，也没有充分利用群体信息，因而容易陷入局部最优，同时在算法陷入局部最优的时候，没有跳出机制，影响了算法的性能.另外，对于多极值函数，蛙跳算法搜索精度也不高.该算法由于其机制简单、容易改造，方便与其它算法结合，也较容易应用到实际问题中去，因此，也成为目前关注的热点.

本文将粒子群算法、蛙跳算法和人工鱼群算法相结合，形成了一种新的优化算法——分组进化人工鱼群算法（grouping evolutionary artificial fish swarm algorithm，GEAFSA），这种组合算法充分利用了粒子群、蛙跳和人工鱼群算法的优点，避免了各算法的一些缺陷.实验证明，结合后的算法性能得到了很大的提高.

1 分组进化人工鱼群算法

分组进化人工鱼群算法仿照蛙跳算法，让种群分组进化，并将人工鱼群算法的思想简化为在个体不拥挤时执行追尾行为，在个体拥挤时执行觅食行为，同时，为了充分利用个体和各小组的信息，对人工鱼群算法中的追尾行为和觅食行为进行了改进：在追尾行为中，组内最优个体参照自身信息和全局最优个体信息进行位置更新，其余个体则仿照粒子群算法个体更新机制，参照自身信息、组内最优个体和全局最优个体信息进行位置更新，以保证充分利用群体信息，提高搜索性能；在觅食行为中，随机产生新个体，若新个体更优，则替代原个体，尝试若干次仍没有改进时，随机产生一个新的个体代替原个体.改进算法中的拥挤度是具体到组内的，组内的拥挤度用下式来计算，

其中，δ是组内拥挤度，fb为组内最优个体的适应度，fi为组内第i个个体的适应度，n为组内个体数.当组内过于拥挤时，组内所有个体执行觅食行为.组内进化若干次后，再将所有个体按适应度重新分组进行位置更新，直到找到最优解.

组内个体的位置更新由下述赋值表达式给出：

其中，xb为组内最优个体，g为种群全局最优个体，xi（i＝1，2，…，n，i≠b）为组内非最优个体，r1,r2,r3∈rand[0,1]，即，最优个体根据式（2）进行位置更新，而组内其余个体根据式（3）进行更新.

该算法的基本步骤如下：

Step1：初始化.在定义域内产生F＝m×n个可行解作为初始个体，其中m为子族群数，每个子族群中有n个个体；定义拥挤度δ0，尝试次数try number，全局搜索代数K和局部搜索代数L；

Step2：计算每个个体的适应度，按适应度从小到大排序，记录排在第一位的个体为全局最优个体，并将所有个体分为m组，即第km+i（k＝0，1，…，n-1；i＝1，2，…，m）个个体分配到第i组，循环分配直到所有个体都分配完毕；

Step3：判断局部搜索次数是否已经达到，若未达到，转Step4，否则，转Step5；

Step4：用式（1）计算组内个体的拥挤度，若拥挤度大于δ0，则说明组内不拥挤，按（2）更新组内最优个体，按式（3）更新组内其它个体；否则，针对每个个体，随机产生新解xnew，若xnew优于原个体，则用xnew代替原个体，否则不替换，尝试try number次后，若仍然没有找到更优个体，则随机产生新个体代替原个体.转step3；

Step5：判断全局搜索次数是否已经达到或全局最优解是否已达到要求的精度，若是，则停止，输出最优解；否则，转Step2.

分组进化人工鱼群算法的流程图见图1.

图1 分组进化人工鱼群算法的流程图Fig.1The flow chart of GEAFSA

2 实验分析

2.1 实验设计

为了对分组进化人工鱼群算法的寻优性能进行检验，本文选取四个测试函数，其中两个为单极值函数，两个为多极值函数.让本文算法及文献中的各种算法对这四个函数的全局最优值进行搜索，将它们的搜索速度和精度进行比较分析，以判断各算法寻优性能的优劣.四个测试函数由表1给出，其中“目标精度”按经验值取，函数 f2的全局最优点位于一个平滑、狭长的抛物线形山谷内，较难寻找，因而设置的搜索精度较低.

表1 用于测试各算法性能的函数Tab.1 The functions used to test the performances of various algorithms

本文尝试从以下几个方面对算法性能进行比较、分析：（1）比较本文算法（GEAFSA）与人工鱼群算法、粒子群算法、蛙跳算法和文献中的各改进算法在收敛精度固定时的搜索次数；（2）比较本文算法与人工鱼群算法在迭代次数一定时的搜索速度；（3）与参考文献中的改进算法的搜索精度进行比较；（4）分析各参数对本文算法的影响.

2.2 实验结果及分析

2.2.1 迭代次数的比较

各算法都选取30个个体种群，四种函数的维度和收敛精度的设定见表1，根据经验，设定参数为：局部搜索次数为5次，尝试次数try number为3次，拥挤度δ0为1.5，个体共分为5组.对于每个函数每个算法都独立运行20次搜索，记录每次搜索的相关数据，统计结果见表2.表2中“改进人工鱼群算法”为文献[10]提供的改进算法，“改进蛙跳算法1”为文献[11]提供的改进算法，“GEAFSA”为本文算法.表2中各算法的迭代次数均为算法全局搜索次数与局部搜索次数的乘积；成功率为达到目标精度的运行次数占实验总次数的比率；期望迭代次数＝粒子种群数×平均迭代次数÷成功率，相同参数下，成功率越接近1，算法稳定性越好，期望迭代次数越低，算法整体性能越好；表2中的“---”表示算法未搜索到要求精度下的最优值，“∞”表示无穷大.

表2 在目标精度下独立运行20次的统计结果Tab.2 The statistical results of 20 times independent runs under the target accuracy

从表2可以看出，本文算法可以在较少的迭代次数下，成功搜索到所有四个测试函数的全局最优解，期望迭代次数也比较低，整体性能比文献中的各种算法及其改进算法都有提高.

2.2.2 收敛速度的比较

将迭代次数固定为100次，人工鱼群算法和本文算法的收敛速度和精度如图1所示，AFSA曲线表示人工鱼群算法对四个函数的优化曲线，GEAFSA曲线表示本文算法对四个函数的优化曲线.为了便于观察，四幅图中横轴均为迭代次数，而纵轴均为算法适应度取以10为底的对数值.从中可以清楚地看出，本文算法搜索速度非常快，甚至在100步以内就搜索到了函数 f3和函数 f4的理论最优值，从GEAFSA曲线走势来看，曲线下降速度较快，函数 f3的曲线在平滑一段时间后，又有较快的下降速度，说明算法有跳出局部最优的能力.

图2 人工鱼群算法和本文算法对四个函数的进化曲线图Fig.2The evolution curves of four functions for the AFSA and GEAFSA

2.2.3 搜索精度的比较

在200次进化后，本文算法的收敛精度同文献中的改进算法的收敛精度的比较数据见表3，其中“改进蛙跳算法2”为文献[12]提供的改进蛙跳算法.由表3可以看出，本文算法对函数 f1、函数 f3和函数 f4搜索精度比相关算法都高，甚至可以搜索到理论最优值，对函数 f2的搜索结果较差，但比两种改进蛙跳算法的搜索结果要好些.

2.2.4 参数分析

本文算法中，拥挤度δ0和尝试次数try number这两个参数对算法性能有比较大的影响.拥挤度参数主要决定算法是否执行觅食行为，而具有随机性的觅食行为是本文算法跳出局部最优的主要机制.当拥挤度参数较小时，算法跳出局部最优能力很强，但是因为执行觅食行为过于频繁，算法稳定性比较差，很难向最优解靠拢，影响寻优速度；如果拥挤度参数值比较大，算法非常容易陷入局部最优，这是因为算法很难达到拥挤的要求而进行觅食行为，大量实验结果发现，拥挤度参数一般取值为1.5左右时效果较好.尝试次数决定觅食行为中是否有更多的机会搜索到较优新解，当它的值比较大的时候，搜索速度会加快，但不易跳出局部最优，太小的取值又很难寻找到较优解，大量实验结果发现一般取值3到5时较好.

表3 几种算法的精度比较Tab.3The accuracy comparison of several algorithms

3 结论

本文提出的分组进化人工鱼群算法，充分地结合了目前较流行的几种智能算法的优点，在迭代时仿照蛙跳算法进行分组进化，采用并行机制提高了算法的搜索速度，同时在更新个体位置时，仿照粒子群算法的更新机制，充分利用群体信息，并且利用人工鱼群算法的机制，通过拥挤度控制觅食行为，跳出局部最优.实验发现，该算法有较强的跳出局部最优和整体寻优能力，它的寻优性能比一些文献中提出的改进算法更好，寻优机制比基本鱼群算法更加简化，且参数少，易操作，鲁棒性强，具有很强的应用价值.但对某些函数，搜索效果较差，主要原因是算法在搜索后期，受到函数本身性态的影响，容易陷入局部最优，这需要更有效的跳出局部最优的机制，同时，研究更快速有效的搜索机制才能进一步提高算法的性能和实用性.

[1]林智华，高文，吴春明，等.基于离散粒子群算法的数据中心网络流量调度研究[J].电子学报，2016，44（9）：2197-2202.

[2]杨薪冉，杨鸣，侯庆伟.基于混合蛙跳算法的船舶电力系统励磁控制[J].船电技术，2016，36（8）：44-47.

[3]Kennedy J，Eberhart R C.Particle swarm optimization[C].In:Proc.of the IEEE Conf.on Neural Networks,IV.Perth:IEEE Press，1995：1942-1948.

[4]李胜，何明辉，李建林，等.嵌入层叠混沌策略的随机粒子群算法[J].模式识别与人工智能，2015，28（10）：953-960.

[5]冯浩，李现伟.带自适应变异的粒子群优化算法改进研究[J].洛阳师范学院学报，2015，34（11）：9-12.

[6]李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践，2002，22（11）：32-38.

[7]李小培，张洪伟，邹书蓉.基于全局人工鱼群算法的函数优化[J].成都信息工程学院学报，2014，29（S1）：5-9.

[8]易新兵，杨凯.复合混沌-人工鱼群混合算法的改进及性能研究[J].计算机工程与科学，2013，35（8）：89-95.

[9]吴昌友.一种新的改进人工鱼群优化算法[J].智能系统学报，2015，10（3）：1-6.

[10]黄美华，温洁嫦，何勇.求解多目标背包问题的改进人工鱼群算法[J].广东工业大学学报，2016，33（5）：44-48.

[11]王丽，芦彩林，宫建平.一种求解路径优化问题的新型人工鱼群算法[J].数学的实践与认识，2016，46（20）：199-207.

[12]易正俊，韦磊鹏，袁玉兴.自适应重生鱼群优化算法[J].计算机应用与软件，2016，33（6）：227-230；276.

[13]Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Water Resources Planning and Management，2003，129（3）：210-225.

[14]许恒迎，孙伟斌，张霞，等.自适应视野和步长的局部邻域人工鱼群算法[J].计算机工程与设计，2012，33（7）：2815-2821.

[15]林娟，钟一文，马森林.改进的反向蛙跳算法求解函数优化问题[J].计算机应用研究，2013，30（3）：760-763.

[16]赵鹏军，邵泽军.一种新的改进的混合蛙跳算法[J].计算机工程与应用，2012，48（8）：48-50.

责任编辑：吴兴华

Grouping Evolutionary Artificial Fish Swarm Algorithm

LI Hui
（Department of public foundation，Fujian College of Water Conservancy and Electric Power，Yong’an366000，China）

In view of the poor searching performance of the basic artificial fish swarm algorithm（AFSA）,we combine the advantages of particle swarm algorithm,leapfrog algorithm and artificial fish swarm algorithm to propose a grouping evolu⁃tionary AFSA（GEAFSA）.This algorithm is a simplified version of the AFSA.It takes grouping evolution after leapfrog algo⁃rithm and makes use of the updating mechanism of particle swarm algorithm to update the individuals’positions with com⁃plete group information.Experiments show that the GEAFSA has good optimization,stability and practicality.

grouping evolution；congestion；foraging behavior；optimization

O 224

：A

：1674-4942（2016）04-0373-06

10.12051/j.issn.1674-4942.2016.04.004

2016-09-14