TY - GEN
T1 - A Block-Coordinate Descent EMO Algorithm
T2 - 2024 Genetic and Evolutionary Computation Conference, GECCO 2024
AU - Doerr, Benjamin
AU - Knowles, Joshua
AU - Neumann, Aneta
AU - Neumann, Frank
N1 - Publisher Copyright:
© 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
PY - 2024/7/14
Y1 - 2024/7/14
N2 - We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into k blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms.
AB - We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into k blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms.
KW - block coordinate decent
KW - evolutionary multi-objective optimization
KW - runtime analysis
KW - theory
U2 - 10.1145/3638529.3654169
DO - 10.1145/3638529.3654169
M3 - Conference contribution
AN - SCOPUS:85206939528
T3 - GECCO 2024 - Proceedings of the 2024 Genetic and Evolutionary Computation Conference
SP - 493
EP - 501
BT - GECCO 2024 - Proceedings of the 2024 Genetic and Evolutionary Computation Conference
PB - Association for Computing Machinery, Inc
Y2 - 14 July 2024 through 18 July 2024
ER -