群体智能算法的混合改进综述

唐志崇

（广东工业大学计算机学院，广州510000）

0 引言

群体智能从20 世纪80 年代一出现，就引起了多个学科领域研究人员的关注，在许多领域上发挥着重要作用。主要应用领域有函数优化（目标函数可以是不可微的、多模型的、多组多目标的；搜索空间即可行域也可以是非线性或是不连续的。），以及可以把工程应用中能转成目标函数来优化的求解优化问题。例如机器人学中路径规划、细胞机器的结构优化；控制学中的管道控制、导弹控制；生产学中的任务分配、经济调度指派；组合优化NP 难问题中的TSP 问题、背包问题；深度学习中的模式识别、图像处理、神经网络训练、阈值分割、聚类分析、特征子集选择；信号处理学中的电路设计、数字滤波器设计、布局优化；多输入多输出电力系统，直流电机最优控制等。相对于传统的工程优化算法（牛顿法，梯度下降法，共轭梯度下降法）；群体智能算法对目标函数和可行域的要求更低，可以在不连续、非规则、有噪音、无须导数或其他辅助信息的情况下，能更广泛地应用在工程优化中。此外，群体智能算法在操作上具有高度的并行性，更适合并行处理的新一代计算机体系结构[1]。

群体智能算法大部分是从自然界的行为学习研究中获得灵感启发得来的，也叫做元启发式算法，是一类分散自组织系统的集体智能行为算法的总称。是一种可视为一组简单的个体，其中个体与个体、个体与环境之间存在交互作用，没有中心控制，简单的规则最终却能表现出智能的系统算法。是人类模拟自然界种群自组织与自适应机制求解问题同时保留着鲜明的生物特征的算法。目前主要的群体智能算法有粒子群算法、遗传算法、蚁群算法、人工鱼群算法、乌鸦搜索算法、人工蜂群算法、细菌觅食算法、狼群算法、还有较新的蝙蝠算法、猫群算法、蛙跳算法、帝国竞争算法、布谷鸟算法、鸽群算法等。本文从算法的原理介绍，参数、结构的改进以及融合优化和应用领域角度对已有的算法进行了分类综述；并对这些算法改进进行了横向对比分析，提出了基于奖惩系数的收敛理论，对未来的研究内容和改进方向进行展望。

1 算法

1.1 进化算法

遗传算法，差分进化，进化策略，进化规划等都是演化计算的分支，统称为进化算法。进化算法是以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，而不同的角度出发来模拟生物进化过程衍生出几种算法[2]。

（1）算法原理

初始化种群以及参数-交叉繁殖-变异操作-适值函数计算-取舍选择-迭代重复后面的环节。差分进化与遗传算法主要区别是取舍选择环节的不同（是否让父代参与）随着算法的发展，这些区分界限也不重要了。

（2）改进

参数设置对算法的收敛性以及收敛速度影响较大，需要根据经验类确定相应的参数。基于初始种群改进，张国辉提出了一种全局搜索遗传算法，改进了初始化方法，提升了初始化质量[3]。

基于遗传算子改进：即是交叉繁殖与变异环节的改进。常用的交叉有很多（单点、多点、部分匹配、次序、循环）交叉[4]等。变异的改进是为了让算法可以更好的跳出局部最优，即是需要让变异环节的操作步伐远超过领域搜寻的步伐。

基于取舍选择的改进：这个环节的改进有轮盘法、选择法等。

基于适应值函数改进：在适应值函数可以求得变化率时，将变化率加入取舍选择的衡量因素可以明显改善算法的性能。此外，目标函数不等于适应值函数，目标函数需要经过数学映射转换成非负的适应着函数，如果能对适应值函数进行优化减轻计算机运算，可以很大程度提升算法收敛时间。

（3）应用

进化算法的应用可以分成三大类：第一类是机器学习中的分类系统；第二类是组合优化问题；第三类是复杂的函数优化问题[5]。

1.2 粒子群算法

对比前面的进化算法，粒子群算法更具有种群多样性。进化算法由于交叉环节，整个种群共享信息，以一个优雅的姿势向着最优解的方向移动。粒子群算法中，个体受个体最优与群体最优的影响，算法结束后会留下很多有意思的方案，不会像进化算法因为迭代损失过程中的数据。

（1）算法原理

初始化种群以及参数-个体的适应值函数计算以及当前最优值更新-代入标准公式生成下一代粒子的速度与位置-一直迭代到算法满足结束条件。

（2）改进

基于参数设置改进：惯性权重系数w 的改进，实验总结表明w 在0.8-1.2 之间会有较好收敛速度。此外还有基于算法结构的各个环节改进方案。

