hide
Free keywords:
-
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.
