Level-Based Theorems for Runtime Analysis of Multi-objective Evolutionary Algorithms

Runtime analysis of multi-objective evolutionary algorithms (MOEAs) is a rapidly emerging field in which recent breakthroughs studied state-of-the-art MOEAs like NSGA-II and NSGA-III. These analyses typically bound the expected time to cover the Pareto front by analysing (1) the expected time to find a first Pareto-optimal search point and (2) the expected time to cover the whole Pareto front from there. We support this development by providing a powerful general tool for bounding the expected time to reach a first Pareto-optimal search point. It is based on the well-known fitness-level method, a simple and versatile yet powerful analysis method, adapted to multiple objectives. The benefits are to simplify runtime analyses by removing repetitive arguments used across many runtime analyses, thus allowing for shorter and simpler proofs, and to make runtime analysis of MOEAs more accessible to other researchers. Our level-based theorems further provide additional results on stochastic domination and tail bounds in addition to bounds on expected hitting times. We identify sufficient conditions for NSGA-II and NSGA-III to reach the Pareto front, which may pave the way for runtime analyses of state-of-the-art MOEAs approximating the Pareto front with population sizes smaller than the Pareto front.