6
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Try to replace "genetic algorithms" in your question with "brute force search". :) $\endgroup$ – Jukka Suomela Oct 17 '11 at 19:31
  • 2
    $\begingroup$ The links in this question and its answers might answer some of your questions. $\endgroup$ – Aaron Sterling Oct 17 '11 at 20:08
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 18 '11 at 13:08
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ off topic, but definitely interesting ;) $\endgroup$ – Suresh Venkat Oct 18 '11 at 21:43
7
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.