混沌动态改变权值策略的粒子群优化算法

孟 倩

(江苏师范大学 计算机科学与技术学院，江苏 徐州 221116)

0 引言

粒子群优化(particle swarm optimization，PSO)算法是一种进化优化算法，由Kennedy等[1]于1995年首次提出.PSO算法中可控制粒子速度的惯性权值(w)是一个非常重要的参数，可以调整算法的局部开发和全局探测能力[2].PSO算法简单、容易实现，收敛速度快，容易与其他算法结合，具有深刻的智能背景，既适合科学研究，又特别适合工程应用[3].但是，标准PSO算法的一个缺点是粒子的飞行速度大小影响着算法的全局收敛性，不能保证PSO算法收敛于函数的全局极值点[3-4];另一个缺点是PSO算法容易“早熟收敛”，即参数选择不当时，寻优过程中可能会迅速丧失粒子群体多样性[5].为解决这些问题，学者们提出了很多有效的改进算法,如惯性权重线性调整策略(linearly decreased inertia weight,LDIW)[2]、惯性权重非线性调整策略(nonlinear deceased inertia weight,NDIW)[6]、凹函数递减策略(concave function inertia weight,CFIW)[3]、指数曲线递减策略(exponential curve inertia weight,ECIW)[3]、粒距反馈S函数粒子群权值调整策略[7]、混沌搜索策略[8-9]、动态调节惯性权重策略[10-11]及自适应动态非线性改变权值策略[12-13]等.本文借鉴已有文献思想，提出一种基于混沌和动态改变权值策略(chaos dynamically changing inertia weight,CDCIW)的改进粒子群算法，并通过基准测试函数来验证算法的有效性和可行性.

1 基本粒子群算法

在粒子群优化算法[14]中，优化问题的每个解与搜索空间的一个粒子相对应，每个粒子是一个个体，由位置矢量和速度矢量组成.粒子在运动中产生的最优位置为

pi=(pi1,pi2,…,piD),i=1,2,…,m，

(1)

式中：m为粒子的个数，D为粒子的维数.

第i个粒子的D维位置矢量为xi=(xi1,xi2,…,xiD)，速度矢量为vi=(vi1,vi2,…,viD)，二者分别决定了第i个粒子飞行的位置和方向；整个粒子群历史搜索到的最优位置为pg=(pg1,pg2,…,pgD)，其中g∈{1,2，…,m}为粒子编号.粒子群初始化后，对每个粒子计算其适应值，通过迭代搜索最优解.每个粒子根据

vi(k+1)=wvi(k)+c1r1(pi(k)-xi(k))

+c2r2(pg(k)-xi(k)),

(2)

xi(k+1)=xi(k)+vi(k+1)

(3)

来更新自己的速度和位置.式中：k为迭代次数；w为惯性权重；r1,r2为[0,1]之间的随机数；c1,c2为学习因子，取值范围一般在[0,4]之间.

2 改进的粒子群优化算法

本文提出一种改进的粒子群优化(improved particle swarm optimization,IPSO)算法，改进部分主要表现在以下2个方面：

1)为了有利于粒子进行全局搜索和局部搜索，提出一种基于粒距的动态改变权值w的策略；

2)为了增加粒子多样性，避免粒子群在优化后期陷入局部最优解，引入混沌映射.

2.1 基于粒距的动态改变权值策略

在相关研究成果[2-3,7-9]的基础上，提出一种基于粒子距整个种群的历史最优位置的距离(简称粒距)来动态改变权值策略.在该策略下，惯性权重的计算公式为

w=wmin(wmax/wmin)1/(1+ε·k/kmax),

(4)

式中ε为由粒距决定的权值调节因子.

第k次迭代,第i个粒子的粒距定义为

(5)

式中：xij(k)为第k次迭代时第i个粒子的位置向量的第j个分量；pgj(k)为第k次迭代时，种群历史最优位置向量的第j个分量.

根据每个粒子的粒距选择ε值来控制粒子速度,公式为

(6)

式中：εmax和εmin分别表示ε的最大值和最小值，文中分别取15和8；dmax和dmin分别表示最大和最小粒距.粒距di(k)越大，ε就会越小，该粒子的惯性权重就会越大，粒子速度就越大，有利于粒子进行全局搜索；反之，di(k)越小，ε就会越大，惯性权重就会越小，粒子速度就越小，有利于粒子进行局部搜索.权值w随ε的变化趋势如图1所示.

图1 不同ε取值的惯性权重变化曲线

2.2 引入混沌映射

基于粒距调整粒子群惯性权值策略可以增强粒子的搜索能力，但到了进化后期，如果整个粒子群密集地聚集在一起，粒子多样性消失，有序性增强，粒子飞行速度越来越慢，整个粒子群停滞不前，则仍然可能发生早熟收敛，陷入局部最优解[15].因此，为了避免陷入局部最优解，使种群保持多样性，增加粒子混乱度，本文引入混沌算法,提出基于混沌和粒距的动态改变权值策略(CDCIW).

混沌遍历性特点可被用来进行优化搜索，且能避免陷入局部极值.本文将混沌算法与粒子群算法结合，利用混沌算法来增强全局搜索能力，以提高算法搜索的精度.常用的混沌规则有Logistic map、Henon map以及tent map等[16].研究表明，Lozi映射的混沌方法比常用的Logistic映射混沌方法具有求解精度高及效率高等优点[16].本文选取二维间断离散混沌动力系统Lozi方程[16]

ln=1-a|ln-1|+yn-1，

(7)

yn=bln-1，

(8)

式中：n为迭代次数，ln∈[0,1]为混沌变量;参数a>1.5后进入混沌运动(常取1.7)，b常取0.5.

