基于混沌优化的动态自适应粒子群优化算法

朱洪根，田立勤,2，陈 楠

(1. 华北科技学院 计算机学院,北京 东燕郊 065201; 2. 青海师范大学 计算机学院,青海 西宁 810000)

0 引言

粒子群算法(Particle Swarm Optimization,PSO)是受鸟群和鱼群捕食行为启发而产出的一种全局迭代优化算法，是由Kennedy和Eberhart等[1]在1995年提出的一种演化算法，该算法的优点为:结构简单、收敛速度快、鲁棒性强。

由于PSO算法在寻优搜索过程中，不能很好的平衡粒子的局部和全局搜索能力，导致PSO算法易陷入局部最优，降低了PSO寻优解的精确度。基于此，Shi与Eberhar[2]于1998年提出惯性权重的概念(基本粒子群算法,BPSO)，通过惯性权重可以更好的控制粒子的搜索范围，惯性权重偏大则有利于提高算法的全局搜索能力，偏小则有利于增强算法的局部搜索能力。针对PSO算法的全局和局部搜索能力不平衡问题，Shi与Eberhart进一步提出了线性递减的惯性权重[3](标准粒子群算法,SPSO)，该算法对静态的惯性权重进行了改进，线性递减的惯性权重可以对粒子的迭代前期和后期搜索行为进行限定，粒子在整个迭代期间可以进行多元搜索。文献[4]使用压缩因子K来保证PSO快速收敛(KPSO)，该算法比SPSO能够更快收敛，但也易陷入早熟状态。针对粒子群算法的优化问题，国内学者也取得了一定的研究成果。文献[5]提出一种基于邻域速度模仿策略的粒子群算法，该算法让迭代中的粒子以一定的概率直接模仿邻域内的最优粒子的速度，自适应的调整粒子的收敛情况，并对速度排名靠后的粒子进行质心变异，以增强算法跳出局部极值的能力。文献[6]将种群分成3个子种群，不同种群之间的参数设置将影响最后的PSO算法的综合性能，但该算法需要凭借经验对其算法本身进行参数设置。文献[7]针对求解符号回归问题，提出突变算子和散开算子的概念以改进粒子群算法早熟收敛的问题，当满足突变要求时，对粒子进行突变以改变粒子状态；当某一点上聚集过多粒子时，只保留其中一个，其余粒子采用突变的方式让其离开原始位置。但文献[5-7]并没有对粒子群算法的惯性权重进行改进，基于此，文献[8]使用指数函数来构造惯性权重、文献[9]使用非线性sigmoid函数来构造惯性权重，为惯性权重的改进提供了一种新思路。文献[10]结合差分进化算法对惯性权重进行改进，并加入了边界值的处理，对粒子的速度和搜索位置进行限制，但文中并没有对陷入局部极值的粒子予以处理，算法容易早熟收敛。文献[11]采用多尺度选择性学习机制在多个维度上进行选择性学习，以提高粒子的学习效率，当粒子处于局部极值状态时，执行空间收缩策略，将种群的搜索空间限定在一个较小的区域，以增强算法的搜索能力。文献[12]提出一种自适应惯性权重混沌粒子群算法，使用动态的惯性权重对粒子速度进行更新，并对处于局部极值状态下的粒子使用Logistic方程的一种演化式对粒子的位置进行更新，但该算法存在稳定性不足等问题。

综上所述，针对基本粒子群算法存在早熟收敛、易陷入局部极值的问题，提出了基于混沌优化的动态自适应粒子群优化算法(dynamic adaptive inertial weight particle swarm optimization algorithm based on chaos optimization， DAWCPSO)。使用动态自适应的惯性权重对粒子在迭代前期和后期的搜索行为进行改进，当粒子陷入局部极值状态时，使用混沌优化策略扩大粒子的搜索范围，使粒子能够继续在可行域下进行寻优。

1 基本粒子群算法

(1)

(2)

基本粒子群算法的计算步骤如下：

step1初始化一个规模为N，维度为D的粒子群，设定粒子的初始位置和速度；

step2计算适应度值；

step3更新pbest和gbest信息：

