Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem

Diversity optimization is a class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZ \(_k\) , which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in \(O(kn^3)\) expected iterations. We also analyze the runtime of the GSEMO \(_D\) (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMO \(_D\) optimizes it asymptotically faster than it finds a Pareto-optimal population, in \(O(kn^2\log (n))\) expected iterations, and for the second measure we show an upper bound of \(O(k^2n^3\log (n))\) expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theoretical predictions.