An analysis of evolutionary algorithms for finding approximation solutions to hard optimisation problems

In practice, evolutionary algorithms are often used to find good feasible solutions to complex optimisation problems in a reasonable running time, rather than the optimal solutions. In theory, an important question we should answer is that: how good approximation solutions can evolutionary algorithms produce in a polynomial time? This paper makes an initial discussion on this question and connects evolutionary algorithms with approximation algorithms together. It is shown that evolutionary algorithms can't find good approximation solution to two families of hard problems. © 2003 IEEE.