Name
Abstract | ||
|---|---|---|
Runtime analysis of evolutionary algorithms has become an important part in the theoretical analysis of randomized search heuristics. The first combinatorial problem where rigorous runtime results have been achieved is the well-known single source shortest path (SSSP) problem. Scharnow, Tinnefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective fitness functions for problems like the SSSP yield more efficient evolutionary algorithms. In this paper, we show that the single objective approach yields an efficient (1+1) EA with runtime bounds very close to those of the multi-objective approach. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1527125.1527134 | FOGA |
Keywords | Field | DocType |
computing single source shortest,rigorous runtime result,related single-objective fitness function,multi-objective fitness function,single objective approach yield,multi-objective approach,evolutionary algorithm,runtime analysis,combinatorial problem,efficient evolutionary algorithm,sssp yield,polynomial time,random search,fitness function,shortest path | Mathematical optimization,Evolutionary algorithm,Shortest path problem,Computer science,Fitness function,Heuristics,Artificial intelligence,Single objective,Time complexity,Machine learning,K shortest path routing | Conference |
Citations | PageRank | References |
20 | 0.90 | 15 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Surender Baswana | 1 | 452 | 28.20 |
| Somenath Biswas | 2 | 111 | 11.34 |
| Benjamin Doerr | 3 | 1504 | 127.25 |
| Tobias Friedrich | 4 | 74 | 3.24 |
| Piyush P. Kurur | 5 | 88 | 9.41 |
| Frank Neumann | 6 | 1727 | 124.28 |