一种新的基于预测的动态多目标进化算法

doi:10.19665/j.issn1001-2400.20230902

摘要/Abstract

摘要：

动态多目标优化问题(DMOPs)是指目标函数随时间变化的一类问题,算法求解的目标是持续跟踪移动的Pareto 最优解集或 Pareto最优前沿。基于预测的方法受到格外的关注,然而这些方法多使用历史环境信息进行预测,考虑到使用历史信息预测会存在预测不准确的问题,加强新环境信息的挖掘和利用,提出了一种新的基于预测的动态多目标进化算法,该算法主要包括两个核心部分,分别记为响应机制和加速机制。响应机制在环境变化后重新初始化群体,一部分的个体由预测策略产生,以生成靠近下一环境Pareto 最优解集的个体来提高算法的寻优能力,剩余部分个体采用局部搜索策略生成以增加种群多样性。加速机制用于静态优化过程以提高算法收敛速度。最后,将动态多目标进化算法与其他3种先进的动态多目标优化算法在具有不同动态特征的一系列测试函数上进行实验对比,结果表明,动态多目标进化算法相比其他3个算法在求解动态多目标优化问题中更具有优势。

关键词: 进化算法, 动态多目标优化, 预测策略, 新环境信息

Abstract:

Dynamic multi-objective optimization problems(DMOPs) where the environments change over time require that an evolutionary algorithm be able to continuously track the moving Pareto set or Pareto front.Response strategies based prediction has received much attention.However,these strategies mostly use historical environmental information for prediction,which will make the predicted results inaccurate.In this paper,we strengthen the mining and utilization of new environmental information and propose a new prediction strategy based evolutionary algorithm for dynamic multi-objective optimization(RAM),which includes mainly two core parts,namely,response mechanism and acceleration mechanism.The response mechanism reinitializes the population after the environmental changes,some individuals are generated by the prediction strategy,which is close to the new environmental PS to improve the optimization ability of this algorithm,and the remaining individuals are generated by the local search strategy to increase the population diversity.The acceleration mechanism is used in the static optimization process to accelerate the convergence speed of the RAM.Finally,the RAM is compared with other three advanced dynamic multi-objective optimization algorithms on a series of test functions with different dynamic characteristics.The results show that the RAM has more advantages than other three algorithms in solving dynamic multi-objective optimization problems.

Key words: evolutionary algorithm, dynamic multi-objective optimization, prediction strategy, new environment information

中图分类号:

万梦依, 武燕. 一种新的基于预测的动态多目标进化算法[J]. 西安电子科技大学学报, 2024, 51(3): 124-135.

WAN Mengyi, WU Yan. New prediction strategy based evolutionary algorithm for dynamic multi-objective optimization[J]. Journal of Xidian University, 2024, 51(3): 124-135.

图/表 5

图1

表1

表2

表3

4个算法在不同变化频率下IGD的均值和标准差"

测试函数	(n_t,τ_t)	NSGA-Ⅱ-A mean(std)	Tr-MOEA mean(std)	DSS mean(std)	RAM mean(std)
F9	(10,5)	2.26e+0(3.16e-1)	2.74e+0(1.74e-2)	2.56e-1(3.38e-2)	1.84e-1(1.82e-2)
	(10,10)	1.27e+0(2.67e-1)	2.58e+0(5.18e-2)	9.99e-2(1.05e-2)	6.96e-2(8.60e-3)
	(10,20)	4.95e-1(1.60e-1)	2.24e+0(1.31e-1)	3.34e-2(4.00e-3)	4.39e-2(3.80e-3)
F10	(10,5)	2.56e+0(3.89e-1)	6.72e+0(5.71e-1)	2.02e-1(2.45e-2)	3.05e-1(4.79e-2)
	(10,10)	1.29e+0(2.27e-1)	4.52e+0(5.51e-1)	8.14e-2(8.00e-3)	1.02e-1(2.33e-2)
	(10,20)	5.79e-1(1.04e-1)	2.35e+0(4.32e-1)	3.52e-2(4.60e-3)	3.34e-2(6.30e-3)
