Title :
Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions
Author :
Laumanns, Marco ; Thiele, Lothar ; Zitzler, Eckart
Author_Institution :
Comput. Eng. & Networks Lab., Swiss Fed. Inst. of Technol., Switzerland
fDate :
4/1/2004 12:00:00 AM
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 ε-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.
Keywords :
Boolean functions; evolutionary computation; graph theory; search problems; count ones count zeroes; decision space partition; fair evolutionary multiobjective optimizer; greedy evolutionary multiobjective optimizer; leading ones trailing zeroes; multiobjective evolutionary algorithm; pseudoBoolean functions; randomized graph search algorithm; running time analysis; simple evolutionary multiobjective optimizer; Algorithm design and analysis; Computer networks; Electronic mail; Evolutionary computation; H infinity control; Markov processes; Partitioning algorithms; Shortest path problem; Stochastic processes; Upper bound;
Journal_Title :
Evolutionary Computation, IEEE Transactions on
DOI :
10.1109/TEVC.2004.823470