Journal
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
Volume 8, Issue 2, Pages 170-182Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TEVC.2004.823470
Keywords
convergence time; evolutionary algorithms; (EAs); multiobjective optimization; running time analysis
Ask authors/readers for more resources
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 epsilon-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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available