Running time analysis of evolutionary algorithms on vector-valued pseudo-Boolean functions

Abstract

This paper presents a rigorous running time analysis of evolutionary algorithms on pseudo-Boolean multiobjective optimization problems. We propose and analyze different population-based algorithms, the simple evolutionary multiobjective optimizer SEMO and two improved versions, FEMO and GEMO. The analysis is carried out on two bi-objective model problems, LOTZ (Leading Ones Trailing Zeroes) and COCZ (Count Ones Count Zeroes) as well as on the scalable $m$-objective versions $m$LOTZ and $m$COCZ. Results on the running time of the different population-based algorithms and for an alternative approach, a multistart (1+1)-EA based on the $e$-constraint method, are derived The comparison reveals that for many problems, the simple algorithm SEMO is as efficient as the (1+1)-EA. For some problems, the improved variants FEMO and GEMO are provably better. For the analysis we propose and apply two general tools, an upper bound technique based on a decision space partition and a randomized graph search algorithm, which facilitate the analysis considerably.