自适应迁移的分解多目标多任务进化算法

doi:10.19678/j.issn.1000-3428.0066530

摘要/Abstract

摘要：

多目标多任务进化优化是多目标优化的一个重要研究方向，通过跨任务共享有益信息以同时解决多个相关任务的优化问题。然而，现有多目标多任务进化优化研究存在相似任务匹配准确度低、缺少对知识迁移的动态控制等问题。为提高多目标多任务进化优化算法的优化效果，引入相似性动态指标和迁移概率动态调整机制，提出自适应迁移的分解多目标多任务进化算法。为了给目标任务子问题匹配关联度最高的迁移源，同时考虑种群的当前分布以及种群的进化方向2个指标，设计一种基于种群静态和动态特征相结合的迁移源匹配策略。为了合理地控制任务间的信息传递，提出基于种群进化状态的知识迁移概率自适应调整策略，在优化过程中根据优化任务的进化状态自适应地调整任务间的知识迁移概率，以满足优化任务在不同进化阶段对外部知识的需求。实验结果表明，相比MOEA/D、MO-MFEA、MO-MFEA-Ⅱ等算法，该算法具有较优的稳定性和收敛性，在常用的9组(18个独立任务)多目标多任务测试问题中有15个表现较优，优化率为83%。

关键词: 多目标多任务优化, 进化算法, 迁移优化, 分解策略, 自适应策略

Abstract:

Multi-objective multi-task evolutionary optimization is an important research direction for solving multiple related tasks simultaneously by sharing beneficial information across tasks. However, existing multi-objective multi-task evolutionary optimization studies have problems, such as low accuracy in matching similar tasks and a lack of dynamic control over knowledge transfer. To address these issues, a dynamic index of similarity and dynamic adjustment mechanism of transfer probability are introduced to propose an decomposition multi-objective multi-task evolutionary algorithm with adaptive transfer. The transfer source matching strategy is designed based on a combination of static and dynamic characteristics of the population, to match the transfer source with the highest degree of correlation to the target task subproblem, considering the current distribution and the evolution direction of the population. To reasonably control the information transmission between tasks, an adaptive knowledge transfer probability adjustment strategy based on the population evolution state of the optimization task is proposed, thereby satisfying the different needs of external knowledge in different evolution stages of the optimization task. The experimental results show that compared to MOEA/D, MO-MFEA, and MO-MFEA-Ⅱ, the proposed algorithm displays better stability and convergence. Among the commonly used nine groups(eighteen independent tasks) of multi-objective and multi-task test problems, fifteen performed better, with an optimization rate of 83%.

Key words: multi-objective multi-task optimization, evolutionary algorithm, transfer optimization, decomposition strategy, adaptive strategy

蔡倩倩, 史旭华. 自适应迁移的分解多目标多任务进化算法[J]. 计算机工程, 2023, 49(7): 55-64.

Qianqian CAI, Xuhua SHI. Decomposition Multi-Objective Multi-Task Evolutionary Algorithm with Adaptive Transfer[J]. Computer Engineering, 2023, 49(7): 55-64.

https://www.ecice06.com/CN/Y2023/V49/I7/55

图/表 14

参考文献 26

1	WANG J H, ZHOU Y, WANG Y, et al. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms[EB/OL]. [2022-11-12]. https://ieeexplore.ieee.org/ielx7/6221036/6352949/07062012.pdf?tp=&arnumber=7062012&isnumber=6352949.
2	ZHOU A M, QU B Y, LI H, et al. Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm and Evolutionary Computation, 2011, 1 (1): 32- 49. doi: 10.1016/j.swevo.2011.03.001
3	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182- 197. doi: 10.1109/4235.996017
4	ZHANG Q F, LI H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11 (6): 712- 731. doi: 10.1109/TEVC.2007.892759
5	张景成, 戴光明. 基于指标的多目标进化算法研究. 计算机工程, 2009, 35 (23): 187-189, 193 URL
	ZHANG J C, DAI G M. Research on indicator-based multi-objective evolutionary algorithm. Computer Engineering, 2009, 35 (23): 187-189, 193 URL
