Hot off the Press: The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem

Recently, the first mathematical runtime guarantees have been obtained for the NSGA-II, one of the most prominent multi-objective optimization algorithms, however only for synthetic benchmark problems.In this work, we give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem.More specifically, we show that the NSGA-II with population size ≥ 4(( -1) max + 1) computes all extremal points of the Pareto front in an expected number of ( 2 max log( max )) iterations, where is the number of vertices, the number of edges, and max is the maximum edge weight in the problem instance.This result confirms, via mathematical means, the good performance of the NSGA-II observed empirically.It also paves the way for analyses of the NSGA-II on complex combinatorial optimization problems.As a side result, we also obtain a new analysis of the performance of the GSEMO algorithm on the bi-objective minimum spanning tree problem, which improves the previous best result by a factor of | |, the number of points in the convex hull of the Pareto front, a set that can be as large as max .The main reason for this improvement is our observation that both algorithms find the different extremal points in parallel rather than sequentially, as assumed in the previous proofs.This paper for the Hot-off-the-Press track at