基于MATLAB的人工鱼群混合改进算法

胡振，杨华

基于MATLAB的人工鱼群混合改进算法

胡振，杨华

针对群体智能优化算法普遍存在的容易早熟、收敛较慢等缺陷，提出了一种人工鱼群混合改进算法。在算法中对人工鱼的状态施加Cauchy变异算子，以增强鱼群的全局搜索能力；同时融入非线性规划函数，使其局部搜索能力也得到改善。用MATLAB编程实现该算法，并用3个标准函数进行测试，结果表明其精度与收敛速度皆比基本人工鱼群算法有显著提高。

人工鱼群算法；柯西变异；非线性规划；标准函数

0 引言

群体智能优化算法广泛应用于机器学习、信号处理、模式识别、组合优化、控制系统设计等领域，包括遗传算法、粒子群算法、蚁群算法、人工蜂群算法、人工鱼群算法等，它们虽然在智能计算中显示了无与伦比的优越性，但也共同存在着明显缺陷：其一为容易陷入局部最优，从而引发“早熟”现象；其二是搜索效率低，使得收敛速度较慢。研究者们对此提出的改进方案主要有两种思路：一是对算法本身进行改进，如在遗传算法中改进编码方法、自适应算子概率、引入精英策略[1-2]，粒子群优化算法中自适应控制最优位置、惯性权重和学习因子的动态调整[3-4]，蚁群算法中信息素更新方式与信息素挥发因子的自适应改进[5-6]等；二是在算法中融入其它方法构成混合算法，如蚁群算法中引入粗糙集[7]、粒子群优化算法与共轭梯度法结合[8]、量子行为粒子群优化算法中嵌入非线性规划[9]等。本文以人工鱼群算法为研究对象，综合应用上述两种思路对其进行改进，得到一种融入Cauchy变异算子和非线性规划函数的人工鱼群混合改进算法。

1 基本人工鱼群算法

人工鱼群算法[10](Artificial Fish Swarm Algorithm，AFSA)是根据鱼类活动特点提出的一种基于动物行为的自治体寻优方法，具有良好的求取全局极值的能力，且对初值和参数选择不敏感，简单、易实现、鲁棒性强、可并行处理。

1.1 算法描述

AFSA初始化一个人工鱼群，通过迭代搜寻最优解。在每次迭代过程中，人工鱼通过下列行为更新自身状态：

（1）随机行为

人工鱼随机移动的行为。Xi在视野范围内随机选择一个状态，然后向该方向移动一步。该行为可用如下函数如公式（1）：

式(1)中：rand()为[0,1]区间的随机数。

（2）觅食行为

人工鱼循着食物多的方向游动的一种行为。Xi在其视野内随机选择一个状态Xj，分别计算其目标函数值Yi、Yj并进行比较，若Yj比Yi优，则Xi向Xj方向移动一步；否则，Xi继续在其视野范围内随机移动、选择状态Xj，判断是否满足前进条件…，反复尝试trynumber次之后，若仍未满足前进条件，则执行随机行为。可用函数表示如公式（2）：

（3）聚群行为

人工鱼在游动过程中尽量向临近伙伴的中心移动并避免过分拥挤的一种寻优行为。Xi搜索其视野内的伙伴数目nf及中心位置Xc，若Xc较优且不太拥挤，则Xi向Xc移动一步，否则执行觅食行为。可表示为如下函数如公式（3）：

（4）追尾行为

人工鱼向视野范围内的最优方向移动的一种行为。Xi搜索其视野内的最优伙伴Xo，若Xo的周围不太拥挤，则Xi向Xo移动一步，否则执行觅食行为。其函数表示如公式（4）：

式（1）~（4）描述的是求最小值问题（最大值问题可转换为最小值问题）。实际应用时，根据所要解决问题的性质，人工鱼对当前所处环境进行评价，即模拟聚群、追尾等行为，从中选择行动后食物浓度最小者实际执行，缺省为觅食行为。

1.2 问题的解决

问题的解决是通过自治体在自主活动过程中以某种形式表现出来的。在寻优过程中，通常会有两种形式：

一种形式是通过人工鱼的最终分布情况来确定最优解的分布。通常随着寻优过程的进行，人工鱼往往会聚集在极值点的周围，而且全局最优的极值点周围通常能聚集较多的人工鱼；

另一种形式则在人工鱼个体状态中表现出来，即在寻优过程中，跟踪记录最优个体的状态。