(1) 将粒子i的适应度值和粒子i经过的pbest做比较，如果粒子i的适应度值优于pbest，则pbest的值为粒子i的适应度值；

(2) 将粒子i的适应度值和全局最优位置gbest做比较，如果粒子i的适应度值优于gbest，则gbest的值为粒子i的适应度值；

step4根据式(1)和式(2)，更新每个粒子的位置X和速度V；

step5满足终止条件则退出，否者返回step2继续迭代。

2 DAWCPSO算法

2.1 动态自适应的惯性权重

惯性权重(ω)表示粒子的历史速度对当前速度的影响程度，由于惯性权重的存在，新粒子对历史粒子具有一种“记忆”，能够平衡新粒子的搜索行为。惯性权重较大，则粒子的全局搜索能力较好；反之，则局部搜索能力较好。在PSO算法迭代过程中，线性递减的惯性权重是对惯性权重的一种比较基础改进方式，但PSO算法的迭代演化过程是一种十分复杂的计算，线性递减的方法显得相对单一。在迭代后期，惯性权重偏小，当粒子的pbest和gbest距离较近时，所有粒子会快速趋于一点，此时粒子速度接近于零，虽然能较快收敛，但是也导致了算法早熟收敛。因此，本文提出一种新的动态自适应惯性权重方法，公式如式(3)和式(4)，在算法演化后期，惯性权重稍有提升，能够提升算法演化后期的全局搜索能力。

(3)

(4)

式中，iter和itermax分别表示当前迭代次数和最大迭代次数；参数k是迭代系数[12]，以确保惯性权重在迭代前期较大和后期较小的需要[3,13]。

2.2 结合混沌优化摆脱局部极值

混沌(Chaos)是一种非线性的自然现象[14,15]，其行为复杂，类似随机，但也有内在规律性。由于混沌运动具有遍历性，利用混沌运动的思想优化粒子搜索路径会比盲目无序的随机搜索更具有优越性，它可以避免每次的随机运动不会发生重复。常用的产生类似于随机的混沌序列的方程式为Logistic映射，如式(5)所示。

(5)

(6)

(7)

2.3 DAWCPSO算法计算流程

图1是改进后的粒子群优化算法(DAWCPSO)的计算流程图，以下是DAWCPSO算法的计算步骤：

Step1初始化一个规模为N，维度为D的粒子群，设定参数μ和η，给定粒子的初始位置和速度；

Step2计算适应度值；

Step3更新pbest和gbest信息：

(1) 将粒子i的适应度值和粒子i经过的pbest做比较，如果粒子i的适应度值优于pbest，则pbest的值为粒子i的适应度值；

(2) 将粒子i的适应度值和全局最优位置gbest做比较，如果粒子i的适应度值优于gbest，则gbest的值为粒子i的适应度值。

Step4对粒子的位置X和速度V进行更新：

(1) 根据式(3)和式(4)更新当前迭代的惯性权重；

(2) 根据式(1)和新的惯性权重更新粒子的速度，并判断更新后的粒子速度是否超出速度的临界值，当超出临界值时，则将当前粒子的速度设为临界值状态；

(3) 根据式(7)判断当前粒子的位置是否处于局部极值状态，如果是，则使用式(5)更新粒子的位置信息，否则使用式(1)更新粒子的位置，判断更新后的粒子位置是否超出位置区间的临界值，如果是，则将粒子放在搜索去边界继续搜索。

Step5如果当前迭代次数大于最大迭代次数itermax则退出，否者返回Step2继续迭代。

图1 DAWCPSO算法流程图

2.4 算法复杂度分析

算法时间复杂度是一种能定性描述当前算法的运行时间的指标，算法时间复杂度越大，表示算法的执行效率越低，时间复杂度越小，则执行效率越高。