F11	(10,5)	2.48e+0(3.69e-1)	4.47e+0(1.15e-1)	3.38e-1(1.32e-1)	3.93e-1(8.38e-2)
	(10,10)	1.40e+0(2.52e-1)	3.70e+0(1.76e-1)	1.27e-1(4.21e-2)	9.65e-2(2.08e-2)
	(10,20)	7.70e-1(1.22e-1)	3.13e+0(2.64e-1)	3.99e-2(1.27e-2)	2.75e-2(3.00e-3)
F12	(10,5)	2.34e+0(5.71e-1)	3.18e+0(2.40e-1)	2.19e-1(3.33e-2)	1.76e-1(2.94e-2)
	(10,10)	1.21e+0(3.49e-1)	2.85e+0(1.17e-1)	794e-2(9.20e-3)	5.29e-2(7.60e-3)
	(10,20)	5.02e-1(1.61e-1)	2.37e+0(1.45e-1)	2.73e-2(3.40e-3)	2.42e-2(2.30e-3)
DMOP3	(10,5)	1.04e-1(1.81e-2)	3.20e-2(8.90e-3)	6.27e-2(6.20e-3)	4.97e-2(5.50e-3)
	(10,10)	5.07e-2(2.80e-3)	2.56e-2(6.00e-3)	2.26e-2(3.70e-3)	1.84e-2(2.00e-3)
	(10,20)	3.62e-2(2.20e-3)	2.14e-2(2.20e-3)	1.02e-2(9.00e-3)	1.07e-2(2.00e-3)
ZJZ7	(10,5)	2.83e+0(3.14e-1)	3.92e-1(3.00e-2)	3.94e-1(1.65e-1)	3.36e-1(5.86e-2)
	(10,10)	1.18e+0(2.07e-1)	2.56e-1(1.76e-2)	1.35e-1(3.32e-2)	1.10e-1(1.75e-2)
	(10,20)	3.00e-1(8.76e-2)	1.95e-1(4.80e-3)	4.01e-2(5.70e-3)	3.26e-2(6.20e-3)
ZJZ8	(10,5)	1.25e+0(1.97e-1)	2.81e-1(2.24e-2)	3.37e-1(5.22e-2)	2.64e-1(6.15e-2)
	(10,10)	4.99e-1(1.33e-1)	2.50e-1(8.80e-3)	1.30e-1(2.69e-2)	1.12e-1(2.61e-2)
	(10,20)	1.54e-1(5.12e-2)	1.51e-1(9.80e-3)	3.97e-2(5.30e-3)	2.57e-2(6.50e-3)
JY10	(10,5)	2.38e+0(4.77e-1)	9.68e-1(6.32e-2)	4.28e-1(1.95e-1)	3.18e-1(2.17-1)
	(10,10)	1.26e+0(3.63e-1)	7.11e-1(4.07e-2)	3.10e-1(5.98e-2)	2.59e-1(8.45e-2)
	(10,20)	7.71e-1(2.85e-1)	5.87e-1(5.67e-2)	1.33e-1(5.20e-3)	1.28e-1(8.70e-3)

表3

表4

4个算法在不同变化强度下IGD的均值和标准差"

测试函数	(n_t,τ_t)	NSGA-Ⅱ-A mean(std)	Tr-MOEA mean(std)	DSS mean(std)	RAM mean(std)
F9	(5,10)	1.65e+0(2.12e-1)	2.63e+0(9.19e-2)	8.42e-2(1.77e-2)	7.59e-2(1.66e-2)
	(10,10)	1.26e+0(2.66e-1)	2.58e+0(5.18e-2)	9.99e-2(1.05e-2)	6.96e-2(8.6e-3)
	(20,10)	8.53e-1(2.60e-1)	2.56e+0(3.16e-2)	7.47e-2(1.09e-2)	6.46e-2(1.11e-2)
