Evolutionary Algorithms

Evolutionary and Genetic Algorithms: Learning by Evolving a Good Predictor or an Entire Program

"Genetic programming achieves this goal of automatic programming (also sometimes called program synthesis or program induction) by genetically breeding a population of computer programs using the principles of Darwinian natural selection and biologically inspired operations. The operations include reproduction, crossover (sexual recombination), mutation, and architecture-altering operations patterned after gene duplication and gene deletion in nature."
- Genetic Programming, Inc.

"[G]enetic algorithms are based on a biological metaphor: They view learning as a competition among a population of evolving candidate problem solutions. A 'fitness' function evaluates each solution to decide whether it will contribute to the next generation of solutions. Then, through operations analogous to gene transfer in sexual reproduction, the algorithm creates a new population of candidate solutions."
- From Artificial Intelligence, Structures and Strategies for Complex Problem Solving, Fourth Edition, at page 471. Luger, George F. 2002. Harlow, England: Addison-Wesley.

Now consider the following situations:

  • Pat, a high school senior, wants to visit 12 college campuses located in 10 states before deciding which 5 to apply to. Pat's parents ask Pat to plot the most efficient route for this road trip in the family car.
  • Shawn Carlson must program a computer-controlled telescope so that the number of galaxies that can be observed are maximized and movement of the telescope is minimized.
  • Jesse is responsible for mapping the most efficient transmission path for telephone signals among the options available at any given time. How might Jesse accomplish this?

Each of these is a variation of the Traveling Salesperson Problem (TSP) which has become a classic genetic algorithm (GA) benchmark. The optimal solution will be the fittest individual of the final generation, being the product of many cycles of selection, reproduction, and even mutation.

And keep in mind that GA solutions are not necessarily the very best ones. However, they can be quite useful as you'll discover when you explore the resources offered below.

Contents

Vertical Tabs

Podcasts

Classic Articles & Books

Vertical Tabs