基于约束优化问题的人工鱼群算法及其改进

孙王杰，卢月亮，孙书贝，巩晓悦

(1.吉林化工学院理学院，吉林吉林132022;2.吉林化工学院信息与控制工程学院，吉林吉林132022)

随着应用和需求的不断扩展，出现了一些新颖的优化算法，如人工神经网络、混沌、遗传算法、模拟退火、禁忌搜索等等.这些算法都是通过模拟或揭示某些自然现象或过程而得到发展的.在这期间群智能优化算法也得到了较快发展，如粒子群算法、蚁群算法等等.2002年，李晓磊博士通过研究鱼群的行为特点提出了一种新型的群智能优化算法-人工鱼群算法［1］.人工鱼根据环境的状态通过它的四种行为来寻找最优解［2］，其中4种行为分别是觅食行为、追尾行为、聚群行为和随机行为［3］.

本文改进了人工鱼的觅食行为，将人工鱼群算法与罚函数的理论结合来解决约束优化问题.另外引入了吞噬行为以便加快收敛速度，得到更优的适应度值.仿真结果表明改进的人工鱼群算法在解决约束优化问题时，具有收敛速度快、适应度值优、全局寻优性能强等优点，比基本人工鱼群算法具有更好的性能.

1 人工鱼群算法

1.1 人工鱼群算法简介

人工鱼(artificial fish，AF)是真实鱼的一个虚拟实体，用来进行问题的分析和说明.通过模拟鱼类的四种行为:觅食行为、聚群行为、追尾行为和随机行为，来使鱼类活动在周围的环境.这些行为可以在不同的情况下相互转换.

算法采用面对对象的技术重构人工鱼的模型，将人工鱼封装成变量和函数两部分.变量部分包括人工鱼的总数N/人工鱼的个体的状态X=(x1，x2，…，xn)［其中 xi(i=1，2，…，n)］为欲寻求的变量、人工鱼群移动的最大步长Step、人工鱼群的视野Visual、尝试次数Try_number、拥挤度因子 δ、人工鱼个体 i，j之间的距离 di，j=Xi－Xj.

函数部分包括人工鱼当前所在位置的食物浓度Y=f(X)(Y为目标函数值)、人工鱼的各种行为函数［觅食行为 Prey()、聚群行为Swarm()、追尾行为 Follow()、随机行为Move().及行为评价函数Evaluate()］.通过这种封装，人工鱼的状态可以被其他同伴所感知.

在寻优过程中，人工鱼是通过Visual来确定视野范围.当在视野范围内如果寻找到比现在食物浓度高的位置时，人工鱼将移动到那一位置.

其中X代表当前寻优的人工鱼，XV代表在当前人工鱼X的Visual内寻找到的下一点，Step是人工鱼的步长，Rand()是0到1上的随机数.

准确地来讲，人工鱼是通过它的四种行为在其Visual内寻找下一位置的.这四种行为分别是觅食行为、追尾行为、聚群行为和随机行为.

1.1.1 觅食行为

这是人工鱼的一种基本行动，也就是趋向食物的一种活动，一般我们认为它是通过视觉或味觉来感知水中的食物量或浓度进而来选择趋向的.

行为描述:设人工鱼i当前状态为Xi，在其感知范围内随机选择一个状态Xj

式中，Rand()是一个介于0和1之间的随机数，如果在求极大值问题中，Yi＜Yj(或求极小值Yj＜Yi)，则向该方向前进一步

反之，再重新随机选择状态Xj，判断是否满足前进条件，反复尝试Try_number次后，若仍不满足前进条件，则随机一定一步

1.1.2 聚群行为

鱼在游动过程中会自然的聚集成群，这也是为了保证群体的生存和躲避危害而形成的一种生活习性.

行为描述:在人工鱼群算法中对每条人工鱼做如下规定:一是尽量向邻近伙伴的中心移动;而是避免过分拥挤.

否则执行觅食行为.

1.1.3 追尾行为

鱼群在游动过程中，当其中的一条与或几条鱼发现食物时，其邻近的伙伴会尾随其快速到达食物点.

行为描述:追尾行为是一种向邻近的有着最高适应度的人工鱼追逐的行为，在寻优算法中可以理解为是向附近的最优伙伴前进的过程.设人工鱼 i当前状态为 Xi，搜索当前邻域内(dij＜Visual)的伙伴中Yj为最大值的伙伴Xj.，表明伙伴X的状态具有较高的食物j浓度并且周围不太拥挤，则朝Xj的方向前进一步

否则执行觅食行为.

1.1.4 随机行为

行为描述:

人工鱼在视野中随机选择一个状态，然后向该状态移动，其实是觅食行为的一个缺省行为.

这四种行为在不同条件下会相互转换，鱼类通过对行为的评价选择一种当前最优的行为进行执行，已达到食物浓度更高的位置，这是鱼类的生存习惯.

1.2 改进人工鱼群算法(IAFSA)

因为基本人工鱼群算法存在保持探索与开发平衡的能力较差、算法运行后期搜索的盲目性较大、寻优结果精度低和运算速度慢等缺点，影响了其搜索质量和效率.

1.2.1 改进视野和步长

一般来说，视野和步长的选择对算法的收敛速度有很大的影响.视野范围较大有利于搜索全局最优值，但是耗费的系统资源比较多.然而视野范围较小，耗费的系统资源较少，但是全局寻优就受到了限制.人工鱼群算法是使用自适应视野来寻优的［4］.在本文中，我们根据文献［4］的理论，引入自适应视野，并引入步长因子，

得到自适应步长.这样可以根据迭代次数改变，视野进行相应的改变，既节省了系统的资源，又增加了全局的寻优能力.

