An analysis of evolutionary algorithms for finding approximation solutions to hard optimisation problems
Jun He, Xin Yao · 2004
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.