| 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. |
