基于局部协同与竞争变异的动态多种群粒子群算法

孙欣 于慧 王宇嘉 林炜星 梁海娜 陈万芬

摘 要：针对粒子群算法在处理复杂优化问题时，出现多样性较差、收敛精度低等问题，提出了基于局部协同与竞争变异的动态多种群粒子群算法（Dynamic Multi-population Particle Swarm Optimization Based on Local Cooperative and Competitive Mutation，LC-DMPPSO）。LC-DMPPSO算法设计了一种局部协同的方法，该方法划分种群成多个子种群，划分后的子种群再通过非支配排序、差分变异的方法选择出一对领导粒子。同时，对粒子的更新方法进行改进，让各个目标优化更加均衡，增强LC-DMPPSO算法的局部搜索能力，提高收敛精度。在LC-DMPPSO算法中，为了防止出现“早熟”收敛的情况，引入竞争变异来增加种群多样性。最后，通过选择一系列标准测试函数将LC-DMPPSO算法与3种进化算法进行比较，验证所提算法的有效性。实验结果显示，所提算法的多样性和收敛性比其他3种进化算法更好，优化效果更佳。

关键词：多目标优化问题;粒子群算法;多种群;局部协同;竞争变异

Abstract：In view of the poor diversity and low convergence accuracy of particle swarm algorithm when dealing with complex optimization problems， a dynamic multi-population particle swarm optimization based on local coordination and competitive mutation （Dynamic Multi-population Particle Swarm Optimization Based on Local Cooperative and Competitive Mutation， LC-DMPPSO）. LC-DMPPSO designed a local coordination method， which divides the population into multiple sub-populations， and then the divided sub-populations select a pair of leader particles through the method of non-dominated sorting and differential mutation. At the same time， the particle update method is improved to make the optimization of each target more balanced， enhance the local search ability of LC-DMPPSO， and improve the accuracy of convergence. In LC-DMPPSO， in order to prevent "premature" convergence， competitive mutation is introduced to increase population diversity. Finally， a series of standard test functions are selected to compare LC-DMPPSO with three evolutionary algorithms to verify the effectiveness of the proposed algorithm. The experimental results show that the diversity and convergence of the proposed algorithm are better than the other three evolutionary algorithms， and the optimization effect is better.

Key words：multi-objective optimization problem （MOP）; particle swarm optimization （PSO）; multi-population; local cooperative; Competition mutation

在現代工程领域中，很多情况下会遇到复杂的多目标问题[1-3]，这些问题中的目标相互冲突，其中一个目标的最佳解决方案可能是另一个目标的最坏解决方案。因此，MOP只能用一组称为帕累托最优解[4] 来描述。在求解MOP中，不难发现的是如何平衡各目标之间的冲突，才是求解的关键。文献[5]中提出一种通过最近邻方法的归档更新机制，减少计算量。文献[6]中使用神经模糊系统确定遗传交叉和变异算子，提高算法性能。文献[7]中将改进的萤火虫算法与粒子群优化算法相结合，解决了自动数据聚类问题。文献[8]中将整个进化过程分为前阶段和后阶段，既保持种群的多样性又能提高种群整体的收敛精度。文献[9]中将加权期望后的贝叶斯优化方法处理电路模块划分问题，并将该方法扩展到MOP上，该方法能够在更少的迭代中，取得最好的优化结果。文献[10]中采用动态分解的参考向量动态划分分解空间的方法寻找最优解。文献[11]中在处理计算昂贵的适应度函数时，提出具有主动学习的代理辅助粒子群算法。然而，该算法牺牲种群多样性为代价提高局部搜索能力。

为了使PSO算法在解决多目标优化问题中的收敛性与种群多样性之间取得平衡，现提出LC-DMPPSO算法。LC-DMPPSO算法通过与其它3种算法，在一系列的标准测试函数进行对比实验，验证其求解复杂优化问题的有效性。

1 MOP模型与PSO

1.1 MOP模型

MOP极小化模型[12]定义如下：

2 算法介绍

2.1 局部协同

