多任务机制驱动的高维多目标进化算法

doi:10.19665/j.issn1001-2400.2022.04.016

摘要/Abstract

摘要：

针对传统进化算法在解决高维多目标优化问题时,因选择压力减少而产生的搜索能力急剧下降的现象,提出了一种多任务机制驱动的高维多目标优化算法。该算法首先采用一种自适应降维算子来构造与原始高维优化任务相关的低维任务,以此来增加优化过程中的选择压力。在低维任务的构造过程中,根据对当前目标子集的评估结果来自适应地选择合适的降维技术对原始高维任务进行降维。然后采用多任务机制同时对低维任务及原始高维任务进行优化。算法采用一种任务间交流算子来完成个体任务分配以及种群的更新操作,进而使得算法在利用低维任务提高搜索能力的同时能够避免降维所引起的有用信息丢失。此外,为了避免算法在搜索过程中出现早熟现象,通过对外部种群中出现代数较多的个体进行差分变异来增加外部种群的多样性。实验部分将该算法与几种常用的高维多目标进化算法在5组标准测试函数上进行对比分析。仿真结果验证了该算法在求解高维多目标优化问题时的有效性。

关键词: 多任务, 高维目标优化, 进化算法, 目标降维, 自适应算法

Abstract:

The searching ability of traditional evolutionary algorithms decrease srapidly because of the reduced selection pressure in dealing with many-objective optimization problems.Therefore,a many-objective evolutionary algorithm based on a multitasking mechanism is proposed.To increase the selection pressure in optimization processes,an adaptive objective reduction strategy is adopted to construct the low-dimensional task,which is related to the traditional many-objective optimization task.In the construction of low-dimensional tasks,the appropriate dimension reduction technique is chosen according to the evaluation of the current objective subset adaptively.After that,the constructed low-dimensional task and the original many-objective task are optimized simultaneously according to the multitasking mechanism.In this paper,an inter-task interaction strategy is adopted to allocate tasks to individuals and update the individual population,so as to improve the searching ability and avoid information loss because of dimension reduction.Moreover,a differential mutation operator is implemented on the individuals which remain unchanged for several generations from the repository population to avoid converging prematurely.In the experimental part,the proposed algorithm is tested on five groups of benchmark functions with several state-of -the-art many-objective evolutionary algorithms.Statistical results demonstrate the effectiveness of the proposed algorithm in solving many-objective optimization problems.

Key words: multitasking, many-objective optimization, evolutionary algorithms, objective reduction, adaptive algorithms

中图分类号:

TP301.6

刘天宇,曹磊. 多任务机制驱动的高维多目标进化算法[J]. 西安电子科技大学学报, 2022, 49(4): 134-143.

LIU Tianyu,CAO Lei. Many-objective evolutionary algorithm based on the multitasking mechanism[J]. Journal of Xidian University, 2022, 49(4): 134-143.

图/表 8

图1

表1

表2

表3

表4

算法针对不同测试问题的平均IGD值"

问题		算法
问题		NSGA-Ⅲ	MaOEA-IGD	NSGA-Ⅱ-LPCA	MT-MaOEA-LPCA	MT-MaOEA
DTLZ5(I,M)	DTLZ5(3,5)	1.17e-01 (3)	3.74e-01 (5)	2.63e-01 (4)	1.10e-01 (2)	1.08e-01 (1)
	DTLZ5(3,10)	2.11e-01 (3)	4.38e-01 (5)	2.23e-01 (4)	1.91e-01 (2)	1.09e-01 (1)
	DTLZ5(5,10)	3.54e-01 (2)	4.15e-01 (3)	9.45e-01 (5)	4.70e-01 (4)	2.66e-01 (1)
	DTLZ5(7,10)	5.51e-01 (3)	5.48e-01 (2)	1.02e+00 (5)	6.23e-01 (4)	4.97e-01 (1)
	DTLZ5(3,15)	3.54e-01 (2)	5.19e-01 (4)	5.61e-01 (5)	5.04e-01 (3)	1.10e-01 (1)
	DTLZ5(6,15)	5.39e-01 (2)	6.30e-01 (4)	1.15e+00 (5)	5.77e-01 (3)	3.58e-01 (1)
	DTLZ5(9,15)	7.13e-01 (2)	7.22e-01 (3)	1.24e+00 (5)	7.96e-01 (4)	7.08e-01 (1)
