Analysis of population-based evolutionary algorithms for the vertex cover problem

Pietro S. OLIVETO, Jun HE, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

47 Citations (Scopus)


Recently it has been proved that the (1+1)-+EA produces poor worst-case approximations for the vertex cover problem. In this paper the result is extended to the (1+λ)-EA by proving that, given a polynomial time, the algorithm can only find poor covers for an instance class of bipartite graphs. Although the generalisation of the result to the (μ+1)-EA is more difficult, hints are given in this paper to show that this algorithm may get stuck on the local optimum of bipartite graphs as well because of premature convergence. However a simple diversity maintenance mechanism can be introduced into the EA for optimising the bipartite instance class effectively. It is proved that the diversity mechanism combined with one point crossover can change the runtime for some instance classes from exponential to polynomial in the number of nodes of the graph. © 2008 IEEE.
Original languageEnglish
Title of host publication2008 IEEE Congress on Evolutionary Computation, CEC 2008
Number of pages8
Publication statusPublished - Jun 2008
Externally publishedYes


Dive into the research topics of 'Analysis of population-based evolutionary algorithms for the vertex cover problem'. Together they form a unique fingerprint.

Cite this