引用本文

张新明, 姜云, 刘尚旺, 刘国奇, 窦智, 刘艳. 灰狼与郊狼混合优化算法及其聚类优化. 自动化学报, 2022, 48(11): 2757−2776 doi: 10.16383/j.aas.c190617

Zhang Xin-Ming, Jiang Yun, Liu Shang-Wang, Liu Guo-Qi, Dou Zhi, Liu Yan. Hybrid coyote optimization algorithm with grey wolf optimizer and its application to clustering optimization. Acta Automatica Sinica, 2022, 48(11): 2757−2776 doi: 10.16383/j.aas.c190617

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190617

关键词

优化算法，灰狼优化算法，郊狼优化算法，混合算法，聚类优化 

摘要

郊狼优化算法(Coyote optimization algorithm, COA)是最近提出的一种新颖且具有较大应用潜力的群智能优化算法, 具有独特的搜索机制和能较好解决全局优化问题等优势, 但在处理复杂优化问题时存在搜索效率低、可操作性差和收敛速度慢等不足. 为弥补其不足, 并借鉴灰狼优化算法(Grey wolf optimizer, GWO)的优势, 提出了一种COA与GWO的混合算法(Hybrid COA with GWO, HCOAG). 首先提出了一种改进的COA (Improved COA, ICOA), 即将一种高斯全局趋优成长算子替换原算法的成长算子以提高搜索效率和收敛速度, 并提出一种动态调整组内郊狼数方案, 使得算法的搜索能力和可操作性都得到增强; 然后提出了一种简化操作的GWO (Simplified GWO, SGWO), 以提高算法的可操作性和降低其计算复杂度; 最后采用正弦交叉策略将ICOA与SGWO二者融合, 进一步获得更好的优化性能. 大量的经典函数和CEC2017复杂函数优化以及K-Means聚类优化的实验结果表明, 与COA相比, HCOAG具有更高的搜索效率、更强的可操作性和更快的收敛速度, 与其他先进的对比算法相比, HCOAG具有更好的优化性能, 能更好地解决聚类优化问题.

文章导读

在现实世界中, 无时无处无不面临着优化问题. 随着社会的发展, 急需处理的优化问题越来越多样化并越来越复杂. 而诸如牛顿法、梯度下降法等传统的方法不能够很好地处理这些急需解决的优化问题. 因此, 许多研究者建立了各种仿生类的智能计算模型, 提出了许多智能优化算法. 群智能优化算法(Swarm intelligence optimization algorithm, SIOA)是模拟自然界社会群体集体行为的一种智能优化方法[1], 包括粒子群优化(Particle swarm optimization, PSO)算法[2]、灰狼优化算法(Grey wolf optimizer, GWO)[3]、郊狼优化算法(Coyote optimization algorithm, COA)[4]等. SIOA具有易于实现、能有效处理全局优化和大规模优化问题等优势, 广泛应用于多目标优化、数据聚类以及模式识别等诸多领域[5]. 但根据无免费午餐定理[6], 没有任何一种SIOA能独立地解决所有的优化问题, 每种SIOA都有自身的优势和局限性. 因此许多学者提出了大量新奇和改进的SIOA, 其中包括算法的混合改进. 两种或多种算法的混合可以达到优势互补, 以获得最佳的优化性能[7].

GWO是由Mirjalili等[3]于2014年提出的一种新颖的SIOA, 具有原理简单、开采能力强、可调参数少等优点, 但存在易陷入局部最优、解决复杂优化问题性能差等缺点. 因此许多学者对其进行了研究和改进, 其中包括混合改进. 例如张新明等[7]提出一种GWO与人工蜂群算法的混合算法, 其中在人工蜂群观察蜂阶段自适应融合GWO, 以便增强开采能力和提高优化效率. Zhang等[8]提出一种基于生物地理学优化算法和GWO的混合算法, 将改进的基于生物地理学优化算法和基于反向学习的GWO混合, 使得优化性能最大化. Teng等[9]提出一种PSO与GWO结合的混合算法, 该算法具有更好的寻优能力和更强的鲁棒性. Arora等[10]提出一种乌鸦搜索算法与GWO的混合算法, 更有效地实现了全局优化.

COA是由Pierezan等[4]于2018年提出的一种模拟郊狼群居生活、成长、生死等现象的新型SIOA. COA具有独特的搜索模型和结构以及出色的优化能力, 尤其在解决复杂优化问题优势明显, 但仍存在搜索效率低、可操作性不强以及收敛速度慢等缺陷, 且由于COA提出的时间较短, 需改进和完善并拓展其应用领域. 鉴于GWO和COA各有优势和不足, 本文将两种算法分别进行改进和简化, 得到改进的COA (Improved COA, ICOA)和简化的GWO (Simplified GWO, SGWO), 然后通过正弦交叉策略将ICOA和SGWO有机融合在一起, 从而获得了一种性能优越且高效的混合COA (Hybrid COA with GWO, HCOAG). 另外, 混合算法的研究一直是优化领域的热点, 因此研究GWO与COA的混合是一项较有意义的工作.

图1 GWO的流程图

图2 组数Np与组内郊狼数Nc的分配图

图3 GWO与SGWO的等级情况对比

针对COA存在的不足, 本文提出了一种COA与GWO的混合算法(HCOAG). 首先, 改进COA (ICOA). 1)在成长过程中, 提出一种高斯全局趋优成长算子, 提高了搜索能力; 2)提出一种动态调整组数方案, 搜索前期采用较少组数, 减弱全局最优解的正反馈作用, 强化探索能力, 后期采用较多组数, 增强全局最优解的正反馈作用, 强化开采能力, 并提高可操作性. 然后, 对GWO进行改进, 提出了一种精简的GWO (SGWO), 在发挥其局部搜索能力强的优势同时, 提高了可操作性. 最后, 采用正弦交叉策略将ICOA与SGWO有机融合, 很好地平衡了组内郊狼的探索与开采能力, 从而获得了最佳优化性能. 大量经典函数与CEC2017复杂函数优化的实验结果表明, 在经典函数上, COA不及GWO; 在复杂函数上, GWO不及COA; 而HCOAG在两类优化问题上都有更好的性能, 说明二者混合有必要和有效; 与其他先进的对比算法相比, HCOAG具有更好的优化性能. K-Means聚类优化结果表明, 与对比算法相比, HCOAG获得了竞争性的优化性能.

总之, 与COA相比, HCOAG具有如下优势: 1)普适性强, 经典函数和复杂函数优化以及聚类优化3组实验结果表明, HCOAG都有更好的表现; 2)耗时少, 因此有更好的搜索效率; 3)更好的收敛质量; 4)更强的稳定性和鲁棒性, 5)可操作性更强.

作者简介

张新明

河南师范大学教授. 主要研究方向为智能优化算法, 图像去噪, 图像增强和图像分割. 本文通信作者.E-mail: xinmingzhang@126.com

姜云

河南师范大学硕士研究生. 主要研究方向为智能优化算法和图像分割.E-mail: jiangyun951120@163.com

刘尚旺

河南师范大学副教授. 主要研究方向为图像处理和计算机视觉.E-mail: shwl08@126.com

刘国奇

河南师范大学副教授. 主要研究方向为图像分割和偏微分方程.E-mail: liuguoqi080408@163.com

窦智

河南师范大学讲师. 主要研究方向为算法及数字图像处理.E-mail: 619534345@163.com

刘艳

河南师范大学实验师. 主要研究方向为优化算法和图像分割. E-mail: liu_yan122@sina.com