Genetic Algorithms provide computers with the solve all manner of problems by following the simple principles of natural evolution, largely by breeding virtual programs, allowing them to compete at solving a problem, then selecting the best to reproduce and create a new generation of possible solutions.

I first came across this concept while reading The Blind Watchmaker by Richard Dawkins, a book I cannot recommend highly enough – while it focuses on the evolution of life, it provides insight on all manner of subjects.  In the book Richard Dawkins introduces Biomorphs, a computer program he wrote that would take a simple genotype (a coded sequence similar to a DNA string) use it as a seed for a development algorithm which would result in a phenotype (in this case images which bore striking resemblances to insects or plants).  A few examples from his book:

Without going into the technical details, genetic algorithms such as have the potential to solve all sorts of problems faster than random searches or even human design.  Some applications include:

  • Acoustics, in the design of amongst other things opera houses and high fidelity speaker cone enclosures  for optimum sound reproduction
  • Engineering, for example car and wind turbine shapes for aerodynamics
  • Astronomy, in the identification of undiscovered star systems
  • Electrical Engineering, in all manner of chip design optimisations
  • Financial Markets, in many cases outperforming traders predicting market changes
  • Playing games such as Chequers, to the level that within a relatively small number of generations can beat any but the most expert players.
  • Military and other logistical planning, both areas where it is used to aid human decisions in summarizing a near infinity of variables.
  • Data mining or search, particularly in areas where the data sets are so vast that patterns simply cannot be put forward or tested by simpler techniques (including skilled humans) with any hope of success.
  • Recognition of patterns and objects in images.
  • Developing agent and team behavior, used in many computer games and real world competitions such as RoboCup.

My interest in the field is as an underpinning to the main subjects of my research, right now focusing on the use of agent intelligence and procedural content generation to create digital content such as environments, worlds, graphics, music and virtual characters and agents.

These require slightly different use of Genetic Algorithms than in the above examples – generally GA’s are able to find a solution to a given problem when this can be expressed formally (such as a mathematical sum) however in general are not optimised for finding a solution that is based upon taste, fashion or other qualities that are difficult to quantify. They do, however, provide a mechanism to help a human designer create and evaluate such content, an area which traditional procedural content generation techniques have been criticized for being unable to do.  An early example of this happening comes courtesy of Karl Sims from a contribution to the SIGGRAPH 5 years after the Blind Watchmaker was published.

This slideshow requires JavaScript.

To get an idea of the state of the art have another look at Avatar, pretty much 90% of what you see on screen was created using GA graphic techniques.