1.3 蚁群算法

蚁群算法相比于前面的粒子群算法与进化算法有着独特的演化策略。利用正反馈达到“能者多劳占得多”与适应值函数判断有着一样的作用；迭代的效果不一样，不能使用迭代次数来判断是否结束收敛。

（1）算法原理

初始化种群以及参数-算法运行生成蚂蚁行程路线-信息激素更新地图更新-根据新的地图的信息素概率选择路线。

（2）改进

举例一种基于算法结构的改进：多信息素的蚁群算法被提出，几种信息素有着不同的更新策略与选择概率系数。

（3）应用

蚁群算法的算法结构演化策略是根据路径短从而获得正反馈，不能处理多目标函数的优化，工程优化和应用领域中也相应受限。

1.4 人工鱼群算法

人工鱼群算法相比于前面的算法，增加了一个行为选择以及视距概念，是基于行为的自下而上策略的人工智能算法。

（1）算法原理

初始化种群（包括位置，各种数据）；个体根据视野选择行动模式（觅食行为、群聚行为、追尾行为）；更新公示牌；迭代至次数满足算法结束条件。

（2）算法改进

人工鱼群算法的参数是较多的，参数的设置也是依靠实验总结的经验，缺乏理论支撑。此外，鱼群算法是一种个体集群搜索算法，有集群拥挤系数控制，这个系数前期要调大，后期调小。可以改善算法后期收敛的困难。

1.5 人工蜂群算法

作为早期的智能算法，在同类开创了分工策略；是第一个在种群内部有着分工分类的算法，可以有效的保持了种群的多样性，也为奖惩系数提供了新的表现。

（1）算法原理

初始化种群以及相关数据-分工分类（引领蜂、跟随蜂、侦查蜂）-根据各个种类的规则更新数据以及阈值判断（更换工种）-迭代至满足算法结束条件。

（2）改进

文献[6]提出了一种人工蜂群-差分算法；利用差分进化算法的思想，增加了一个淘汰环节，从而提升了算法性能。

1.6 其他算法

（1）细菌觅食算法

细菌觅食也是一个分行为的算法，趋化行为、复制行为、驱散行为。

算法原理：初始化种群以及参数-个体根据算法判断选择行为-迭代终止条件。很明显，这个算法，有局部优秀解时，会很快繁殖，在惩罚时，就会大概率留下这个局部的解。

（2）乌鸦搜索算法

初始种群数据-各个乌鸦根据视野选择行为-更新各个乌鸦的收藏的解-迭代；乌鸦会搜素新的更好的解，也会回到自己最好的解，跟踪、反跟踪。

（3）狼群算法

狼群算法作为较新的群体智能算法，也是分工分类策略。简略介绍如下：初始化种群以及参数-以适应值为主对种群个体等级调整（分工分类）-高等级决定搜素方向，低等级受高等级影响负责骚扰与包围猎物-迭代至终止条件。

（4）蝙蝠算法

蝙蝠算法是针对“视野”的视距策略算法。主要特点表现在个体的位置不轻易改变，通过低频率大振幅搜素猎物即是保持一个较大的步长、视距搜索领域；在发现较优解时，小步长小视距搜索领域并移动到较优解的位置。

（5）猫群算法

猫群算法是分行为策略算法，有搜寻模式、跟踪模式、移动模式。此外辅助有线性变化追踪，当个体猫群发现有一个步长内变化较大的解时会追逐到解的位置，同时其他的个体有概率吸引过来。

（6）蛙跳算法

蛙跳算法有一个能保住种群多样性的环节-划分子群体。设置了步长判断，在连续几次迭代中的取舍选择只对子群体起效，哪怕一个子群体在几次迭代后都是适应值靠后的个体，也会保留了大部分。

（7）帝国竞争算法

利用殖民地初始覆盖，然后向帝国中心（当前最优的一组解）移动中搜寻最优解。当帝国统一后，算法结束。显然能否得到理论最优解太过于看运气了。

（8）鸽群

两种行为模式：自行搜索或者参照其他鸽子移动。与猫群算法很像。

（9）布谷鸟算法

布谷鸟算法的核心是在一个有限的列表中存储当前较优的解，同时也会概率丢弃。很显然，标准的布谷鸟算法的收敛性差。

烟花算法与上面的算法有着很大的区别，不属于一类型算法。不在此阐述。

我们知道，最优参数的设置是主要的优化方法之一。以遗传算法为例，交叉概率、变异概率、解群大小、最大迭代次数等都是影响着算法性能的因素。最优参数设置是一个很复杂的问题，群体智能算法都是非线性智能计算模型，很难用数学方法来准确预测运行结果。求解实际问题时，主要凭经验确定[7]。

