1) Paper Title Towards fast approximations for the hypervolume indicator for multi-objective optimization problems by Genetic Programming 2) Authors Cristian Sandoval Reyes Calz del Tecnológico 12950, Tomas Aquino, 22414 Tijuana, B.C., Mexico sr_cristian@outlook.es +52 1 614 174 8176 Oliver Fernando Cuate Gonzalez D.R. Instituto Politécnico Nacional (IPN). Av. Luis Enrique Erro S/N, Unidad Profesional Adolfo López Mateos, Zacatenco, Alcaldía Gustavo A. Madero, C.P. 07738, Ciudad de México ocuateg@ipn.mx +52 5524343238 Luis C González Gurrola Universidad Autónoma de Chihuahua C. Escorza 900, Col. Centro 31000 Chihuahua, Chih. México lcgonzalez@uach.mx +52 1 614 285 7762 Leonardo Trujillo Reyes Calz del Tecnológico 12950, Tomas Aquino, 22414 Tijuana, B.C., Mexico leonardo.trujillo@tectijuana.edu.mx +52 664 3389391 Oliver Av. Instituto Politécnico Nacional 2508, Col. San Pedro Zacatenco, Delegación Gustavo A. Madero, Ciudad de México, Código Postal 07360. Apartado Postal: 14-740, 07000 Ciudad de México schuetze@cs.cinvestav.mx +52 1 55 5461 3434 3) Corresponding Author: Leonardo Trujillo 4) Abstract 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. 5) Satisfied Criteria (b), (D), (E), (F), (G) 6) Criteria Satisfaction (B) Our solution outperforms all other human made methods to estimate the hypervolume (HV) indicator, one of the most well-known mathematical tools used to analyze and solve multi-objective problems. For instance, the best algorithm for computing it has a complexity of O(N^(k/3)polylog(N)) while our approximation only requires O(kN log N), with k the number of objectives and N the number of individuals. This translates to speedups as high as 1000X for standard runs. (D) Since we use Genetic Programming, we have produced syntactic models that are not at all complex or difficult to understand, the fact that they were produced by an evolutionary approach is not relevant from the perspective of multi-objective optimization. (E) Making the HV computation more efficient has been a core topic in multi-objective optimization, especially since it can be used to transform a multi-objective problem into a single objective task. However, given the high computational cost its practical use can be limited. We have produced the most efficient method to approximate, with high accuracy, the HV indicator. (F) The methods against which we can directly compare our method are all highly-cited and well-known, the focus of much research and discussion within the GECCO community. (G) Theoretically, computing the HV in an efficient manner seems unlikely, with exponential complexity for the best exact method. Practical methods require Monte Carlo approximations, but for accurate results these approaches are not particularly fast for more than three objectives. Our proposal is the most efficient method to approximate the HV, with orders of magnitude improvement in experimental testing. 7) Full Citation Cristian Sandoval, Oliver Cuate, Luis C. González, Leonardo Trujillo, Oliver Schütze, Towards fast approximations for the hypervolume indicator for multi-objective optimization problems by Genetic Programming, Applied Soft Computing, 2022, 109103, ISSN 1568-4946. 8) Prize Money Equally among all authors 9) Best Our results show that an evolved model does not only "compete" with a human design, it completely outperforms it, and by a wide margin. Our method allows for speed-ups in hypervolume computation that range from 10X to 1000X depending on the particular use case, allowing for efficient analysis and solution of multi-objective problems without requiring increased computing power or resources. Moreover, our work comes full circle, where one evolutionary method (genetic programming) is used to enhance a whole family of other evolutionary techniques (multi-objective evolutionary algorithms), in a sense opening up the possibility for our method to one day be used to generate the first meta-"human-competitive" result. 10) Type of EA Genetic Programming 11) Date of publication August 2022