|
Authors: | Marco Laumanns, Lothar Thiele, Eckart Zitzler |
Group: | Computer Engineering |
Type: | Techreport |
Title: | Running Time Analysis of Evolutionary Algorithms on Vector-Valued Pseudo-Boolean Functions |
Year: | 2003 |
Month: | May |
Pub-Key: | LTZ2003d |
Keywords: | EMO |
Rep Nbr: | 165 |
Institution: | Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich |
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. |
Resources: | [BibTeX] [Paper as PDF] |