6	GUPTA A, ONG Y S, FENG L. Multifactorial evolution: toward evolutionary multitasking. IEEE Transactions on Evolutionary Computation, 2016, 20 (3): 343- 357. doi: 10.1109/TEVC.2015.2458037
7	LIANG Z P, LIANG W Q, XU X J, et al. A two stage adaptive knowledge transfer evolutionary multi-tasking based on population distribution for multi/many-objective optimization[EB/OL]. [2022-11-12]. https://arxiv.org/abs/2001.00810v1.
8	GUPTA A, ONG Y S, FENG L, et al. Multiobjective multifactorial optimization in evolutionary multitasking. IEEE Transactions on Cybernetics, 2017, 47 (7): 1652- 1665. doi: 10.1109/TCYB.2016.2554622
9	HUANG S J, ZHONG J H, YU W J. Surrogate-assisted evolutionary framework with adaptive knowledge transfer for multi-task optimization. IEEE Transactions on Emerging Topics in Computing, 2021, 9 (4): 1930- 1944. doi: 10.1109/TETC.2019.2945775
10	邱鸿辉, 刘海林, 陈磊. 基于协方差矩阵调整的多目标多任务优化算法. 计算机工程, 2022, 48 (8): 306- 312. doi: 10.19678/j.issn.1000-3428.0062365
	QIU H H, LIU H L, CHEN L. Multi-objective multi-tasking optimization algorithm based on adjustment of covariance matrix. Computer Engineering, 2022, 48 (8): 306- 312. doi: 10.19678/j.issn.1000-3428.0062365
