<p>To bring this to something resembling theoretical computer science: In his PNAS 2008 paper <a href="http://www.cs.berkeley.edu/~christos/papers/MixabilityTheory-1.pdf">A Mixability Theory of Sex in Evolution</a>, 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).</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-10-18T21:43:56.980Z
off topic, but definitely interesting ;)
Suresh Venkat
CC BY-SA 3.0
2011-10-18T20:53:21.013Z
2011-10-18T20:53:21.013Z
David Eppstein
<p>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.</p>

<p>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. </p>

<p>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. </p>

<p>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.</p>

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

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

CC BY-SA 3.0
2011-10-18T16:24:19.970Z
2011-10-18T16:24:19.970Z
John Mark
<p>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.</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-17T19:31:15.983Z
Try to replace "genetic algorithms" in your question with "brute force search". :)
Jukka Suomela
CC BY-SA 3.0
2011-10-17T20:08:18.393Z
The links in [this question](http://cstheory.stackexchange.com/q/844/30) and its answers might answer some of your questions.
Aaron Sterling
CC BY-SA 3.0
2011-10-18T13:08:49.590Z
I think you should add some background to the question, e.g. what are "the current performance of genetic algorithms and neural networks" that you are referring to? Also check the items in the FAQ about how to write a good question.
Kaveh
<ne.neural-evol><genetic-algorithms><genetic-programming>
What limits the performance of evolutionary computing techniques?
yaron shavit
# What limits the performance of evolutionary computing techniques?

(Asked by: username_0 on 2011-10-17)

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.

**Tags:** ne.neural-evol, genetic-algorithms, genetic-programming
> **Comments:**
> **username_1**: Try to replace "genetic algorithms" in your question with "brute force search". :)  
> **username_2**: The links in [this question](http://cstheory.stackexchange.com/q/844/30) and its answers might answer some of your questions.  
> **username_3**: I think you should add some background to the question, e.g. what are "the current performance of genetic algorithms and neural networks" that you are referring to? Also check the items in the FAQ about how to write a good question.  

---

## 2 answers

### Answer by username_4 on 2011-10-18. Score: 14

To bring this to something resembling theoretical computer science: In his PNAS 2008 paper [A Mixability Theory of Sex in Evolution](http://www.cs.berkeley.edu/~christos/papers/MixabilityTheory-1.pdf), 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.

> **Comments:**
> **username_5**: off topic, but definitely interesting ;)  

---

### Answer by username_6 on 2011-10-18. Score: 7

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!


---

