Edge-based representation beats vertex-based representation in shortest path problems
Authors:
Open Access
- 7 July 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 759-766
Abstract
In this paper, we present a new representation for individuals in the single-source shortest path problem. Contrary to previous approaches, it has the natural property that different vertex degrees do not induce unfairness in the mutation step. In particular, at any time each edge has roughly the same probability of being added to or removed from the current individual. This turns out to be a crucial property. Mainly based on this, we prove superior bounds for the optimization time two evolutionary algorithms for the single-source shortest path problem. For both the multi-criteria formulation of the problem (introduced by Scharnow, Tinnefeld and Wegener (2002, 2004)) and the single-criteria one (regarded in Baswana et al. (2009)), we improve the existing bounds by a factor of n2/m, where m denotes the number of edges and n the number of vertices of the underlying graph. Given that most graphs found in practical applications are sparse, this is a considerable gain.Keywords
This publication has 12 references indexed in Scilit:
- Drift analysis and linear functions revisited2010
- Crossover can provably be useful in evolutionary computation2008
- A memetic algorithm and a tabu search for the multi-compartment vehicle routing problemComputers & Operations Research, 2008
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problemTheoretical Computer Science, 2007
- Fast Routing in Road Networks with Transit NodesScience, 2007
- Evolutionary algorithms for route selection and rate allocation in multirate multicast networksApplied Intelligence, 2007
- Computing Many-to-Many Shortest Paths Using Highway Hierarchies2007
- Engineering Highway Hierarchies2006
- The Analysis of Evolutionary Algorithms on Sorting and Shortest Paths ProblemsJournal of Mathematical Modelling and Algorithms, 2004
- A note on two problems in connexion with graphsNumerische Mathematik, 1959