群智能算法的混合策略研究

(广东司法警官职业学院信息管理系，广东 广州510520）

群智能算法是以模拟群体生物行为为特征的仿生类进化算法，采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现，已在传统NP问题求解和诸多优化领域中展现其卓越性能和巨大的发展潜力。蚁群算法和粒子群算法是最典型的群智能算法，蚁群算法是对蚂蚁群落食物采集过程的模拟，适合于离散优化问题。粒子群优化算法则是模拟鸟群觅食过程，适合连续优化问题。这2种算法性能优越但也各存缺点，为了提高算法的优化性能，在算法引入其它启发式算法已成为一个研究热点，笔者在介绍蚁群算法和粒子群算法基础上对上述算法的各种混合策略进行分析比较，为该问题的研究提供参考。

1 蚁群算法

蚁群算法(Ant Colony Algorithm，ACA）于20世纪90年代由Colorni等[1]提出，该算法模拟蚁群的群体协作觅食过程，由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。

蚁群算法具有正反馈性、并行性、鲁棒性等优点，特别适合于离散领域的优化，但该算法存在着初始信息素缺乏、收敛速度慢、容易陷入局部最优等缺点。针对这些缺点，很多学者在ACA中结合其他优化技术，产生一种新的混合优化算法，并将其应用于实际问题中，以进一步提高ACA的优化性能。

1．1 蚁群算法与遗传算法混合

遗传算法(Genetic Algorithm，GA）是一种强有力的自适应全局优化概率搜索方法，对于各种搜索问题都可以使用。刘立东等[2]提出了一类融入遗传算法的混合蚁群算法：蚁群算法在每代进化中保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进行运算。交叉和变异操作扩大了解的搜索空间，避免陷入局部最优，对优秀解公共解集的保留则加快了算法收敛速度。丁建强等[3]采用遗传算法生成信息素分布，利用蚁群算法求精确解，优势互补。高尚等[4]提出的混合算法是首先由遗传算法产生较优解，较优路径上留下信息素，其他不改变。蚁群算法完成一次遍历后，再作遗传算法的交叉和变异操作，如果交叉和变异后得到的解得到改善，则代替原来路径。

1．2 蚁群算法与模拟退火混合

模拟退火算法(Simulated Annealing，SA）是一种典型的局部搜索算法，其具有的突跳能力能有效帮助ACA跳出局部最优。主要混合策略有以下2种：①在模拟退火算法中运用蚁群算法思想找邻域的解；②采用模拟退火生成信息素分布，蚁群算法寻优过程中采用模拟退火在邻域内找另外一个解。

1．3 蚁群算法与差分演化结合

差分演化算法(Differential Evolution，DE）是一种基于种群的并行随机搜索算法，该算法从初始种群开始，通过交叉、变异和选择等操作生成新种群，不断进化以搜索全局最优解。差分演化算法擅长连续问题的优化，蚁群算法控制参数连续变化，可以利用DE对其进行参数优化，进而改善蚁群算法的性能。崔娇等[5]将差分演化算法应用到蚁群算法的参数选取中，将蚁群算法的参数作为差分演化算法解空间的向量元素，自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。新算法对于蚁群算法中的参数进行自适应调整，避免了大量盲目测试，而且扩大了蚁群算法的搜索空间，提高了全局搜索能力。此外，蚁群算法还可以与禁忌搜索、集束搜索、模糊系统、免疫系统等结合以提高算法优化性能。

2 粒子群算法

粒子群优化算法(Particle Swarm Optimization，PSO）是继蚁群算法后，由Kennedy等[6]于1995年提出的另一种著名群智能算法，该算法是受鸟群觅食行为的启发而提出的。PSO是一种基于群体迭代的启发式算法，其基本思想是随机初始化一群粒子，每个粒子视为优化问题的一个可行解，粒子的质量由适应度函数确定。粒子以一定速度追随当前的最优粒子在可行解空间中探索，通过迭代得到最优解。在每一代中，粒子通过跟踪本身所找到的最优解和整个种群目前找到的最优解来进行更新。

标准PSO模型中，设搜索空间为D维，粒子数为n，第i个粒子位置表示为向量Xi＝（xi1，xi2，…，xid，…，xiD），飞行速度为Vi＝(vi1，vi2，…，viD），其历史最优位置为Pi＝(pi1，pi2，…，piD），Pg为所有Pi（i＝1，…，n）中的最优。每个粒子的位置按式（1）和（2）进行更新：

式中，c1和c2为加速因子；rand（）为[0，1]间的随机数；ω为惯性因子。

粒子群初始位置和速度随机产生，然后进行迭代，直至找到最优解。实现步骤如下：①初始化粒子群，随机产生每个粒子的位置和速度；②计算每个粒子的适应度；③对每个粒子，将其适应度值与pid比较，如果较好，则替换pid；④对每个粒子，将其适应度值与pgd比较，如果较好，则替换pgd；⑤更新每个粒子的速度和位置；⑥如果满足约束条件(误差足够好或达到最大循环次数）退出，否则返回②。

粒子群算法概念简单、容易实现、可调参数少，而且具有扩展性，容易与其他算法结合，适用于处理连续优化问题。但是该算法存在着容易早熟收敛、局部寻优能力差以及搜索性能对参数设置具有依赖性等缺点。很多学者尝试在PSO中结合其他启发式算法，以克服传统PSO的不足，提高算法整体性能。

2．1 蚁群算法与粒子群算法混合

将粒子群算法引入到蚁群算法中，让蚂蚁也具有粒子的特性。两者融合不仅可以提高数据搜索的范围而且可以避免早熟，在时间效率上优于蚁群算法，在求解精度上优于粒子群算法。支成秀等[7]利用粒子群算法较强的全局搜索能力，经过一定的迭代次数得到问题的次优解，利用问题的次优解调整蚁群算法中的信息素的初始分布，再利用蚁群算法的正反馈机制求出问题的精确解，从而提高时间效率和求解精度。高尚等[4]提出的算法首先通过蚁群算法进行搜索，然后用粒子群算法对蚁群算法得到的有效路径进行调整：将每只蚂蚁的当前路径分别与全局最优和个体最优交叉，然后以一定概率变异，如果新路径的目标函数较优，则接受新值，否则拒绝。

2．2 粒子群算法与遗传算法结合

Angeline[8]提出了混合群体，首次将GA的锦标赛选择算子结合到PSO中，通过保留具有较高适应值的粒子进行复制来加快收敛速度，但仍然容易陷入局部最优。Lovbjerg等[9]提出了带有繁殖和子种群的混合PSO算法，在每次迭代中按交叉率选择一定数量的粒子放入一个池中，池中粒子随机两两交叉，产生具有新的空间坐标和速度的子代以取代父代，并且把种群分为若干子种群，交叉可以在同一子种群内进行，也可在不同种群间进行。该混合算法使粒子增强搜索能力，易于跳出局部最优。Ratnaweera等[10]则将GA的变异算子引入到PSO中，将粒子与当前最优距离小于一定值时，按一定变异率让粒子随机初始化，该算法保证了群体的多样性。钟文亮[11]等针对PSO在优化多峰函数时容易早熟的缺点，在PSO中引入启发性变异机制，扩展了算法的搜索区域，提高了算法的速度和精度且不容易陷入局部最优。

2．3 粒子群算法与模拟退火结合

PSO早期时收敛速度快，但后期受随机振荡现象的影响，容易停滞于局部最优点。为解决该问题，在PSO中引入SA后可以跳出局部最优。高鹰等[12]提出以PSO为主体运算流程，引入模拟退火机制，并混合了基于遗传算法思想的杂交运算和带高斯变异的SA-PSO算法。在保持PSO算法简单容易实现基础上，提高PSO算法摆脱局部极值的能力，避免算法陷入局部最优，提高算法的收敛速度和精度。王联国等[13]把SA引入到PSO算法中，提出了一种混合优化算法。该算法在各温度下依次进行PSO和SA搜索，结合了PSO的并行搜索和SA的概率突跳性的特点，从而有效防止PSO算法陷入局部极小。

2．4 粒子群算法与差分演化结合

许多学者尝试把PSO和DE的优点结合起来实现逃离局部最优点。池元成等[14]提出的混合算法首先利用DE的变异和选择算法产生新的群体，然后使用PSO和交叉、选择算法进行局部搜索。李丽等[15]提出了一种新型的混合全局优化算法，即采用双种群进化策略，其中一个种群按PSO操作进化，另一个种群按DE操作进化，每次进化过程中通过信息交流搜寻信息，以避免各种群陷入局部最优。倪霖等[16]通过在PSO种群和DE种群之间建立一种信息交流机制，使信息能够在两个种群中传递，以避免个体因错误的信息判断而陷入局部最优点，并通过实例验证了算法在资源受限项目调度优化问题上的有效性。

此外，粒子群算法还可以结合混沌优化、进化策略和进化规划等技术提高性能。

3 结 语

各种群智能算法都有其自身特点和独特优势，但同时也存在各种不足。对于不同的优化问题，采用单一的优化算法往往在运行速度或优化精度上难以获得满意的效果。根据各优化算法的优缺点，采用一定的混合策略使各种算法形成优势互补关系，从而提升算法性能和拓宽算法应用领域。

[1]Colorni A，Dorigo M，Theraulaz G．Swarm intelligence：From natural to artificial systems [M]．New York：Oxford Universyty Press，1999．

[2]刘立东，蔡淮．融入遗传算法的混合蚁群算法 [J]．计算机工程与设计，2008，29（5）：1248-1252．

[3]丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合 [J]．计算机研究与发展，2003，40（9）：1351-1356．

[4]高尚，杨静宇．群智能算法及其应用 [M]．北京：中国水利水电出版社，2006：108-111．

[5]崔娇，黄少荣．基于差分演化的自适应参数控制蚁群算法 [J]．计算机工程，2011，37（6）：190-193．

[6]Kennedy J，Eberhart R．Particle Swarm Optimization [R]．IEEE International Conference on Neural Networks，Piscataway，NJ：IEEE Service Center，1995：1942-1948．

[7]支成秀，梁正友．融合粒子群优化算法与蚁群算法的随机搜索算法 [J]．广西科学院学报，2006，22（4）：231-233．

[8]Angeline P J．Using selection to improve particle swarm optimization [A]．Proc of the IEEE International Conference on Evolutionary Computation [C]．Piscataway，NJ：IEEE Service Center，1998：84-89．

[9]Lovbjerg M，Rasmussen T K，Krink T．Hybrid particle swarm optimizer with breeding and subpopulations [A]．Proceedings of the Genetic and Evolutionary Computation Conference [C]．San Francisco，2001：469-476．

[10]Ratnaweera A，Halgamuge S．Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]．Evolutionary Computation，2004，8(3）：240-255．

[11]钟文亮，张惠森，张军，等．带启发性变异的粒子群优化算法 [J]．计算机工程与设计，2008，29（13）：3402-3406．

[12]高鹰，谢胜利．基于模拟退火的粒子群优化算法 [J]．计算机工程与应用，2004，40（1）：47-50．

[13]王联国，洪毅，赵付青，等．一种模拟退火和粒子群混合优化算法 [J]．计算机仿真，2009，25（11）：179-182．

[14]池元成，方杰，蔡国飙．基于差分进化和粒子群优化算法的混合优化算法 [J]．计算机工程与设计，2009，30（12）：2963-2965．

[15]李丽，牛奔．粒子群优化算法 [M]．北京：冶金工业出版社，2009．

[16]倪霖，段超，贾春兰．差分进化混合粒子群算法求解项目调度问题 [J]．计算机应用研究，2011，28（4）：286-1289．