Pareto解集旋转的分类多策略预测动态多目标优化

doi:10.3778/j.issn.1002-8331.2401-0145

摘要/Abstract

摘要： 为更有效地解决Pareto解集（Pareto set，PS）旋转的动态多目标优化问题，提出PS旋转的分类多策略预测方法（rotation-based forecasting method，RFM）。将PS的旋转类型分为PS中心点旋转、PS原点旋转和非标准旋转；针对以上不同的PS旋转类型，自适应地选择合适的预测模型，建立不同点集的时间序列，为后续进化提供初始种群。引入拉丁超立方策略（Latin hypercube strategy，LHS）生成的随机种群与上述预测种群共同构建新种群，保证种群的多样性。为验证算法的有效性，将RFM算法与DNSGA-II、PPS、SPPS和MMP算法在8个标准的动态测试函数上进行实验对比。实验结果表明，RFM算法取得了6个最优[IGD]值、7个最优[SP]值、3个最优[MS]值，证明了RFM算法可以更有效地解决基于PS旋转的动态多目标优化问题。同时验证了RFM算法的普适性，在FDA系列函数上进行实验对比，实验结果表明，该算法在处理非旋转的动态多目标优化问题中仍具有较优性能。

关键词: 动态多目标优化, 进化算法, 分类预测, Pareto解集旋转

Abstract: In order to solve the dynamic multi-objective optimization problem of Pareto set (PS) rotation more effectively, this paper proposes a classification multi-strategy prediction method based on PS rotation (RFM). Firstly, the rotation types of PS are divided into PS center point rotation, PS origin rotation and non-standard rotation. Then, the appropriate prediction model is adaptively selected for the above different PS rotation types, and the time series of different point sets is established to provide the initial population for the subsequent evolution. Finally, the random population generated by Latin hypercube strategy (LHS) is introduced to construct a new population together with the above predicted population to ensure the diversity of the population. In order to verify the effectiveness of the algorithm, the RFM algorithm is compared with DNSGA-II, PPS, SPPS and MMP algorithms on eight standard dynamic test functions. The experimental results show that the RFM algorithm achieves six optimal [IGD] values, seven optimal [SP] values and three optimal [MS] values, which proves that the RFM algorithm can solve the dynamic multi-objective optimization problem based on PS rotation more effectively. At the same time, the generality of the RFM algorithm is verified by experiments on the FDA series of functions. The experimental results show that the algorithm still has better performance in dealing with non-rotating dynamic multi-objective optimization problems.

Key words: dynamic multi-objective optimization, evolutionary algorithm, classified prediction, Pareto set rotation

李二超, 刘辰淼. Pareto解集旋转的分类多策略预测动态多目标优化[J]. 计算机工程与应用, 2024, 60(22): 87-104.

LI Erchao, LIU Chenmiao. Classification Multi-Strategy Predictive Dynamic Multi-Objective Optimization with Pareto Set Rotation[J]. Computer Engineering and Applications, 2024, 60(22): 87-104.

参考文献

