Evolutionary computation is a fantastic field in computer science. Apart from allowing you to play God using your computer, it takes inspiration from Darwinian evolution to solve problems in mechanics, physics, logistics, robotics and virtually any field you can think of. Today I’m going to discuss genetic algorithms.
What is evolution?
In the real world, evolution is the process by which organisms change over time in response to selection pressures. For evolution to work on a population there are four requirements:
- There must be variation in the population.
- Selection pressure must act on the population.
- There must be replication (inheritance).
- This replication must not be perfect (mutations can occur).
Selection pressure is a term which refers to the ‘force’ that favours certain characteristics in the population. For example, being well camouflaged might prevent predators from finding you. Being eaten as a baby is a sure-fire way to not have any offspring, so individuals who are better camouflaged have an advantage over others. In this situation, we would say that there is a selection pressure on the species for being well camouflaged.
Variation in a population gives a sub-section of the population an advantage (i.e. some individuals are fitter than others). Selection pressure acts to ensure fitter members of the population are more likely to have offspring. The offspring inherit the characteristics which made their parents good at reproducing and so are likely to go on to have more offspring of their own. With each generation the population becomes fitter and fitter. The replication process, however, must be error prone so that there is a source of variation. This allows new characteristics to be discovered and tested.
Artificial evolution and genetic algorithms
Genetic algorithms take this basic process of evolution and recreate it using a computer program. A number of virtual organisms (called solutions) change through subsequent generations, inheriting characteristics from their “parents”. Like in biological evolution, artificial evolution favours individuals which contain fitter characteristics, allowing them to produce offspring at a higher rate than less fit individuals.
Using computers to do evolution is useful because we can specify the selection pressures which shape the evolving solutions. This is the main difference between biological and artificial evolution. In biological evolution fitness is always determined as the ability to reproduce. In artificial evolution, the computer programmer can decide what constitutes fitness, then let evolution take care of designing things which better meet that criteria. It’s similar to selectively breeding animals to create breeds which contain particular characteristics (see picture below). But instead of a human applying selection pressure by explicitly choosing which individuals are allowed to reproduce in each generation, a computer program automates the process.
This can be used to do some really cool stuff. Not only can we use them to solve difficult problems, but they can be used to come up with innovations which human designers may never think of. Human engineers are constrained by human ways of thinking, their training, and the tools they’re provided with. Evolution has none of these constraints (or more correctly, evolution has different constraints). Karl Sims illustrates a wide range of design innovations by evolving virtual organisms to swim, jump, run and crawl in a virtual 3D environment. The whole research project resembles some sort of Olympic games for virtual creatures (a video is embedded below). A more practical (though less fun) example is work by Smith et al, which uses genetic algorithms to search for new manoeuvres for fighter pilots to use during aerial dogfights.
Genetic algorithms have also been used to evolve virtual (but functional) Lego bridges and evolve walking behaviour in six legged robots. There’s even a web application which allows you to evolve Lego structures using your own specifications (requires Java).
Rather than running a genetic algorithm once to find a solution, they can run continuously, allowing computer systems to adapt to changes in their operating environment as they arise. This can be taken a step further by using them to control specialised computer circuits which can change their configuration. This makes it possible to have adaptable, evolving electronics which respond to their current situation (this field is called evolvable hardware). Skynet, anyone? NASA are involved in research which will hopefully one day lead to self-repairing satellites and unmanned spacecraft which can adapt to unexpected conditions and extreme changes in temperature. While this research is in the early stages, the advantages that your multi-million dollar unmanned spacecraft can repair itself mid-mission are obvious. Besides, if robots are going to evolve sentience it might be better if they do it in the outer edges of the solar system…
Evolutionary algorithms feed back into biology
So, understanding biological processes has helped create new tools and solve problems in all manner of other fields. That is pretty cool. But evolutionary computation also feeds back into biology, helping us better understand biological processes! They’ve been used to help predict the shape and function of proteins, a notoriously difficult task in molecular biology. Their similarity to biological evolution makes them ideal for modelling many phenomena in natural evolution, such as the selection pressures exhorted by the immune system on the malarial parasite during an infection.
I couldn’t find anywhere to put this, but I thought it was too entertaining to leave out. It’s a video of a simulated humanoid learning to jump, using a genetic algorithm. I am constantly amazed by the number of things people have done with genetic algorithms.
References and interesting videos:
- A video of robots learning to walk using a genetic algorithm and neural network to control their leg behaviour.
- A video showing digital fighters evolving to find and shoot each other.
- Google Tech talk about Polyworld, a tool allowing you to evolve virtual ecosystems.
- Sims, K. (1994). Evolving 3D morphology and behavior by competition. Artificial life, 1(4), 353-372. Video: https://www.youtube.com/watch?v=JBgG_VSP7f8
- Smith, R. E., Dike, B. A., Mehra, R. K., Ravichandran, B., & El-Fallah, A. (2000). Classifier systems in combat: two-sided learning of maneuvers for advanced fighter aircraft. Computer Methods in Applied Mechanics and Engineering, 186(2), 421-437. Subscription required.
- Gallagher, J. C., Beer, R. D., Espenschied, K. S., & Quinn, R. D. (1996). Application of evolved locomotion controllers to a hexapod robot. Robotics and Autonomous Systems, 19(1), 95-103. Subscription required.
- Funes, P. J., & Pollack, J. B. (1999). Computer evolution of buildable objects for Evolutionary Design by Computer. You can also evolve your own Lego structures with this web app.
- Unger, R., & Moult, J. (1993). Genetic algorithms for protein folding simulations. Journal of molecular biology, 231(1), 75-81. Subscription required.
- Buckee, C. O., & Recker, M. (2012). Evolution of the Multi-Domain Structures of Virulence Genes in the Human Malaria Parasite, Plasmodium falciparum. PLoS computational biology, 8(4), e1002451. Open access!
- Stoica, A., Fukunaga, A., Hayworth, K., & Salazar-Lazaro, C. (1998). Evolvable hardware for space applications (pp. 166-173). Springer Berlin Heidelberg.