Title | ||
---|---|---|
Running Time Analysis of Multi-objective Evolutionary Algorithms on a Simple Discrete Optimization Problem |
Abstract | ||
---|---|---|
For the first time, a running time analysis of population-based multi-objective evolutionary algorithms for a discrete optimization problem is given. To this end, we define a simple pseudo-Boolean bi-objective problem (LOTZ: leading ones - trailing zeroes) and investigate time required to find the entire set of Pareto-optimal solutions. It is shown that different multi-objective generalizations of a (1+1) evolutionary algorithm (EA) as well as a simple population-based evolutionary multi-objective optimizer (SEMO) need on average at least 驴(n3) steps to optimize this function. We propose the fair evolutionary multi-objective optimizer (FEMO) and prove that this algorithm performs a black box optimization in 驴(n2 log n) function evaluations where n is the number of binary decision variables. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/3-540-45712-7_5 | PPSN |
Keywords | DocType | ISBN |
time analysis,population-based multi-objective evolutionary algorithm,function evaluation,simple population-based evolutionary multi-objective,simple discrete optimization problem,black box optimization,fair evolutionary multi-objective optimizer,evolutionary algorithm,different multi-objective generalization,multi-objective evolutionary algorithms,n2 log n,discrete optimization problem,multi objective optimization,discrete optimization,timing analysis | Conference | 3-540-44139-5 |
Citations | PageRank | References |
45 | 9.41 | 9 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marco Laumanns | 1 | 1452 | 108.63 |
Lothar Thiele | 2 | 14025 | 957.82 |
Eckart Zitzler | 3 | 4678 | 291.01 |
E. Welzl | 4 | 3311 | 552.52 |
Kalyanmoy Deb | 5 | 21058 | 1398.01 |