11	TANG J, CHEN Y K, DENG Z X, et al. A group-based approach to improve multifactorial evolutionary algorithm[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence. New York, USA: ACM Press, 2018: 3870-3876.
12	ZHANG J, ZHOU W E, CHEN X Q, et al. Multisource selective transfer framework in multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, 2020, 24 (3): 424- 438. doi: 10.1109/TEVC.2019.2926107
13	BALI K K, ONG Y S, GUPTA A, et al. Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2020, 24 (1): 69- 83. doi: 10.1109/TEVC.2019.2906927
14	THANH BINH H T, QUOC TUAN N, THANH LONG D C. A multi-objective multi-factorial evolutionary algorithm with reference-point-based approach[C]//Proceedings of Congress on Evolutionary Computation. Washington D. C., USA: IEEE Press, 2019: 2824-2831.
15	田红军, 汪镭, 吴启迪. 一种求解多目标优化问题的进化算法混合框架. 控制与决策, 2017, 32 (10): 1729- 1738. URL
	TIAN H J, WANG L, WU Q D. A hybrid framework of evolutionary algorithm for solving multi-objective optimization problems. Control and Decision, 2017, 32 (10): 1729- 1738. URL
16	ZHOU A M, ZHANG Q F. Are all the subproblems equally important? resource allocation in decomposition-based multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 2016, 20 (1): 52- 64. doi: 10.1109/TEVC.2015.2424251
17	WANG X P, DONG Z M, TANG L X, et al. Multiobjective multitask optimization-neighborhood as a bridge for knowledge transfer. IEEE Transactions on Evolutionary Computation, 2023, 27 (1): 155- 169. doi: 10.1109/TEVC.2022.3154416
18	BLANK J, DEB K, DHEBAR Y, et al. Generating well-spaced points on a unit simplex for evolutionary many-objective optimization. IEEE Transactions on Evolutionary Computation, 2021, 25 (1): 48- 60. doi: 10.1109/TEVC.2020.2992387
19	MARDLE S, MIETTINEN K M. Nonlinear multiobjective optimization. The Journal of the Operational Research Society, 2000, 51 (2): 246. doi: 10.1007/978-1-4615-5563-6
20	LIANG R H. Application of grey relation analysis to hydroelectric generation scheduling. International Journal of Electrical Power & Energy Systems, 1999, 21 (5): 357- 364. doi: 10.1016/S0142-0615(98)00055-6
21	DEB K, AGRAWAL R. Simulated binary crossover for continuous search space[EB/OL]. [2022-11-12]. https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=0A9E92AEA8531E5C5E5F48D5FA440D42?doi=10.1.1.26.8485&rep=rep1&type=pdf.
22	STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11 (4): 341- 359. doi: 10.1023/A:1008202821328
23	DEB K, TIWARI S. Omni-optimizer: a generic evolutionary algorithm for single and multi-objective optimization. European Journal of Operational Research, 2008, 185 (3): 1062- 1087. doi: 10.1016/j.ejor.2006.06.042
24	YUAN Y, ONG Y S, FENG L, et al. Evolutionary multitasking for multiobjective continuous optimization: benchmark problems, performance metrics and baseline results[EB/OL]. [2022-11-12]. https://arxiv.org/pdf/1706.02766.pdf.
25	ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 2003, 7 (2): 117- 132. URL
26	EMMERICH M, BEUME N, NAUJOKS B. An EMO algorithm using the hypervolume measure as selection criterion[C]//Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Germany: Springer, 2005: 62-76.

算法	SBC算子		DE交叉算子		PM算子
算法	$ {\eta }_{c} $	$ {p}_{c} $	$ F $	$ {C}_{r} $	$ {\eta }_{m} $	$ {p}_{m} $
MO-MFEA	10	1.0	—	—	10	1/D
MO-MFEA-Ⅱ	10	1.0	—	—	10	1/D
MOEA/D	—	—	0.5	0.9	20	1/D
MTEA/D-DN	—	—	0.5	0.9	20	1/D
ATMOEA/D	—	—	0.5	0.9	20	1/D

算法	SBC算子		DE交叉算子		PM算子
算法	$ {\eta }_{c} $	$ {p}_{c} $	$ F $	$ {C}_{r} $	$ {\eta }_{m} $	$ {p}_{m} $
MO-MFEA	10	1.0	—	—	10	1/D
MO-MFEA-Ⅱ	10	1.0	—	—	10	1/D
MOEA/D	—	—	0.5	0.9	20	1/D
MTEA/D-DN	—	—	0.5	0.9	20	1/D
ATMOEA/D	—	—	0.5	0.9	20	1/D

测试问题	测试任务	凹凸性	最优解分布
完全交集高相似（CIHS）	任务T¹	凹	单峰
完全交集高相似（CIHS）	任务T²	凹	单峰
完全交集中相似（CIMS）	任务T¹	凹	多峰
完全交集中相似（CIMS）	任务T²	凹	单峰
完全交集低相似（CILS）	任务T¹	凹	多峰
完全交集低相似（CILS）	任务T²	凸	多峰
部分交集高相似（PIHS）	任务T¹	凸	单峰
部分交集高相似（PIHS）	任务T²	凸	多峰
部分交集中相似（PIMS）	任务T¹	凹	单峰
部分交集中相似（PIMS）	任务T²	凹	多峰
部分交集低相似（PILS）	任务T¹	凹	多峰
部分交集低相似（PILS）	任务T²	凹	多峰
无交集高相似（NIHS）	任务T¹	凹	多峰
无交集高相似（NIHS）	任务T²	凹	单峰
无交集中相似（NIMS）	任务T¹	凹	多峰
无交集中相似（NIMS）	任务T²	凹	单峰
无交集低相似（NILS）	任务T¹	凹	多峰
无交集低相似（NILS）	任务T²	凹	多峰

测试问题	测试任务	凹凸性	最优解分布
完全交集高相似（CIHS）	任务T¹	凹	单峰
完全交集高相似（CIHS）	任务T²	凹	单峰
完全交集中相似（CIMS）	任务T¹	凹	多峰
完全交集中相似（CIMS）	任务T²	凹	单峰
完全交集低相似（CILS）	任务T¹	凹	多峰
完全交集低相似（CILS）	任务T²	凸	多峰
部分交集高相似（PIHS）	任务T¹	凸	单峰
部分交集高相似（PIHS）	任务T²	凸	多峰
部分交集中相似（PIMS）	任务T¹	凹	单峰
部分交集中相似（PIMS）	任务T²	凹	多峰
部分交集低相似（PILS）	任务T¹	凹	多峰
部分交集低相似（PILS）	任务T²	凹	多峰
无交集高相似（NIHS）	任务T¹	凹	多峰
无交集高相似（NIHS）	任务T²	凹	单峰
无交集中相似（NIMS）	任务T¹	凹	多峰
无交集中相似（NIMS）	任务T²	凹	单峰
无交集低相似（NILS）	任务T¹	凹	多峰
无交集低相似（NILS）	任务T²	凹	多峰

测试问题	测试任务	MOEA/D	MO-MFEA	MO-MFEA-Ⅱ	MTEA/D-DN	ATMOEA/D
CIHS	任务T¹	$ 3.71\times {10}^{-1} $	$ 8.46\times {10}^{-2} $	$ 6.14\times {10}^{-2} $	$ 9.46\times {10}^{-3} $	$ {\bf{8.46\times {10}^{-3}}} $
CIHS	任务T²	$ 2.31\times {10}^{-1} $	$ 2.38\times {10}^{-1} $	$ 7.83\times {10}^{-2} $	$ 5.72\times {10}^{-2} $	$ {\bf{4.32\times {10}^{-2}}} $
CIMS	任务T¹	$ 4.83\times {10}^{0} $	$ 3.03\times {10}^{0} $	$ 2.99\times {10}^{0} $	$ 2.71\times {10}^{-3} $	$ {\bf{2.50\times {10}^{-3}}} $
CIMS	任务T²	$ 6.20\times {10}^{-3} $	$ 3.00\times {10}^{-1} $	$ 4.34\times {10}^{-1} $	$ 4.14\times {10}^{-3} $	$ {\bf{3.73\times {10}^{-3}}} $
CILS	任务T¹	$ 2.92\times {10}^{1} $	$ 6.96\times {10}^{-2} $	$ 3.64\times {10}^{-2} $	$ 1.63\times {10}^{-2} $	$ {\bf{1.36\times {10}^{-2}}} $
CILS	任务T²	$ 1.06\times {10}^{-2} $	$ 5.49\times {10}^{-3} $	$ 4.43\times {10}^{-3} $	$ 3.99\times {10}^{-3} $	$ {\bf{3.66\times {10}^{-2}}} $
PIHS	任务T¹	$ 1.86\times {10}^{-1} $	$ 7.63\times {10}^{-1} $	$ 2.43\times {10}^{-1} $	$ 4.70\times {10}^{-2} $	$ {\bf{3.95\times {10}^{-2}}} $
PIHS	任务T²	$ 6.96\times {10}^{1} $	$ 2.01\times {10}^{1} $	$ 2.04\times {10}^{1} $	$ 4.39\times {10}^{0} $	$ {\bf{3.14\times {10}^{0}}} $
PIMS	任务T¹	$ 3.23\times {10}^{-1} $	$ 4.63\times {10}^{-1} $	$ 2.60\times {10}^{-1} $	$ 8.47\times {10}^{-2} $	$ {\bf{6.07\times {10}^{-2}}} $
PIMS	任务T²	$ 7.45\times {10}^{2} $	$ 5.32\times {10}^{2} $	$ {\bf{4.47\times {10}^{2}}} $	$ 6.51\times {10}^{2} $	$ 6.04\times {10}^{2} $
PILS	任务T¹	$ 1.96\times {10}^{-2} $	$ 2.64\times {10}^{-2} $	$ 1.38\times {10}^{-2} $	$ 1.29\times {10}^{-2} $	$ {\bf{1.16\times {10}^{-2}}} $
PILS	任务T²	$ 1.27\times {10}^{1} $	$ 2.36\times {10}^{0} $	$ 1.80\times {10}^{0} $	$ 2.78\times {10}^{0} $	$ {\bf{1.67\times {10}^{0}}} $
NIHS	任务T¹	$ 3.52\times {10}^{2} $	$ 6.05\times {10}^{1} $	$ 5.92\times {10}^{1} $	$ 4.87\times {10}^{1} $	$ {\bf{4.62\times {10}^{1}}} $
NIHS	任务T²	$ 1.65\times {10}^{-1} $	$ 2.85\times {10}^{-1} $	$ 2.54\times {10}^{-1} $	$ 1.28\times {10}^{-2} $	$ {\bf{1.12\times {10}^{-2}}} $
NIMS	任务T¹	$ 1.87\times {10}^{1} $	$ 4.89\times {10}^{1} $	$ 5.07\times {10}^{1} $	$ {\bf{1.05\times {10}^{1}}} $	$ 1.09\times {10}^{1} $
NIMS	任务T²	$ 8.14\times {10}^{-1} $	$ 4.85\times {10}^{0} $	$ 3.56\times {10}^{0} $	$ 2.25\times {10}^{-2} $	$ {\bf{2.06\times {10}^{-2}}} $
NILS	任务T¹	$ 4.70\times {10}^{-2} $	$ 8.45\times {10}^{-1} $	$ 8.99\times {10}^{-2} $	$ 4.62\times {10}^{-2} $	$ {\bf{3.26\times {10}^{-2}}} $
NILS	任务T²	$ {\bf{1.97\times {10}^{1}}} $	$ 2.04\times {10}^{1} $	$ 2.04\times {10}^{1} $	$ 2.03\times {10}^{1} $	$ 2.02\times {10}^{1} $

选择文件类型/文献管理软件名称

选择包含的内容