Faster Evolutionary Algorithms by Superior Graph Representation
Carola Doerr, Christian Klein, Tobias Storch · 2007
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 runtime of Theta(m2log(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(m3or 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