Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Conference paper
Title: Computing single source shortest paths using single-objective fitness functions
Author: Baswana, S.
Biswas, S.
Doerr, B.
Friedrich, T.
Kurur, P.
Neumann, F.
Citation: Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms (FOGA' 09), 2009: pp.59-66
Publisher: ACM Press
Publisher Place: New York
Issue Date: 2009
ISBN: 9781605584140
Conference Name: ACM SIGEVO Workshop on Foundations of Genetic Algorithms (10th : 2009 : Orlando, Florida)
Editor: Garibay, I.I.
Jansen, T.
Wiegand, R.P.
Wu, A.S.
Statement of
Surender Baswana, Somenath Biswas, Benjamin Doerr, Tobias Friedrich, Piyush P. Kurur and Frank Neumann
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 andWegener [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.
Keywords: Theory
Rights: Copyright 2009 ACM
DOI: 10.1145/1527125.1527134
Published version:
Appears in Collections:Aurora harvest 5
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.