3 IPSO算法

设f(xi)为优化目标函数：

minf(x1,x2,…,xn)，xi∈(ai,bi).

(9)

IPSO算法如下：

步骤1粒子初始化.设置PSO参数，包括粒子群体大小N(N过小，容易陷入局部最优解，N过大容易导致算法运行时间过长，一般取20～40)，粒子维度D，加速因子c1和c2等.

步骤2随机产生种群，初始化粒子速度和位置，初始化每个粒子历史最优位置(pbest)和所有粒子的最优位置(gbest).

步骤3计算每个粒子的适应度函数值.如果当前粒子适应度值优于pbest对应的适应度值，则将pbest更新为当前粒子位置.

步骤4对每一个粒子，如其当前位置的适应度值优于全局gbest对应的适应度值，则将gbest更新为该粒子的当前位置.

步骤5按照本文提出的基于粒距动态改变权值策略，由公式(4)—(6)计算惯性权重w值.

步骤6按照公式(2)和(3)对每个粒子的速度和位置进行更新.

步骤7对最优位置pg=(pg1,pg2,…,pgD)进行混沌优化.

1)通过

li=(pgi-ai)/(bi-ai),i=1,2,…,D,

(10)

将pgi(i=1,2,…,D)映射到[0,1]上.

3)通过

(11)

对混沌序列作逆映射，使其回原解空间，从而得到一个混沌变量可行解序列

(12)

4)计算可行解矢量的适应度值，并保留适应度值最优时对应的可行解，记为p*.

5)从当前粒子群中随机选择一个粒子的位置，用p*代替.

步骤8如果满足迭代停止条件，停止搜索，输出结果，否则跳到步骤3.

4 试验结果

采用3个标准函数来测试本文提出的IPSO算法的寻优性能，并与基于LDIW、CFIW、NDIW和ECIW惯性权值策略的粒子群算法LDIWPSO、CFIWPSO、NDIWPSO和ECIWPSO做比较.3个标准测试函数的全局最小值都为0，各PSO算法中粒子数均取30，c1=c2=2，迭代结束条件为迭代次数超过2 000.为了考察算法的可扩展性，对每个测试函数分别取10维和30维进行试验.

1)函数f1(Ackley function):

minf1(x)=f(0,0,…,0)=0.

它是一个具有大量局部最优点的多峰函数，xi=0时达到全局极小点0.2维Ackley函数图像见图2.表1为10、30维时，每种方案独立运行30次，5种算法求解的全局最优适用度平均值(表中简称平均最优值,下同)和标准差，以此作为性能比较的依据.当n=30时，Ackyley函数最优适应值随迭代次数变化曲线见图3.

图2 Ackyley函数图像

表1 Ackyley函数平均最优值与标准差

图3 Ackyley函数最优适应值随迭代次数变化曲线(n=30)

2)函数f2(Rosenbrock function):

minf2(x)=f(1,1,…,1)=0.

它是一个全局最小值位于一个非常狭窄的山谷中的非凸的二次函数.由于该函数解空间有相当多的狭窄通道，所以收敛到全局极小点是非常困难的.图4描绘了n=2时的Rosenbrock函数图像，表2为10、30维时，每种方案独立运行30次，5种算法求解的全局最优适用度平均值和标准差，以此作为性能比较的依据.当n=30时，Rosenbrock函数最优适应值随迭代次数变化的曲线如图5所示.

图4 Rosenbrock函数图像

图5 Rosenbrock函数最优适应值随迭代次数变化曲线(n=30)

表2 Rosenbrock函数平均最优值与标准差

3)函数f3(Rastrigin function)：

xi∈(-5.12,5.12)，

minf3(x)=f(0,0,…,0)=0.

它是一个具有很多局部最小值点和局部最大值点的多峰函数，在点xi=(0,0,…,0)处获得全局最优值0.优化算法很容易陷入局部极点而不能得到全局最优解.2维Rastrigin函数图像如图6所示.表3为10、30维时，每种方案独立运行30次，5种算法求解的全局最优适用度平均值和标准差，以此作为性能比较的依据.当n=30时，Rastrigin函数最优适应值随迭代次数变化曲线如图7所示.

图6 Rastrigin函数图像

图7 Rastrigin函数最优适应值随迭代次数变化曲线(n=30)

表3 Rastrigin函数平均最优值与标准差

从表1—3和图3、5、7中可以看出，本文提出的IPSO算法在3个测试函数上的表现普遍优于其他算法，其平均最优适应值都最小，因此,IPSO算法比其他4种PSO算法精度更高，更稳定.当增加到30维后，虽然IPSO算法精度丢失较大，但仍优于其他算法，而且标准差最小，即结果较为稳定.这是由于IPSO算法惯性权重选择较为恰当，且引入混沌运算，使种群更加多样化，增强了PSO算法摆脱局部极值点的能力，从而提高了算法的全局搜索能力和精度.LDIWPSO、CFIWPSO、NDIWPSO 3种算法性能较为接近，优化结果都不太理想;ECIWPSO算法性能虽低于IPSO算法，但也较为理想，优于其他3种算法.

5 结论

本文提出了一种基于混沌和粒距的动态改变权值策略的改进的粒子群优化算法：根据粒距在每次迭代动态改变权值，有助于避免陷入局部最优解；为了增加粒子的多样性，引入混沌优化思想.本文算法可有效改善粒子群算法摆脱局部极值点的能力，从而提高粒子群算法的寻优能力和精度.在Ackley、Rosenbrock、Rastrigin 3个基准测试函数上仿真，结果表明，本文算法对于多极值点的高维复杂函数，能够获得精度较高的全局极值，其精度明显优于作比较的其他粒子群优化算法.