具备自纠正和逐维学习能力的粒子群算法

张津源，张 军，季伟东，孙小晴，张 珑

1(哈尔滨师范大学 计算机科学与信息工程学院，哈尔滨 150025)

2(天津师范大学 计算机与信息工程学院，天津 300387)

1 引 言

粒子群算法(Particle Swarm Optimization)是由Kennedy和Eberhart[1]在1995年受鸟类觅食行为的启发提出的一种进化算法.在算法中，每个粒子代表一个问题的潜在解.每个粒子以一定速度在多维搜索空间中飞行，粒子速度随着个体最佳位置和群体最佳位置的变换而更新.粒子群算法运行速度快且易于实现，近年来在旅行商问题[2]、文本功能选择[3]、预测时间[4]和动态车辆路径[5]等众多领域被广泛应用.但这些特点也使得粒子群算法存在很大的随机性，当粒子群算法在优化比较复杂的多峰问题时易出现过早陷入局部最优、收敛速度慢、收敛精度低等一系列问题，针对PSO存在的这些问题，研究学者们在调整参数、结合其他优化策略或算法以及改变粒子的邻域拓扑结构等方面做出了许多改进工作.

1998年Shi和Eberhart[6]提出了带有惯性权重的的粒子群优化算法，改进了最早期的PSO算法容易陷入局部最优的问题.Clerc随后就提出了带有压缩因子的粒子群优化算法[7]，根据粒子进化的不同阶段控制权重大小，解决陷入局部最优的问题并提高收敛速度.这是两种最经典的PSO改进算法.Gang[8]基于自然界中的种群迁移行为，将种群随机划分为若干子种群，利用竞赛选择的方式进行粒子迁移.Zhang[9]采用自适应策略在子种群上更新惯性权重，并通过共享信息自适应地更新当前记录.Xin[10]等人将粒子群算法和差分演化算法相结合,周期性的分析两算法性能并根据判定结果设置使用概率，将两算法充分结合，提高了解的质量.Xia[11]保留初始种群中的最差粒子并记录粒子的历史最差位置，利用这些信息牵引部分粒子迅速逃离局部最优；同时使用较优粒子的差分结果指导局部学习，有效平衡了粒子收敛能力和种群多样性.Li[12]提出了一种基于信息共享机制的竞争-协作PSO，一旦种群陷入局部最优，使用竞争机制选择评价结果更优的粒子指导其学习，同时种群中的所有粒子共享个体最优位置，加强了解之间的交流.随后Xia[13]又提出了一种基于多尺度选择性学习和探测-收缩机制的PSO.粒子根据当前进化阶段选择不同尺度进行学习，并且利用历史信息指导最优粒子在不同情况下采用探测收缩策略，保证了个体学习效率和算法开采能力.Wang[14]基于Logistic模型提出了一种自适应控制种群规模的策略，能够自适应的兼顾种群有效性和多样性，将该策略应用于PSO中显著提高了粒子收敛速度.Zhu[15]等人关注个体最优和群体最优的选择，将多目标优化问题分解为子问题集并为其分配相应的对象指导优化.Cao[16]深入探索了粒子种群的并行属性，根据分布式并行计算的特点提出了一种针对优化多目标大规模种群问题的改进粒子群算法.Tian[17]采用混沌反向策略生成高质量的解提高粒子寻优能力，基于有效的多样性机制使用3种不同突变策略来提高种群多样性.Li[18]遵循一阶差分方程的原理构造粒子的搜索轨迹，减少粒子的随机搜索使得粒子更加完全地探索搜索空间.Santos[19]通过对梯度信息和多样性控制提出了一种半自治的粒子群优化算法，提高了局部搜索效率.Abdelhafiz[20]利用粒子群优化和Akaike信息准则确定非线性放大器行为模型的维数，将该方案应用于广义记忆多项式模型，减少了发现最小模型的时间.上述研究成果中基于PSO的改进算法各有优点，都在粒子群算法的收敛速度和精度上有所改善，但是没有消除粒子群算法中随机性的影响，且大部分采用整体更新评价策略，无法避免维间干扰问题.

