This week, in The Nature of Code, we’re talking about genetic algorithms. A genetic algorithm is a search technique that involves a simulated population of candidate “solutions” (represented by virtual chromosomes) that evolve towards an optimal state. The process is a computational model of principles from biological evolution, such as selection, inheritance, crossover, and mutation.
One of the more challenging aspects to developing a genetic algorithm is coming up with a good “fitness function” for your candidate solutions, i.e. how well does this candidate solve the problem? Without a good fitness function, you won’t get anywhere since the function determines the likelihood of reproducing for the next generation. This is Survival of the Fittest in code.
Nevertheless, as per Flake, a better natural selection catch-phrase might be “Survival of the Survivors.” In the biological world, there is no fitness “function.” The longer you survive, the more likely you are to reproduce.
With that in mind, the above example is a simple evolution simulation, where the simple ability to live longer affords creatures (called “bloops”) a greater chance of having a child (the example uses asexual reproduction for simplicity, but could be modified to incorporate two parents). A bloop’s DNA determines its size and speed (the larger it is, the slower it moves.) The bloops wither away and die unless they find food, in which case their strength increases, causing them to they survive longer and hopefully reproduce.
There’s nothing inherently interesting about this example (other than as a demonstration of the technique itself) and it yields a fairly obvious result:
Bloops that are too big can’t move, don’t find food, die, and aren’t very likely to have children. Bloops that are tiny can move around very quickly, but aren’t terribly likely to find food either because of their small size. After about 10 minutes or so of running, the bloops evolve towards a “midpoint” where a reasonably sized, reasonably fast family of bloops take over (see above screenshots for “before” and “after.)
Since color is encoded into the genes, you can follow bloops from generation to generation (though it should be noted that color plays no role whatsoever in a bloop’s ability to survive.)
A very interesting animation…I noticed a few things.
1) The “food” is larger than the smallest bloop.
2) The model seems to assume that bigger bloops don’t consume the smaller bloops,–in other words that they choose their food.
3) It also assumes that food is both immobile and doesn’t have the equivalent of a “come hither” look. In other words, it presumes that things like smell and mobility don’t trigger a desire for proximity.
But, if the purpose of movement is to find food, then the chance of finding food appears here totally disconnected from a “will” to survive or the ability to choose what is food and what isn’t.
Cool, and yes, people DO read your blog!!
:o))
Thanks for the comments. Indeed, the system is not particularly advanced. The bloops only move randomly and happen upon food (and completely ignore / have no awareness of each other.) There is no will or desire to eat and live, it’s simply an arbitrary fact of their lives. A more involved simulation would want to integrate some of the features you suggested.
This is sweet. I like how it isn’t a fitness function per se, but a survival function. I bet there are some bacteria that are almost as simple as this example.
This paper is really interesting if you’re into evolution. It comes out of a project where they have been studying e. coli evolution through 20,000 generations — they’re actually at 30,000 now but haven’t gone through all the data
http://myxo.css.msu.edu/lenski/pdf/2001, EcoAchievementChallenge, Lenski.pdf
Starting on page 10 of the pdf is a fascinating look at how the bacteria evolve in response to predatory viruses and end up forming different kinds of ecosystems. Could make a good simulation
I have never felt comfortable with the surival of the fitess model, it is something that is repeated without thought. The reality is the long you live the chances for reproduction is higher. But factored into this longevity is the ability to surive, which indirectly factors in fitness.
Mark
Irish single parents