What limits the performance of evolutionary computing techniques?

Question

What limits the current performance of genetic algorithms and neural networks? The principles underlying these techniques, at least the popular science presentation of these principles, suggests that with enough training they could be improved as much as desired. It seems that this is not the case though.

What are the causes for this? Why can't better results be achieved simply with more computing power? Are there fundamental theoretical reasons for this?

I realize this is a very broad question, but I'm sure some of the people here push against these bounds in their work, and I'd like to hear what they have to say.

Answer 1

To bring this to something resembling theoretical computer science: In his PNAS 2008 paper A Mixability Theory of Sex in Evolution, Christos Papadimitriou has theorized that one limit on the power of genetic algorithms is that they do not optimize what you think they should be optimizing (the objective function you're using in the selection part of the algorithm) but rather they optimize "mixability" (a measure of robustness, the ability of genomes to be combined and still have a high objective function value).

So, if the space of solutions that you're trying to optimize has moderately-high plateaus of pretty good but not great solutions that combine well with each other, and a few steep spikes of high quality solutions that do not combine well, you'll be stuck on the plateaus.

Papadimitriou then uses this observation to make inferences about sexual reproduction in nature, but that's getting off-topic again.

Answer 2

I can't speak for neural networks, but the performance of a genetic algorithm is primarily limited by the difficulty of the problem and how long you're willing to run your algorithm.

What frequently happens with standard genetic algorithms is that after a certain amount of time, the solutions tend to converge to a local optimum. Genetic algorithms work by initially creating a set amount of random solutions and then combining and mutating those solutions. The best solutions are kept and the worst are thrown away. The set of solutions is referred to as the population and one iteration of the recombination, mutation, and replacing solutions is called a generation. The user will set a limit of generations to take place before the algorithm ends.

In a standard genetic algorithm, the solutions in the population tend to become very similar to each other after a number of generations (depending on the problem type and how hard the problem is). The more difficult the problem, the sooner the population tends to converge on a single or a very small number of different solutions. There are MANY different proposed solutions for this, none of which are perfect. Researchers have developed new operators for recombination, mutation, replacing solutions, as well as entire new representations for the solutions. I think it is generally accepted that the better you tune your operators and representation to maintain good diversity within the population, your algorithm will be more successful. However, this is a VERY hard problem and there is no single solution.

The most popular conferences in this area are GECCO, WCCI/CEC, and Evo*. They'd have papers on the state of the art in the field for these things.

TL;DR - The population converges to a very small number of solutions and has a hard time breaking away from these.

I'm not sure if I answered your question sufficiently, but I hope this helps!