Running time analysis of a multi-objective evolutionary algorithm on a simple discrete optimization problem

For the first time, a running time analysis of a multi-objective evolutionary algorithm for a discrete optimization problem is given. To this end, a simple pseudo-Boolean problem (Lotz: leading ones - trailing zeroes) is defined and a population-based optimization algorithm (FEMO). We show, that the algorithm performs a black box optimization in Θ(n2 log n) function evaluations where n is the number of binary decision variables