Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
This work provides a rigorous runtime analysis for diversity optimization in multi-objective evolutionary algorithms, which is incremental as it focuses on a specific benchmark and algorithm step.
The paper tackles the problem of evolutionary diversity optimization for Pareto-optimal solutions on the bi-objective OneMinMax benchmark, proving that the GSEMO algorithm with a diversity heuristic finds an optimally diverse population in expected O(n^2) time when the problem size n is odd.
The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time $O(n^2)$, when the problem size $n$ is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.