在面对复杂的多目标问题时，利用多个种群可以取得更好的优化结果，基于这种思想，LC-DMPPSO采用一种协同策略，即局部协同。其是将初始种群划分为M+1个子种群。M个待优化的目标分别对应M个子种群。接下来，划分后得到的M个子种群在选择领导粒子时，通过非支配排序的方式进行筛选，每个子种群最终得到一对领导粒子，该方法为粒子提供更多向优秀个体学习的机会，引导种群向更好的方向进化。在第M+1的子种群中，利用差分变异方式（Differential Mutation，DM）选择领导粒子，充分利用DM的全局搜索优势，能够保障LC-DMPPSO的收敛性。具体步骤如下：

（1） 将整个初始种群按照M个待优化目标随机划分为M+1子种群;

（2） M个子种群针对M个目标进行优化，计算粒子的适应度值以及拥挤距离，得到该粒子的非支配等级。然后，依据非支配等级选择出一对领导粒子。最后，更新粒子信息;

（3） 另一个子种群依照DM的方法从自身最优粒子中选择领导粒子，每个子种群通过领导粒子完成更新操作;

（4） 完成上述工作，将M+1个子种群合并。

2.2 领导粒子选择

在LC-DMPPSO中，会根据种群中的每个粒子的特点去决定领导粒子。被选择作为领导粒子的一对粒子，引导其向更好的方向发展。假设M个子种群中的第k（k=1，2，…，M）个子种群针对目标fk进行优化。此时，第i个粒子选择领导粒子时，需要判断粒子i的非支配等级，预选的领导粒子的非支配等级必须在粒子i之上。接下来，预选的领导粒子被确定后，可以在其中任意选择一个非支配等级。然后，对排列在相同等级下的粒子进行进一步的筛选，通过计算粒子在目标fk上的适应度值，选择表现最好的粒子作为领导粒子lbest1。

但是，若在该非支配等级上存在两个及以上的粒子，那么就会按照拥挤距离作为评判标准，选择其中较大的那个粒子成为领导粒子，记为lbest1。然后，依据领导粒子lbest1进行排序后，选择距离lbest1最近且拥挤距离最大的粒子作为另一个领导粒子，记为lbest2，构成的一对领导粒子lbest1，lbest2将引导整个种群的进化方向。

领导粒子的具体选择操作如下：首先，建立一个临时档案用来存储所有粒子，临时档案中有6个粒子，编号为1～6。此时，假设子种群针对目标fk进行优化，6个粒子在临时档案中进行非支配排序后的等级排序结果如表1所示，表1中共有三个等级。假设子种群的第i个粒子选择领导粒子时，第i个粒子的非支配等级为一级，此时的预选领导粒子分别为1﹑5。若随机选择种群的第i个粒子的等级为二级，领导粒子lbest1应是粒子1、5、3、6中在目标fk上表现最好的粒子，假设粒子3是fk上表现最好，那么粒子3就被选为领导粒子lbest1。然后，再根据粒子3的位置，在剩余的5个粒子中选择非支配排序离它最近且拥挤距离最大的粒子作为领导粒子lbest2。LC-DMPPSO算法中选择两个领导粒子，让其余所有粒子有机会向邻近粒子学习，增强局部搜索能力，同时，设计多个子种群可以动态地针对单个目标进行优化，能够有效地提高LC-DMPPSO算法的收敛精度。

同时，为了更直观地验证LC-DMPPSO有效性，4种算法在3个目标上得到的pareto前沿的实验仿真结果如图3～图5所示。从图3中可以看出，LC-DMPPSO在3个目标测试函数DTLZ4上能够得到更多的非支配解，MOPSO-SDCD和MMOPSO明显没有很好的收敛在pareto前沿上，没有达到很好的优化效果。同样，在3个目标DTLZ4上，LC-DMPPSO的pareto分布最好。最后，在3个目标WFG9上，LC-DMPPSO分布依然是4个算法中优化效果最佳，证明所提算法的种群多样性最好。

从实验结果可以明显看出，在优化5个目标测试函数时，LC-DMPPSO在GD、SP、IGD评价指标上全部取得了不错的优化效果，且在3个目标的测试函数上生成的Pareto前沿分布性要明显优于另外三种算法，具有最好的竞争力。结合所有实验分析验证了所提算法LC-DMPPSO在解决复杂的多目标优化问题上的有效性。

