Abstract
Surrogate-assisted evolutionary algorithms (SAEAs) hold significant importance in resolving expensive optimization problems. Extensive efforts have been devoted to improving the efficiency of SAEAs through the development of proficient model-assisted solution selection methods, which, however, first requires generating high-quality solutions. The fundamental paradigm of evaluating a limited number of solutions in each generation within SAEAs reduces the variance of adjacent populations, thereby affecting the quality of offspring solutions. This is a frequently encountered issue yet receives little attention. To address the issue, this paper presents a framework using unevaluated solutions to enhance the efficiency of SAEAs. The surrogate model is employed to identify high-quality solutions for the direct generation of new solutions without evaluation. To ensure dependable selection, we have introduced two tailored relation models to select the optimal solution and the unevaluated population. A comprehensive experimental analysis is performed on two test suites, which showcases the superiority of the relation model over regression and classification models in the solution selection phase. Furthermore, the surrogate-selected unevaluated solutions with high potential have been shown to enhance the efficiency of the algorithm significantly.
Article PDF
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bäck T, Fogel D B, Michalewicz Z. Handbook of Evolutionary Computation. Bristol: IOP Publishing Ltd., 1997
Jin Y. Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evolary Comput, 2011, 1: 61–70
Liu Y R, Hu Y Q, Qian H, et al. ZOOpt: a toolbox for derivative-free optimization. Sci China Inf Sci, 2022, 65: 207101
Yang P, Zhang L, Liu H, et al. Reducing idleness in financial cloud via multi-objective evolutionary reinforcement learning based load balancer. 2023. ArXiv:2305.03463
Li J Y, Zhan Z H, Zhang J. Evolutionary computation for expensive optimization: a survey. Mach Intell Res, 2022, 19: 3–23
Zhan D, Xing H. Expected improvement for expensive optimization: a review. J Glob Optim, 2020, 78: 507–544
Zhang J, Zhou A, Zhang G. Preselection via classification: a case study on global optimisation. Int J Bio-Inspir Comput, 2018, 11: 267–281
Hao H, Zhang J, Lu X, et al. Binary relation learning and classifying for preselection in evolutionary algorithms. IEEE Trans Evol Comput, 2020, 24: 1125–1139
Liu B, Zhang Q, Gielen G G E. A Gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems. IEEE Trans Evol Comput, 2014, 18: 180–192
Chen G, Zhang K, Xue X, et al. Surrogate-assisted evolutionary algorithm with dimensionality reduction method for water flooding production optimization. J Pet Sci Eng, 2020, 185: 106633
Sun C, Jin Y, Cheng R, et al. Surrogate-assisted cooperative swarm optimization of high-dimensional expensive problems. IEEE Trans Evol Comput, 2017, 21: 644–660
Willmes L, Back T, Jin Y, et al. Comparing neural networks and kriging for fitness approximation in evolutionary optimization. In: Proceedings of Congress on Evolutionary Computation, 2003. 663–670
Li H, He F, Yan X. IBEA-SVM: an indicator-based evolutionary algorithm based on pre-selection with classification guided by SVM. Appl Math J Chin Univ, 2019, 34: 1–26
Pan L, He C, Tian Y, et al. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization. IEEE Trans Evol Comput, 2019, 23: 74–88
Loshchilov I, Schoenauer M, Sebag M. Comparison-based optimizers need comparison-based surrogates. In: Proceedings of International Conference on Parallel Problem Solving from Nature, 2010. 364–373
Hao H, Zhou A, Qian H, et al. Expensive multiobjective optimization by relation learning and prediction. IEEE Trans Evol Comput, 2022, 26: 1157–1170
Hao H, Zhou A, Zhang H. An approximated domination relationship based on binary classifiers for evolutionary multiobjective optimization. In: Proceedings of IEEE Congress on Evolutionary Computation, 2021. 2427–2434
Hao H, Zhou A. A relation surrogate model for expensive multiobjective continuous and combinatorial optimization. In: Proceedings of the 12th International Conference on Evolutionary Multi-Criterion Optimization, 2023. 205–217
Yuan Y, Banzhaf W. Expensive multiobjective evolutionary optimization assisted by dominance prediction. IEEE Trans Evol Computat, 2022, 26: 159–173
Tian Y, Hu J, He C, et al. A pairwise comparison based surrogate-assisted evolutionary algorithm for expensive multi-objective optimization. Swarm Evolary Comput, 2023, 80: 101323
Zhang J, He L, Ishibuchi H. Dual-fuzzy-classifier-based evolutionary algorithm for expensive multiobjective optimization. IEEE Trans Evol Comput, 2023, 27: 1575–1589
Zhou A, Zhang J, Sun J, et al. Fuzzy-classification assisted solution preselection in evolutionary optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence, 2019. 2403–2410
Li G, Wang Z, Gong M. Expensive optimization via surrogate-assisted and model-free evolutionary optimization. IEEE Trans Syst Man Cybern Syst, 2023, 53: 2758–2769
Frazier P I. A tutorial on Bayesian optimization. 2018. arXiv:1807.02811
Srinivas N, Krause A, Kakade S M, et al. Gaussian process optimization in the bandit setting: no regret and experimental design. 2009. ArXiv:0912.3995
Jones D R, Schonlau M, Welch W J. Efficient global optimization of expensive black-box functions. J Glob Opt, 1998, 13: 455–492
Mockus J. The application of Bayesian methods for seeking the extremum. In: Towards Global Optimization. Amsterdam: North-Holand, 1998
Hao H, Wang S, Li B, et al. A surrogate model assisted estimation of distribution algorithm with mutil-acquisition functions for expensive optimization. In: Proceedings of IEEE Congress on Evolutionary Computation, 2022. 1–8
Hoffman M, Brochu E, de Freitas N. Portfolio allocation for Bayesian optimization. In: Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, Barcelona, 2011. 327–336
Li F, Cai X, Gao L, et al. A surrogate-assisted multiswarm optimization algorithm for high-dimensional computationally expensive problems. IEEE Trans Cybern, 2021, 51: 1390–1402
Wei F F, Chen W N, Yang Q, et al. A classifier-assisted level-based learning swarm optimizer for expensive optimization. IEEE Trans Evol Comput, 2021, 25: 219–233
Lian Y, Liou M S. Multiobjective optimization using coupled response surface model and evolutionary algorithm. AIAA J, 2005, 43: 1316–1325
Zhou A, Zhang J, Sun J, et al. Fuzzy-classification assisted solution preselection in evolutionary optimization. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019. 2403–2410
Zhang Q F, Li H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput, 2007, 11: 712–731
Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge: MIT Press, 1992
Storn R, Price K. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. J Glob Opt, 1997, 11: 341–359
Zhou A, Sun J, Zhang Q. An estimation of distribution algorithm with cheap and expensive local search methods. IEEE Trans Evol Comput, 2015, 19: 807–822
Hollander M, Wolfe D A, Chicken E. Nonparametric Statistical Methods. Hoboken: John Wiley & Sons, 2013
Mckay M D, Beckman R J, Conover W J. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 2000, 42: 55–61
Chen T, Guestrin C. XGBoost: a scalable tree boosting system. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016. 785–794
Yao X, Liu Y, Lin G M. Evolutionary programming made faster. IEEE Trans Evol Comput, 1999, 3: 82–102
Hansen N, Ostermeier A. Completely derandomized self-adaptation in evolution strategies. Evolary Comput, 2001, 9: 159–195
Tian Y, Cheng R, Zhang X, et al. PlatEMO: a MATLAB platform for evolutionary multi-objective optimization [educational forum]. IEEE Comput Intell Mag, 2017, 12: 73–87
Friedman M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J Am Stat Assoc, 1937, 32: 675–701
Acknowledgements
This work was supported by National Natural Science Foundation of China (Grant No. 62306174), China Postdoctoral Science Foundation (Grant Nos. 2023M74225, 2023TQ0213), and National Supported Postdoctoral Research Program (Grant No. GZC20231588).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hao, H., Zhang, X. & Zhou, A. Enhancing SAEAs with unevaluated solutions: a case study of relation model for expensive optimization. Sci. China Inf. Sci. 67, 120103 (2024). https://doi.org/10.1007/s11432-023-3909-x
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-023-3909-x