Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)


Evolutionary Algorithms and the Vertex Cover Problem

by Pietro S. Oliveto, Jun He, Xin Yao

Experimental results have suggested that evolutionary algorithms may produce higher quality solutions for instances of Vertex Cover than a very well known approximation algorithm for this NP-Complete problem. A theoretical analysis of the expected runtime of the (1+1)-EA on two well studied instance classes confirms such a conjecture for the considered classes. Furthermore, a class for which the (1+1)-EA takes exponential optimization time is examined and the characteristics that make the problem hard for the evolutionary algorithm are highlightes. Nevertheless, given polynomial time, the evolutionary algorithm still produces a better solution. Recently, the existence of an instance class has been proved for which the (1+1)-EA produces poor approximate solutions, given polynomial time. Here it is pointed out that, by using multiple runs, the (1+1)-EA finds the optimal cover of each instance of the considered graph class in polynomial time.

Back to mainpage