Expected runtimes of evolutionary algorithms for the Eulerian cycle problem

摘要: Evolutionary algorithms are randomized search heuristics, which applied to problems whose structure is not well understood, as in combinatorial optimization. They have successfully been different kinds of arc routing problems. To start the analysis evolutionary with respect expected optimization time on these problems, we consider Eulerian cycle problem. We show that a variant well-known (1+1) EA working important encoding permutations able find an tour graph polynomial time. Altering operator used for mutation considered algorithms, changes from exponential.