一种基于角度信息的约束高维多目标进化算法

doi:10.12263/DZXB.20201044

摘要/Abstract

摘要：

目前约束高维多目标进化算法大多注重提高收敛精度, 而收敛速度相对较慢. 为提高算法的收敛速度, 提出一种基于角度信息的约束高维多目标进化算法. 该算法提出基于角度违反度函数的选择操作, 依据动态的收敛性和分布性直接选择较优个体, 提高收敛速度; 此外, 提出了基于差分进化算法的交叉操作, 在不同的进化阶段选用不可行解参与交叉操作, 补偿收敛精度.在标准测试函数集C-DTLZ上进行仿真实验, 并与当前国内外性能优异的4种约束高维多目标进化算法进行对比, 证明了本文算法收敛精度保持良好, 而收敛速度得到了提升, 且目标维数越高提升效果越明显.

关键词: 约束高维多目标优化, 角度违反度, 选择操作, 差分算法, 交叉操作

Abstract:

Most of the current constrained many-objective evolutionary algorithms focus on the convergence accuracy, but the convergence speed is relatively slow. In order to improve the convergence speed, a constrained many-objective evolutionary algorithm based on angle information (CMaOEA-AI) is proposed. In the algorithm, a selection operation based on the angle violation function is proposed to improve the convergence speed, which directly selects the superior individuals according to the dynamic convergence and diversity. Thereafter a crossover operation based on the differential evolutionary algorithm is proposed, which can select the infeasible solutions to participate in the crossover operation at different evolutionary stages. Simulation experiments are performed on the standard test function sets C-DTLZ. Compared with four state-of-the-art constrained many-objective evolutionary algorithms, the proposed algorithm shows good convergence accuracy while the convergence speed is greatly improved, and the higher the objective dimension, the better the effect.

Key words: constrained many-objective optimization, angle violation function, selection operation, differential evolution algorithm, crossover operation

中图分类号:

TP18

刘冰洁, 毕晓君. 一种基于角度信息的约束高维多目标进化算法[J]. 电子学报, 2021, 49(11): 2208-2216.

Bing-jie LIU, Xiao-jun BI. A Constrained Many‑Objective Evolutionary Algorithm Based on Angle Information[J]. Acta Electronica Sinica, 2021, 49(11): 2208-2216.

图/表 8

参考文献 30

1	ZHOU Y, MIN Z, WANG J, et al. Tri-goal evolution framework for constrained many-objective optimization[J]. IEEE Transactions on Systems, Man & Cybernetics Systems, 2018.1 - 14.
2	LI M Q, ZHOU Y R, XIANG Y, et al. An angle based constrained many-objective evolutionary algorithm[J]. Applied Intelligence, 2017, 47: 705 - 720.
3	顾清华, 莫明慧, 卢才武, 陈露. 求解约束高维多目标问题的分解约束支配NSGA-II优化算法[J]. 控制与决策, 2020, 35(10): 2466 - 2474.
	GU Q H, MO M H, LU C W, CHEN L. Decomposition-based constrained dominance principle NSGA-II for constrained many-objective optimization problems[J]. Control and Decision, 2020, 35(10): 2466 - 2474. (in Chinese)
4	MIYAKAWA M, SATO H, SATO Y. Utilization of infeasible solutions in MOEA/D for solving constrained many-objective optimization problems[A]. Proceedings of the Genetic and Evolutionary Computation Conference Companion[C]. Berlin, Germany: ACM, 2017. 35 - 36.
5	MIYAKAWA M, SATO H, SATO Y. Directed mating in decomposition-based MOEA for constrained many-objective optimization[A]. Proceedings of the Genetic and Evolutionary Computation Conference Companion[C]. Kyoto, Japan: ACM, 2018. 721 - 728.
6	李智勇, 黄滔, 陈少淼, 李仁发. 约束优化进化算法综述[J]. 软件学报, 2017, 28(6): 1529 - 1546.
	LI Z Y, HUANG T, CHEN S M, LI R F. Overview of constrained optimization evolutionary algorithms[J]. Journal of Software, 2017, 28(6): 1529 - 1546. (in Chinese)
7	MATIAS J, CORREIA A, MESTRE P, et al. Adaptive penalty and barrier function based on fuzzy logic[J]. Expert Systems with Applications, 2015, 42(19): 6777 - 6783.
8	DEB K, PRATAP A, AGARWAL S, MEYARIVAN T. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182 - 197.
9	ZHANG M, LUO W J, WANG X F. Differential evolution with dynamic stochastic selection for constrained optimization[J]. Information Sciences, 2008, 178(15): 3043 - 3074.
10	张磊, 毕晓君, 王艳娇. 基于重新匹配策略的ε约束多目标分解优化算法[J]. 电子学报, 2018, 46(5): 1032 - 1040.
	ZHANG L, BI X J, WANG Y J. The ε constrained multi-objective decomposition optimization algorithm based on re-matching strategy[J]. Acta Electronica Sinica, 2018, 46(5): 1032 - 1040. (in Chinese)