DTLZ2(M)	DTLZ2(3)	5.96e-02 (1)	4.80e-01 (5)	1.18e-01 (4)	9.59e-02 (3)	6.02e-02 (2)
	DTLZ2(5)	5.99e-01 (2)	6.16e-01 (4)	7.07e-01 (5)	6.12e-01 (3)	5.94e-01 (1)
	DTLZ2(10)	6.47e-01 (1)	7.26e-01 (3)	1.69e+00 (5)	1.19e+00 (4)	7.05e-01 (2)
	DTLZ2(15)	1.49e+00 (4)	7.94e-01 (1)	1.76e+00 (5)	1.25e+00 (3)	9.32e-01 (2)
DTLZ3(M)	DTLZ3(3)	1.67e+01 (2)	5.81e+01 (4)	6.22e+01 (5)	3.56e+01 (3)	1.05e+01 (1)
	DTLZ3(5)	1.87e+01 (1)	6.46e+01 (4)	2.16e+02 (5)	5.71e+01 (3)	1.97e+01 (2)
	DTLZ3(10)	7.67e+01 (3)	6.61e+01 (1)	3.09e+02 (5)	7.27e+01 (3)	6.94e+01 (2)
	DTLZ3(15)	8.64e+01 (3)	7.08e+01 (1)	2.14e+02 (5)	9.56e+01 (4)	7.88e+01 (2)
WFG3(M)	WFG3 (3)	7.12e-01 (2)	3.19e+00 (5)	4.43e-01 (3)	1.91e+00 (4)	6.29e-01 (1)
	WFG3 (5)	8.51e-01 (2)	4.44e+00 (5)	1.06e+00 (3)	2.14e+00 (4)	6.68e-01 (1)
	WFG3 (10)	1.70e+00 (2)	6.20e+00 (5)	3.54e+00 (4)	2.59e+00 (3)	1.52e+00 (1)
	WFG3 (15)	2.14e+00 (2)	1.29e+01 (1)	3.62e+00 (5)	2.73e+00 (4)	2.66e+00 (3)
WFG7(M)	WFG7 (3)	2.58e-01 (2)	1.25e+00 (3)	1.94e+00 (5)	1.46e+00 (4)	2.32e-01 (1)
	WFG7 (5)	2.99e+00 (4)	2.81e+00 (3)	3.76e+00 (5)	1.57e+00 (2)	1.25e+00 (1)
	WFG7 (10)	6.19e+00 (2)	9.94e+00 (5)	8.47e+00 (4)	7.14e+00 (3)	5.85e+00 (1)
	WFG7 (15)	1.02e+01 (1)	1.50e+01 (4)	1.39e+01 (3)	1.56e+01 (5)	1.16e+01 (2)

表4

表5

算法针对不同测试问题的平均SP值"

问题		算法
问题		NSGA-Ⅲ	MaOEA-IGD	NSGA-Ⅱ-LPCA	MT-MaOEA-LPCA	MT-MaOEA
DTLZ5(I,M)	DTLZ5(3,5)	7.72e-02 (4)	8.58e-02 (5)	7.06e-02 (3)	4.72e-02 (2)	4.23e-02 (1)
	DTLZ5(3,10)	9.97e-01 (5)	8.86e-02 (3)	8.95e-02 (4)	5.61e-02 (2)	5.14e-02 (1)
	DTLZ5(5,10)	3.25e-01 (5)	2.96e-01 (4)	1.53e-01 (2)	2.09e-01 (3)	1.36e-01 (1)
	DTLZ5(7,10)	4.07e-01 (1)	5.67e-01 (3)	4.13e-01 (2)	6.04e-01 (5)	4.60e-01 (4)
	DTLZ5(3,15)	7.89e-00 (5)	7.71e-01 (4)	6.61e-01 (3)	6.36e-01 (2)	1.03e-01 (1)
	DTLZ5(6,15)	2.89e-02 (1)	1.42e-01 (2)	2.48e-01 (5)	1.99e-01 (4)	1.48e-01 (3)
	DTLZ5(9,15)	6.36e-01 (3)	3.60e-01 (2)	7.34e-01 (5)	6.70e-01 (4)	2.03e-01 (1)
