Analysis of the $(1+1)$-EA for Finding Approximate Solutions to Vertex Cover Problems
- 22 September 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 13 (5) , 1006-1029
Abstract
Vertex cover is one of the best known NP-hard combinatorial optimization problems. Experimental work has claimed that evolutionary algorithms (EAs) perform fairly well for the problem and can compete with problem-specific ones. A theoretical analysis that explains these empirical results is presented concerning the random local search algorithm and the (1+1)-EA. Since it is not expected that an algorithm can solve the vertex cover problem in polynomial time, a worst case approximation analysis is carried out for the two considered algorithms and comparisons with the best known problem-specific ones are presented. By studying instance classes of the problem, general results are derived. Although arbitrarily bad approximation ratios of the (1+1)-EA can be proved for a bipartite instance class, the same algorithm can quickly find the minimum cover of the graph when a restart strategy is used. Instance classes where multiple runs cannot considerably improve the performance of the (1+1)-EA are considered and the characteristics of the graphs that make the optimization task hard for the algorithm are investigated and highlighted. An instance class is designed to prove that the (1+1)-EA cannot guarantee better solutions than the state-of-the-art algorithm for vertex cover if worst cases are considered. In particular, a lower bound for the worst case approximation ratio, slightly less than two, is proved. Nevertheless, there are subclasses of the vertex cover problem for which the (1+1)-EA is efficient. It is proved that if the vertex degree is at most two, then the algorithm can solve the problem in polynomial time.Keywords
This publication has 24 references indexed in Scilit:
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problemTheoretical Computer Science, 2007
- A Comparative Study of Three Evolutionary Algorithms Incorporating Different Amounts of Domain Knowledge for Node Covering ProblemIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2005
- On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functionsJournal of Discrete Algorithms, 2005
- Time complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matchingJournal of Computer Science and Technology, 2004
- Towards an analytic framework for analysing the computation time of evolutionary algorithmsArtificial Intelligence, 2003
- Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitnessIEEE Transactions on Evolutionary Computation, 2001
- Drift analysis and average time complexity of evolutionary algorithmsArtificial Intelligence, 2001
- On the optimization of unimodal functions with the (1+1) evolutionary algorithm1998
- The time complexity of maximum matching by simulated annealingJournal of the ACM, 1988
- Hitting-time and occupation-time bounds implied by drift analysis with applicationsAdvances in Applied Probability, 1982