Faster Evolutionary Algorithms by Superior Graph Representation

Doerr, Benjamin; Klein, Christian; Storch, Tobias

doi:10.1109/FOCI.2007.372176

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Faster Evolutionary Algorithms by Superior Graph Representation

MPS-Authors

/persons/resource/persons44338

Doerr, Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44793

Klein, Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Doerr, B., Klein, C., & Storch, T. (2007). Faster Evolutionary Algorithms by Superior Graph Representation. In First IEEE Symposium on Foundations of Computational Intelligence (FOCI-2007) (pp. 245-250). Piscataway, N.J.: IEEE. doi:10.1109/FOCI.2007.372176.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1F36-0

Abstract

We present a new representation for individuals in problems that have cyclic permutations as solutions. To demonstrate its usefulness, we analyze a simple randomized local search and a (1+1) evolutionary algorithm for the Eulerian cycle problem utilizing this representation. Both have an expected run-time of $\Theta(m^2 \log(m))$, where $m$ denotes the number of edges of the input graph. This clearly beats previous solutions, which all have an expected optimization time of $\Theta(m^3)$ or worse (PPSN~'06, CEC~'04). We are optimistic that our representation also allows superior solutions for other cyclic permutation problems. For NP-complete ones like the TSP, however, other means than theoretical run-time analyses are necessary.