2 人工鱼群算法的改进

AFSA的不足之处主要有：（1）算法获取的是满意解域，对于精确解的获取还需进行适当改进；（2）若寻优的域较大或处于平坦区域，则部分人工鱼会处于无目的随机移动状态，这将影响寻优效率，容易陷入局部最优；（3）算法的参数较多，且取固定值，致其收敛速度在初期较快、后期则往往减慢。

2.1 现有的改进方案

2.1.1 对AFSA本身的改进

大多数改进措施都着眼于AFSA内部，如：在算法中引入生存机制和竞争机制，使用公告板，加入变异算子，动态调整视野、步长和拥挤度因子，运用分区域搜索、深度优先遍历技术，采取分阶段、变参数寻优策略，……，等等。具体改进方案多为其中数项措施的组合。

2.1.2 AFSA与其他方法的融合

AFSA与其他技术、方法融合即构成混合优化算法，已经提出的融合方案有：AFSA与模拟退火算法，AFSA与小生境技术，AFSA与禁忌搜索算法，AFSA与遗传算法，……等等。

2.2 基于MATLAB的人工鱼群混合改进算法

本文针对AFSA的缺陷，提出一种基于MATLAB的混合改进算法。其主要思路为：（1）在AFSA中引入Cauchy变异算子，增强其全局寻优能力；（2）在此基础上融入非线性规划函数，提高算法的局部搜索效率，加快其收敛速度。通过这两种措施的综合作用，显著改善算法的计算精度和寻优速度。

2.2.1 在AFSA中引入Cauchy变异算子

Cauchy分布具有两翼较长的概率特性，它比Gaussian分布的范围更宽，很容易产生远离原点的随机数。因此，在AFSA的迭代过程中，当人工鱼选择执行某种行为后，对其当前状态增加Cauchy分布随机数扰动项作为变异算子，可保持人工鱼群的多样性，减少其陷入局部最优的可能性，从而增强算法的全局搜索能力，防止发生早熟现象。相应的改进公式为公式（5）：

公式（5）中： π(tan( -0))5. *rand()可得标准Cauchy分布随机数，其中rand()为[0,1]区间的均匀分布随机数；Xi为人工鱼的当前状态。

需要注意的是，这种改进策略可能导致人工鱼超出优化变量取值范围的几率增加，故应随之进行粒子越界处理。

设增加Cauchy变异算子后的人工鱼状态为Xi，优化变量取值范围为[rl,rr]，则越界处理为公式（6）：

AFSA经过如此改进后，可称之为C-AFSA。

2.2.2 将非线性规划函数融入算法

C-AFSA的全局搜索性能有了显著增强，但其局部搜索能力尚待改善。为此，我们再在C-AFSA中融入非线性规划函数，构成一种混合改进算法，称之为CN-AFSA。

非线性规划

（1）非线性规划（Nonlinear Programming）研究n元实函数在一组等式或不等式约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。其一般形式为公式（7）：

（2）C-AFSA中融入非线性规划函数

求解非线性规划问题的经典算法皆以梯度下降法为基础，其特点是局部搜索能力较强。因此，将C-AFSA与非线性规划结合，可增强算法的搜索能力，提高计算精度，并加快收敛速度。

Matlab提供了求解非线性规划问题的函数fmincon()，可从一个预估值开始搜索约束条件下多元非线性函数的最小值。其约束条件如下：

其中：x为变量，A、b为线性不等约束，Aeq、beq为线性相等约束；c、ceq分别为非线性不等约束和非线性相等约束；lb、ub分别为x的下界与上界。x、b、beq、lb和ub是向量，A和Aeq为矩阵，f(x)、c(x)和ceq(x)为非线性函数。

fmincon()函数的调用格式为：

式（7）中：fun为目标函数，x0为x的初设值，lb、ub为x的下界和上界，其余参数则可缺省。

将非线性规划函数嵌入C-AFSA中即构成CN-AFSA：令C-AFSA每迭代10次即执行1次非线性规划，调用时将人工鱼的当前状态传递给fmincon()函数的参数x0，以此为初设值进行局部搜索，从而提高算法的精度和速度。

2.2.3 CN-AFSA的执行流程

Step 1 在目标搜索空间初始化人工鱼群。

Step 2 各人工鱼分别模拟追尾行为和聚群行为，选择目标函数值较优的行为实际执行，缺省行为方式为觅食行为。

Step 3 对人工鱼的状态按式(5)实施变异，并进行越界处理。