为进一步解决以上问题，同时关注到已有国内学者将逐维策略应用在一些除粒子群以外的其他群体智能算法上[21-23]获得了不错的优化效果.本文提出了一种具备自纠正和逐维学习能力的粒子群算法.通过提出一种纠正策略来控制算法随机性，同时使用改进的逐维学习策略更新最优粒子，有效提高粒子寻优能力.通过使用不同的控制周期巧妙结合两种策略的特性，使得本算法将两种策略的优点实现最大化的发挥.本文对选取的12个测试函数进行实验，结果表明，本文提出的两种策略发挥出了各自优势，改进的SCDLPSO相比PSO的寻优速度更快，求解精度更高；相比于其他3种改进的主流PSO算法[11，14,24]，SCDLPSO同样具有一定的竞争力.

2 具备自纠正和逐维学习能力的粒子群算法

2.1 纠正策略

传统PSO中粒子在进化过程中按照公式(1)和公式(2)进行速度和位移更新，粒子在进化过程中受个体最优(Pbest)和群体最优(Gbest)的指导，缺乏对粒子整个运动过程的关注，特别是在寻优难度较大的复杂多峰函数上，使得粒子在进化过程中产生很大的随机性，这是导致粒子群算法收敛速度慢的重要原因之一.

(1)

(2)

比如在种群进化过程中可能存在这种情况：粒子初始运动方向是向着最优解的方向前进的，但由于寻优过程的复杂性，接下来的某代上却朝着偏离最优解的方向移动，此时若继续按照公式(1)、公式(2)更新速度和位移，受由上一代部分粒子随机飞行而产生的错误信息指导，必然浪费粒子学习时间，导致收敛速度变慢.

为了解决这个问题，提出了一种纠正策略，即通过监督粒子在整个进化过程中运动方向的变化情况，对粒子下一代寻优方向实施干预以避免其继续受到错误指导，从而提高种群收敛速度.图1给出了纠正策略的简单示意图.图中A类粒子表示受到了随机性和错误指导的影响的粒子，其下一代更新将偏离最优解的方向，使用公式(3)更新速度，将速度向量方向取反，使得下一代能够向着最优解的方向移动，提高收敛速度，位置更新使用公式(2)；同时，运动方向正确的B类粒子则将继续按照原有的方式进行更新.

图1 纠正策略的二维示意图

(3)

2.2 Pbest指导Gbest的逐维学习策略

目前在大部分研究中，对种群中最优粒子指导方面都采用了选取所有维度整体更新再评价的策略，但对于复杂的多维函数的优化问题，使用这种方法会由于维间的相互干扰导致某些正确进化维度的信息被掩盖，从而导致评价次数的浪费，降低算法的收敛速度和效率.而逐维学习策略将最优解和学习对象在维度上进行拆分，独立的对每一维度上的信息进行考察，能够有效避免维间干扰的问题.

在PSO中，随着种群的进化，每个粒子的Pbest都在不断更新，它记录并更新着在飞行过程中的历史最佳表现，利用价值高.因此为了保证逐维策略中学习对象的多样性和有效性，本文结合Pbest的特点和逐维策略的优势提出了一种Pbest指导Gbest的逐维学习策略.

图2给出了本策略的模型示意图.图中引入了数据结构中的压栈与出栈操作模拟种群中所有Pbest逐个的对最优粒子进行指导的动作.

图2 Pbest指导Gbest的逐维学习策略模型图

该策略的思想是：按维度分解Gbest和Pbest位置向量，将Pbest上某一维的值和Gbest上其他维的值组成新的Gbest；计算适应度值评价新解；若当前新解质量更优则保留Pbest该维度信息对解的更新结果；否则放弃当前维度值，保留原Gbest维度信息不变.采用这样的贪心评价方式，直到各维度更新完毕.当一个Pbest的所有维上的信息都对Gbest的相应维指导结束后，执行出栈操作离开Pbest栈容器，并对Pbest栈容器进行压缩，开始其他Pbest对Gbest的指导.

算法1.Pbest指导Gbest的逐维学习策略

1.Fori=1:sizepop

2. Forj=1:D

3. 将第i个粒子的Pbest的第j维上的值替换给Gbest第j维得到newGbest;

4. Iffun(newGbest)

5. 用newGbest更新Gbest位置；

6. End

7. End

8.End

sizepop表示种群规模，D表示维数，newGbest表示在Pbest中第i维替换给Gbest第i维后的粒子，fun表示用于计算粒子适应度值的函数(fun(Gbest)即粒子Gbest的适应度值).