11	ZENG S Y, JIAO R W, LI C H, et al. A general framework of dynamic constrained multiobjective evolutionary algorithms for constrained optimization[J]. IEEE Transactions on Cybernetics, 2017, 47 (9): 2678 - 268.
12	ASAFUDDOULA M, RAY T, SARKER R. A decomposition-based evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(3): 445 - 460.
13	JAN M A, ZHANG Q F. MOEA/D for constrained multiobjective optimization: Some preliminary experimental result[A]. 2010 UK Workshop on Computational Intelligence[C]. UKCI: IEEE, 2010. 1 - 6.
14	JAIN H, DEB K. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part Ⅱ: Handling constraints and extending to an adaptive approach[J]. IEEE Transactions on Evolutionary Computation, 2014, 18 (4): 602 - 622.
15	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.
16	CAI X, MEI Z, FAN Z. A decomposition-based many-objective evolutionary algorithm with two types of adjustments for direction vectors[J]. IEEE Transactions on Cybernetics, 2018, 48(8):2335 - 2348.
17	LI K, DEB K, ZHANG Q F, SAM K. An evolutionary many-objective optimization algorithm based on dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(5): 694 - 716.
18	LI K, CHEN R Z, FU G T, YAO X. Two-archive evolutionary algorithm for constrained multi-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 303 - 315.
19	FAN Z, WANG Z J, LI W J, et al. Push and pull search embedded in an M2M framework for solving constrained multi-objective optimization problems[J]. Swarm and Evolutionary Computation, 2020, 54: 100651.
20	MARTINEZ S Z, COELL C C. A multi-objective evolutionary algorithm based on decomposition for constrained multi-objective optimization[A]. Proceedings of 2014 IEEE Congress on Evolutionary Computation[C]. Beijing, China: IEEE, 2014. 429 - 436.
21	王丽萍, 章鸣雷, 邱飞岳, 江波. 基于角度惩罚距离精英选择策略的偏好高维目标优化算法[J]. 计算机学报, 2018, 41(1): 236 - 253.
	WANG L P, ZHANG M L, QIU F Y, JIANG B. Many-objective optimization algorithm with preference based on the angle penalty distance elite selection strategy[J]. Chinese Journal of Computers, 2018, 41(1): 236 - 253. (in Chinese)
22	刘元, 郑金华, 邹娟, 喻果. 基于邻域竞赛的多目标优化算法[J]. 自动化学报, 2018, 44(7): 1304 - 1320.
	LIU Y, ZHENG J H, ZOU J, YU G. An evolutionary algorithm through neighborhood competition for multi-objective optimization[J]. Acta Automatica Sinica, 2018, 44(7): 1304 - 1320. (in Chinese)
23	陈振兴, 严宣辉, 吴坤安, 白猛. 融合张角拥挤控制策略的高维多目标优化[J]. 自动化学报, 2015, 41(6): 1145 - 1158.
	CHEN Z X, YAN X H, WU K A, BAI M. Many-objective optimization integrating open angle based congestion control strategy[J]. Acta Automatica Sinica, 2015, 41(6): 1145 - 1158. (in Chinese)
24	LIU Z Z, WANG Y, HUANG P Q. AnD: A many-objective evolutionary algorithm with angle-based selection and shift-based density estimation[J]. Information Sciences, 2018, doi: 10.1016/j.ins.2018.06.063.
25	毕晓君, 王朝. 一种基于角度惩罚距离的高维多目标进化算法[J]. 电子与信息学报, 2018, 40(02): 314 - 322.
	BI X J, WANG C. A many-objective evolutionary algorithm based on angle penalized distance[J]. Journal of Electronics & Information Technology, 2018, 40(02): 314 - 322. (in Chinese)
26	DEB K, AGRAWAL R B. Simulated binary crossover for continuous search space[J]. Complex Systems, 1994, 9(3): 115 - 148.
27	王亚辉, 吴金妹, 贾晨辉. 基于动态种群多策略差分进化模型的多目标进化算法[J]. 电子学报, 2016, 44(6): 1472 - 1480.
	WANG Y H, WU J M, JIA C H. Multi-objective evolutionary algorithm based on dynamic population multi-strategy differential models[J]. Acta Electronica Sinica, 2016, 44(6): 1472 - 1480. (in Chinese)
