TY - GEN
T1 - Ensuring smoothly navigable approximation sets by Bézier curve parameterizations in evolutionary bi-objective optimization
AU - Maree, Stefanus C.
AU - Alderliesten, Tanja
AU - Bosman, Peter A. N.
PY - 2020
Y1 - 2020
N2 - The aim of bi-objective optimization is to obtain an approximation set of (near) Pareto optimal solutions. A decision maker then navigates this set to select a final desired solution, often using a visualization of the approximation front. The front provides a navigational ordering of solutions to traverse, but this ordering does not necessarily map to a smooth trajectory through decision space. This forces the decision maker to inspect the decision variables of each solution individually, potentially making navigation of the approximation set unintuitive. In this work, we aim to improve approximation set navigability by enforcing a form of smoothness or continuity between solutions in terms of their decision variables. Imposing smoothness as a restriction upon common domination-based multi-objective evolutionary algorithms is not straightforward. Therefore, we use the recently introduced uncrowded hypervolume (UHV) to reformulate the multi-objective optimization problem as a single-objective problem in which parameterized approximation sets are directly optimized. We study here the case of parameterizing approximation sets as smooth Bézier curves in decision space. We approach the resulting single-objective problem with the gene-pool optimal mixing evolutionary algorithm (GOMEA), and we call the resulting algorithm BezEA. We analyze the behavior of BezEA and compare it to optimization of the UHV with GOMEA as well as the domination-based multi-objective GOMEA. We show that high-quality approximation sets can be obtained with BezEA, sometimes even outperforming the domination- and UHV-based algorithms, while smoothness of the navigation trajectory through decision space is guaranteed.
AB - The aim of bi-objective optimization is to obtain an approximation set of (near) Pareto optimal solutions. A decision maker then navigates this set to select a final desired solution, often using a visualization of the approximation front. The front provides a navigational ordering of solutions to traverse, but this ordering does not necessarily map to a smooth trajectory through decision space. This forces the decision maker to inspect the decision variables of each solution individually, potentially making navigation of the approximation set unintuitive. In this work, we aim to improve approximation set navigability by enforcing a form of smoothness or continuity between solutions in terms of their decision variables. Imposing smoothness as a restriction upon common domination-based multi-objective evolutionary algorithms is not straightforward. Therefore, we use the recently introduced uncrowded hypervolume (UHV) to reformulate the multi-objective optimization problem as a single-objective problem in which parameterized approximation sets are directly optimized. We study here the case of parameterizing approximation sets as smooth Bézier curves in decision space. We approach the resulting single-objective problem with the gene-pool optimal mixing evolutionary algorithm (GOMEA), and we call the resulting algorithm BezEA. We analyze the behavior of BezEA and compare it to optimization of the UHV with GOMEA as well as the domination-based multi-objective GOMEA. We show that high-quality approximation sets can be obtained with BezEA, sometimes even outperforming the domination- and UHV-based algorithms, while smoothness of the navigation trajectory through decision space is guaranteed.
KW - Approximation set navigation
KW - Bézier curve estimation
KW - Evolutionary algorithm
KW - Hypervolume
KW - Multi-objective optimization
UR - http://www.scopus.com/inward/record.url?scp=85091174702&partnerID=8YFLogxK
U2 - https://doi.org/10.1007/978-3-030-58115-2_15
DO - https://doi.org/10.1007/978-3-030-58115-2_15
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 - 215
EP - 228
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 -