DTLZ2(M)	DTLZ2(3)	4.39e-02 (3)	6.40e-01 (5)	6.32e-02 (4)	4.24e-02 (2)	3.58e-02 (1)
	DTLZ2(5)	1.39e-01 (1)	1.82e-01 (5)	1.76e-01 (4)	1.72e-01 (3)	1.53e-01 (2)
	DTLZ2(10)	3.32e-01 (2)	5.11e-01 (3)	8.12e-01 (5)	5.23e-01 (4)	2.32e-01 (1)
	DTLZ2(15)	4.26e-01 (2)	1.92e-02 (1)	8.03e-01 (5)	5.07e-01 (3)	6.44e-01 (4)
DTLZ3(M)	DTLZ3(3)	7.04e+00 (4)	1.46e+01 (5)	2.29e+00 (3)	1.85e+00 (2)	7.29e-01 (1)
	DTLZ3(5)	7.41e+00 (2)	1.18e+01 (3)	2.88e+01 (5)	1.93e+01 (4)	9.31e-01 (1)
	DTLZ3(10)	8.36e+00 (1)	1.16e+01 (3)	4.91e+01 (5)	2.38e+01 (4)	9.11e+00 (2)
	DTLZ3(15)	1.17e+01 (1)	3.55e+01 (4)	3.93e+01 (5)	2.97e+01 (3)	2.37e+01 (2)
WFG3(M)	WFG3 (3)	1.37e-01 (4)	6.98e-03 (2)	4.65e-02 (5)	1.09e-02 (3)	4.06e-03 (1)
	WFG3 (5)	1.36e-01 (1)	6.18e-01 (5)	2.51e-01 (3)	6.03e-01 (4)	1.82e-01 (2)
	WFG3 (10)	5.35e-01 (2)	3.11e+00 (5)	1.89e+00 (4)	6.85e-01 (3)	4.38e-01 (1)
	WFG3 (15)	5.31e-01 (1)	7.59e+00 (5)	5.01e+00 (4)	8.76e-01 (3)	6.09e-01 (2)
WFG7(M)	WFG7 (3)	6.16e-02 (3)	2.03e-01 (4)	1.33e+00 (5)	2.18e-03 (2)	1.16e-03 (1)
	WFG7 (5)	4.97e-01 (1)	8.82e-01 (4)	3.99e+00 (5)	8.62e-01 (3)	3.69e-01 (1)
	WFG7 (10)	5.69e-01 (1)	4.26e+00 (4)	6.79e+00 (5)	3.07e+00 (3)	2.64e+00 (2)
	WFG7 (15)	6.68e+00 (3)	5.15e+01 (1)	1.21e+01 (5)	9.85e+00 (4)	5.68e+00 (2)

表5

表6

图2

参考文献 29

