How to Use the Metropolis Algorithm for Multi-Objective Optimization?

As demonstrated by empirical and theoretical work, the Metropolis algorithm can cope with local optima by accepting inferior solutions with suitably small probability. This paper extends this research direction into multi-objective optimization. The original Metropolis algorithm has two components, one-bit mutation and the acceptance strategy, which allows accepting inferior solutions. When adjusting the acceptance strategy to multi-objective optimization in the way that an inferior solution that is accepted replaces its parent, then the Metropolis algorithm is not very efficient on our multi-objective version of the multimodal DLB benchmark called DLTB. With one-bit mutation, this multi-objective Metropolis algorithm cannot optimize the DLTB problem, with standard bit-wise mutation it needs at least Ω(n5) time to cover the full Pareto front. In contrast, we show that many other multi-objective optimizers, namely the GSEMO, SMS-EMOA, and NSGA-II, only need time O(n4). When keeping the parent when an inferior point is accepted, the multi-objective Metropolis algorithm both with one-bit or standard bit-wise mutation solves the DLTB problem efficiently, with one-bit mutation experimentally leading to better results than several other algorithms. Overall, our work suggests that the general mechanism of the Metropolis algorithm can be interesting in multi-objective optimization, but that the implementation details can have a huge impact on the performance. This paper for the Hot-off-the-Press track at GECCO 2024 summarizes the work Weijie Zheng, Mingfeng Li, Renzhong Deng, and Benjamin Doerr: How to Use the Metropolis Algorithm for Multi-Objective Optimization? In Conference on Artificial Intelligence, AAAI 2024, AAAI Press, 20883--20891. https://doi.org/10.1609/aaai.v38i18.30078 [22].