DocumentCode :
958825
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
Volume :
8
Issue :
2
fYear :
2004
fDate :
4/1/2004 12:00:00 AM
Firstpage :
170
Lastpage :
182
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;
fLanguage :
English
Journal_Title :
Evolutionary Computation, IEEE Transactions on
Publisher :
ieee
ISSN :
1089-778X
Type :
jour
DOI :
10.1109/TEVC.2004.823470
Filename :
1288055
Link To Document :
بازگشت