[1]	LIANG Z P, HU K Y, MA X L, et al. A Many-Objective Evolutionary Algorithm Based on a Two-Round Selection Strategy[J]. IEEE Transactions on Cybernetics, 2021, 51(3):1417-1429. doi: 10.1109/TCYB.2019.2918087
[2]	ZHANG Z X, CAO Y, CUI Z H, et al. A Many-Objective Optimization based Intelligent Intrusion Detection Algorithm for Enhancing Security of Vehicular Networks in 6G[J]. IEEE Transactions on Vehicular Technology, 2021, 70(6):5234-5243. doi: 10.1109/TVT.2021.3057074
[3]	YANG Y, YANG X W, ZHOU Y R, et al. Going Deeper with Optimal Software Products Selection Using Many-Objective Optimization and Satisfiability Solvers[J]. Empirical Software Engineering, 2020, 33(6):591-626.
[4]	ZHU Z H. A Hybrid Indicator Many-Objective Optimization Algorithm for the Selection and Delivery of Disaster Relief Materials Problem[J]. Concurrency Computation, 2021, 33(6):e5948.
[5]	CUI Z H, ZHANG J J. A Hybrid Many-Objective Optimization Algorithm for Coal Green Production Problem[J]. Concurrency Computation, 2021, 33(6):e6040.
[6]	ZHU S W, XU L H, GOODMAN E D, et al. A New Many-Objective Evolutionary Algorithm Based on Generalized Pareto Dominance[EB/OL]. [2021-02-10]. https://ieeexplore.ieee.org/document/9352206.
[7]	代才, 王宇平, 何晓光. 高维多目标问题的排序新方法[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.
[8]	PAN L Q, LI L H, HE C, et al. A Subregion Division-Based Evolutionary Algorithm with Effective Mating Selection for Many-Objective Optimization[J]. IEEE Transactions on Cybernetics, 2020, 50(8):3477-3490. doi: 10.1109/TCYB.2019.2906679
[9]	SHEN J T, WANG P, WANG X J. A Controlled Strengthened Dominance Relation for Evolutionary Many-Objective Optimization[EB/OL]. [2020-09-10]. https://ieeexplore.ieee.org/document/9194364.
[10]	LI L, CHANG L, GU T N, et al. On the Norm of Dominant Difference for Many-Objective Particle Swarm Optimization[J]. IEEE Transactions on Cybernetics, 2021, 51(4):2055-2067. doi: 10.1109/TCYB.2019.2922287
[11]	ZHANG X Y, TIAN Y, JIN Y C. A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(6):761-776. doi: 10.1109/TEVC.2014.2378512
[12]	DEB K, JIAN 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. doi: 10.1109/TEVC.2013.2281535
[13]	WU M Y, LI K, KWONG S, et al. Evolutionary Many-Objective Optimization Based on Adversarial Decomposition[J]. IEEE Transactions on Cybernetics, 2020, 50(2):753-764. doi: 10.1109/TCYB.2018.2872803
[14]	SHANG K, ISHIBUCHI H. A New Hypervolume-Based Evolutionary Algorithm for Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(5):839-852. doi: 10.1109/TEVC.2020.2964705
[15]	SUN Y N, 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]	WANG H D, JIAO L C, YAO X. Two_ARCH2:An Improved Two-Archive Algorithm for Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(4):524-541. doi: 10.1109/TEVC.2014.2350987
[17]	YUAN Y, ONG Y S, GUPTA A, et al. Objective Reduction in Many-Objective Optimization:Evolutionary Multiobjective Approaches and Comprehensive Analysis[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(2):189-210. doi: 10.1109/TEVC.2017.2672668
[18]	LI Y F, LIU H L, GOODMAN E D. Hyperplane-Approximation-Based Method for Many-Objective Optimization Problems with Redundant Objectives[J]. Evolutionary Computation, 2019, 27(2):313-344. doi: 10.1162/evco_a_00223
[19]	SAXENA D K, DURO J A, TIWARI A, et al. Objective Reduction in Many-Objective Optimization:Linear and Nonlinear Algorithms[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(1):77-99. doi: 10.1109/TEVC.2012.2185847
[20]	李升远, 张馨恬, 唐世阳. 采用OFDM-LFM的MIMO雷达高速目标波形设计[J]. 西安电子科技大学学报, 2018, 45(3):7-12.
	LI Shengyuan, ZHANG Xintian, TANG Shiyang. MIMO Radar Waveform Design via OFDM-LFM for a High Speed Target[J]. Journal of Xidian University, 2018, 45(3):7-12.
[21]	BROCKHOFF D, ZITZLER E. Objective Reduction in Evolutionary Multiobjective Optimization:Theory and Applications[J]. Evolutionary Computation, 2009, 17(2):135-166. doi: 10.1162/evco.2009.17.2.135
[22]	GUPTA A, ONG Y S, FENG L, et al. Multiobjective Multifactorial Optimization in Evolutionary Multitasking[J]. IEEE Transactions on Cybernetics, 2017, 47(7):1652-1665. doi: 10.1109/TCYB.2016.2554622
[23]	BAI L, LIN W, GUPTA A, et al. From Multitask Gradient Descent to Gradient-Free Evolutionary Multitasking:A Proof of Faster Convergence[EB/OL]. [2021-03-11]. https://ieeexplore.ieee.org/document/9376716.
[24]	XIANG Y, ZHOU Y R, YANG X W, et al. A Many-Objective Evolutionary Algorithm with Pareto-Adaptive Reference Points[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(1):99-113. doi: 10.1109/TEVC.2019.2909636
[25]	DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197. doi: 10.1109/4235.996017
[26]	刘若辰, 焦李成, 雷七峰, 等. 一种新的差分进化约束优化算法[J]. 西安电子科技大学学报, 2011, 38(1):47-53.
	LIU Ruochen, JIAO Licheng, LEI Qifeng, et al. New Differential Evolution Constrained Optimization Algorithm[J]. Journal of Xidian University, 2011, 38(1):47-53.
[27]	DEB K, AGRAWAL R B. Simulated Binary Crossover for Continuous Search Space[J]. Journal of Complex Systems, 1995, 9(2):115-148.
[28]	GONG M G, LI C J, DU H F, et al. Multiobjective Immune Algorithm with Nondominated Neighbor-Based Selected[J]. Evolutionary Computation, 2008, 16(2):225-255. doi: 10.1162/evco.2008.16.2.225
[29]	LIU T Y, JIAO L C, MA W P, 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

算法	参数设置
NSGA-Ⅲ	M=5时N=212,M=10时N=276,M=15时N=136,p_c=1,p_m=1/N,η_c=20,η_m=20
MaOEA-IGD	N=240,p_c=0.9,p_m=1/N,η_c=20,η_m=20
NSGA-Ⅱ-LPCA	N=100,p_c=0.9,p_m=1/N,η_c=20,η_m=20
NSGA-Ⅱ-k-EMOSS	N=100,p_c=0.9,p_m=1/N,η_c=20,η_m=20,k=3
MT-MaOEA-LPCA	N=100,n=50,G=60
MT-MaOEA-k-EMOSS	N=100,n=50,G=60,k=3
MT-MaOEA	N=100,n=50,G=60,k=3

问题	平均IGD值
问题	G=10	G=20	G=30	G=40	G=50	G=60	G=70	G=80	G=90
DTLZ5(3,5)	0.110 1	0.115 1	0.109 1	0.115 9	0.112 8	0.108 3	0.110 0	0.120 2	0.109 3
DTLZ5(5,10)	0.382 0	0.538 3	0.331 7	0.379 3	0.333 9	0.265 8	0.287 1	0.360 3	0.329 9
DTLZ5(6,15)	1.145 9	1.243 4	1.099 0	1.680 5	0.549 4	0.357 6	0.753 4	1.827 7	1.280 4
DTLZ2(5)	0.617 2	0.572 8	0.487 4	0.249 7	0.222 7	0.594 5	0.608 1	0.629 6	0.648 3
DTLZ2(10)	0.742 3	0.701 8	0.708 6	0.744 1	0.710 3	0.705 2	0.781 0	0.790 5	0.794 6
WFG3(15)	2.759 5	2.511 8	2.742 8	2.725 2	2.662 8	2.664 3	2.612 5	2.633 0	2.714 8

问题	平均IGD值
问题	NSGA-Ⅱ-LPCA	NSGA-Ⅱ-k-EMOSS	MT-MaOEA-LPCA	MT-MaOEA-k-EMOSS	MT-MaOEA
DTLZ5(3,5)	0.263 4	0.386 7	0.109 9	0.120 0	0.108 3
DTLZ5(5,10)	0.945 7	1.429 0	0.470 2	0.547 3	0.265 8
DTLZ5(6,15)	1.148 6	7.588 5	0.576 8	1.832 9	0.357 6
DTLZ2(5)	0.706 9	1.186 8	0.612 0	0.678 9	0.594 5
DTLZ2(10)	1.691 1	1.978 9	1.186 2	1.141 3	0.705 2
WFG3(15)	3.617 0	1.763 9	2.732 3	2.710 3	2.664 3