一种新的混合粒子群优化算法

          徐生兵， 冯继强

(东莞理工学院城市学院,       广东东莞523419) 

(深圳大学智能计算科学研究所，广东深圳518060) 

文章已被智能系统学报杂志社录用，智能系统学报杂志社投稿网址链接：http://www.zazhi114.cn/zhinenxitongxuebao

摘  要 针对粒子群算法在进化后期收敛精度低，收敛速度慢，容易早熟等问题，提出了一种新的混合粒子群优化算法。新算法首先设计了一种新的惯性权重，使其值在进化初期和后期都较为适中；其次，为了有效抑制粒子陷入局部极值，引入了粒子最优速度和最差适应值的概念，并以此为基础，设计了粒子的一种新的自适应变异方式。最后，对8个标准测试函数在100维，200维进行的数值实验证实：新算法收敛精度高，收敛速度快，且有效预防了早熟现象。

关键词 粒子群优化，惯性权重，收敛，早熟，变异

中图法分类号　TP18　　　  文献标识码　A

  A New Hybrid Particle Swarm Optimization

XU Sheng-bing ，FENG Ji-qiang

        (City College of Dongguan University of Technology，Dongguan 523000, China)

(Institute of Intelligent Computing Science, Shenzhen University，Shenzhen 518060, China)

Abstract  To overcome the disadvantages such as bad precision, low convergence and easy premature during the later evolutionary period of particle swarm optimization, a new hybrid particle swarm optimization(NHPSO) was proposed. In NHPSO, a new inertia weight was designed firstly to make its value to be moderate during the early or later evolutionary period; Secondly, to restrain particles from falling into local optima area, the concept of particle’s best velocity and worst fitness were introduced to make particles to mutate in a new adaptive style. Finally, the numeric experiments of eight benchmark functions in 100 and 200 dimensions prove that NHPSO has high convergence precision, fast convergence and prevents particle premature effectively.

Keywords  Particle swarm optimization (PSO); Inertia weight; Convergence; Premature; Mutation

1. 引言

粒子群优化( PSO)算法^[1]由Eberhart，Kennedy于1995

年提出来的一种基于种群智能行为的优化算法，由于其概念明确，要设置的参数少，编程易于实现等优点，目前在工程领域已经得到广泛的应用^[2- 6]。但PSO算法在优化复杂函数问题时，极容易陷入局部极值，并且会出现早熟现象，这又限制了PSO算法的进一步应用。为提高PSO算法的优化性能，许多学者提出了各种改进的PSO算法。其中，在惯性权重方面：SHI^[7]等人于1998首次引入了惯性权重的概念，并提出了一种线性递减的权重策略(详见第2小节)；为确保PSO算法的收敛，1999年，Clerc^[8]引入了压缩因子的概念，并提出了带有压缩因子的PSO算法；2001年，SHI^[9]等人又提出了模糊惯性权重的方法，即利用模糊控制器来动态自适应调节惯性权重，实现了对惯性权重的非线性控制；2009年，黄轩^[10]等人提出了一种基于随机惯量权重的快速PSO算法(Faster PSO with Random inertia weight， FRPSO)，即惯性权重在0.4～0.6之间随机取值。在改变粒子速度更新方式方面：2009年，Zeng^[11]提出了一种带有丰富社会认知的PSO算法，加强了粒子利用社会认知信息的能力；为加强粒子间的协作与信息共享的能力，Liang^[12]等人于2010年提出了一种利用种群质心和种群个体极值质心的PSO算法(PSO with Centroid，CPSO)，使得粒子的更新不仅与传统PSO算法中的个体极值和全局极值相关，而且与种群中其他粒子的位置和个体极值相关。2014年，胡旺^[13]通过目标空间变换方法,采用Pareto 前端在被称为平行格坐标系统的新目标空间中的分布熵及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似Pareto 前端的收敛性和多样性

本文首先对^[7,10]中的惯性权重的特点进行了分析，然后重构了一种新的惯性权重，使得其兼顾二者的优点；其次，对粒子陷入局部极值采取“防微杜渐”的策略，即在每一次迭代中，对满足某种条件的粒子进行一种新的自适应变异，而这种新变异是基于粒子最优速度和最差适应值的概念而提出来的。在与经典的LDWPSO，新近提出的FRPSO和CPSO的数值对比实验表明：新算法在优化复杂高维多模函数方面具有显著的优势。

