Ask HN: Are there any very long term genetic programming experiments?
Given that biological evolution has taken billions of years to yield intelligent life, shouldn't computer scientists be carrying out very long term genetic programming experiments?
26 comments
I believe the problem is with ever advancing hardware. The new chips are much faster and would "overtake" an experiment that's been running.
This problem is sometimes described as putting colonists on a space ship and sending then off. They travel for generations but before arriving they are overtaken by another ship which started several generations later, but was much faster because technology back on Earth kept advancing.
Then there's the problem with convergence. Even on a scale as large and complicated as Earth creature often reach an adaptive maximum which tends to keep them the same until an external shock. Think sharks, or punctuated equilibrium.
In a computer the simulation will also quickly reach a maximum and there's only so large and complex a simulation can be before you're talking crazy money for the machines. Without crazy money the simulation could hardly be complex enough to keep evolving for ever.
Obviously we have game-of-life like algorithms which can generate new patterns for ever, but they are not under selective pressure.
This problem is sometimes described as putting colonists on a space ship and sending then off. They travel for generations but before arriving they are overtaken by another ship which started several generations later, but was much faster because technology back on Earth kept advancing.
Then there's the problem with convergence. Even on a scale as large and complicated as Earth creature often reach an adaptive maximum which tends to keep them the same until an external shock. Think sharks, or punctuated equilibrium.
In a computer the simulation will also quickly reach a maximum and there's only so large and complex a simulation can be before you're talking crazy money for the machines. Without crazy money the simulation could hardly be complex enough to keep evolving for ever.
Obviously we have game-of-life like algorithms which can generate new patterns for ever, but they are not under selective pressure.
Here's a physics paper that analyzes that question. It's a joke paper, but the conclusion is valid (subject to various simplifying assumptions). Their conclusion is that if a computation takes over 30 months to complete, you're better off waiting for faster hardware.
http://arxiv.org/abs/astro-ph/9912202 The Effects of Moore's Law and Slacking on Large Computations Authors: C Gottbrath, J Bailin, C Meakin, T Thompson, J.J. Charfman
We show that, in the context of Moore's Law, overall productivity can be increased for large enough computations by `slacking' or waiting for some period of time before purchasing a computer and beginning the calculation.
http://arxiv.org/abs/astro-ph/9912202 The Effects of Moore's Law and Slacking on Large Computations Authors: C Gottbrath, J Bailin, C Meakin, T Thompson, J.J. Charfman
We show that, in the context of Moore's Law, overall productivity can be increased for large enough computations by `slacking' or waiting for some period of time before purchasing a computer and beginning the calculation.
> I believe the problem is with ever advancing hardware. The new chips are much faster and would "overtake" an experiment that's been running.
There's no reason why this would have to be a problem. It should be possibly at any given iteration to take a snapshot of the population and transfer it over to new hardware. One could even consider experiments in which you periodically scaled the population up to utilize an order of magnitude more computing power (to increase diversity in a population that had converged to some local optimum) and then scaled it back down to some randomly selected subset once sufficient divergence had occurred.
Since computing resources can be purchased in small discrete units these days, this might even be a viable method to reduce overall search cost.
There's no reason why this would have to be a problem. It should be possibly at any given iteration to take a snapshot of the population and transfer it over to new hardware. One could even consider experiments in which you periodically scaled the population up to utilize an order of magnitude more computing power (to increase diversity in a population that had converged to some local optimum) and then scaled it back down to some randomly selected subset once sufficient divergence had occurred.
Since computing resources can be purchased in small discrete units these days, this might even be a viable method to reduce overall search cost.
Why? We do long-term experiments in biology because genetic evolution is slow - whereas with genetic programming we can speed it up limited only by the computing technology.
Let's say biological evolution has been going for 4.5 Billion years, at an average of one mutation per second for all that time. A quick search says that a modern Core 2 Extreme can process about 50,000 MIPS. Let's say that each mutation takes 100 instructions on average (including set-up and tear-down, etc.), and that we have 5,000 MIPS available for this calculation process - then it would be possible to do all that calculation in about 9 seconds of CPU time.
Bottom line - even if my back-of-the-envelope calculation about is two or three orders of magnitude off - is that you don't need you run a long-term experiment to give genetic algorithms the same amount of run-time as nature had with us, you just need a few bucks of AWS credit.
Let's say biological evolution has been going for 4.5 Billion years, at an average of one mutation per second for all that time. A quick search says that a modern Core 2 Extreme can process about 50,000 MIPS. Let's say that each mutation takes 100 instructions on average (including set-up and tear-down, etc.), and that we have 5,000 MIPS available for this calculation process - then it would be possible to do all that calculation in about 9 seconds of CPU time.
Bottom line - even if my back-of-the-envelope calculation about is two or three orders of magnitude off - is that you don't need you run a long-term experiment to give genetic algorithms the same amount of run-time as nature had with us, you just need a few bucks of AWS credit.
>Bottom line - even if my back-of-the-envelope calculation about is two or three orders of magnitude off - is that you don't need you run a long-term experiment to give genetic algorithms the same amount of run-time as nature had with us, you just need a few bucks of AWS credit
Depends on the simulation, anything approaching an accurate simulation C A N N O T currently be simulated with the technology we have. Take for example the evolution of the brain. A human brain consists of 100 billion nerve cells. A supercomputer simulating an organ this complicated -- using current technology -- would take up the space of several soccer fields and draw $3 billion worth of electricity every year. http://www.spiegel.de/fotostrecke/fotostrecke-19430.html Similar orders of magnitude are applicable to the genome of a fruitfly or an amoeba. There is no satisfactory simulation of a cell ....
Depends on the simulation, anything approaching an accurate simulation C A N N O T currently be simulated with the technology we have. Take for example the evolution of the brain. A human brain consists of 100 billion nerve cells. A supercomputer simulating an organ this complicated -- using current technology -- would take up the space of several soccer fields and draw $3 billion worth of electricity every year. http://www.spiegel.de/fotostrecke/fotostrecke-19430.html Similar orders of magnitude are applicable to the genome of a fruitfly or an amoeba. There is no satisfactory simulation of a cell ....
True - but I don't think that's what the author is talking about.
You can't simulate biological world-scale evolution right now. As you say, it's just too complex and operating at too large a scale. We somewhat know how, but the technology to actually do it isn't there yet.
Genetic programming, on the other hand, we can do. It's generally used as part of an optimization process, and is simple enough that we can simulate it quite well. To give those processes the amount of run-time that resulted in us (which is what I interpreted the author as talking about) would be trivial, as I showed. To create a virtual world, start it up with some amino acids and a jolt of lightning, and end up with us is way beyond our capability right now - and probably wouldn't end up with "us" anyways, owing to the randomness in there.
You can't simulate biological world-scale evolution right now. As you say, it's just too complex and operating at too large a scale. We somewhat know how, but the technology to actually do it isn't there yet.
Genetic programming, on the other hand, we can do. It's generally used as part of an optimization process, and is simple enough that we can simulate it quite well. To give those processes the amount of run-time that resulted in us (which is what I interpreted the author as talking about) would be trivial, as I showed. To create a virtual world, start it up with some amino acids and a jolt of lightning, and end up with us is way beyond our capability right now - and probably wouldn't end up with "us" anyways, owing to the randomness in there.
You correct about the usefulness of GP in CS, I am not so sure of its usefulness in Biology (since we define the fitness factors rather than nature and an uncontrolled environment). My favorite application from the Hummies Awards, self-correcting programs http://www.genetic-programming.org/hc2009/1-Forrest/Forrest-...
Furthermore, biological evolution experiments with immense population sizes in parallel. At the low extreme, there are about 10 to the 10th humans in the current generation. At the high extreme, there are (very approximately) 10 to the 20th algae in the current generation. So you'll need somewhere north of 10 to the 10th of those soccer field sized mainframes.
I think you are missing a critical point. Computer simulations can have iterations that are several magnitudes faster than anything you would likely see with bio evolution.
"Computer simulations can have iterations that are several magnitudes faster than anything you would likely see with bio evolution."
I think you are missing a critical point. Bio evolution operates with a level of detail unlike anything you would likely see with computer simulations.
It may still take a long time to run enough simulations to get comparable effects.
I think you are missing a critical point. Bio evolution operates with a level of detail unlike anything you would likely see with computer simulations.
It may still take a long time to run enough simulations to get comparable effects.
Well, even if we can get the necessary level of detail, that doesn't mean our experiments need to take as long. As soon a generation is "created" the program starts on the next one. None of that annoying waiting around for the kids to grow up, reach puberty, etc...
Assuming, of course, we have a powerful enough machine to do things quick enough.
Assuming, of course, we have a powerful enough machine to do things quick enough.
Sometimes, you just need a lifetime to evaluate fitness, you know?
You're in one.
This may be fanciful, but I think this is a likely outcome of the spam/malware vs. filters arms race. At some point this kind of code may become sufficiently self-modifying to evolve on its own, with interesting results. A kind of virtual cockroach.
I feel you overestimate both the anti virus industry, and the malware industry. It's rare for a piece of malware to do anything that the average, mediocre programmer couldn't write in a weekend.
A similar question and its responses - http://stackoverflow.com/questions/396938/computer-simulatio...
I was wondering just the same thing after those evolving block creatures that were posted yesterday, "what would happen if you let that stew for a couple of years?"
You'd most likely converge onto some optimal creature and just stop at that point since the fitness function is fixed.
Intelligent behavior seems more likely to evolve if you provided a complex, usefully manipulable environment that could vary significantly and unpredictably during the lifetime of the individual.
I'm not sure I see a purpose. Even if you aren't looking to product "intelligence" but just something interesting, I don't think its likely. The ratio size and complexity of the environment (fitness function, domain of the chromosomes, degree of mutation, etc...) compared to the size of each creature (i.e. how many possible chromosome possibilities there are) would have to be enormous to make a long experiment worthwhile.
Tom Ray of Tierra fame started a project like that: http://life.ou.edu/pubs/reserves/node1.html
I remember downloading the source code sometime years ago; but if they ever published any results, I haven't seen it.
I remember downloading the source code sometime years ago; but if they ever published any results, I haven't seen it.
I feel obliged to point out a friend of mine's really great short story: http://www.teamten.com/lawrence/writings/coding-machines/
I'm not sure how feasible this would be or what you are technically thinking about. The whole thing with genetic programming is to have the population converge onto some optimal solution but in real biology this optimum is constantly moving around.
The whole thing with genetic programming is to have the population converge onto some optimal solution... I think what you are referring to is "Genetic Algorithms".