通过在逐维学习策略中引入贪心评价策略，彻底消除了某些维上出现退化的情况，避免了进化维度信息被掩盖的的问题，从而获得更高质量的解，显著提高收敛精度.同时，与大多数逐维学习策略中所采用的向某个单一对象学习的方式不同，该策略中Gbest受种群个体Pbest的指导影响，加强了个体最优粒子与群体最优粒子之间的联系，提高了最优粒子学习对象的多样性.

2.3 具备自纠正和逐维学习能力的粒子群算法

为了实现自动化的判断粒子更新方向，本文预设周期T1跟踪粒子运动轨迹并最终作出评估，若偏离最优解，则在T1+1代采用纠正策略；为了降低算法复杂度，采用每进化T2代使用一次逐维策略的办法.通过在两策略中引入两种不同的控制周期，提出了自纠正PSO(Self-Correcting Particle Swarm Optimization,SCPSO)、逐维学习的PSO(Dimension by Dimension Learning Particle Swarm Optimization,DLPSO)和具备自纠正和逐维学习能力的PSO(Particle Swarm Optimization with Self-Correcting and Dimension by Dimension Learning Capabilities,SCDLPSO).

首先，为了将纠正策略动态的应用于PSO，实现自动化地干预粒子学习方向，基于周期性思想，提出了自纠正PSO(SCPSO).每T1个评估代和1个纠正代共同组成自纠正策略的控制周期，及时避免粒子向更坏趋势更新.下面给出了两个功能代的概念和使用纠正策略的具体运行方式.

概念1评估代：判断粒子进化趋势的正确性.在评估代内记录粒子更新的适应度值，通过采用二分均值的比较办法，将预设的评估周期代数T1分半，在每个评估周期末代比较粒子后T1/2与前T1/2的适应度值平均值大小，如果粒子前T1/2的解更优，则判定粒子在本个评估周期T1内的更新受到了误导；反之，则判定粒子寻优方向基本准确.粒子在评估代上使用公式(1)更新速度.

概念2纠正代：根据评估结果作出响应，干预粒子学习方向.根据前T1个评估代的判定结果在第T1+1代作出响应，如果粒子受到了误导，则在纠正代触发纠正策略，使用公式(3)将粒子的速度方向置反，保证粒子的运动方向在下一个评估代开始之前得到纠正；反之，则继续使用公式(1)进行速度更新.粒子在评估代和纠正代上的位置更新公式都使用公式(2).

SCPSO在评估代上的运作方式和标准PSO大致相同，且大部分工作都是在纠正代上完成，因此算法2的自纠正策略中省略了评估代上的工作流程.

算法2.自纠正策略

1.Fori=1:sizepop

2. IFearlyMin

3. 使用公式(3)更新速度，使用公式(2)更新位置；

4.ELIFearlyMin>laterMin

5. 使用公式(1)更新速度，使用公式(2)更新位置；

6. End

7. 计算适应度值，更新Pbest,Gbest；

8.End

sizepop表示种群规模，earlyMin表示粒子在评估代T代中的前T1/2代的适应度值平均值，laterMin表示粒子在评估代T代中的后T1/2代的适应度值平均值

其次，考虑到连续使用逐维学习策略将导致计算量大、算法复杂度升高的问题，基于周期性思想提出了逐维学习的PSO(Dimension by Dimension Learning Particle Swarm Optimization,DLPSO)，在算法1中设置了一个较大的逐维学习周期T2，种群的整个迭代过程中只有在周期时间点上开启全局最优向个体最优逐维学习的机制，在略微影响求解精度的情况下，能够大幅减小了算法的复杂度.DLPSO将2.2中的算法1默认在每T2代上使用.

最后，SCDLPSO通过使用不同的控制周期将两策略结合，当粒子每进化T1个评估代后使用纠正策略，能够自动化的对粒子进化趋势进行监督，提高收敛速度，而后根据评估结果在每T1+1个纠正代上作出响应.采用纠正策略后，为进一步提高粒子的收敛精度，在每T2个代数周期上使用逐维学习策略，通过减少运行次数的方式来达到降低算法复杂度的目的.通过使用两种不同的控制周期充分结合两策略，发挥出最大优势.SCDLPSO的运行流程如图3所示.

图3 算法整体流程图

2.4 算法流程

具备自纠正和逐维学习能力的PSO(SCDLPSO)的算法流程如下：

Step 1.初始化种群，设置相应参数；

Step 2.判断当前代是否为评估代，若是，转Step 3，若不是，说明当前为纠正代，转Step 5；

Step 3.使用公式(1)、公式(2)更新种群中粒子的速度和位置；

