Expensive High-Dimensional Optimization Algorithm with Three-Stage Adaptive Sampling and Incremental Kriging Assistance

doi:10.3778/j.issn.1002-8331.2306-0252

Abstract

Abstract: Surrogate-assisted evolutionary algorithms have been widely used to solve costly multi-objective optimization problems, but are often restricted to solving problems with low-dimensional decision variables due to the limitations of the surrogate model. In order to solve the expensive high-dimensional multi-objective optimization problem, an improved incremental Kriging-assisted evolutionary algorithm based on the three-stage adaptive sampling strategy is proposed in this paper. The algorithm uses an improved incremental Kriging model to approximate each objective function. This model’s hyperparameters are adaptively updated according to prediction uncertainty, reducing computational complexity while ensuring the model’s accuracy in high dimensions. In addition, the three-stage adaptive sampling strategy is proposed for model management, which divides the sampling process into different optimization stages to tailor the selection of individuals. It is able to guarantee convergence first and improve the convergence speed of the algorithm. To verify the effectiveness of the proposed algorithm, experiments are conducted on two sets of test problems containing various features DTLZ (deb-tiele-laumanns-zitzler), MaF (many-objective function) and path planning real engineering problems compared with state-of-the-art algorithms of the same type. The results show that the algorithm is highly competitive in solving expensive multi-objective optimization problems with high-dimensional decision variables.

Key words: expensive optimization, multi-objective optimization, high-dimensional decision variables, surrogate-assisted evolutionary algorithm, incremental Kriging models, three-stage adaptive sampling strategy

摘要： 代理辅助进化算法已广泛应用于求解代价高昂的多目标优化问题，但大多数由于代理模型的局限性而仅限于解决决策变量低维的问题。为了解决高维的昂贵多目标优化问题，提出了一种基于三阶段自适应采样策略的改进增量克里金辅助的进化算法。该算法使用改进的增量克里金模型来近似每个目标函数，此模型的超参数根据预测的不确定性进行自适应更新，降低计算复杂度的同时保证模型在高维上的准确性；此外，在模型管理方面提出一种三阶段自适应采样的策略，将采样过程分为不同的优化阶段以更有针对性的选择个体，能够首先保证收敛性，提高算法的收敛速度。为了验证算法的有效性，在包含各种特征的两组测试问题DTLZ（deb-thiele-laumanns-zitzler）、MaF（many-objective function）和路径规划实际工程问题上与最新的同类型算法进行实验对比，结果表明该算法在解决决策变量高维的昂贵多目标优化问题上具有较强的竞争力。

关键词: 昂贵优化, 多目标优化, 决策变量高维, 代理辅助进化算法, 增量克里金模型, 三阶段自适应采样策略

GU Qinghua, LIU Sihan, WANG Qian, LUO Jiale, LIU Di. Expensive High-Dimensional Optimization Algorithm with Three-Stage Adaptive Sampling and Incremental Kriging Assistance[J]. Computer Engineering and Applications, 2024, 60(5): 76-87.

顾清华, 刘思含, 王倩, 骆家乐, 刘迪. 三阶段自适应采样和增量克里金辅助的昂贵高维优化算法[J]. 计算机工程与应用, 2024, 60(5): 76-87.

References