28	王柳静, 张贵军, 周晓根. 基于状态估计反馈的策略自适应差分进化算法[J]. 自动化学报, 2020, 46(04): 752 - 766.
	WANG L J, ZHANG G J, ZHOU X G. Strategy self-adaptive differential evolution algorithm based on state estimation feedback[J]. Acta Automatica Sinica, 2020, 46(04): 752 - 766.(in Chinese)
29	ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multi-objective optimizers: An analysis and review[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 117 - 132.
30	DEB K, THIELE L, LAUMANNS M, ZITZLER Z. Scalable test problems for evolutionary multi-objective optimization [A]. Proceedings of Evolutionary Multi-objective Optimization: Theoretical Advances and Applications[C]. London, UK: IEEE, 2005. 105 - 145.

M	参考方向规模	种群大小（N）
3	91（H=12）	92
5	210（H=6）	212
8	156（H₁=3， H₂=2）	156
10	275（H₁=3， H₂=2）	276
15	135（H₁=2， H₂=1）	136

M	参考方向规模	种群大小（N）
3	91（H=12）	92
5	210（H=6）	212
8	156（H₁=3， H₂=2）	156
10	275（H₁=3， H₂=2）	276
15	135（H₁=2， H₂=1）	136

测试问题	M	G_max	C-NSGA-III	C-MOEA/D	C-MOEA/DD	C-TAEA	CMaOEA-AI
C1-DTLZ1	3	5000	2.0376e-2 （2.08e-4） +	2.1100e-2 （3.17e-3） ≈	2.0371e-2 （1.50e-4） +	2.0726e-2 （1.23e-3） ≈	2.6617e-2 （1.13e-3）
	5	6000	5.1603e-2 （4.10e-4） +	5.2940e-2 （7.79e-3） ≈	5.1352e-2 （2.90e-4） +	5.9782e-2 （4.98e-4） -	6.2075e-2 （1.24e-3）
	8	8000	1.2470e-1 （1.15e-2） -	1.0935e-1 （6.75e-3） +	1.2066e-1 （2.98e-4） -	1.0007e-1 （2.32e-3） +	1.3925e-2 （2.62e-3）
	10	10000	1.3617e-1 （7.93e-3） -	1.8022e-1 （7.81e-3） -	1.3179e-1 （8.07e-4） ≈	1.3010e-1 （1.85e-4） +	1.5584e-1 （7.77e-4）
	15	15000	1.9966e-1 （9.80e-4） +	2.6049e-1 （7.74e-3） ≈	2.4220e-1 （1.03e-1） -	1.9058e-1 （1.68e-4） +	2.3030e-1 （4.21e-3）
C1-DTLZ3	3	10000	8.0133e+0 （6.31e-3） -	8.007e+0 （1.72e-3） -	8.6610e-2 （3.05e-2） -	5.7687e-2 （8.17e-3） +	9.7757e-2 （3.55e-2）
	5	15000	1.1571e+1 （1.02e-2） -	1.1554e+0 （3.69e-3） -	2.1601e-1 （1.60e-2） -	1.7177e-1 （3.19e-1） -	6.6539e-1 （2.29e-3）
	8	25000	1.1668e+1 （7.83e-2） -	1.1610e+1 （2.64e-3） -	3.1596e-1 （6.90e-2） ≈	2.1762e-1 （1.45e-2） +	8.1711e-1 （1.31e-2）
	10	35000	1.4267e+1 （5.12e-2） -	1.4140e+1 （4.30e-2） -	2.4128e-1 （5.72e-3） -	5.8109e-1 （1.09e-3） +	8.4374e-1 （4.23e-3）
	15	50000	1.4630e+1 （2.26e-1） -	1.4463e+1 （8.22e-2） -	7.4207e-1 （1.24e-3） +	8.6244e-1 （4.52e-2） -	9.4453e-1 （3.09e-2）
+/≈/-			3/0/7	1/3/6	3/2/5	6/1/3

测试问题	M	G_max	C-NSGA-III	C-MOEA/D	C-MOEA/DD	C-TAEA	CMaOEA-AI
C1-DTLZ1	3	5000	2.0376e-2 （2.08e-4） +	2.1100e-2 （3.17e-3） ≈	2.0371e-2 （1.50e-4） +	2.0726e-2 （1.23e-3） ≈	2.6617e-2 （1.13e-3）
	5	6000	5.1603e-2 （4.10e-4） +	5.2940e-2 （7.79e-3） ≈	5.1352e-2 （2.90e-4） +	5.9782e-2 （4.98e-4） -	6.2075e-2 （1.24e-3）
	8	8000	1.2470e-1 （1.15e-2） -	1.0935e-1 （6.75e-3） +	1.2066e-1 （2.98e-4） -	1.0007e-1 （2.32e-3） +	1.3925e-2 （2.62e-3）
	10	10000	1.3617e-1 （7.93e-3） -	1.8022e-1 （7.81e-3） -	1.3179e-1 （8.07e-4） ≈	1.3010e-1 （1.85e-4） +	1.5584e-1 （7.77e-4）
	15	15000	1.9966e-1 （9.80e-4） +	2.6049e-1 （7.74e-3） ≈	2.4220e-1 （1.03e-1） -	1.9058e-1 （1.68e-4） +	2.3030e-1 （4.21e-3）
C1-DTLZ3	3	10000	8.0133e+0 （6.31e-3） -	8.007e+0 （1.72e-3） -	8.6610e-2 （3.05e-2） -	5.7687e-2 （8.17e-3） +	9.7757e-2 （3.55e-2）
	5	15000	1.1571e+1 （1.02e-2） -	1.1554e+0 （3.69e-3） -	2.1601e-1 （1.60e-2） -	1.7177e-1 （3.19e-1） -	6.6539e-1 （2.29e-3）
	8	25000	1.1668e+1 （7.83e-2） -	1.1610e+1 （2.64e-3） -	3.1596e-1 （6.90e-2） ≈	2.1762e-1 （1.45e-2） +	8.1711e-1 （1.31e-2）
	10	35000	1.4267e+1 （5.12e-2） -	1.4140e+1 （4.30e-2） -	2.4128e-1 （5.72e-3） -	5.8109e-1 （1.09e-3） +	8.4374e-1 （4.23e-3）
	15	50000	1.4630e+1 （2.26e-1） -	1.4463e+1 （8.22e-2） -	7.4207e-1 （1.24e-3） +	8.6244e-1 （4.52e-2） -	9.4453e-1 （3.09e-2）
+/≈/-			3/0/7	1/3/6	3/2/5	6/1/3

测试问题	M	G_max	C-NSGA-III	C-MOEA/D	C-MOEA/DD	C-TAEA	CMaOEA-AI
C2-DTLZ2	3	2500	4.8195e-2 （1.86e-4） +	4.9069e-2 （3.74e-4） +	4.9725e-2 （5.80e-4） -	4.4169e-2 （1.46e-3） -	4.8765e-2 （5.05e-4）
	5	3500	1.4868e-1 （3.28e-4） ≈	1.4863e-1 （5.93e-4） ≈	1.4800e-1 （3.86e-4） -	1.4569e-2 （1.63e-3） +	1.4835e-1 （6.59e-4）
	8	5000	4.0162e-1 （2.57e-1） -	4.1220e-1 （7.64e-1） -	2.9225e-1 （1.33e-3） -	2.4970e-1 （1.70e-3） +	3.5213e-1 （1.29e-3）
	10	7500	2.7665e-1 （6.10e-2） -	2.5412e-1 （5.57e-3） ≈	2.7047e-1 （2.43e-4） +	1.9095e-1 （9.78e-4） +	2.4783e-1 （1.86e-2）
	15	10000	3.8095e-1 （8.77e-2） -	3.9317e-1 （6.43e-2） -	3.8126e-1 （1.13e-1） -	2.5915e-1 （2.49e-3） +	3.3123e-1 （4.97e-2）
C2-DTLZ2*	3	2500	3.4636e-2 （5.26e-4） +	3.9069e-2 （1.05e-3） +	4.3562e-2 （2.19e-4） +	4.1667e-2 （1.04e-3） +	5.0590e-2 （2.21e-3）
	5	7500	6.5637e-2 （7.01e-4） +	7.1074e-2 （1/84e-3） ≈	8.7447e-2 （1.35e-3） -	6.3779e-2 （7.37e-4） +	7.8708e-2 （4.52e-3）
	8	15000	1.4006e-1 （1.06e-3） +	1.6735e-1 （7.64e-3） +	1.3209e-1 （1.13e-3） ≈	2.1033e-1 （9.76e-3） -	2.8256e-1 （3.32e-3）
	10	25000	1.1358e-1 （2.24e-3） -	1.4919e-1 （1.03e-3） +	1.4979e-1 （4.35e-4） -	3.0437e-1 （2.34e-2） -	3.1828e-1 （4.22e-2）
	15	35000	2.4336e-1 （3.69e-2） -	2.5052e-1 （2.38e-2） -	2.8508e-1 （1.70e-2） -	3.3610e-1 （1.61e-2） -	3.5038e-1 （2.01e-2）
+/≈/-			4/1/5	4/3/3	2/1/7	6/0/4