Step 4.计算种群中粒子适应度值，并更新种群Pbest、Gbest；转Step 6；

Step 5.使用算法2更新种群中粒子的速度、位置和Pbest、Gbest；

Step 6.判断当前代是否为逐维学习代，若是，转Step 7，若不是，转Step 8；

Step 7.使用算法1更新种群Gbest；

Step 8.判断是否满足停止条件，若不满足，转Step 2，若满足，结束.

3 仿真实验与结果分析

本文使用Matlab2018a进行仿真实验.选取了表1中的12个经典测试函数来评估算法的寻优能力.算法在不同类型的函数上表现不同，因此本文选择了多个特征明显的函数进行实验，表1中F1、F2、F3、F9、F11、F12是高维单峰函数，仅存在一个全局最优点；F4～F8是高维多峰函数，含多个局部最优点，寻优难度较大.12个测试函数均为寻找最小值问题，全局最优值为0，F10的维数不能少于4维，且全局最小值和维数有关，易陷入局部最优.每个函数的特征如表1所示.

为了更加全面地验证本文提出的算法有效性，本实验共分为两阶段完成.在3.1的实验中将主要对比传统PSO、SCPSO、DLPSO和SCDLPSO，这一阶段的主要目的有两个，分别是：1)通过对比结果来验证本文算法策略的有效性和分析在不同指标上取得改进的原因；2)通过增加不同维度上测试函数的对比实验来说明本文算法策略的有效性和稳定性.3.2的实验中将本文的SCDLPSO与RLPSO[11]、SaDCPS+PSO[14]、CPSO[24]几种优秀的PSO改进算法进行比较，以便分析本文算法在同级别改进算法中的竞争力.

3.1 与PSO对比实验结果分析

3.1.1 寻优能力比较

本实验将本文提出的3种算法与传统PSO进行对比，验证应用两种策略使得算法在不同方面取得优势的真实性.基本参数设置如下：计算次数Time=10，最大迭代次数maxgen=1000，种群规模sizepop=50，维数D=100，学习因子c1、c2都为2；本文算法1(DLPSO)中的评估学习周期T设置为50，每个算法独立运行10次，算法2(SCPSO)中的评估周期T设置为4，上述将两种结合的整体算法(SCDLPSO)中的参数和算法1、2中的一致，评估周期T1设置为4，学习周期T2设置为50.

选取了表1中12个经典的测试函数来验证本文提出的3种算法性能.取平均值和最优值作为测试结果，具体测试结果详细见表2和图4.通过表2不难看出本文提出的SCDLPSO在12个测试函数上的性能表现相比基本PSO都更加优秀，其中对于函数F1、F4、F9、F11上优势明显，函数的均值相比基本PSO分别降低了16、31、16和16个数量级，说明本文中的算法能够显著改善粒子群的寻优能力、在避免发生早熟收敛的问题上更加具有优势，且其解非常接近最优解.同时本文先后提出的SCPSO、DLPSO相比基本PSO也都更加优秀，而SCDLPSO相比SCPSO，DLPSO在12个测试函数上的表现又更加优秀，说明本文算法达到了充分结合并发挥两种算法的优越性的目的.

表1 12个经典的测试函数

表2 改进算法与传统PSO在12个测试函数优化的结果

图4是4个PSO算法在12个测试函数上寻优过程的收敛曲线图，从图中可以清晰的看出，本文提出的3种算法在12个测试函数上的收敛速度和精度明显优于基本PSO，同时SCDLPSO优于SCPSO和DLPSO.

下面通过对本文提出的3种算法在函数6上的收敛曲线进行详细分析：如图4(f)所示，SCDLPSO与SCPSO相比，收敛曲线中出现了断层式的下降.这是由于DLPSO发挥了作用，通过在每个设置好的周期点上使用逐维学习策略使得最优解的寻找过程发生周期性的量级变化，说明SCDLPSO算法中引入的算法1更容易跳出局部最优值，避免早熟收敛；SCDLPSO相比DLPSO，在每个相同的时间点上几乎都能搜索到更优的解，这是由于在周期性的使用纠正策略的过程中选择了较小的控制周期，使得纠正粒子学习倾向的频率更高，能更加及时的对粒子进化趋势进行监督并纠正.说明SCPSO有效提升了种群粒子的收敛速度.收敛曲线表明SCDLPSO能够结合SCPSO和DLPSO算法的不同优势，保证粒子收敛速度的同时，仍能够提高求解精度.