1.2.2 改进觅食行为

执行基本人工鱼群算法的觅食行为时，人工鱼在寻找到比当前位置较优的位置时，就向该位置的方向移动一步.但是基本人工鱼群算法突显出的问题是每次觅食行为中Try_number仅仅被执行了几次，这样大大的削弱了觅食行为的能力.基本觅食行为中人工鱼较优位置的方向上移动时不能确定移动到的那一位置比当前位置优，所以传统觅食行为既削弱了人工鱼的觅食能力，又浪费了系统的大量资源.针对传统觅食行为的缺点，我们对觅食行为进行改进.在完全执行Try_number次数之后，人工鱼直接移动到这一最优的位置.

1.2.3 添加吞噬行为

在改进觅食行为以后，我们可以引入吞噬行为来解决觅食行为执行时间变长的问题.吞噬行为是仿照自然界中优胜劣汰的规律进行改编的.在执行程序几次迭代后，较优的人工鱼把最不优的人工鱼吞噬掉，于是就节省了不优人工鱼的寻优时间.

2 人工鱼群算法求解约束优化问题

2.1 约束优化问题描述

约束优化最小化问题可以表示如下:

这里是x=(x1，…xn)T∈Rn是n维实向量，f(x)为目标函数，hi(x)为第i个等式的约束，gj(x)是第j个不等式的约束，xk变量在区间［，表示搜索空间.

2.2 改进的人工鱼群算法求解约束函数优化问题

在人工鱼群算法中每个人工鱼通过探索领域内伙伴的变化情况和目标函数的变化情况等环境状态从而从以上几种行为中选择一种执行经过若干次的迭代搜索最后人工鱼将聚集在极值的周围.算法步骤如下:

Setp1.初始化参数:人工鱼总数 M，视野Visual，步长Step，步长因子a，觅食行为的尝试次数Try_number，迭代次数t，人工鱼的初始位置等等.

Step2.选出在四种行为中适应度值最优的行为并执行.在M个人工鱼都执行行为之后.选出最优的人工鱼与公告牌上的人工鱼进行比较，人工鱼优于公告牌则将自身所有属性与公告牌上面的进行替换，反之保留公告牌属性.

Step3.进行吞噬行为，去掉最不优的人工鱼.

Step4.经过一次迭代之后保留公告牌的属性，更新人工鱼的数目.

Step5.如不满足终止条件，返回step.2.

Step6.输出人工鱼的各项参数及最优值的图.

3 仿真实验

使用matlab7.0软件，选取以下2个约束函数进行测试这些都是带有非线性约束的目标规划问题［5-6］，两个测试函数如下所示:

用基本人工鱼群和改进的人工鱼群测试函数(9)的结果如图1所示

图1 x1和x2的值

图1中可以看出，基本AFSA和IAFSA的x1和x2都满足大于0小于6的约束条件.从图2和图3中，我们可以清楚的知道IAFSA满足C1、C2两个约束条件的性能较强.图4中IAFSA的适应度值与文献［4］中提出的适应度值相等，并且从图4中我们可以看出改进的人工鱼群算法在第3次迭代时就获得了最优适应度值.

图2 基本AFSA和IAFSA满足约束条件c1的情况

图3 基本AFSA和IAFSA满足约束条件c2的情况

图4 基本AFSA和IAFSA的适应度值

图5 x1和x2的值

用基本人工鱼群和改进的人工鱼群测试函数(10)的结果如图5所示.

图5 x1和x2的值

图6 基本AFSA和IAFSA满足约束条件c1的情况

图7 基本AFSA和IAFSA满足约束条件c2的情况

图8 基本AFSA和IAFSA的适应度值

图5(a)和5(b)中我们可以看出，基本AFSA和IAFSA的x1和x2都满足大于0小于10的约束条件.从图6和图7中，我们可以清楚的知道IAFSA满足C1、C2两个约束条件的性能较强.图8中基本AFSA和IAFSA的最优适应度值都与文献［10］中提出的适应度值相等，并且从图8中我们可以看出改进的人工鱼群算法在第3次迭代时就获得了最优适应度值.而基本AFSA在第5次迭代才获得最优适应度值.

4 结 论

人工鱼群算法是一种相对新型的群集智能算法该文在描述了人工鱼群算法的基本原理的基础上研究了如何使用该算法解决约束函数优化问题.在基本人工鱼群算法的基础上，改进了人工鱼的觅食行为，另外引入了吞噬行为，加快了收敛速度，得到了更优的适应度值，具有更快的收敛速度，比基本人工鱼群算法具有更好的性能.

［1］ 李晓磊，钱积新.人工鱼群算法:自上而下的寻优模式［J］.系统工程理论与实践，2002，2(3):76-82.

［2］ 李晓磊.一种新型的智能优化方法——人工鱼群算法［D］.杭州:浙江大学，2003.

［3］ 李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式:鱼群算法［J］.系统工程理论和实践，2002，22(11):32-28.

［4］ 王锡淮，郑晓明，肖建梅.求解约束优化问题的人工鱼群算法［J］.计算机工程与应用，2007，43(3):40-42.

［5］ Yanbin Gao，Lianwu Guan，Tingjun Wang，et al.Research on the Calibration of FOG Based on AFSA”［J］.IEEE ICMA inter.Con.2013:412-417

［6］ Deb K.An efficient constraint handling method for genetic algorithms［J］.Computer Methods in Applied Mechanics and Engineering，2000，186(2):311-338.

［7］ Dong Ying，Tang Jia-fu，Xu Bao-dong，et al.An application of swarm optimization to nonlinear programming［J］.Computers and Mathematics with Applications，2005，49:1655-1668.