TY - GEN
T1 - Multi-objective optimization by uncrowded hypervolume gradient ascent
AU - Deist, Timo M.
AU - Maree, Stefanus C.
AU - Alderliesten, Tanja
AU - Bosman, Peter A. N.
PY - 2020
Y1 - 2020
N2 - Evolutionary algorithms (EAs) are the preferred method for solving black-box multi-objective optimization problems, but when gradients of the objective functions are available, it is not straightforward to exploit these efficiently. By contrast, gradient-based optimization is well-established for single-objective optimization. A single-objective reformulation of the multi-objective problem could therefore offer a solution. Of particular interest to this end is the recently introduced uncrowded hypervolume (UHV) indicator, which is Pareto compliant and also takes into account dominated solutions. In this work, we show that the gradient of the UHV can often be computed, which allows for a direct application of gradient ascent algorithms. We compare this new approach with two EAs for UHV optimization as well as with one gradient-based algorithm for optimizing the well-established hypervolume. On several bi-objective benchmarks, we find that gradient-based algorithms outperform the tested EAs by obtaining a better hypervolume with fewer evaluations whenever exact gradients of the multiple objective functions are available and in case of small evaluation budgets. For larger budgets, however, EAs perform similarly or better. We further find that, when finite differences are used to approximate the gradients of the multiple objectives, our new gradient-based algorithm is still competitive with EAs in most considered benchmarks. Implementations are available at https://github.com/scmaree/uncrowded-hypervolume.
AB - Evolutionary algorithms (EAs) are the preferred method for solving black-box multi-objective optimization problems, but when gradients of the objective functions are available, it is not straightforward to exploit these efficiently. By contrast, gradient-based optimization is well-established for single-objective optimization. A single-objective reformulation of the multi-objective problem could therefore offer a solution. Of particular interest to this end is the recently introduced uncrowded hypervolume (UHV) indicator, which is Pareto compliant and also takes into account dominated solutions. In this work, we show that the gradient of the UHV can often be computed, which allows for a direct application of gradient ascent algorithms. We compare this new approach with two EAs for UHV optimization as well as with one gradient-based algorithm for optimizing the well-established hypervolume. On several bi-objective benchmarks, we find that gradient-based algorithms outperform the tested EAs by obtaining a better hypervolume with fewer evaluations whenever exact gradients of the multiple objective functions are available and in case of small evaluation budgets. For larger budgets, however, EAs perform similarly or better. We further find that, when finite differences are used to approximate the gradients of the multiple objectives, our new gradient-based algorithm is still competitive with EAs in most considered benchmarks. Implementations are available at https://github.com/scmaree/uncrowded-hypervolume.
KW - Gradient search
KW - Multi-objective optimization
KW - Uncrowded hypervolume
UR - http://www.scopus.com/inward/record.url?scp=85091187462&partnerID=8YFLogxK
U2 - https://doi.org/10.1007/978-3-030-58115-2_13
DO - https://doi.org/10.1007/978-3-030-58115-2_13
M3 - Conference contribution
SN - 9783030581145
VL - 12270 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 186
EP - 200
BT - Parallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings
A2 - Bäck, Thomas
A2 - Preuss, Mike
A2 - Deutz, André
A2 - Emmerich, Michael
A2 - Wang, Hao
A2 - Doerr, Carola
A2 - Trautmann, Heike
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th International Conference on Parallel Problem Solving from Nature, PPSN 2020
Y2 - 5 September 2020 through 9 September 2020
ER -