TY - JOUR
T1 - Towards fast approximations for the hypervolume indicator for multi-objective optimization problems by Genetic Programming
AU - Sandoval, Cristian
AU - Cuate, Oliver
AU - González, Luis C.
AU - Trujillo, Leonardo
AU - Schütze, Oliver
N1 - Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2022/8
Y1 - 2022/8
N2 - Hypervolume (HV) has become one of the most popular indicators to assess the quality of Pareto front approximations. However, the best algorithm for computing these values has a computational complexity of O(Nk/3polylog(N)) for N candidate solutions and k objectives. In this study, we propose a regression-based approach to learn new mathematical expressions to approximate the HV value and improve at the same time their computational efficiency. In particular, Genetic Programming is used as the modeling technique, because it can produce compact and efficient symbolic models. To evaluate this approach, we exhaustively measure the deviation of the new models against the real HV values using the DTLZ and WFG benchmark suites. We also test the new models using them as a guiding mechanism within the indicator-based algorithm SMS-EMOA. The results are very consistent and promising since the new models report very low errors and a high correlation for problems with 3, 4, and 5 objectives. What is more striking is the execution time achieved by these models, which in a direct comparison against standard HV calculation achieved extremely high speedups of close to 100X for a single front and over 1000X for all the HV contributions in a population, speedups reach over 10X in full runs of SMS-EMOA compared with the standard Monte Carlo approximations of the HV, particularly for large population sizes. Finally, the evolved models generalize across multiple complex problems, using only two problems to train the problems from the DTLZ benchmark and performing efficiently and effectively on all remaining DTLZ and WFG benchmark problems.
AB - Hypervolume (HV) has become one of the most popular indicators to assess the quality of Pareto front approximations. However, the best algorithm for computing these values has a computational complexity of O(Nk/3polylog(N)) for N candidate solutions and k objectives. In this study, we propose a regression-based approach to learn new mathematical expressions to approximate the HV value and improve at the same time their computational efficiency. In particular, Genetic Programming is used as the modeling technique, because it can produce compact and efficient symbolic models. To evaluate this approach, we exhaustively measure the deviation of the new models against the real HV values using the DTLZ and WFG benchmark suites. We also test the new models using them as a guiding mechanism within the indicator-based algorithm SMS-EMOA. The results are very consistent and promising since the new models report very low errors and a high correlation for problems with 3, 4, and 5 objectives. What is more striking is the execution time achieved by these models, which in a direct comparison against standard HV calculation achieved extremely high speedups of close to 100X for a single front and over 1000X for all the HV contributions in a population, speedups reach over 10X in full runs of SMS-EMOA compared with the standard Monte Carlo approximations of the HV, particularly for large population sizes. Finally, the evolved models generalize across multiple complex problems, using only two problems to train the problems from the DTLZ benchmark and performing efficiently and effectively on all remaining DTLZ and WFG benchmark problems.
KW - Automatic algorithm design
KW - Genetic programming
KW - Hypervolume
KW - Multi-objective optimization
KW - Regression
UR - http://www.scopus.com/inward/record.url?scp=85132367303&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2022.109103
DO - 10.1016/j.asoc.2022.109103
M3 - Artículo
AN - SCOPUS:85132367303
SN - 1568-4946
VL - 125
JO - Applied Soft Computing
JF - Applied Soft Computing
M1 - 109103
ER -