F10	(5,10)	1.88e+0(2.80e-1)	4.03e+0(5.02e-1)	1.24e-1(2.78e-2)	1.43e-1(4.40e-2)
	(10,10)	1.29e+0(2.27e-1)	4.52e+0(5.51e-1)	8.14e-2(8.00e-3)	1.02e-1(2.33e-2)
	(20,10)	7.75e-1(1.73e-1)	4.06e+0(5.34e-1)	8.83e-2(9.68e-1)	7.39e-2(1.43e-2)
F11	(5,10)	2.02e+0(3.52e-1)	3.99e+0(1.78e-1)	1.36e-1(2.70e-2)	1.45e-1(3.57e-2)
	(10,10)	1.40e+0(2.52e-1)	3.70e+0(1.76e-1)	1.27e-1(4.21e-2)	9.65e-2(2.08e-2)
	(20,10)	9.68e-1(2.31e-1)	3.54e+0(1.75e-1)	8.86e-2(3.78e-2)	6.67e-2(2.00e-2)
F12	(5,10)	1.88e+0(3.14e-1)	2.85e+0(1.23e-1)	1.24e-1(2.06e-2)	6.44e-2(6.60e-3)
	(10,10)	1.21e+0(3.49e-1)	2.85e+0(1.17e-1)	7.94e-2(9.20e-3)	5.29e-2(7.60e-3)
	(20,10)	9.61e-1(4.25e-1)	2.73e+0(2.78e-2)	5.97e-2(9.80e-3)	4.55e-2(7.5e-3)
DMOP3	(5,10)	8.72e-2(1.40e-2)	2.53e-2(1.26e-2)	2.55e-2(3.10e-3)	1.71e-2(2.50e-3)
	(10,10)	5.07e-2(2.81e-3)	2.56e-2(6.00e-3)	2.26e-2(3.70e-3)	1.84e-2(2.00e-3)
	(20,10)	3.81e-2(2.30e-3)	2.14e-2(2.20e-3)	2.13e-2(3.40e-3)	1.79e-2(2.40e-3)
ZJZ7	(5,10)	1.19e+0(2.02e+0)	3.11e-1(9.80e-3)	1.54e-1(5.63e-2)	1.02e-1(2.81e-2)
	(10,10)	1.18e+0(2.07e-1)	2.56e-1(1.76e-2)	1.35e-1(3.32e-2)	1.10e-1(1.75e-2)
	(20,10)	1.16e+0(2.09e-1)	3.10e-1(1.27e-2)	1.43e-1(5.16e-2)	1.07e-1(1.83e-2)
ZJZ8	(5,10)	5.15e-1(1.16e-1)	3.06e-1(1.28e-2)	1.61e-1(2.45e-2)	1.19e-1(2.53e-2)
	(10,10)	5.00e-1(1.33e-1)	2.50e-1(8.80e-3)	1.30e-1(2.69e-2)	1.12e-1(2.61e-2)
	(20,10)	5.42e-1(1.65e-1)	3.06e-1(1.11e-2)	1.36e-1(2.69e-2)	1.17e-1(3.30e-2)
JY10	(5,10)	7.28e-1(4.67e-1)	8.75e-1(5.17e-2)	5.37e-1(2.38e-1)	4.76e-1(2.28e-1)
	(10,10)	1.27e+0(3.63e-1)	7.11e-1(4.07e-2)	3.10e-1(5.89e-2)	2.60e-1(8.45e-2)
	(20,10)	1.01e+0(4.88e-1)	6.97e-1(6.24e-2)	2.94e-1(2.32e-1)	3.12e-1(2.69e-1)

表4

参考文献 37