4 结 论

针对多目标优化问题中多样性与收敛性之间的不平衡问题，提出了LC-DMPPSO算法。该算法通过引入局部协同的思想，将种群划分为多个子种群共同完成进化，并为子種群选择一对领导粒子的操作方式，大大提高了LC-DMPPSO算法的局部搜索能力，实现了各目标之间的多样性与收敛性的平衡，利用竞争变异策略保证了种群的多样性。实验结果表明，LC-DMPPSO算法能有效平衡各个目标之间的关系，优化结果最佳。

参考文献

[1] 史文欣，毛剑琳.基于五行环优化算法的多目标柔性车间调度问题研究[J].电子测量技术， 2020， 43（20）：63-68.

[2] 隗寒冰，贺少川.基于深度强化学习的插电式柴电混合动力汽车多目标优化控制策略[J].重庆交通大学学报（自然科学版）， 2021， 40（1）：44-52.

[3] 周天沛，孙伟.基于充电设备利用率的电动汽车充电路径多目标优化调度[J].电力系统保护与控制， 2019， 47（4）：115-123.

[4] 郑夏，马良.应急物资储备中心多目标优化选址的仿真研究[J].计算机仿真， 2019， 36（9）：473-478.

[5] ALKEBSI K， DU Wen-li. A fast multi-objectiveparticle swarm optimization algorithm based on a new archive updating mechanism[J]. IEEE Access， 2020， 8： 124734-124754.

[6] DZIWINSKI P， BARTCZUK L. A new hybrid particle swarm optimization and genetic algorithm method controlled by fuzzy logic[J]. IEEE Transactions on Fuzzy Systems， 2020， 28（6）：1140-1154.

[7] AGBAJE M B， EZUGWU A E， ELS R. Automatic data clustering using hybrid firefly particle swarm optimization algorithm[J]. IEEE Access， 2019， 7： 184963-184984.

[8] FENG Qian， LI Qing， WANG Heng， et al. Two-stage adaptive constrained particle swarm optimization based on bi-objective method[J]. IEEE Access， 2020， 8： 150647-150664.

[9] LYU Wen-long， XUE Pan， YANG Fan， et al. An efficient bayesian optimization approach for automated optimization of analog circuits[J]. IEEE Transactions on Circuits and Systems， 2018， 65（6）：1954-1967.

[10]GAO Tiao-kang， CAO Bin， ZHANG Meng-xuan. Multi-objective complex network clustering based on dynamical decomposition particle swarm optimization[J].IEEE Access， 2020， 8：32341-32352.

[11]LV Zhi-ming， WANG Lin-qing， HAN Zhong-yang， et al. Surrogate-assisted particle swarm optimization algorithm with pareto active learning for expensive multi-objective optimization[J]. IEEE/CAA Journal of Automatica Sinica， 2019， 6（3）：838-849.

[12]何愛华，张晓青，赵克全.多目标优化问题近似解的组合标量化[J].重庆师范大学学报（自然科学版）， 2019，36（3）：7-10.

[13]高云龙，闫鹏.基于多种群粒子群算法和布谷鸟搜索的联合寻优算法[J].控制与决策， 2016， 31（4）：601-608.

[14]CHEN Yong-gang， LI Li-xiang， PENG Hai-peng， et al. Particle swarm optimizer with two differential mutation[J]. Applied Soft Computing， 2017， 61：314-330.

[15]CHENG Ran， JIN Yao-chu. A competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics， 2015， 45（2）：191-204.

[16]LIN Qiu-zhen， LI Jian-qiang， DU Zhi-hua， et al. A novel multi-objective particle swarm optimization with multiple search strategies[J]. European Journal of Operational Research， 2015， 247（3）：732-744.

[17]PENG Guang， FANG Yang-wang， PENG Wei-shi， et al. Multi-objective particle optimization algorithm based on sharing-learning and dynamic crowding distance[J]. Optik， 2016， 127：5013-5020.

[18]DEB K， JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach， part i： solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation， 2014， 18（4）：577-601.