A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis
This work addresses a theoretical gap for researchers in evolutionary multi-objective optimization, but it is incremental as it focuses on a specific test case.
The paper tackled the open problem of whether block-coordinate descent can be asymptotically efficient in evolutionary multi-objective optimization by proposing a block-coordinate version of GSEMO and comparing its running time to the standard GSEMO algorithm. The results on a bi-objective test function demonstrated cases where block-coordinate descent is faster.
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.