Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem

This paper analyzes the runtime of evolutionary diversity optimization (EDO) algorithms on a multi-objective benchmark function called LOTZ_k. The authors prove runtime bounds for the GSEMO and GSEMO_D algorithms to find Pareto-optimal solutions and optimize diversity measures.

Details

This paper provides a theoretical runtime analysis of evolutionary diversity optimization (EDO) algorithms on a multi-objective benchmark function called LOTZ_k. LOTZ_k is a modification of the well-known (LeadingOnes, TrailingZeros) problem. The authors analyze the runtime of the GSEMO algorithm, which is a general evolutionary multi-objective optimizer, to compute the set of all Pareto-optimal solutions. They prove that GSEMO finds this set in O(kn^3) expected iterations, where k is the number of objectives and n is the problem size. The authors also analyze a variant called GSEMO_D, which is designed for diversity optimization. They show that GSEMO_D can optimize the total imbalance diversity measure in O(kn^2log(n)) expected iterations, and the imbalances vector diversity measure in O(k^2n^3log(n)) expected iterations. The theoretical results are complemented by an empirical study, which suggests the bounds for total imbalance are tight, while the bounds for the imbalances vector are too pessimistic.