research-article

Edge-based representation beats vertex-based representation in shortest path problems

Authors:

Benjamin Doerr,

Daniel JohannsenAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 759 - 766

https://doi.org/10.1145/1830483.1830618

Published: 07 July 2010 Publication History

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 n²/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.

References

[1]

H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566, 2007.

[2]

S. Baswana, S. Biswas, B. Doerr, T. Friedrich, P. P. Kurur, and F. Neumann. Computing single-source shortest paths using single-objective fitness. In FOGA '09, pages 59--66. ACM, 2009.

Digital Library

[3]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269--271, 1959.

Digital Library

[4]

B. Doerr and L. A. Goldberg. Private communication.

[5]

B. Doerr, E. Happ, and C. Klein. A tight bound for the (1+1)-EA on the single-source shortest path problem. In CEC '07, pages 1890--1895. IEEE, 2007.

[6]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In GECCO '08, pages 539--546. ACM, 2008.

Digital Library

[7]

B. Doerr, D. Johannsen, and C. Winzen. Drift analysis and linear functions revisited. In CEC '10. IEEE, 2010. To appear.

[8]

B. Doerr and M. Theile. Improved analysis methods for crossover-based algorithms. In GECCO '09, pages 247--254. ACM, 2009.

Digital Library

[9]

M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, 2004.

Digital Library

[10]

A. El-Fallahi, C. Prins, and R. W. Calvo. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & OR, 35(5):1725--1741, 2008.

Digital Library

[11]

S. J. Kim and M. K. Choi. Evolutionary algorithms for route selection and rate allocation in multirate multicast networks. Applied Intelligence, 26(3):197--215, 2007.

Digital Library

[12]

S. Knopp, P. Sanders, D. Schultes, F. Schulz, and D. Wagner. Computing many-to-many shortest paths using highway hierarchies. In ALENEX '07, 2007.

[13]

F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In GECCO '04, pages 713--724, 2004.

Digital Library

[14]

P. Sanders and D. Schultes. Engineering highway hierarchies. In ESA '06, pages 804--816, 2006.

Digital Library

[15]

J. Scharnow, K. Tinnefeld, and I. Wegener. Fitness landscapes based on sorting and shortest paths problems. In PPSN '02, volume 2439 of LNCS, pages 54--63. Springer, 2002.

Digital Library

[16]

J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithm, 3(4):349--366, 2004.

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Show More Cited By

Index Terms

Edge-based representation beats vertex-based representation in shortest path problems
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Complexity of some inverse shortest path lengths problems

The input to an inverse shortest path lengths problem (ISPL) consists of a graph G with arc weights, and a collection of source-sink pairs with prescribed distances that do not necessarily conform to the shortest path lengths in G. The goal is to modify ...
On the difficulty of some shortest path problems

We prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph G with non-negative edge weights, ...
Shortest vertex-disjoint two-face paths in planar graphs

Let G be a directed planar graph of complexity n, each arc having a nonnegative length. Let s and t be two distinct faces of G let s₁,…,s_k be vertices incident with s let t₁,…,t_k be vertices incident with t. We give an algorithm to compute k pairwise ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
148
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Doerr BKrawiec K(2021)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461406(369-398)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461406
Doerr BCoello Coello C(2020)A gentle introduction to theory (for non-theoreticians)Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389889(373-403)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389889
Doerr B(2020)The Runtime of the Compact Genetic Algorithm on Jump FunctionsAlgorithmica10.1007/s00453-020-00780-wOnline publication date: 13-Nov-2020
https://doi.org/10.1007/s00453-020-00780-w
Doerr BAuger AStützle T(2019)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323373(523-549)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323373
Shir ODoerr CBäck TTakadama K(2018)Compiling a benchmarking test-suite for combinatorial black-box optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208251(1753-1760)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208251
Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Doerr B(2017)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067713(389-412)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067713
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents