复合混沌人工鱼群混合算法的改进及性能研究＊－

易新兵，杨 凯

（1.空军工程大学航空航天工程学院，陕西 西安710038；2.95019部队，湖北 老河口441800）

1 引言

近年来，在优化算法领域出现的群智能SI（Swarm Intelligence）优化算法［1］，作为解决传统复杂问题的一种新兴演化计算技术已成为国内外众多研究者关注的热点。它通过模拟自然界昆虫的行为研究，利用特定规则来指导整个解空间中优良解的探索，人工鱼群算法是一种群智能优化算法，它研究模拟鱼类的觅食行为、追尾行为和聚群行为等，通过每条人工鱼的局部寻优达到全局寻优。它作为一种新型的寻优策略，具有鲁棒性强、全局收敛性好、对初值敏感性小等优势，可以用于解决各种连续优化和组合优化问题［2］。但是，由于固定步长和随机行为的存在，该算法存在着寻优精度不高、后期收敛速度变慢及不易跳出局部极值等不足。由于混沌运动的遍历性，混沌作为一种局部搜索方法可以提高人工鱼群算法的全局搜索能力。人工鱼群算法已搜索的最优解能够反馈指导人工鱼移动，并引入吞食行为，以降低算法复杂度。因此，研究基于混沌搜索和人工鱼群行为的混合算法改进及其寻优性能，可以改良单一算法的全局寻优精度和收敛速度，对于解决现实的复杂工程优化问题具有重要的理论意义和实际价值。

文献［3］介绍了人工鱼吞食（Swallowing）行为，定义在算法达到一定迭代次数后每次淘汰掉一个弱小人工鱼；文献［4］采用混沌人工鱼群算法对灌区优化配水模型进行了优化计算。本文以混沌优化搜索和改进人工鱼行为为重点，组合映射产生复合混沌搜索局部极值策略，并引入人工鱼的反馈－吞食行为，提高人工鱼群算法全局收敛性，反馈信息和吞食行为提高算法的收敛精度和速度，基于此策略和行为的混合算法性能得到更大提升。（

2 基于复合映射的混沌搜索

混沌运动具有遍历性、随机性等特性，能在一定范围内按其自身规律不重复地遍历所有状态［5］，其轨迹对初始值极其敏感，由确定性的迭代公式产生。基于此特征的混沌映射可以作为一种局部搜索方法来提高其他优化算法的全局搜索能力，并能够避免算法陷入局部极值。

2.1 复合混沌映射

本文提出了利用Tent映射和Logistic映射进行复合产生混沌映射的搜索方法。

Logistic映射定义为：

将式（2）的初始值xn产生的迭代数列xn＋1∈（0，1）代入式（1）中，作为Tent映射的初始值进行复合迭代，可以得到新的映射，其具有类抛物线型，该复合映射在μ∈［1，2］时是单一的满映射，序列具有有界性，并可进入混沌状态。其方程式为：

Tent映射定义为：

2.2 Lyapunov指数对比及最佳μ值

Lyapunov指数表示映像中相邻点相互分离的快慢或奇异吸引子中轨道对初始条件的敏感依赖。Lyapunov指数定义为：

图1为根据式（4）求得的上述三种映射Lyapunov指数随参数μ（α）变化的曲线。

Figure 1 Three mapping systems Lyapunov exponent spectrum with different aandμ图1 不同α、μ值下，三种映射系统对应的Lyapunov指数谱（α、μ均等分1 000点，初值x1 ＝0.4，迭代2 000点）

计算得知，在相同条件下，复合映射的最大Lyapunov指数为0.829 6，比Logistic映射的最大Lyapunov指数（0.629 5）和Tent映射的最大Lyapunov指数（0.577 6）都要大。而且当μ＝2时由式（3）确定的复合映射Lyapunov指数达到最大值，具有更好的初值敏感性，混沌特性明显，从而使其局部搜索能力较单一混沌映射要强。复合混沌映射方程式为：

2.3 复合混沌搜索策略

不失一般性，设有一个n维优化问题：min σ＝f（X），X ＝ （x1，x2，…，xn），xj是其第j 维决策变量且xmin，j＜xj＜xmax，j，复合混沌搜索的具体步骤如下。

步骤4 根据所求优化问题的目标函数σ＝f（X）评价决策变量的优劣。如果优于，即f（X（k＋1））＜f（X（k）），则输出，，…，）作为复合混沌局部搜索结果；否则，令k＝k＋1，返回步骤2。

作为局部搜索技术的混沌搜索策略［6］，采用对初值更具敏感性和轨迹遍历性的复合混沌搜索局部极值，能够提高搜索精度和速度，避免长时间寻优陷入局部极值的问题。

3 基于复合混沌搜索及改进人工鱼群行为的混合算法

3.1 基本人工鱼群算法

人工鱼群算法是在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法，根据“水域中鱼生存数目最多的地方一般就是本水域中富含营养物质最多的地方”这一特点来模仿鱼群的觅食、聚群、追尾和随机四种基本行为而实现寻优，主要通过模拟鱼类的基本行为，采用自上而下的寻优模式从构造个体的底层行为开始，利用鱼群中各个体的局部寻优，达到全局最优值在群体中突现出来的目的。算法的人工鱼模型有五个基本参数变量：人工鱼总数N、移动最大步长step、人工鱼视野visual、尝试次数try＿number和拥挤度因子δ；函数部分包括人工鱼所在位置食物浓度、人工鱼行为函数和评价函数。

人工鱼群算法在优化过程中跳出局部极值区域、实现全局极值寻优的原理为：在人工鱼觅食行为中，较少的尝试次数提供了更多随机游动的机会，使鱼跳出局部极值的领域；拥挤度因子限制鱼聚群的规模，使较优的地方聚集更多人工鱼来广泛寻优；聚群和追尾行为能够使陷于局部极值的人工鱼向大部分趋向全局最优值的鱼方向聚集，或者向处于更优的全局极值的鱼方向追随，从而逃离局部极值。在基本人工鱼群算法中，觅食行为奠定了算法收敛的基础，聚群行为增强了算法收敛的稳定性，追尾行为则增强了收敛的速度和全局性，行为分析过程为人工鱼群算法的速度效率和稳定性提供了保障［7］。

3.2 人工鱼群反馈－吞食策略的提出

为了记录最优人工鱼的状态，人工鱼群算法引入了公告牌。通过人工鱼自身状态与公告牌状态的比较，使得公告牌记录历史最优值。同时，公告牌记录的最优状态也可以反馈给人工鱼用来指导下一步行动［8］。定义反馈行为：人工鱼以一定概率向公告牌记录的最优状态游动。鱼群算法在寻优过程中，首先执行觅食、追尾和聚群行为，假若这三种行为均不能找到比当前更优的状态，则人工鱼执行随机行为。考虑到在优化后期人工鱼聚集在全局最优附近时，随机行为的执行会降低算法的优化精度和优化效率，规定：人工鱼以反馈概率Pfb执行随机行为，以概率 （1－Pfb）执行反馈行为，且Pfb随优化过程线性减小，即Pfb＝αPfb，α为Pfb的衰减因子。保证在优化前期，随机行为有更多机会执行，而后期的反馈行为则有更多机会执行。

人工鱼群算法的收敛速度正比于人工鱼数量，随个体增多收敛越快，但因需要更多存储空间，造成算法复杂度增加。因为在人工鱼群算法中目标函数值很低，弱小的人工鱼对算法的收敛速度和全局寻优能力影响很小，根据自然界中弱小的鱼会被大鱼吞食的现象，在此引入吞食行为：经过若干次迭代后，将目标函数值较低的人工鱼以一定比例淘汰掉，释放其所占空间，此后迭代将舍去这些人工鱼。

综上，人工鱼的反馈－吞食策略描述为：每次迭代，当人工鱼执行觅食、追尾和聚群行为后，其状态均不优于当前状态时，排列所有人工鱼的适应度值，将较小适应度值的人工鱼以（1－Pfb）比例淘汰掉，剩下的人工鱼以概率Pfb执行随机行为，以概率（1－Pfb）执行反馈行为，优化过程中Pfb＝αPfb线性减小。该策略使得在优化前期，淘汰少量的弱小人工鱼，在降低算法复杂度的同时防止收敛速度变缓，且保证有更多机会执行随机行为；在优化后期，淘汰的弱小人工鱼增多，加快算法的收敛，且保证反馈行为有更多机会执行。

3.3 混合算法的具体步骤

混沌作为一种有效防止优化算法陷入局部最优的机制，将第2节提出的复合混沌搜索引入人工鱼群算法中。人工鱼群算法执行全局寻优搜索，而复合混沌搜索则在此结果的基础上实行局部搜索。改进人工鱼引入反馈－吞食行为，使得鱼群算法复杂度降低、收敛效率提高。基于以上两点思路，由复合混沌－人工鱼群构造的混合算法能够避免人工鱼长时间呆在局部最优值附近，减少算法复杂度，从而提高人工鱼群算法的全局收敛性和寻优效率，算法的收敛精度和收敛效率增强［9］。

基于复合混沌搜索和改进人工鱼群行为的混合算法具体步骤描述如下：

步骤1 算法初始化，包括人工鱼的位置、种群规模total、步长step、视野visual、反馈概率Pfb、反馈概率衰减因子α；

步骤2 计算所有人工鱼的适应度值，将最优的人工鱼记入公告牌；

步骤3 人工鱼执行觅食行为、追尾行为和聚群行为，对执行所得结果进行评价，如果执行后的状态优于当前状态，则人工鱼向此优良状态的方向前进一步，继而转到步骤5；

步骤4 按适应度值大小排列所有人工鱼，以（1－Pfb）比例淘汰掉较低值的人工鱼，产生一个随机数rand（），若rand（）＜Pfb，剩余人工鱼执行随机行为，否则执行反馈行为；

步骤5 最优人工鱼执行复合混沌搜索；

步骤6 更新公告牌；

步骤7 利用式Pfb＝αPfb更新反馈概率；

步骤8 如果算法满足终止条件，则停止算法运行，输出最后结果，否则返回步骤3。

混合算法的流程图如图2所示。

4 算法性能的验证与分析

选取三个标准测试函数（F1，F2，F3）测试混合算法的性能。这些函数都具有很多局部极值，普通的优化算法很难找到全局最优值，测试函数如表1所示，图3为其三维效果图。实验对每个函数进行30次，每次迭代600代，每个函数优化参数设定一致，F1、F2、F3函数收敛阈值分别为820、3 564、3。实验结果如表2所示。

Figure 2 Diagram of compound chaos－improved artificial fish hybrid algorithm图1 复合混沌－改进人工鱼群混合算法流程示意图

由表2实验结果可以看出，本文的混合算法无论是收敛精度、收敛速度还是到达收敛阈值所需要的平均迭代收敛次数，均优于基本人工鱼群算法。

由表2的验证实验，三个测试函数的收敛曲线如图4～图6所示，人工鱼总数均为20条，算法迭代600次。

图4中，两种算法步长step＝3，视野visual＝12，尝试次数try＿number＝3，拥挤度因子δ＝0.11，混合算法反馈概率Pfb＝0.99，衰减因子α＝0.99。由图4可以看出，混合算法得出的收敛曲线的收敛速度更快，能够更好地接近全局最优值，收敛精度高。

Table 1 Standard test functions表1 标准测试函数

Table 2 Experimental results表2 实验结果

图5中，两种算法步长step＝0.01，视野visual＝1，尝试次数try＿number＝5，拥挤度因子δ＝0.05，混合算法反馈概率Pfb＝0.96，衰减因子α＝0.98。由图5可以得出，混合算法寻找全局极值点所需的迭代次数少，收敛效率更高，收敛速度较快。

Figure 5 Convergence curve of test function F2图5 F2函数的收敛曲线

Figure 6 Convergence curve of test function F3图6 F3函数的收敛曲线

