Evolutionary Algorithms and the Vertex Cover Problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Colleges, School and Institutes

Abstract

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 a well studied instance class confirms such a conjecture for the considered class. Furthermore, a class for which the (1+1)-EA takes exponential optimization time is examined. Nevertheless, given polynomial time, the evolutionary algorithm still produces a better solution than the approximation algorithm. 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.

Details

Original languageEnglish
Title of host publicationIEEE Congress on Evolutionary Computation, 2007. CEC 2007.
Publication statusPublished - 1 Sep 2007
EventIEEE Congress on Evolutionary Computation, 2007 (CEC 2007) - Singapore, Singapore
Duration: 25 Sep 200728 Sep 2007

Conference

ConferenceIEEE Congress on Evolutionary Computation, 2007 (CEC 2007)
Country/TerritorySingapore
CitySingapore
Period25/09/0728/09/07