一种多样性控制的多目标粒子群算法

doi:10.19665/j.issn1001-2400.2021.03.014

摘要/Abstract

摘要：

针对传统多目标粒子群算法容易早熟的问题,提出了一种基于多样性控制的多目标粒子群算法。该算法采用一种基于权值向量的多样性评价指标来度量算法在每一次迭代时的种群多样性,并根据评估值来自适应地控制算法的进化过程。为了保证种群的多样性,采用一种基于Steffensen方法的自适应变异策略对外部种群进行更新。通过自适应地选择粒子的全局最优位置来实现种群多样性与收敛性之间的平衡。将该算法与几种常用的多目标进化算法在一系列标准测试函数上进行了仿真实验,统计结果证明了所提算法的有效性。

关键词: 多目标优化, 粒子群优化, 自适应算法, 多样性控制, Steffensen方法

Abstract:

For solving the premature in traditional multiobjective particle swarm optimization,a multi-objective particle swarm optimization based on diversity control is proposed.The proposed algorithm utilizes a diversity metric,which is based on weight vectors,to evaluate the population diversity in each generation and control the evolution process of the algorithm adaptively.To maintain population diversity,an adaptive mutation strategy based on Steffensen’s method is adopted to update the repository population.With the purpose of balancing the population diversity and convergence,the global best positions of particles areselected adaptively.This algorithm is compared with several widely used multiobjective evolutionary algorithms on a set of benchmark test problems in the experimental part.Statistical results demonstrate the effectiveness of the proposed algorithm.

Key words: multiobjective optimization, particle swarm optimization, adaptive algorithms, diversity control, Steffensen’s method

中图分类号:

TP301.6

刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.

LIU Tianyu,WANG Zhu. Diversity controlled multiobjective particle swarm optimization[J]. Journal of Xidian University, 2021, 48(3): 106-114.

图/表 16

图1

图2

图3

图4

表1

表2

表3

表4

图5

图6

图7

表5

图8

图9

图10

图11

参考文献 17

[1]	XU Z, ZHANG E Z, CHEN Q W. Rotary Unmanned Aerial Vehicles Path Planning in Rough Terrain Based on Multi-Objective Particle Swarm Optimization[J]. Journal of Systems Engineering and Electronics, 2020,31(1):130-141.
[2]	YU S, FAN Y, WU Y W, et al. Multi-Power Quality Controller Coordination Control Based on Multi-Objective Particle Swarm Optimization[C]// Proceedings of the 2019 IEEE 2nd International Conference on Electronics and Communication Engineering (ICECE).Piscataway:IEEE, 2019: 397-402.
[3]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019,46(1):130-136.
	WANG Yan. Enhanced Multi-objective Evolutionary Algorithm for Workflow Scheduling on the Cloud Platform[J]. Journal of Xidian University, 2019,46(1):130-136.
[4]	COELLO C A C, LECHUGA M S. MOPSO:a Proposal for Multiple Objective Particle Swarm Optimization[C]// Proceedings of the 2002 Congress on Evolutionary Computation.Piscataway:IEEE, 2002: 1051-1056.
[5]	于慧, 王宇嘉, 陈强, 等. 基于多种群动态协同的多目标粒子群算法[J]. 电子科技, 2019,32(10):28-33.
	YU Hui, WANG Yujia, CHEN Qiang, et al. Multi-Objective Particle Swarm Optimization Based on Multi-population Dynamic Cooperation[J]. Electronic Science and Technology, 2019,32(10):28-33.