此外，群体智能算法主要改进思路是算法结构改进。①对算法自身机构的改进，如有周昊天提出的简化粒子群优化方法，直接用位置更新取代了速度更新。②融合其他群体智能算法改进，也就是混合算法将在后面单独列出。

群体智能的标准算法、改进的算法以及混合算法广泛的应用函数优化领域、路径规划学、控制学、生产学、组合优化问题、深度学习、信号处理学、电力系统，成为工程优化的重要方法。在群智能发展的今天，各种算法的应用领域区别不大也没必要区分。因为群体智能算法的本质是一样的，都是在一个个测试适应值，模仿演化中向着最优解的方向寻找。

2 融合改进

融合其他算法的混合算法其实是算法结构改进的一种，结合其他算法可以很好的改善原算法的不足，提升算法的性能。群体智能算法（标准算法）都是在自然界一个部落群体中学习，并参照这个群体的行为制定一些简单的规则，使得整个群体向最优解的方向有序的前进。改进分类有两个：①参数重设。②算法结构改进。上一章的改进大部分都是参数重设和基于算法单个环节改进。在当前性能最好的是融合改进的混合算法。其中除了群体智能算法内部的算法融合，常用于融合算法有混沌理论、量子理论、模拟退火、禁忌算法等。

（1）前沿研究

南云等提出了一种具有双层结构的交替迭代式遗传模拟算法，为制定不确定装备车间生产计划与调度方式提供了一种合理解决方案。Li 等人[8]提出了一种遗传禁忌算法。罗德[9]提出了一种粒子融合人工鱼群算法，一部分运用粒子群算法，一部分运用鱼群算法，当前最优值的公告共用，从而提升收敛速度。人工蜂群混沌混合算法[10]被提出，可以利用混沌运动的随机性，遍历性，让侦查蜂有着更好的全局搜索能力。文献[11]提出了粒子群-细菌觅食混合算法，解决了细菌觅食算法的收敛慢的缺点。文献[12]对细菌觅食算法的趋化行为作出改进，加入差分进化思想，可以更好的逼近最优解。

（2）收敛理论

群体智能算法能够在没有中心控制，个体遵循简单的规则，却能在整个种群涌现智能。主要的核心在于迭代思想，在于每一次迭代后，对种群的个体适应值给出了奖励或是惩罚。根据演化-达尔文思想，在若干次迭代后，就会涌现出向着更好的适应值群体演变。其中影响着演变速度的正是奖励或者惩罚的程度即是奖惩系数。优秀群体智能算法的奖罚系数应当在算法前期应当保持低的奖惩系数，可以保持种群的多样性，同时缓慢的全局搜素；算法中期，奖惩系数缓慢加速上升，但总体还在较低的水平，算法可以避免陷入局部最优解；在后期用较高的奖惩系数让算法快速收敛到全局最优值。

文献[13]提到的试验，粒子群算法的改进中将惯性权重参数w 设置从0.9 到0.4 线性下降使算法的性能得到明显提升。惯性权重参数w 越大，个体越有自主性即少受当前最优值影响，也等于个体表现不良受到的惩罚小；后期参数w 变小，个体受到当前最优值的影响变大即是如果个体表现不良受到惩罚变大，同时表现最优的个体及当前最优吸引其他个体的能力变大即奖励变大。

很多算法与模拟退火融合后总能提升性能，正是模拟退火的前期大概率不接受取舍选择的结构，奖惩系数较低。后期大概率接受取舍选择的结果，奖惩系数较高。与禁忌算法融合的混合算法中，禁忌列表不让吸引过多，也是奖罚系数调整的体现。因此，群体智能的融合改进的核心是奖罚系数的调整，使之符合算法前期保持种群多样性，后期快速收敛。

3 结语

对于群体智能算法，应用领域十分广泛，长久以来都是研究热点。当今群体智能算法的发展已经陷入瓶颈了。虽然陆续有新的算法出现，但再也无法模拟当年蚁群算法刚被提出来时的带给学术界的震惊。重要的原因是，理论依旧弱于实验数据，一个算法是否有更好的性能，总要通过基准函数测试或者具体实验案例对比分析。这个跟我们认知模式是不符合的。

本文有选择地介绍了群体智能算法的原理、改进方案，以及混合算法。提出了基于奖惩系数的收敛理论。需要经过大量的实验测试对比确定性能的提升；此外，还需要更进一步研究奖惩系数对收敛的量化表现。