An Expensive Many-Objective Optimization Algorithm Based on Efficient Expected Hypervolume Improvement

• Published in: IEEE transactions on evolutionary computation 2023-12, Vol.27 (6), p.1822-1836
• Main Authors: Pang, Yong, Wang, Yitang, Zhang, Shuai, Lai, Xiaonan, Sun, Wei, Song, Xueguan
• Format: Article
• Language: English
• Subjects: Computing costs; Expected hypervolume improvement (EHVI); expensive many-objective optimization; Genetic algorithms; Importance sampling; importance sampling (IS); kriging; Multiple objective analysis; Optimization; Optimization algorithms; Pareto optimization; Prediction algorithms; Predictive models; Sociology; Sorting; Sorting algorithms; Statistics; Uncertainty
• ISSN: 1089-778X; 1941-0026
• DOI: 10.1109/TEVC.2022.3228516

The expected hypervolume improvement (EHVI) is one of the most popular infill criteria for multiobjective optimization problems. Although it has a significant advantage in exploring potential Pareto-optimal solutions, it has rarely been applied in many-objective problems due to its high computational cost. To address this issue, this article proposes an expensive many-objective optimization algorithm based on the framework of nondominated sorting genetic algorithm III (NSGA-III) and assisted by the kriging surrogate models. In the proposed algorithm, the Monte Carlo sampling (MCS) method for EHVI estimation is improved by importance sampling, in which only one sampling process is required during the entire optimization process using a uniform distribution in normalized objective space. Considering the predicted uncertainty from the kriging model, an uncertainty-assisted nondominated sorting approach is proposed to substitute for the conventional approach in NSGA-III. In the proposed method, the predicted uncertainty is incorporated into the objective space as one independent dimension for nondominated sorting, which can enable the exploration of potential points with desirable EHVI values. In addition, the proposed algorithm considers the diversity of the solutions by de-emphasizing the pursuit of the best EHVI. The experimental results on benchmark problems demonstrate that the proposed EHVI calculation method can save computational costs compared with MCS and indicate the superiority of the proposed algorithm over the others.