[6]	HAN H G, WU X L, ZHANG L, et al. Self-Organizing RBF Neural Network Using an Adaptive Gradient Multiobjective Particle Swarm Optimization[J]. IEEE Transactions on Systems,Man,and Cybernetics, 2019,49(1):69-82.
[7]	ZHANG X Y, ZHENG X T, CHENG R, et al. A Competitive Mechanism Based Multi-Objective Particle Swarm Optimizer with Fast Convergence[J]. Information Sciences, 2018,427:63-76. doi: 10.1016/j.ins.2017.10.037
[8]	RAQUEL C R, NAVAL P C. An Effective Use of Crowding Distance in Multi-Objective Particle Swarm Optimization[C]// Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation.Piscataway:IEEE, 2005: 257-264.
[9]	MARTÍNEZ S Z, COELLO C A C. A Multi-Objective Particle Swarm Optimizer Based on Decomposition[C]// Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation.Piscataway:IEEE, 2011: 69-76.
[10]	LI H, ZHANG Q F. Multiobjective Optimization Problems with Complicated Pareto Sets,MOEA/D and NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2009,13(2):284-302. doi: 10.1109/TEVC.2008.925798
[11]	JAIN P. Steffensen Type Methods for Solving Non-Linear Equations[J]. Applied Mathematics and Computation, 2007,194(2):527-533. doi: 10.1016/j.amc.2007.04.087
[12]	AFZALINEJAD M. Rapidly Convergent Steffensen-Based Methods for Unconstrained Optimization[J]. Rairo-Operations Research, 2019,53(2):657-666. doi: 10.1051/ro/2017043
[13]	DAS I, DENNIS J E. Normal-Boundary Intersection:A New Method for Generating The Pareto Surface in Nonlinear Multicriteria Optimization Problems[J]. SIAM Journal on Optimization, 1998,8(3):631-657. doi: 10.1137/S1052623496307510
[14]	DEB K, AGRAWAL S, PRATAP A, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197. doi: 10.1109/4235.996017
[15]	ZHANG Q F, LI H. MOEA/D:a Multi-Objective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007,11(6):712-731. doi: 10.1109/TEVC.2007.892759
[16]	COELLO C A, CORTÉS N C, Solving Multiobjective Optimization Problems Using an Artificial Immune System[J]. Genetic Programming and Evolvable Machines, 2005,6(2):163-190. doi: 10.1007/s10710-005-6164-x
[17]	LIU T, JIAO L, MA W, et al. Cultural Quantum-Behaved Particle Swarm Optimization for Environmental/Economic Dispatch[J]. Applied Soft Computing, 2016,48:597-611. doi: 10.1016/j.asoc.2016.04.021

算法	参数设置
MOPSO	学习因子w=0.4
dMOPSO	年龄阈值T_a=2;惩罚因子θ=5
NSGA-II	文叉概率p_c=0.9;变异概率p_m=1/N;交叉因子η _c=20;变异因子η_m=20
MOEA/D	对2目标及3目标问题,权值向量数目分别为100和105;邻域规模δ=20
MOPSO-DC	对2目标及3目标问题,权值向量数目分别为10和21;学习因子w=0.4;邻域规模δ=5,控制参数s=0.7

问题	平均IGD值
问题	s=0.1	s=0.3	s=0.5	s=0.7	s=0.9
ZDT 1	4.58e-03	4.89e-03	4.16e-03	4.01e-03	4.25e-03
ZDT 4	1.39e+01	1.60e+01	9.94e+00	1.14e+01	1.64e+01
DTLZ 2	5.55e-02	5.62e-02	5.53e-02	5.48e-02	5.57e-02

问题	算法
问题	MOPSO-DC	MOPSO	dMOPSO	NSGA-II	MOEA/D
ZDT 1	4.01e-03 (1)	2.70e+01 (5)	234e-02 (2)	1.64e-01 (3)	1.76e-01 (4)
ZDT 2	4.18e-03 (1)	4.78e+01 (5)	3.79e-01 (3)	5.21e-01 (4)	3.30e-01 (2)
ZDT 3	3.74e-03 (1)	4.54e+01 (5)	2.32e-02 (2)	1.95e-01 (3)	2.06e-01 (4)
ZDT 4	1.14e+01 (4)	2.32e+01 (5)	5.68e-01 (3)	2.92e-01 (1)	4.38e-01 (2)
ZDT 6	3.40e-03 (1)	4.22e-01 (5)	4.58e-03 (2)	7.27e-02 (3)	9.75e-02 (4)
DTLZ 1	9.07e+00 (4)	1.09e+01 (5)	8.45e+00 (3)	9.16e-02 (2)	4.01e-02 (1)
DTLZ 2	5.48e-02 (1)	1.05e-01 (4)	1.37e-01 (5)	7.14e-02 (3)	6.14e-02 (2)
DTLZ 3	1.90e+02 (4)	2.62e+02 (5)	3.76e+01 (3)	8.31e+00 (1)	1.38e+01 (2)
WFG 1	1.52e+00 (3)	1.96e+00 (5)	1.55e+00 (4)	1.04e+00 (1)	1.16e+00 (2)
WFG 2	2.04e-01 (1)	3.23e-01 (4)	3.71e-01 (5)	2.22e-01 (2)	3.21e-01 (3)
WFG 3	1.56e-01 (2)	3.58e-01 (3)	4.05e-01 (4)	1.18e-01 (1)	4.63e-01 (5)
WFG 4	2.68e-01 (1)	4.15e-01 (5)	3.92e-01 (4)	2.79e-01 (2)	2.95e-01 (3)
WFG 5	2.59e-01 (1)	3.63e-01 (4)	3.95e-01 (5)	2.86e-01 (3)	2.78e-01 (2)
WFG 6	2.64e-01 (1)	4.88e-01 (5)	4.48e-01 (4)	3.27e-01 (3)	3.00e-01 (2)
WFG 7	2.62e-01 (1)	4.43e-01 (4)	4.67e-01 (5)	2.80e-01 (2)	4.35e-01 (3)
WFG 8	3.74e-01 (1)	3.86e-01 (2)	5.99e-01 (5)	3.96e-01 (4)	3.91e-01 (3)
WFG 9	2.53e-01 (1)	3.88e-01 (4)	3.67e-01 (3)	2.64e-01 (2)	4.47e-01 (5)

