Hot off the Press: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces

We start the runtime analysis of multi-objective evolutionary algorithms for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths: changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. We rigorously prove on a recently proposed benchmark that unit mutation can be slow when the initial solutions are far from the Pareto front. When setting the expected change right, exponential-tail mutation yields the best runtime guarantees in our results—however, with a wrong choice of this expectation, the performance guarantees quickly become uninteresting. With power-law mutation, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, power-law mutation outperforms the exponential-tail mutation even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.