一种适应度排序的高维多目标粒子群优化算法

doi:10.19665/j.issn1001-2400.2021.03.0010

摘要/Abstract

摘要：

针对高维多目标优化问题复杂度高,求解难度大的特点,提出了一种集成适应度排序的高维多目标粒子群优化算法。该算法通过获取种群中个体与参考点最近的向量,结合基于惩罚的边界交叉方法对种群中的个体进行排序,并对较差的个体进行删除,留下的精英个体被保存到外部档案中。将该算法与性能先进的4种高维多目标进化优化算法在13个标准测试实例的5,8,10,15目标上进行实验对比,结果表明,提出的算法在大多数测试用例上的性能表现优于对比算法,同时说明了该算法具有较好的收敛性与多样性,能够有效地处理高维多目标优化问题。

关键词: 集成适应度排序, 高维多目标优化, 粒子群优化, 基于惩罚的边界交叉方法

Abstract:

Due to the complexity and difficulty of solving the many-objective optimization problem,a many-objective particle swarm optimization algorithm for ensemble fitness ranking is proposed.In this algorithm,the nearest vector between the individual and reference points in the population is obtained,and the individuals in the population are sorted by the penalty-based boundary intersection approach.Then,the poor individuals in the population are deleted and the elite individuals are saved in the external archives.The four advanced many-objective evolutionary optimization algorithms are adopted to make comparisons on 5,8,10,15 objectives of 13 standard test sets.Experimental results show that the performance of the proposed algorithm is better than comparison algorithms in most of the test cases.It has also been proved that the algorithm has good convergence and diversity,and that it can effectively deal with many-objective optimization problems.

Key words: ensemble fitness ranking, many-objective optimization, particle swarm optimization, penalty-based boundary intersection approach

中图分类号:

TP18

杨五四,陈莉,王毅,张茂省. 一种适应度排序的高维多目标粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(3): 78-84.

YANG Wusi,CHEN Li,WANG Yi,ZHANG Maosheng. Many-objective particle swarm optimization algorithm for fitness ranking[J]. Journal of Xidian University, 2021, 48(3): 78-84.

图/表 6

表1

表2

表3

算法MaPSO-EFR与四种对比算法在DTLZ和WFG的不同目标维数上获得的IGD平均值和标准差"

测试用例	目标维度	NSGAIII	EFRRR	MaOEAIGD	MOEAD	MaPSOEFR
DTLZ1	5	6.338 2×10^-2=	6.335 2×10^-2=	4.577 0×10^-1-	6.342 0×10^-2=	6.820 4×1 $0 - 2$
	8	1.067 7×10^-1=	1.029 8×10^-1=	1.568 8×10^-1-	9.569 1×10^-2=	9.746 1×1 $0 - 2$
	10	1.443 2×10^-1-	1.403 4×10^-1-	1.215 2×10^-1=	1.265 5×10^-1-	1.160 4×10^-1
	15	2.158 6×10^-1-	1.389 2×10^-1+	1.831 5×10^-1-	1.294 0×10^-1+	1.641 5×10^-1
DTLZ2	5	1.948 8×10^-1=	1.948 9×10^-1=	1.975 1×10^-1=	1.949 0×10^-1=	1.948 5×10^-1
	8	3.399 5×10^-1+	3.266 5×10^-1+	3.279 9×10^-1+	3.149 6×10^-1+	4.022 4×10^-1
	10	5.303 2×10^-1-	4.569 0×10^-1=	4.538 3×10^-1=	4.560 6×10^-1=	4.741 8×10^-1
	15	6.384 0×10^-1-	5.547 9×10^-1+	5.612 8×10^-1+	5.262 0×10^-1+	5.986 5×10^-1
DTLZ3	5	2.013 8×10^-1+	1.973 4×10^-1+	8.444 1×10⁰-	2.500 3×10^-1=	2.617 1×10^-1
	8	1.007 7×10⁰-	4.883 9×10^-1-	5.108 8×10⁰-	5.237 1×10^-1-	3.939 6×10^-1
	10	6.399 1×10⁰-	4.433 6×10⁰-	6.490 6×10⁰-	5.960 4×10^-1-	5.032 8×10^-1
	15	5.201 3×10¹-	7.218 2×10^-1+	1.934 8×10⁰-	1.233 7×10⁰-	7.688 8×10^-1
DTLZ4	5	2.176 6×10^-1-	1.955 1×10^-1=	2.838 8×10^-1-	3.529 5×10^-1-	1.950 8×10^-1
	8	3.482 1×10^-1=	3.364 4×10^-1=	3.348 2×10^-1=	5.544 1×10^-1-	3.417 8×10^-1
	10	4.559 0×10^-1-	4.583 3×10^-1-	4.537 2×10^-1=	6.300 7×10^-1-	4.534 5×10^-1
	15	6.045 4×10^-1=	5.896 0×10^-1=	5.770 0×10^-1+	7.255 0×10^-1-	5.936 3×10^-1