[1]	LIN W, XU S, HE L, et al. Multi-Resource Scheduling and Power Simulation for Cloud Computing[J]. Information Sciences, 2017, 397:168-186.
[2]	WU H, KUANG L, WANG F, et al. A Multi-Objective Box-Covering Algorithm for Fractal Modularity on Complex Networks[J]. Applied Soft Computing, 2017, 61:294-313.
[3]	ZHANG Z. Multi-Objective Optimization Immune Algorithm in Dynamic Environments and Its Application to Greenhouse Control[J]. Applied Soft Computing, 2008, 8(2):959-971.
[4]	LIN W, XU S Y, LI J, et al. Design and Theoretical Analysis of Virtual Machine Placement Algorithm Based on Peak Workload Characteristics[J]. Soft Computing, 2017, 21(5):1301-1314.
[5]	LI Y, TONG S, LI T. Adaptive Fuzzy Output Feedback Dynamic Surface Control of Interconnected Nonlinear Pure-Feedback Systems[J]. IEEE Transactions on Cybernetics, 2014, 45(1):138-149.
[6]	BUI L T, MICHALEWICZ Z, PARKINSON E, et al. Adaptation in Dynamic Environments:A Case Study in Mission Planning[J]. IEEE Transactions on Evolutionary Computation, 2011, 16(2):190-209.
[7]	MAVROVOUNIOTIS M, MÜLLER F M, YANG S. Ant Colony Optimization with Local Search for Dynamic Traveling Salesman Problems[J]. IEEE Transactions on Cybernetics, 2016, 47(7):1743-1756.
[8]	YAN X H, CAI B G, NING B, et al. Moving Horizon Optimization of Dynamic Trajectory Planning for High-Speed Train Operation[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 17(5):1258-1270.
[9]	LIU M. Robotic Online Path Planning on Point Cloud[J]. IEEE Transactions on Cybernetics, 2015, 46(5):1217-1228.
[10]	CRUZ A R, CARDOSO R T N, TAKAHASHI R H C. Multi-Objective Dynamic Optimization of Vaccination Campaigns Using Convex Quadratic Approximation Local Search[C]//International Conference on Evolutionary Multi-Criterion Optimization. Heidelberg:Springer, 2011:404-417.
[11]	JIANG M, HUANG Z, QIU L, et al. Transfer Learning-Based Dynamic Multi-Objective Optimization Algorithms[J]. IEEE Transactions on Evolutionary Computation, 2017, 22(4):501-514.
[12]	刘远振, 杨颜博, 张嘉伟, 等. 一种抗分布式机器学习恶意节点的区块链方案[J]. 西安电子科技大学学报, 2023, 50(2):178-187.
	LIU Yuanzhen, YANG Yanbo, ZHANG Jiawei, et al. A Blockchain Scheme Against Distributed Machine Learning Malicious Nodes[J]. Journal of Xidian University, 2023, 50(2):178-187.
[13]	郭刚, 杨超, 陈明哲, 等. 结合机器学习的SSR代理下App流量识别方法[J]. 西安电子科技大学学报, 2023, 50(2):138-146.
	GUO Gang, YANG Chao, CHEN Mingzhe, et al. App Traffic Recognition Based on SSR Agent Combined with Machine Learning[J]. Journal of Xidian University, 2023, 50(2):138-146.
[14]	GOH C K, TAN K C. A Competitive-Cooperative Coevolutionary Paradigm for Dynamic Multi-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2008, 13(1):103-127.
[15]	CHEN R, LI K, YAO X. Dynamic Multi-Objectives Optimization with a Changing Number of Objectives[J]. IEEE Transactions on Evolutionary Computation, 2017, 22(1):157-171.
[16]	RUAN G, YU G, ZHENG J, et al. The Effect of Diversity Maintenance on Prediction in Dynamic Multi-Objective Optimization[J]. Applied Soft Computing, 2017, 58:631-647.
[17]	MARTINEZ-PENALOZA M G, MEZURA-MONTES E. Immune Generalized Differential Evolution for Dynamic Multi-Objective Environments:an Empirical Study[J]. Knowledge-Based Systems, 2018, 142:192-219.
[18]	MA X, YANG J, SUN H, et al. Multiregional Co-Evolutionary Algorithm for Dynamic Multi-Objective Optimization[J]. Information Sciences, 2021, 545:1-24.
[19]	PENG Z, ZHENG J, ZOU J, et al. Novel Prediction and Memory Strategies for Dynamic Multi-Objective Optimization[J]. Soft Computing, 2015, 19:2633-2653.
[20]	WANG Y, LI B. Investigation of Memory-Based Multi-Objective Optimization Evolutionary Algorithm in Dynamic Environment[C]//2009 IEEE Congress on Evolutionary Computation.Piscataway:IEEE, 2009:630-637.
[21]	ZHAO Q, YAN B, SHI Y, et al. Evolutionary Dynamic Multi-Objective Optimization via Learning from Historical Search Process[J]. IEEE Transactions on Cybernetics, 2021, 52(7):6119-6130.
[22]	WANG P, MA Y, WANG M. A Dynamic Multi-Objective Optimization Evolutionary Algorithm Based on Particle Swarm Prediction Strategy and Prediction Adjustment Strategy[J]. Swarm and Evolutionary Computation, 2022, 75:101164.
[23]	CHEN Y, ZOU J, LIU Y, et al. Combining a Hybrid Prediction Strategy and a Mutation Strategy for Dynamic Multi-Objective Optimization[J]. Swarm and Evolutionary Computation, 2022, 70:101041.
[24]	WU Y, JIN Y, LIU X. A Directed Search Strategy for Evolutionary Dynamic Multi-Objective Optimization[J]. Soft Computing, 2015, 19(11):3221-3235.
[25]	XU D, JIANG M, HU W, et al. An Online Prediction Approach Based on Incremental Support Vector Machine for Dynamic Multi-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(4):690-703.
[26]	WANG F, LI Y, LIAO F, et al. An Ensemble Learning Based Prediction Strategy for Dynamic Multi-Objective Optimization[J]. Applied Soft Computing, 2020, 96:106592.
[27]	LIU R, NIU X, FAN J, et al. An Orthogonal Predictive Model-Based Dynamic Multi-Objective Optimization Algorithm[J]. Soft Computing, 2015, 19:3083-3107.
[28]	RONG M, GONG D, ZHANG Y, et al. Multidirectional Prediction Approach for Dynamic Multi-Objective Optimization Problems[J]. IEEE Transactions on Cybernetics, 2018, 49(9):3362-3374.
[29]	WU Y, SHI L, LIU X. A New Dynamic Strategy for Dynamic Multi-Objective Optimization[J]. Information Sciences, 2020, 529:116-131.
[30]	WU H, KUANG L, WANG F, et al. A Multi-Objective Box-Covering Algorithm for Fractal Modularity on Complex Networks[J]. Applied Soft Computing, 2017, 61:294-313.
[31]	LIU Z, WANG H. Improved Population Prediction Strategy for Dynamic Multi-Objective Optimization Algorithms Using Transfer Learning[C]//2021 IEEE Congress on Evolutionary Computation.Piscataway:IEEE, 2021:103-110.
[32]	JIANG M, HUANG Z, QIU L, et al. Transfer Learning-Based Dynamic Multi-Objective Optimization Algorithms[J]. IEEE Transactions on Evolutionary Computation, 2017, 22(4):501-514.
[33]	JIANG M, HU W, QIU L, et al. Solving Dynamic Multi-Objective Optimization Problems via Support Vector Machine[C]//2018 Tenth International Conference on Advanced Computational Intelligence.Piscataway:IEEE, 2018:819-824.
[34]	HU W, JIANG M, GAO X, et al. Solving Dynamic Multi-Objective Optimization Problems Using Incremental Support Vector Machine[C]//2019 IEEE Congress on Evolutionary Computation.Piscataway:IEEE, 2019:2794-2799.
[35]	JIANG M, WANG Z, HONG H, et al. Knee Point-Based Imbalanced Transfer Learning for Dynamic Multi-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 25(1):117-129.
[36]	WELCH G, BISHOP G. An Introduction to the Kalman Filter(1995)[J/OL].[1995-01-01].https://perso.crans.org/club-krobot/doc/kalman.pdf.
[37]	FARINA M, DEB K, AMATO P. Dynamic Multi-Objective Optimization Problems:Test Cases,Approximations,and Applications[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(5):425-442.

测试函数	(n_t,τ_t)	NSGA-Ⅱ-A mean(std)	Tr-MOEA mean(std)	DSS mean(std)	RAM mean(std)
FDA1	(10,10)	9.91e-2(2.22e-2)	1.58e-1(7.40e-3)	2.61e-2(1.90e-3)	2.02e-2(1.70e-3)
FDA1	(10,10)	9.91e-2(2.22e-2)	1.58e-1(7.40e-3)	2.61e-2(1.90e-3)	2.02e-2(1.70e-3)
FDA4	(10,10)	5.09e-2(4.20e-3)	5.74e-2(3.80e-3)	1.83e-1(6.00e-3)	1.83e-1(7.80e-3)
dMOP1	(10,10)	1.08e-1(2.24e-2)	6.67e-2(1.37e-2)	1.51e-1(8.60e-2)	6.52e-2(3.88e-2)
dMOP2	(10,10)	6.84e-2(4.40e-3)	9.33e-2(1.75e-2)	3.53e-2(4.70e-3)	3.59e-2(3.00e-3)
F5	(10,10)	9.06e+0(4.01e+0)	6.72e-1(1.49e-2)	2.86e-1(7.72e-2)	2.52e-1(7.49e-2)
F6	(10,10)	5.30e+0(2.13e+0)	7.01e-1(1.15e-2)	5.58e-1(4.95e-1)	2.47e-1(2.51e-1)
F7	(10,10)	7.49e+0(1.91e+0)	7.60e-1(1.02e-2)	2.47e-1(1.05e-1)	1.64e-1(8.84e-2)
F8	(10,10)	6.93e-2(3.70e-3)	6.52e-2(2.60e-3)	2.44e-1(1.92e-2)	2.42e-1(1.22e-2)
F9	(10,10)	9.26e+0(3.62e+0)	5.81e-1(1.12e-2)	3.40e-1(6.47e-2)	2.22e-1(3.70e-2)
F10	(10,10)	9.13e+0(3.62e+0)	5.98e-1(2.59e-2)	2.62e-1(7.01e-2)	3.75e-1(1.21e-1)
F11	(10,10)	9.30e+0(2.56e+0)	8.01e-1(7.00e-3)	8.40e-1(5.97e-1)	5.04e-1(2.44e-1)
F12	(10,10)	8.39e+0(4.03e+0)	7.06e-1(1.69e-2)	2.89e-1(5.77e-2)	1.92e-1(5.62e-2)
dMOP3	(10,10)	2.55e-1(1.01e-2)	2.78e-2(5.80e-3)	2.64e-2(4.90e-3)	1.58e-1(5.20e-3)
ZJZ7	(10,10)	8.24e+0(2.31e+0)	2.77e-1(1.72e-2)	4.12e-1(1.08e-1)	3.97e-1(1.16e-1)
ZJZ8	(10,10)	3.19e+0(7.83e-1)	2.71e-1(1.01e-2)	4.96e-1(2.14e-1)	3.89e-1(1.33e-1)
JY10	(10,10)	5.27e+0(7.33e-1)	4.23e-1(1.20e-1)	3.49e-1(2.96e-1)	3.64e-1(6.75e-1)