Faster Evolutionary Algorithms by Superior Graph Representation

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