Adjacency list matchings: An ideal genotype for cycle covers

We propose and analyze a novel genotype to represent walk and cycle covers in graphs, namely matchings in the adjacency lists. This representation admits the natural mutation operator of adding a random match and possibly also matching the former partners. To demonstrate the strength of this set-up, we use it to build a simple (1+1) evolutionary algorithm for the problem of finding an Eulerian cycle in a graph. We analyze several natural variants that stem from different ways to randomly choose the new match. Among other insight, we exhibit a (1+1) evolutionary algorithm that computes an Euler tour in a graph with $m$ edges in expected optimization time (m log m). This significantly improves the previous best evolutionary solution having expected optimization time (m² log m) in the worst-case, but also compares nicely with the runtime of an optimal classical algorithm which is of order (m). A simple coupon collector argument indicates that our optimization time is asymptotically optimal for any randomized search heuristic.