WFG4	5	1.172 7×10⁰-	1.294 3×10⁰-	6.739 6×10⁰-	1.865 2×10⁰-	1.167 3×10⁰
	8	3.112 4×10⁰=	3.192 0×10⁰-	9.751 3×10⁰-	6.962 5×10⁰-	3.028 4×10⁰
	10	4.782 4×10⁰=	4.837 5×10⁰=	1.204 6×10¹-	9.434 4×10⁰-	4.724 9×10⁰
	15	8.554 1×10⁰=	8.850 8×10⁰=	1.926 ×10¹-	1.623 5×10¹-	8.925 1×10⁰
WFG5	5	1.164 1×10⁰=	1.236 2×10⁰-	6.323 5×10⁰-	1.615 8×10⁰-	1.132 2×10⁰
	8	2.961 1×10⁰=	3.261 8×10⁰-	1.334 3×10¹-	6.533 4×10⁰-	2.954 7×10⁰
	10	4.725 5×10⁰-	5.539 9×10⁰-	1.757 5×10¹-	9.062 3×10⁰-	4.501 5×10⁰
	15	8.088 9×10⁰+	8.497 8×10⁰=	2.820 8×10¹-	1.591 9×10¹-	8.439 4×10⁰
WFG6	5	1.165 4×10⁰=	1.352 2×10⁰-	5.945 3×10⁰-	1.983 6×10⁰-	1.162 3×10⁰
	8	2.957 2×10⁰=	3.282 3×10⁰-	1.206 1×10¹-	7.092 3×10⁰-	3.053 4×10⁰
	10	4.784 4×10⁰=	5.311 4×10⁰-	1.304 4×10¹-	9.767 8×10⁰-	4.756 5×10⁰
	15	1.184 7×10¹-	8.835 3×10⁰=	2.449 0×10¹-	1.647 4×10¹-	8.775 1×10⁰
WFG7	5	1.178 7×10⁰=	1.238 8×10⁰=	5.923 7×10⁰-	2.110 5×10⁰-	1.177 6×10⁰
	8	2.976 3×10⁰=	3.273 2×10⁰-	1.008 2×10¹-	7.037 0×10⁰-	3.041 1×10⁰
	10	4.812 3×10⁰=	5.247 0×10⁰-	1.299 8×10¹-	9.579 8×10⁰-	4.721 1×10⁰
	15	1.049 4×10¹-	9.021 4×10⁰-	2.320 8×10¹-	1.664 7×10¹-	8.509 2×10⁰
WFG8	5	1.146 7×10⁰=	1.315 9×10⁰-	4.068 0×10⁰-	1.835 9×10⁰-	1.166 4×10⁰
	8	3.123 2×10⁰=	3.344 7×10⁰-	7.376 8×10⁰-	6.459 9×10⁰-	3.062 5×10⁰
	10	5.059 0×10⁰-	5.401 9×10⁰-	6.465 3×10⁰-	8.673 6×10⁰-	4.528 9×10⁰
	15	9.354 3×10⁰-	8.751 6×10⁰-	1.996 4×10¹-	1.473 2×10¹-	8.394 7×10⁰
WFG9	5	1.131 9×10⁰=	1.268 1×10⁰-	4.409 2×10⁰-	1.737 4×10⁰-	1.116 2×10⁰
	8	2.939 9×10⁰+	3.324 7×10⁰-	8.600 0×10⁰-	6.719 7×10⁰-	3.071 0×10⁰
	10	4.567 2×10⁰-	5.363 0×10⁰-	6.038 8×10⁰-	9.166 5×10⁰-	4.360 8×10⁰
	15	7.811 5×10⁰+	8.303 3×10⁰+	1.053 7×10¹=	1.594 6×10¹-	9.143 4×10⁰
+/-/=		5/14/21	6/21/13	3/31/6	3/32/5

表3

图1

表4

图2

参考文献 16

[1]	QI Y T, LI X D, YU J S, et al. User-preference Based Decomposition in MOEA/D without Using an Ideal Point[J]. Swarm and Evolutionary Computation, 2019,44:597-611. doi: 10.1016/j.swevo.2018.08.002
[2]	WANG S, ALI S, YUE T, et al. Integrating Weight Assignment Strategies with NSGA-II for Supporting User Preference Multiobjective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2018,22(3):378-393. doi: 10.1109/TEVC.2017.2778560
[3]	李笠, 王万良, 徐新黎, 等. 基于网格排序的多目标粒子群优化算法[J]. 计算机研究与发展, 2017,54(5):1012-1023.
	LI Li, WANG Wanliang, XU Xinli, et al. Multi-objective Particle Swarm Optimization Based on Grid Ranking[J]. Journal of Computer Research and Development, 2017,54(5):1012-1023.
