引用本文

邓志诚, 孙辉, 赵嘉, 王晖, 吕莉, 谢海华. 方波触发勘探与开发的粒子群优化算法. 自动化学报, 2022, 48(12): 3042−3061 doi: 10.16383/j.aas.c190842

Deng Zhi-Cheng, Sun Hui, Zhao Jia, Wang Hui, Lv Li, Xie Hai-Hua. Particle swarm optimization with square wave triggered exploration and exploitation. Acta Automatica Sinica, 2022, 48(12): 3042−3061 doi: 10.16383/j.aas.c190842

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

关键词

粒子群优化算法，方波触发机制，勘探与开发，全局优化 

摘要

在粒子群优化算法中, 当勘探时间持续过长, 将可能导致种群在解空间过度徘徊; 种群在开发阶段陷入局部最优后, 难以再次进行全局勘探. 针对上述问题, 提出方波触发勘探与开发的粒子群优化算法. 依据方波的周期特性, 在前半个周期内使用标准粒子群优化算法执行全局勘探, 后半个周期使用改进的更新公式执行局部开发. 经过实验验证, 在方波触发机制下, 通过为粒子提供多变步长, 可达到周期性触发勘探与开发的目的. 使用多类型测试函数, 将该算法与新改进粒子群算法、改进人工蜂群算法、改进差分算法在30、50和100维下比较, 实验结果表明, 该算法在收敛速度和精度上更具优势.

文章导读

为解决传统优化算法难以解决的复杂优化问题, 研究者们受启发于生物和自然物理现象, 提出了粒子群优化算法、差分进化算法、人工蜂群算法、和声搜索算法和进化策略等优化技术以解决各领域的优化任务.

粒子群优化算法(Particle swarm optimization, PSO)是由Kennedy等[1]在1995年提出的群智能优化算法. 该算法具备计算快速和易实现等优点, 作为群体智能算法的一个重要分支, 得到了众多学者广泛深入的研究. 且已应用于预测[2]、工程设计[3]、特征选择[4]和经济[5]等众多领域.

粒子群优化算法是源于对鸟群捕食行为的模仿研究, 人们从鸟群捕食过程当中得到启示, 并将其用于解决优化问题. 该算法通过群体中粒子间合作与竞争产生的群体智能指导优化搜索. 根据算法的特性, 全局最优粒子将信息传递给其他粒子是单向的信息流动, 可使粒子快速的收敛于最优解. 但当全局最优粒子处于局部最优位置时, 易导致所有粒子收敛到局部最优. 此外, 粒子在进化过程中, 从全局勘探转为局部开发阶段后, 若粒子处于局部最优位置, 将难以获得逃离局部最优位置的步长. 针对上述问题, 提出方波触发勘探与开发的粒子群优化算法(Particle swarm optimization with square wave triggered exploration and exploitation, SWTPSO), 在提高全局最优质量的同时, 进一步增强粒子逃离局部最优的能力.

SWTPSO中提出方波触发机制. 首先, 将标准PSO的更新公式进行改进, 去除速度项和加速因子的影响, 使新改进的公式局部搜索能力增强, 并存储当前粒子的位置, 作为下次使用标准PSO公式更新种群时粒子的新步长. 然后, 根据种群设定的总迭代次数, 将种群进化的过程划分为多个方波周期. 最后, 按照种群当前运行的迭代次数属于方波周期内的“高”或“低”值, 分别执行标准PSO公式和新改进公式更新种群, 使粒子的搜索状态随方波周期性变化. 将SWTPSO与多种其他优化算法进行比较, 其在数值优化问题上展现较好的优化性能.

本文结构如下: 第1节介绍标准粒子群算法原理及相关研究; 第2节阐述方波触发机制; 第3节对本文提出的策略进行理论分析和实验验证; 第4节将SWTPSO与新改进的PSO和其他智能算法进行仿真实验, 并分析算法的优化性能; 第5节为总结与展望.

图 1  不同f 值的失败次数

图 3  PSO和PSO+SW的种群多样性变化

图 4  PSO和PSO + SW的收敛性

为提高粒子群算法全局最优的质量, 增强粒子逃离局部最优的能力, 本文提出方波触发机制, 在种群初始化后, 在前半个方波周期内进行全局勘探, 探索更多新解空间区域, 在后半个方波周期内转换为局部开发, 对该区域进行精细搜索. 在下个周期将自动获得与粒子当前位置有关的新速度, 使粒子获得的运动步长多变, 种群多样性增强. 在第3.1节中通过实验测定出方波触发机制的最佳周期, 并在第3.2节中证明, 方波触发机制通过为粒子提供多变步长, 提升种群的多样性. 在多类型测试函数上与新改进粒子群算法进行30、50、100维的测试, 且与其他新种类智能算法比较, 结果都表明SWTPSO优化性能更具优势.

但是, SWTPSO在高维情况下测试复杂函数时, 仍易陷入局部最优. 下一步的研究工作可从以下方面展开: 在方波触发机制中, 使用标准PSO公式进行全局勘探, 未考虑进化后期标准PSO中粒子的速度将变小, 全局勘探能力减弱的问题, 下一步的研究中, 可提出改进的更新公式, 承担全局勘探任务.

作者简介

邓志诚

南昌工程学院硕士研究生. 主要研究方向为群智能算法.E-mail: deng_zc215@163.com

孙辉

南昌工程学院教授. 1988年获清华大学硕士学位, 2002年获南昌大学博士学位. 主要研究方向为群智能算法, 粗糙集和变分不等原理. 本文通信作者.E-mail: sun_hui2006@163.com

赵嘉

南昌工程学院教授. 主要研究方向为群智能算法与数据挖掘.E-mail: zhaojia925@163.com

王晖

南昌工程学院教授. 主要研究方向为群智能算法与水资源优化.E-mail: huiwang@nit.edu.cn

吕莉

南昌工程学院教授. 主要研究方向为群智能算法与目标跟踪.E-mail: lvli623@163.com

谢海华

南昌工程学院硕士研究生. 主要研究方向为群智能算法.E-mail: pxlh_xhh@163.com