图4 4种算法在12个测试函数上的寻优曲线

3.1.2 维度变化比较

为了验证SCDLPSO算法在随着维度的变化是否仍能够拥有比传统PSO更佳的收敛水平，进一步说明本文提出的改进算法的有效性，因此本节在3.1.1实验中设置的维数D=100的基础之上，将维数设置分别减小50维度和增加50维度，同样选取表1当中的12个经典测试函数再次进行实验对比寻优结果.设定计算次数Time=10，最大迭代次数maxgen=1000，种群规模sizepop=50，学习因子c1、c2都为2；SCDLPSO算法中评估周期T1=4，学习周期T2=50.表3给出了PSO算法和SCDLPSO算法分别在D=50和D=150的条件下运行后的平均值和最优值，最好的结果由粗体显示.如表3所示，本文提出的SCDLPSO算法的寻优效果在12个测试函数上都显著优于PSO算法.PSO算法维度从50增加到150的情况下，在12个测试函数上的寻优能力大幅降低，F1、F3、F7、F8、F11和F12函数的寻优结果的精度以2到3个数量级的大小的降低.相反，SCDLPSO算法在维度升高时，虽然数量级也有增加，但在除F2、F3、F10和F12以外的8个测试函数上的收敛精度都仍然趋近于最优值0，充分说明了本文提出的改进算法在求解精度上的有效性和稳定性.同时，当D=50时，函数F1、F4、F6、F11搜索到了最优值0；D=150时，函数F11搜索到了最优值0.由此可见，SCDLPSO算法采用的自纠正和逐维策略，在及时纠正粒子进化方向的同时，避免了维间干扰，展示出了更好的局部开采能力，有效解决了传统PSO在高维环境下收敛精度低的问题.

3.2 与其他改进PSO对比实验结果分析

为充分展现本文策略的有效性，本实验将本文提出的SCDLPSO与3种基于融合不同改进策略的PSO算法进行对比，选取改进的PSO算法分别为在多峰函数表现优秀的RLPSO[13]、能够自适应控制种群规模的SaDCPS+PSO[14]和引入混沌策略的CPSO[24].种群规模sizepop=50，维数D=100，最大迭代次数maxgen=2000，其他改进算法的参数与其文献保持一致.表3给出了4种改进算法在12个测试函数上所寻找到的最优解.

表3 不同维度的寻优结果

从表4可以直观的看出，针对不同函数，各个算法表现的性能也各不相同.对于F1，4种优化算法均寻找到了最优解0.针对F2和F3，SCDLPSO算法的性能弱于CPSO，但优于其他算法.在F5、F6、F8、F9、F10、F12上，SCDLPSO算法的性能都优于其他3个算法，特别是在F9上，SCDLPSO相比其他算法寻找到的最优结果超过了26个数量级，显著提升了解的质量.在F7和F11上，SCDLPSO和RLPSO都寻找到了最优解0.对于函数F6，其它改进算法性能不理想，但SCDLPSO能够成功收敛.

表4 各算法实验对比结果

本文提出的SCDLPSO算法的优化结果无论是在处理单峰函数还是多峰函数问题上，相比另外3种算法都达到了更佳的寻优效果，充分证明本算法的有效性，体现出在改进算法中较强的竞争力.

4 结 论

为了解决由于PSO算法的随机性而导致粒子在寻优过程中收敛速度慢、收敛精度低的问题，本文提出了一种具备自纠正和逐维学习能力的粒子群算法.通过提出的自纠正策略使得粒子能够自动评估解的优劣情况，并及时纠正粒子的寻优方向；同时利用个体最优粒子对群体最优粒子进行逐维指导，提高粒子学习对象的多样性并能够充分利用Pbest上的有效信息，改善解的质量；分别应用不同的控制周期将两策略结合到PSO中形成了SCPSO、DLPSO和SCDLPSO三种改进算法，实验结果表明，本文提出的SCDLPSO能够充分结合两种改进策略的优势，相比其他改进算法具有更快的收敛速度和更高的收敛精度.

虽然通过多次实验对比能够基本正确的设置控制周期，但文中算法控制周期的确定同样也是一个优化问题，目前仍不能够通过某种科学办法平衡两种策略的特点设置控制周期.因此，后续工作将主要解决这个问题，以充分发挥算法效能.此外，还需要将本算法在更多的实际优化问题中应用并进行分析验证.