图6 中，两种算法步长step＝0.089，视野visual＝10，尝试次数try＿number＝3，拥挤度因子δ＝0.15，混合算法反馈概率Pfb＝0.99，衰减因子α＝0.95。从图6中能够得出，基本鱼群算法易长时间陷入局部极值，而混合算法能稳定地跳出局部极值达到全局寻优，优化能力增强。

图7～图9分别给出了两种算法对F1、F2、F3优化实验中人工鱼群的初始分布和最终分布情况。图中“○”代表人工鱼，总数为20条。

Figure 9 Artificial fish distribution of F3function algorithm图9 F3函数优化实验中算法的人工鱼分布图

由图7可以看出，混合算法使更多的人工鱼能够到达全局最优值区域，提高了寻优精度；图8中混合算法的人工鱼较多地跳出局部极值，提高了优化效率；图9混合算法中部分极值点附近均有人工鱼聚集，表明算法在找到全局最优解的同时能得到部分的次优解，增强了算法的优化生存能力。

5 结束语

本文利用常见的两种混沌映射进行组合，以复合形式得出的混沌搜索具有更强遍历性的搜索局部极值能力，使得优化问题的全局寻优能跳出局部极值得到精确解。在人工鱼群算法中引入反馈－吞食行为，该行为策略在降低算法复杂度的同时保证了寻优的收敛精度和效率。基于复合混沌搜索与改进人工鱼群的混合算法，使得以人工鱼为解题模型的优化问题全局寻优能力在算法复杂度、收敛速度和跳出局部极值方面均有很大提高，可以应用到复杂工程优化设计中，对于通信和信号图像处理等领域的大规模数据优化问题也将同样起着重要作用。

［1］ Gao Shang，Yang Jing－yu.Swarm intelligence algorithm and its application［M］.Beijing：China Water Power Press，2006.（in Chinese）

［2］ Li Xiao－lei.A new method of intelligence optimization－artificial fish swarm algorithm［D］.Hangzhou：Zhejiang University，2003.（in Chinese）

［3］ Cheng Y M，Jiang M Y，Yuan D F.Novel clustering algorithms based on improved artificial fish swarm algorithm［C］∥Proc of the 6th International Conference on Fuzzy Systems and Knowledge Discovery（FSKD’09），2009：141－145.

［4］ Gao Yu－fang，Zhang Zhan－yu.Chaotic artificial fish swarm algorithm and its application in the irrigation district optimize water distribution［J］.Journal of Agricultural Engineering，2010，27（6）：2084－2086.（in Chinese）

［5］ Yu Si－min.Chaotic systems and chaotic circuits：Principle，design and its application in communications［M］.Xi’an：Xi’an University of Electronic Science and Technology Publishing House，2011.（in Chinese）

［6］ Bucolo M，Caponetto R，Fortuna L，et al.Does chaos work better than noise？［J］.IEEE Circuits and System Magazine，2002，2（3）：4－19.

［7］ Jiang Ming－yan，Yuan Dong－feng.Artificial fish swarm algorithm and its application［M］.Beijing：Science Press，2012：44－48.（in Chinese）

［8］ Zhu K C，Jiang M Y.Quantum artificial fish swarm algorithm［C］∥Proc of the 8th World Congress on Intelligent Control and Automation，2010：1－5.

［9］ Zhu K C，Jiang M Y.An improved artificial fish swarm algorithm based on chaotic search and feedback strategy［C］∥Proc of International Conference on Computational Intelligence and Software Engineering（CISE），2009：1－4.

附中文参考文献：

［1］ 高尚，杨静宇.群智能算法及其应用［M］.北京：中国水利水电出版社，2006.

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

［4］ 高玉芳，张展羽.混沌人工鱼群算法及其在灌区优化配水中的应用［J］.农业工程学报，2010，27（6）：2084－2086.

［5］ 禹思敏.混沌系统与混沌电路—原理、设计及其在通信中的应用［M］.西安：西安电子科技大学出版社，2011.

［7］ 江铭炎，袁东风.人工鱼群算法及其应用［M］.北京：科学出版社，2012：44－48.