[4]	肖婧, 王科俊, 毕晓君. 基于改进K支配排序的高维多目标进化算法[J]. 控制与决策, 2014,29(12):2165-2170.
	XIAO Jing, WANG Kejun, BI Xiaojun. Multi-objective Evolutionary Algorithm Based on Improved K-dominated Sorting[J]. Control and Decision, 2014,29(12):2165-2170.
[5]	梅海涛, 华继学, 王毅, 等. 基于直觉模糊支配的混合多目标粒子群算法[J]. 计算机科学, 2017,44(1):253-258.
	MEI Haitao, HUA Jixue, WANG Yi, et al. Hybrid Multi-objective Particle Swarm Optimization Based on Intuitionistic Fuzzy Dominance[J]. Computer Science, 2017,44(1):253-258.
[6]	林梦嫚, 周欢, 王丽萍. 基于alpha支配的高维目标进化算法研究[J]. 计算机科学, 2017,44(1):264-270.
	LING Mengman, ZHOU Huan, WANG Liping. Research of Many-objective Evolutionary Algorithm Based on Alpha Dominance[J]. Computer Science, 2017,44(1):264-270.
[7]	余伟伟, 谢承旺, 闭应洲, 等. 一种基于自适应模糊支配的高维多目标粒子群算法[J]. 自动化学报, 2018,44(12):168-179.
	YU Weiwei, XIE Chengwang, BI Yingzhou, et al. Many-objective Particle Swarm Optimization Based on Adaptive Fuzzy Dominance[J]. Acta Automatica Sinica, 2018,44(12):168-179.
[8]	YUAN Y, XU H, WANG B, et al. Balancing Convergence and Diversity in Decomposition-based Many-objective Optimizers[J]. IEEE Transactions on Evolutionary Computation, 2016,20(2):180-198. doi: 10.1109/TEVC.2015.2443001
[9]	代才, 王宇平, 何晓光. 高维多目标问题的排序新方法[J]. 西安电子科技大学学报, 2014,41(6):89-94.
	DAI Cai, WANG Yuping, HE Xiaoguang. New Ranking Method for Many-objective Problems[J]. Journal of Xidian University, 2014,41(6):89-94.
[10]	RAHIMI S, ABDOLLAHPOURI A, MORADI P. A Multi-objective Particle Swarm Optimization Algorithm for Community Detection in Complex Networks[J]. Swarm and Evolutionary Computation, 2018,39:297-309. doi: 10.1016/j.swevo.2017.10.009
[11]	LIN Q Z, LI J Q, DU Z H, et al. A Novel Multi-objective Particle Swarm Optimization with Multiple Search Strategies[J]. European Journal of Operational Research, 2015,247(3):732-744. doi: 10.1016/j.ejor.2015.06.071
[12]	DEB K, JAIN H. An Evolutionary Many-objective Optimization Algorithm Using Reference-point-based Nondominated Sorting Approach,Part I:Solving Problems with Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2014,18(4):577-601. doi: 10.1109/TEVC.2013.2281535
[13]	ZHANG Q S, ZHU W, LIAO B, et al. A Modified PBI Approach for Multi-objective Optimization with Complex Pareto Fronts[J]. Swarm and Evolutionary Computation, 2018,40:216-237. doi: 10.1016/j.swevo.2018.02.001
[14]	ZHANG Q F, LI H. MOEA/D:a Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007,11(6):712-731. doi: 10.1109/TEVC.2007.892759
[15]	SUN Y A, YEN G G, YI Z. IGD Indicator-based Evolutionary Algorithm for Many-objective Optimization Problems[J]. IEEE Transactions on Evolutionary Computation, 2019,23(2):173-187. doi: 10.1109/TEVC.2018.2791283
[16]	TIAN Y, CHENG R, ZHANG X, et al. PlatEMO:a MATLAB Platform for Evolutionary Multi-objective Optimization[J]. IEEE Computational Intelligence Magazine, 2017,12(4):73-87.

测试问题	目标数	决策变量数	参数k
DTLZ1	5,8,10,15	m+k-1	5
DTLZ2-DTLZ4	5,8,10,15	m+k-1	10
WFG4-WFG9	5,8,10,15	k+l	2 (m-1);l=20

目标数	种群数	进化次数
5	150	100 000
8	200	100 000
10	250	100 000
15	300	100 000