TY - GEN
T1 - Computing single source shortest paths using single-objective fitness functions
AU - Baswana, Surender
AU - Biswas, Somenath
AU - Doerr, Benjamin
AU - Friedrich, Tobias
AU - Kurur, Piyush P.
AU - Neumann, Frank
PY - 2009/9/21
Y1 - 2009/9/21
N2 - 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, Tin-nefeld 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.
AB - 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, Tin-nefeld 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.
KW - Algorithms
KW - Performance
KW - Theory
UR - https://www.scopus.com/pages/publications/70349105398
U2 - 10.1145/1527125.1527134
DO - 10.1145/1527125.1527134
M3 - Conference contribution
AN - SCOPUS:70349105398
SN - 9781605584140
T3 - Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
SP - 59
EP - 65
BT - Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
T2 - 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09
Y2 - 9 January 2009 through 11 January 2009
ER -