问题	算法
问题	MOPSO-DC	MOPSO	dMOPSO	NSGA-II	MOEA/D
ZDT 1	4.54e-03 (1)	2.61e-02 (5)	1.02e-02 (2)	1.32e-02 (3)	2.26e-02 (4)
ZDT 2	4.51e-03 (1)	1.84e-02 (4)	5.40e-03 (2)	4.88e-02 (5)	1.09e-02 (3)
ZDT 3	7.34e-03 (1)	3.18e-02 (4)	2.52e-02 (3)	1.54e-02 (2)	6.46e-02 (5)
ZDT 4	1.04e-01 (3)	1.06e-01 (4)	3.52e-03 (1)	2.22e-01 (5)	1.35e-02 (2)
ZDT 6	2.17e-03 (1)	2.05e-01 (5)	3.37e-03 (2)	1.31e-02 (3)	3.30e-02 (4)
DTLZ 1	2.56e+00 (3)	6.17e+00 (4)	6.25e+00 (5)	2.34e-02 (1)	2.56e-02 (2)
DTLZ 2	5.22e-02 (1)	6.41e-02 (4)	6.55e-02 (5)	5.37e-02 (2)	5.60e-02 (3)
DTLZ 3	2.89e+01 (3)	6.86e+01 (5)	4.87e+01 (4)	4.66e-01 (1)	1.67e+00 (2)
WFG 1	7.18e-02 (1)	4.71e-01 (5)	1.84e-01 (3)	3.58e-01 (4)	1.68e-01 (2)
WFG 2	2.66e-01 (2)	2.88e-01 (4)	2.81e-01 (3)	2.95e-01 (5)	1.19e-01 (1)
WFG 3	1.14e-01 (1)	1.43e-01 (3)	2.13e-01 (4)	1.17e-01 (2)	2.23e-01 (5)
WFG 4	2.26e-01 (3)	2.01e-01 (1)	2.42e-01 (4)	2.25e-01 (2)	2.79e-01 (5)
WFG 5	2.01e-01 (1)	2.04e-01 (2)	3.23e-01 (5)	2.27e-01 (3)	2.42e-01 (4)
WFG 6	2.03e-01 (1)	2.18e-01 (2)	2.51e-01 (4)	2.35e-01 (3)	2.65e-01 (5)
WFG 7	2.15e-01 (3)	1.78e-01 (1)	2.64e-01 (4)	2.04e-01 (2)	3.24e-01 (5)
WFG 8	2.39e-01 (2)	1.99e-01 (1)	2.65e-01 (3)	2.67e-01 (4)	3.00e-01 (5)
WFG 9	2.00e-01 (2)	1.83e-01 (1)	2.88e-01 (4)	2.07e-01 (3)	2.84e-01 (5)

问题	算法
问题	MOPSO-DC	MOPSO	dMOPSO	NSGA-II	MOEA/D
IGD指标	1.71	4.41	3.65	2.35	2.88
SP指标	1.76	3.24	3.41	2.94	3.65