[1] HAN S G, WON S S, YOUNG J P. Space-constrained scheduling optimization method for minimizing the effects of stacking of trades[J]. Applied Sciences, 2021, 11(22): 11047.
[2] WANG C L, YANG X, LI H. Improved Q-learning applied to dynamic obstacle avoidance and path planning[J]. IEEE Access, 2022, 10: 92879-92888.
[3] ZHANG S H, CUI G F, WANG W D. Joint data downloading and resource management for small satellite cluster networks[J]. IEEE Transactions on Vehicular Technology, 2022, 71(1): 887-901.
[4] PARK P, ERGEN S C, FISCHIONE C, et al. Wireless network design for control systems: a survey[J]. IEEE Communications Surveys & Tutorials, 2017, 20(2): 978-1013.
[5] 陈珂锐, 孟小峰. 机器学习的可解释性[J]. 计算机研究与发展, 2020, 57(9): 1971-1986.
CHEN K R, MENG X F. Interpretability of machine learning [J]. Journal of Computer Research and Development, 2020, 57(9): 1971-1986.
[6] MARYAM S, MOHSEN A, HAMED H S. Dynamic distributed constraint optimization using multi-agent reinforcement learning[J]. Soft Computing, 2022, 26(8): 3601-3629.
[7] WANG X Y, LI Z B, LUO X Y, et al. A novel bi-level optimization model-based optimal energy scheduling for hybrid ship power system[J]. MRS Energy Sustainability, 2023, 10(2): 247-260.
[8] DEB K, RAO U B, KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-II: a case study on hydro-thermal power scheduling[C]//Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg: Springer, 2007: 803-817.
[9] HATZAKIS I, WALLACE D. Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach[C]//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2006: 1201-1208.
[10] ZHOU A, JIN Y, ZHANG Q, et al. Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization[C]//Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg: Springer, 2007: 832-846.
[11] ZHOU A M, JIN Y C, ZHANG Q F. A population prediction strategy for evolutionary dynamic multi-objective optimization[J]. IEEE Transactions on Cybernetics, 2014, 44(1): 40-53.
[12] LI Q Y, ZOU J, SHENG X Y, et al. A predictive strategy based on special points for evolutionary?dynamic?multi-objective?optimization[J]. Soft Computing, 2019, 23(11): 3723-3739.
[13] 丁进良, 杨翠娥, 陈立鹏, 等. 基于参考点预测的动态多目标优化算法[J]. 自动化学报, 2017, 43(2): 313-320.
DING J L, YANG C E, CHEN L P, et al. Dynamic multi-objective optimization algorithm based on reference point prediction[J]. Acta Automatica Sinica, 2017, 43(2): 313-320.
[14] 郑金华, 彭舟, 邹娟, 等. 基于引导个体的预测策略求解动态多目标优化问题[J]. 电子学报, 2015, 43(9): 1816-1825.
ZHENG J H, PENG Z, ZOU J, et al. A prediction strategy based on guide-individual for dynamic multi-objective optimization[J]. Acta Electronica Sinica, 2015, 43(9): 1816-1825.
[15] YE Y L, LI L J, LIN Q Z, et al. Knowledge guided Bayesian classification for dynamic multi-objective optimization[J]. Knowledge-Based Systems, 2022, 250: 109173.
[16] 唐晓乐, 王宏伟, 夏浩, 等. 组合预测策略的动态多目标优化算法[J]. 计算机工程与设计, 2022, 43(7): 1930-1940.
TANG X L, WANG H W, XIA H, et al. Dynamic multi-objective optimization algorithm based on combination prediction strategy[J]. Computer Engineering and Design, 2012, 43(7): 1930-1940.
[17] ALINIYA Z, KHASTEH S H. A novel combinational response mechanism for dynamic multi-objective optimization[J]. Expert Systems with Applications, 2023, 233: 120951.
[18] ZHANG X, YU G, JIN Y C, et al. Elitism-based transfer learning and diversity maintenance for dynamic multi-objective optimization[J]. Information Sciences, 2023, 636: 118927.
[19] RONG M, GONG D W, ZHANG Y, et al. Multidirectional prediction approach for dynamic multi-objective optimization problems[J]. IEEE Transactions on Cybernetics, 2018, 49(9): 3362-3374.
[20] RONG M, GONG D W, PEDRYCZ W, et al. A multi-model prediction method for dynamic multi-objective evolutionary optimization[J]. IEEE Transactions on Computation, 2020, 24(2): 290-304.
[21] MCKAY M D, BECKMAN J R, CONOVER J W. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code[J]. Technometrics, 2000, 42(1): 55-61.
[22] 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.
[23] XU B, ZHANG Y, GONG D W, et al. Environment sensitivity-based cooperative co-evolutionary algorithms for dynamic multi-objective optimization[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2017, 15(6): 1877-1890.
[24] 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.
[25] ZITALER E, THIELE L. Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271.
[26] SCHOTT J R. Fault tolerant design using single and multi-criteria genetic algorithms[D]. Massachusetts Institute of Technology, 1995.
[27] DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Paris, Sep 18-20, 2000. Berlin, Heidelberg: Springer, 2000: 849-858.