I suppose you've all heard about Spore by now. Many of you have probably already tried out the Creature Creator, too, since the full game isn't available yet. I haven't download it yet, and will probably just wait until I can get the full deal. There are also many other related projects to play with while we wait.
And if you don't know what's Spore's all about yet, the important piece of info is this: with Spore, you can "EVOLVE Your Creature through Five Stages - It’s survival of the funnest as your choices reverberate through generations and ultimately decide the fate of your civilization."
Sounds pretty cool. But while Will Wright had the insight and ability to turn evolution into a compelling video game, there are many more applications of the concept. Check out this article written by a friend and fellow Carleton U alumni, Elan Dubfrofsky. It's called The Ultimate Problemsolver: Computer + Evolution = Genius, and includes all kinds of interesting uses of evolution.
Take, for instance, the travelling salesman problem. It turns out it's not so easy to automatically figure out how to travel to an arbitrary number of cities, only once each except for a return home, in the shortest possible way. In fact, this problem is classified as NP-hard, and if the number of cities is large enough, only approximate solutions can be computed in any reasonable amount of time. But not to worry - by starting with some random solutions, mutating and recombining them, and finally filtering out the best solutions so far, we can eventually come up with a pretty darned good approximation of the best answer. We just need to give this process enough time. Ah, the beauty of evolution!
Another example that Elan points out is the design of an antenna for NASA, developed in 2006. Many very strange looking devices were suggested through this process of evolution, but once it was all said and done, the winning design really was the most fit for the job, consuming only a small amount of power and being easy to produce.
I've even talked about evolutionary techniques earlier in this post. After reading Elan's article, you might enjoy the discussion about the state of artificial intelligence and the evolution of a virtual checkers player. Be sure to read through the comments as well!
So the next time you are working on an optimization problem, ask yourself if you might be able to evolve a good solution rather than trial-and-error your own. Or just wait for Spore and watch evolution in action while creating some silly looking creatures on the side.
I think we all need to be aware that evolution is not a panacea. While directed evolution can help a lot with (say) protein design and optimization problems, it has real limitations. There is a recent paper ("Evolvability") by Leslie Valiant that, among other things, addresses this.
ReplyDeleteSomething else that I think is interesting is how the flow of ideas from evolutionary biology to engineering is now also going the other way. Many biologists are now applying engineering concepts (like modularity, robustness, and abstraction) to biotechnology. The idea is that biotechnology could scale better if we had some sort of standards for biological parts. Do a search for "synthetic biology" if you are interested.
On your first point... quite true. But it can do more than some people give it credit for (not being aware of it in the context of many comp sci problems), so it's worth talking about it so people consider giving it a try for their problem. I'll have to check out that paper.
ReplyDeleteOn the second point... cool!