假设粒子总数为N、搜索维度为D、最大迭代次数为Imax，假设基本粒子群算法每一次迭代过程的计算时间为TB，则T1为N×D×Imax×TB。假设DAWCPSO算法在每次迭代过程中的计算时间为TD，则T2为N×D×Imax×TD，从T1和T2可以看出，BPSO和DAWCPSO算法的时间复杂度本质上取决于算法每次迭代过程的计算时间。BPSO算法的每次迭代需要对式(1)和式(2)进行计算；DAWCPSO算法的每次迭代则先对式(1)进行计算，再根据式(7)的计算结果做出判断选择(2)或式(5)进行计算。但由于当前适应度值和全局最优值的计算结果是在对式(7)判断之前计算完成的，所以DAWCPSO算法比BPSO算法需要多花的时间开销便是对式(7)中的分子和分母做商值计算的时间以及与η做判断的时间，其时间复杂度相当于在BPSO算法基础上多做了两次计算。根据时间复杂度的计算规则，这两次计算所消耗的时间属于常数时间，可忽略不计，其推理过程如下：

式中，n表示算法的运算量。

综上所述，DAWCPSO算法的时间复杂度和基本粒子群算法的时间复杂度都为O(n)，空间复杂度也是O(n)。

3 算例分析

为了验证DAWCPSO算法的有效性，使用6种测试函数对该算法进行测试，测试函数信息见表1，并与BPSO[2]、SPSO[3]、KPSO[4]、IPSO[1]算法进行比较。

表1 测试函数及其参数

3.1 实验环境与参数设定

3.1.1 实验环境

硬件环境：CPU型号为Intel Core i5-10300H @ 2.50 GHz (8 CPUs)，内存为DDR4 (16G )，硬盘为KINGSTON OM8PCP3(512G)；软件环境：操作系统为64位的Windows10，编程语言为Python 3.6.10，集成开发环境为PyCharm Professional 2020.2。

3.1.2 参数设定

粒子群算法的粒子数都设定为30，搜索维度都设为30，学习因子c1和c2都取2，最大迭代次数为3000次。不同PSO算法的其他参数设定如下：BPSO算法的惯性权重为0.83；SPSO算法中，ωmax为0.9，ωmin为0.4；KPSO算法中，α取值为4.1，则K为0.729；IPSO算法中，a和b分别取值0.1和0.2；DAWCPSO算法中，μ为3.98，η为0.3。

3.2 实验结果与分析

3.2.1 实验结果

每种算法执行50次后取其平均值进行比较，各算法对表1中6种测试函数的测试结果如图2-8所示，其中，由于各算法对Ridge函数的寻优结果起始点过高(1464.668)，为了便于观察，将第1000次迭代到3000次的迭代结果重新画图，如图7所示；各算法的平均最优解如表2所示。

表2 各算法寻优结果的平均最优值

图2 各算法对Sphere的收敛曲线

图3 各算法对Schwefel’s 2.22的收敛曲线

图4 各算法对Ackley的收敛曲线

图5 各算法对Schaffer’s F7的收敛曲线

图6 各算法对Ridge的收敛曲线

3.2.2 结果分析

从表2可以看出，DAWCPSO算法在6个测试函数上的测试效果都要优于其他对比PSO算法。其中，DAWCPSO算法对Sphere和Rastrigin函数的解已经达到了理论最优解。且在Schwefel’s 2.22、Ackley、Schaffer’s F7、Ridge函数的测试结果中，DAWCPSO算法的解精度也更高。当粒子处于局部极值状态时，DAWCPSO算法能够对当前粒子的位置做出调整，及时改变粒子的搜索位置使其能够继续在可行域下寻找其他可能解。从图2～图6以及图8可以看出，DAWCPSO算法在较短时间内可收敛到某个局部极值点，但在该极值点停留一段时间后，粒子开始继续迭代寻优，进一步提高解的精度。

4 结 论

(1) 针对粒子群算法易早熟收敛的问题，本文提出了基于混沌优化的动态自适应惯性权重粒子群优化算法，其中，惯性权重根据粒子的迭代次数进行调整，以平衡算法的全局和局部搜索能力。

(2) 当DAWCPSO算法判断当前粒子处于局部极值点时，能够使用混沌优化策略扩大粒子的搜索范围，当前粒子能够获得一个新的随机且不重复的位置，从而能够继续在可行域下寻找最优解。

(3) 经时间复杂度分析，在不影响粒子群算法收敛性能的前提下，DAWCPSO算法提升了粒子群算法所求解的精度。