Step 4 若当前迭代次数为10的倍数，则调用非线性规划函数。

Step 5 如果尚未满足终止条件（达到最大迭代次数或预定的误差范围），则重复执行Step 2~4；否则执行Step 6。

Step 6 算法终止，输出最优解。

3 算法测试

我们在Windows XP系统环境中用MATLAB编程实现了本文提出的人工鱼群混合改进算法，选用3个有代表性的标准函数测试其有效性，并在相同条件下用AFSA和C-AFSA进行对比测试，以分析基本人工鱼群算法与改进算法在优化精度、收敛速度和鲁棒性等方面的差异。

3.1 标准函数选择

（1）Schaffer F6

具有强烈振荡的二维多峰函数，最小值附近有无数局部极小点，在(0,0)处有最小值0。

（2）Rastrigin

高维多峰函数，有很多局部极小点，在(0,0,…,0)处有最小值0。

（3）Griewank

非线性多模态函数，有许多局部极小点，数目与问题的维数有关，在(0,0,…,0)处有最小值0。

3.2 测试结果分析

用3个标准函数对AFSA及其改进算法进行测试时，运行参数都设置为：人工鱼群群规模50，最大迭代次数100；觅食时最多试探次数30，视野、步长和拥挤度因子分别为1、0.1和0.618。以函数值小于10-5为优化目标，分别独立运行50次，所得结果如表1所示：

表1 标准函数测试结果

图1 Griewank函数寻优的迭代过程

另两个函数的迭代过程与之相似。

表1的结果表明：当人工鱼群规模不大、迭代次数较少时，AFSA不能收敛到预设的优化目标值，且其寻优结果与理论值相差甚远；C-AFSA则显著改善了寻优效果，3个标准函数都能部分达到预设的优化目标；CN-AFSA进一步提高了计算精度，不仅其寻优结果已非常接近理论最小值，且其稳定性更好，收敛速度大为加快。

4 总结

本文提出了人工鱼群算法的一种混合改进方案，在基本人工鱼群算法中引入了Cauchy变异算子，并进而融入MATLAB的非线性规划函数，所得改进算法的优化精度、收敛速度和鲁棒性都有显著提高。与现有的其它改进算法相比，本文算法简单、容易实现，复杂度无明显增加，能保持较高的运行效率。而且，本文对人工鱼群算法的改进思想可从两方面加以推广：

（1）在算法中采用Gauss变异算子来代替Cauchy变异算子，同样可达到增加人工鱼群的多样性，进而增强其全局寻优能力的目的。

（2）可应用于其它群体智能优化算法，如粒子群优化算法、蚁群算法、量子粒子群优化算法等。

[1] 刘怀兰,牛辉,王佳.基于改进遗传算法的智能组卷模型优化[J].华中科技大学学报(自然科学版),2013,41(5):82-85.

[2] 马登武,郭小威,吕晓峰.基于改进遗传算法的舰载机弹药调度[J].计算机工程与应用,2012,48(8):246-248.

[3] 郜振华,梅莉,祝远鉴.复合策略惯性权重的粒子群优化算法[J].计算机应用,2012,32(8):2216-2218.

[4] 赵远东,方正华.带有权重函数学习因子的粒子群算法[J].计算机应用,2013,33(8):2265-2268.

[5] 陈明杰,黄佰川,张旻.混合改进蚁群算法的函数优化[J].智能系统学报,2012,7(4):370-376.

[6] 高芳,韩璞,翟永杰.基于变异操作的蚁群算法用于连续函数优化[J].计算机工程与应用,2011,47(4):5-8.

[7] 卢宇凡,张莉.基于粗糙集和蚁群算法的机器人路径规划研究[J].计算机与数字工程,2012,40(12):7-9.

[8] 王俭臣,齐晓慧,单甘霖.基于进食粒子群和共轭梯度的混合优化策略[J].计算机应用,2013,33(8):2257-2260.

[9] 胡振.QPSO混合算法在 PID控制器优化中的应用[J].计算机系统应用,2014,23(10):233-238.

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

TP301.6 文献标志码：A

2014.12.29）

1007-757X(2015)08-0028-03

四川高等职业教育研究中心立项课题（GZY14C42；南充市应用技术研究与开发资金项目（14A0079）

胡 振（1967-），男，汉，四川岳池人，南充职业技术学院，信息与管理工程系，副教授，研究方向：智能算法应用、微机系统运维技术，南充，637000