[1] 顾清华, 骆家乐, 李学现. 基于小生境的多目标进化算法[J]. 计算机工程与应用, 2023, 59(1): 126-139.
GU Q H, LUO J L, LI X X. Evolutionary algorithm based on niche for multi-objective optimization[J]. Computer Engineering and Applications, 2023, 59(1): 126-139.
[2] JIN Y C, WANG H D, CHUGH T, et al. Data-driven evolutionary optimization: an overview and case studies[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(3): 442-458.
[3] WANG H D, JIN Y C, JANSEN J O. Data-driven surrogate-assisted multiobjective evolutionary optimization of a trauma system[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(6): 939-952.
[4] GUO D, CHAI T Y, DING J L, et al. Small data driven evolutionary multi-objective optimization of fused magnesium furnaces[C]//Proceedings of the IEEE Symposium Series on Computational Intelligence (IEEE SSCI), Dec 6-9, 2016. New York: IEEE, 2016: 1-8.
[5] JIN Y C. Surrogate-assisted evolutionary computation: recent advances and future challenges[J]. Swarm and Evolutionary Computation, 2011, 1(2): 61-70.
[6] ZHANG J Y, ZHOU A M, ZHANG G X, et al. A classification and Pareto domination based multiobjective evolutionary algorithm[C]//Proceedings of the IEEE Congress on Evolutionary Computation (CEC), May 25-28, 2015. New York: IEEE, 2015: 2883-2890.
[7] PAN L Q, HE C, TIAN Y, et al. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(1): 74-88.
[8] 顾清华, 张晓玥, 陈露. 基于改进集成学习分类的代理辅助进化算法[J]. 控制与决策, 2022, 37(10): 2456-2466.
GU Q H, ZHANG X Y, CHEN C. Improved ensemble learning classification based surrogate-assisted evolutionary algorithm[J]. Control and Decision, 2022, 37(10): 2456-2466.
[9] KNOWLES J. ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(1): 50-66.
[10] CHUGH T, JIN Y C, MIETTINEN K, et al. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 129-142.
[11] HABIB A, SINGH H K, CHUGH T, et al. A multiple surrogate assisted decomposition-based evolutionary algorithm for expensive multi/many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(6): 1000-1014.
[12] 陈万芬, 王宇嘉, 林炜星. 异构集成代理辅助多目标粒子群优化算法[J]. 计算机工程与应用, 2021, 57(23): 71-80.
CHEN W F, WANG Y J, LIN W X. Heterogeneous ensemble surrogate assisted multi-objective particle swarm Optimization Algorithm[J]. Computer Engineering and Applications, 2021, 57(23): 71-80.
[13] 白富生, 陈姣伶. 基于聚类的昂贵多目标优化代理辅助进化算法[J]. 运筹学学报, 2022, 26(4): 31-42.
BAI F S, CHEN J L. A clustering-based surrogate-assisted evolutionary algorithm for expensive multi-objective optimization[J]. Operations Research Transations, 2022, 26(4): 31-42.
[14] BUCHE D, SCHRAUDOLPH N N, KOUMOUTSAKOS P. Accelerating evolutionary algorithms with Gaussian process fitness function models[J]. IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 2005, 35(2): 183-194.
[15] SHAHRIARI B, SWERSKY K, WANG Z Y, et al. Taking the human out of the loop: a review of Bayesian optimization[J]. Proceedings of the IEEE, 2016, 104(1): 148-175.
[16] ZHAN D W, XING H L. A fast Kriging-assisted evolutionary algorithm based on incremental learning[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(5): 941-955.
[17] YUAN J, LIU H L, GU F, et al. Investigating the properties of indicators and an evolutionary many-objective algorithm using promising regions[J]. IEEE Transactions on Evolutionary Computation, 2020, 25(1): 75-86.
[18] TOAL D J J, BRESSLOFF N W, KEANE A J. Kriging hyperparameter tuning strategies[J]. AIAA Journal, 2008, 46(5): 1240-1252.
[19] DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multiobjective optimization[M]. London: Springer-Verlag, 2005: 105-145.
[20] CHENG R, LI M, TIAN Y, et al. A benchmark test suite for evolutionary many-objective optimization[J]. Complex & Intelligent Systems, 2017, 3(1): 67-81.
[21] 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, 2013, 18(4): 577-601.
[22] HAO H, ZHOU A M, QIAN H, et al. Expensive multiobjective optimization by relation learning and prediction[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(5): 1157-1170.
[23] WANG X L, JIN Y C, SCHMITT S, et al. An adaptive Bayesian approach to surrogate-assisted evolutionary multi-objective optimization[J]. Information Sciences, 2020, 519: 317-331.
[24] GUO D, WANG X, GAO K, et al. Evolutionary optimization of high-dimensional multiobjective and many-objective expensive problems assisted by a dropout neural network[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(4): 2084-2097.
[25] GUO D, JIN Y C, DING J L, et al. Heterogeneous ensemble-based infill criterion for evolutionary multiobjective optimization of expensive problems[J]. IEEE Transactions on Cybernetics, 2019, 49(3): 1012-1025.
[26] SONG Z S, WANG H D, HE C, et al. A Kriging-assisted two-archive evolutionary algorithm for expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1013-1027.
[27] TIAN Y, CHENG R, ZHANG X Y, et al. PlatEMO: a MATLAB platform for evolutionary multi-objective optimization[J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
[28] WEISE J, MOSTAGHIM S. A scalable many-objective pathfinding benchmark suite[J]. IEEE Transactions on Evolutionary Computation, 2021, 26(1): 188-194.