Running Time Analysis of Multiobjective Evolutionary Algorithms on 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, fair evolutionary multiobjective optimizer (FEMO) and greedy evolutionary multiobjective optimizer (GEMO). The analysis is carried out on two biobjective model problems, leading ones trailing zeroes (LOTZ) and count ones count zeroes (COCZ), as well as on the scalable m-objective versions mLOTZ and mCOCZ. Results on the running time of the different population-based algorithms and for an alternative approach, a multistart (1+1)-EA based on the /spl epsi/-constraint method, are derived. The comparison reveals that for many problems, the simple algorithm SEMO is as efficient as this (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.