2. 粒子群优化算法

PSO算法的数学描述过程如下：

在维搜索空间中，PSO算法首先初始化个随机粒

子，然后通过追踪两个极值(全局极值和个体极值)位置对粒子的位置进行更新，迭代运行直至满足停机条件，最后输出最优解。其中，在第代时，假设某个粒子的位置为，速度为，则第代粒子的位置和速度分别为：

                (1)

                              (2)

其中，式(1)，(2)分别称为速度更新方程和位置更新方程；称为惯性权重，表示对前一代速度的保留程度，一般取值范围为0.9~0.1；称为学习因子，一般取值为2.0；是之间均匀分布的随机数；为粒子自身迄今为止找到的最好位置，即粒子的个体极值位置；为整个种群迄今位置找到的最好位置，即种群的全局极值位置。

上述的惯性权重是PSO算法一个十分重要的参数。SHI^[6]等人通过大量的数值实验表明：较大的惯性权重有利于全局搜索，而较小的惯性权重有利于局部搜索，因而可以在迭代初期设置一个较大的惯性权重，以便较为迅速地定位到一个较优的搜索区域，在迭代后期使用一个较小的惯性权重，以便在这个较优的区域进行局部搜索，进而搜索到更好的解。因此，SHI提出了一种惯性权重线性递减(Linear-Decreased Weight，LDW)的策略，即： 

                (3)

其中，为最大惯性权重，为最小惯性权重，一般地取，；为当前迭代次数；为总迭代次数。这样，就会随着迭代次数的增加而线性递减。因此，使用(3)式权重策略的PSO算法被称为惯性权重线性递减的PSO算法，即LDWPSO算法。

3.  一种新的混合粒子群优化算法(NHPSO)

3.1一种新的惯性权重策略

由于惯性权重在PSO算法中可以控制算法的全局搜索能力和局部搜索能力，因此，关于惯性权重的研究已经取得了不少的进展^[7-10]，其中文献^[10]经过大量数值实验证实：惯性权重在0.4～0.6之间随机取值时，其总体实验效果要优于LDWPSO。与LDWPSO的惯性权重相比，FRPSO的特点是：初期惯性权重较小，后期惯性权重较大。但后期惯性权重较大是不利于粒子局部搜索的，(这在文献^[10]FRPSO与LDWPSO的对比实验中也可以看出来)，考虑到两种权重的各自特点和实验效果，本文构造了一种新的惯性权重，使其值在初期和后期均介于两者之间，具体如下：

                      (4)

其中，，。是一个变化范围较小的惯性权重，其变化范围约为[0.1,0.37]，且在迭代后期权重稍有回升；是一个非线性递减的权重，其变化范围约为[0.9,0.14]，这样的变化范围约为[0.15,0.67]。这样，与LDWPSO中的惯性权重相比，新惯性权重初期较小，后期稍大；与FRPSO惯性权重相比，初期稍大，后期较小，符合设计的初衷。三种权重的变化如图1所示(以为例)。

图1 三种PSO算法权重变化示意图

3.2 一种新的变异策略

PSO算法在陷入局部极值的时候，粒子之间的差异性很小，因此，让部分粒子变异将使得算法更有机会搜索到更好的解。文献^[14]提出了一种信息充分交流的PSO算法，利用了种群中大量可利用的信息，但没有利用粒子的速度信息。受此启发，本文利用粒子的速度信息和种群适应值的信息，构造了一种新的粒子位置的变异策略。为了叙述方便，先对粒子最优速度和最差适应值作如下定义：

定义1  PSO算法中，某个粒子在第代的最优速度，其中，表示粒子的初始速度。

定义2  PSO算法中，某个粒子在第代的最差适应值，其中，表示粒子的初始适应值。

那么，对粒子的变异操作是

                  (5)

其中，表示粒子在第代的适应值；表示全局极值粒子的最优速度，表示整个种群的当前最优适应值，用来给一个速度扰动。由于是一个较大的数，因此粒子可以以很大概率远离当前位置。

