|
The Ultimate Problemsolver: Computer + Evolution = Genius
Lee Graham has been fascinated with both biology and computers ever since he was a young boy. These two interests have come together into an innovative new trend called evolutionary computing. Lee is playing his role with his ”Virtual Creatures” evolution simulator.
Lee grew up in a house with a huge forest in the backyard and he loved to catch and study animals such as frogs and snakes. When not out learning about nature, he could often be found on a computer such as the one his father bought him when he was 7 years old. “I had to choose between biology and computer science” recalls Lee from his high school days. “I went with computers because I thought that would lead to better opportunities”. What he didn’t realize was just how useful his background in biology would prove to be.
As Lee was nearing the end of his undergraduate computer science degree at Carleton University he noticed a course in evolutionary computing. Evolution, a theory first published by Charles Darwin in his “On the Origin of Species” proposes that species can evolve over the course of generations by means of random mutation and natural selection. Evolutionary computing uses these concepts to enhance the capabilities of computer programs.
The course propelled Lee into an academic career exploring the power of evolution as a computer algorithm, which is a procedure for solving problems. For his PHD thesis he developed a computer program called “Virtual Creatures”, a system that uses evolutionary processes to transform simple blocks, or cuboids, into complex creatures. You set what qualities will be considered beneficial in the potential creature, also known as the fitness function, and evolution does the rest of the work. The results are often far from predictable. “Lots of times I use the same fitness function and there is a new creature every time” says Lee. “That is my favorite part.”
Evolutionary algorithms are used to solve the problem of optimization. Holger Hoos, a computer science professor at UBC, explains that an optimization problem is one where there are many possible solutions and the goal is to find the best one. Dr. Hoos notes that these types of problems are ubiquitous. “There are tons of optimization problems out there. They occur in all sciences and in industry as well”.
The classic example is called the travelling salesman. Here a salesman has to visit a number of cities and there is a cost associated with traveling from any one city to another. The goal is to figure out the cheapest way for the salesman to visit each city and return to where he started.
Evolutionary algorithms are one of the hot tools being used to solve problems like this. “An evolutionary algorithm is one that mimics certain principles from biological evolution,” explains Dr. Hoos. To solve an optimization problem with an evolutionary algorithm you need to start with a set of possible solutions. By applying evolutionary operators to these solutions, better solutions can emerge.
This takes place through processes of mutation, recombination and selection. Mutation means making random small changes to some of the solutions. Recombination involves combining parts from two “parent” solutions to create a new “child” solution. This is similar to what happens in humans when sperm cells and egg cells are combined. Selection is the process of keeping the best, or most “fit”, solutions and throwing out the weak ones. Just like with biological evolution, if you apply these three operators repeatedly the results can be surprisingly impressive.
Lee’s program uses an evolutionary algorithm such as this to create his virtual creatures. “The most fun for the user is that you can tune the fitness measure,” says Lee. “This means that you can say what it is about creatures that you will like”. Some of Lee’s fitness measures include how fast the creature can run, how high it can jump, whether it will evolve on flat or rugged terrain and its average height above the ground.
Once the fitness measure has been set, the process of evolution can be started. “The program will keep going, generation after generation” says Lee. “It often takes days and weeks of computing time for one creature to evolve to completion”. Since his program takes so long to run, Lee decided to put it on his website and ask people to donate CPU time to run his experiments.
Shane Killian, a web designer from North Carolina, is one of over 70 people that volunteered to test Lee’s program. “It sounded cool and I thought I’d give it a shot,” says Shane. He still recalls the first creature his computer evolved. “It was a kind of a one-eared bunny. It hopped, and had this head, and had one long ear sticking out of it”. Even Lee was surprised when he saw the result. “He was actually afraid for a bit that the bunny was cheating because of how well it worked” recalls Shane.
Shane sees Lee’s program a great educational tool. “You get a really good sense of how powerful evolution is. You start out with these sorry random creatures who can hardly do anything except fall over, and 500 generations later you have this amazing thing that looks like someone designed it,” says Shane.
Lee appreciates his program’s educational value, but he created it to test new theories of how evolutionary algorithms can be improved. One such theory he has been working on is called exaptation. This is where a trait evolves because it serves one function and subsequently evolves to serve another. The example he gives is how birds evolved from dinosaurs. “Their forelimbs were exapted to become wings,” explains Lee. While their initial function was for walking, they later evolved to aid in flight.
While Lee explores evolutionary algorithms for academic purposes, Dr. Hoos is currently consulting for a Vancouver company called Actenum that specializes in tackling environmentally-related optimization problems. He believes that solving optimization problems will be key in answering the challenges of our time. “At the heart of many conflicts in the world there is competition for resources. Since these resources are quite limited, we need to find efficient ways to utilize them”. He refers to fossil fuels specifically. “One key to making progress in global warming is to use fossil fuels more efficiently. This is an optimization problem”.
With the role of optimization problems increasing so rapidly, so will the need for evolutionary algorithms. There are already many success stories, including the design of a NASA antenna in 2006. Using an evolutionary algorithm, the US space agency produced the ST5 X-band antenna that according to Lee “looked kind of funky” but worked amazingly well. “It consumed less power, took less man hours to produce and outperformed its conventionally designed counterpart,” says Lee.
In September 2008, evolution will take another leap, this time into pop culture. The evolution-based video game Spore was announced in 2005 by Electronic Arts and has since become one of the most anticipated game releases in recent memory. It was voted as best in show at the E3 video games trade show in both 2005 and 2006. “The only reason it didn’t win 2007 was because people were tired of it winning” says avid gamer Jonathan Abrams. “It’s also been heavily covered by gaming magazines and blogs.”
Abrams is looking forward to becoming a virtual evolutionary biologist when Spore is finally released. “The scope of Spore is much bigger than any game I have ever seen” says Abrams. “In most games, you control characters that have been designed for you, to do tasks that have been designed for you. Spore will allow the player to evolve creatures and share them with other players over the internet. I don’t think even the developers can predict what kind of strange creatures will be developed once the game is released.”
Whether it is being used to generate virtual creatures, build antennas, solve global warming or entertain gamers, evolution is a concept that has evolved beyond the scope of biology alone. Lee believes that the field of evolutionary computing is still in its infancy and its potential is limitless. “In the future as computing power increases we’ll be able to do some interesting robot evolution” predicts Lee. “We’ll be able to simply propose a problem that you want the robot to solve and let the robot evolve to figure out how to solve it.”
For now, Lee is happy that programs such as his are able increase the public awareness of evolution and biology. “I would like to steer the software in the direction of something that’s easy and enjoyable for the average Joe to use,” comments Lee. “Hopefully people will get some experience with evolutionary computing, and through that gain an understanding of evolution itself, which is seriously lacking nowadays.”