选取哪些粒子变异也是提高PSO算法性能的关键。文献^[15]提出了一种选择粒子进行变异的准则，取得了很好的效果。本文对此准则作了稍许改动，改动后的选取准则如下：

设种群在第代各粒子的适应值分别为，则第代种群的平均适应值，粒子与绝对偏差，检验值，其中，为粒子的个体极值，意义同前。对每个需要进行变异粒子的选取准则是。为了有效防止粒子陷入局部极值和确保算法的稳定性，因此，在每一次迭代中，对每一个满足准则且不是全局极值的粒子按(5)式进行变异操作。

3.3 NHPSO算法计算流程

NHPSO算法的计算流程与LDWPSO算法计算流程基本一致，不同之处有(1)：在最初要初始化粒子的最优速度和最差适应值，在每次更新的时候要更新粒子的最优速度和最差适应值；(2)：在每一迭代过程中，对满足变异条件的粒子均要进行变异操作。NHPSO算法的计算流程图如下：

图2 NHPSO计算流程图

4.  数值仿真实验

4.1 标准测试函数

在数值仿真实验中，选取表1所示的8个标准测试函数对LDWPSO，FRPSO，CPSO和NHPSO进行性能对比实验。

表1 标准测试函数列表

上述测试函数的理论全局最优解均为0。其中，容易优化；低维容易优化，高维很难优化；的优化难度较大；优化难度最大，是典型的极难优化非凸病态函数，是带有一定欺骗性的函数，因为全局最优与最好的局部最优相距很远，因此搜索算法往往朝着错误的方向收敛^[16]，是一个minima Problem^[17]，一般的PSO算法极容易陷入局部极值且极难优化。

4.2 实验参数设置及实验方案设计

4.2.1 实验参数设置

在实验中，所有算法的公共参数设置为：，为搜索区间长度的0.1，粒子的初始化区间为表1所示的搜索区间，但的初始区间为[-300,300]。LDWPSO算法中，；FRPSO和CPSO的参数设置均按参考文献设置，且算法优化性能也与参考文献一致。

4.2.2 实验方案设计

为了叙述方便，先给出算法平均收敛率和平均最小收敛代数的定义

定义3  如果算法在指定代的运算中，最终优化结果，其中为预设精度，则称该次算法收敛。若算法在次运算中，有次收敛，则平均收敛率

定义4 称算法收敛时，第一次满则预设精度的迭代次数为该次算法的最小收敛代数；如果算法在次运算中不收敛，则。设算法在次运算中，最小收敛代数分别为，则最小平均收敛代数。

实验方案1：在固定和条件下，比较。该方案中，，，，见表1，实验结果见表2(其中在表2中分别用Ⅰ，Ⅱ表示)。

实验方案2：固定，比较算法在时的平均值，最小值，方差。此方案中，。实验结果见表3～表4，～在=200的进化曲线见图3～图10。

4.3 实验结果

表2  实验方案1实验结果

算法		f1	f2	f3	f4	f5	f6	f7	f8
LDWPSO	Ⅰ	0	0.02	0	0	0	0	0	0
	Ⅱ	2500	2489	2500	2500	2500	2500	2500	2500
CPSO	Ⅰ	0	0	0	0	0	0	0	0
	Ⅱ	2500	2500	2500	2500	2500	2500	2500	2500
FRPSO	Ⅰ	0	0.06	0	0	0	0	0	0
	Ⅱ	2500	2499	2500	2500	2500	2500	2500	2500
NHPSO	Ⅰ	0.98	1.0 备案信息 举报中心 举报中心 行业协会 网络110 互联网协会 举报热线 首都协会 本站持《出版物经营许可证》 仅从事《西部医学》杂志的网上订阅工作,非任何杂志官网,并不涉及杂志社的出版等事务,特此声明！ 工信部备案：湘ICP备2025122662号-1，营业执照统一社会信用代码：91430721MAEHMRR7OE， 出版物经营许可证号：新安新出发证字第2025002号 特别声明:本站资料均源于网上的共享期刊资源，请特别注意，勿做其他非法用途。 如有侵犯您的版权或其他有损您利益的行为，请联系指出，期刊咨询服务平台会立即进行改正或删除相关内容! 扫码添加微信咨询 QQ客服：1663286777 电话：137-1883-9017 收到信息将及时回复