Genetic algorithm
Genetic algorithms are used to find solutions to mathematical problems that have a very large solution space and no known method of directly computing an optimal solution.
Genetic algorithms are based on techniques found in the evolution of biological organism, mainly mutation and selection. The algorithm uses a population of potential solutions and attempts to drive them towards an optimal solution if one exists. Every step of the algorithm involves evaluating the potential solutions for their fitness value, low fitness solutions are removed from the mating pool, and genetic reproduction of the high fitness solutions follow. There are a variety of techniques used in each step - especially the reproduction step, which can model prokaryotic or eukaryotic organisms, asexual or sexual reproduction, single or multiple chromosomes, and a variety of mutation operators.
Mutation is a key component of the algorithm; without it, the population will tend to converge to the closest locally optimized solution it can find, without adequately searching the entire solution space for a global optimum. Too high of a mutation rate, however, can prevent convergence of a solution at all, and effectively turn the algorithm into a random-search function. Genetic algorithms do not work well for problems in which there is only one absolutely correct answer, and instead require gradient solution spaces to allow for convergence.
External resources
- Golem Project - Automatic Design and Manufacture of Robotic Lifeforms
- DGPF - The Distributed Genetic Programming Framework provides a multi-objective Genetic Algorithm library with many distribution abilities: client/server, p2p, hybrid.
- Introduction to Genetic Algorithms Using RPL2
- Talk.Origins FAQ on the uses of genetic algorithms, by Adam Marczyk
- Genetic algorithm in search and optimization, by Richard Baker
- Differential Evolution using Genetic Algorithm
- Genetic algorithms and Markov Chain Monte Carlo: Differential Evolution makes Bayesian computing easy (genetic algorithm for statistical analysis)
- Introduction to Genetic Algorithms and Neural Networks including an example windows program
- MIT OpenCourseWare | Health Sciences and Technology | HST.508 Genomics and Computational Biology, Fall 2002 | Lecture Notes
- A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory
- Evolutionary computing in search-based software engineering. Leo Rela. How evolutionary computing (specifically GA) is used in software engineering.
- Genetic Algorithm Applet A Java Applet that allows you to experiment with genetic algorithms. Source code included.
- Trainable Mechanical Arm Physical simulation of a mechanical arm and a ball. Using genetic algorithms it learns how to perform a given exercise (e.g. throw the ball as far as possible).
- A video showing a 20 generation evolution of a natural walking legs model
- Genetics Studio - Freeware numeric genetic algorithm utility for the novice to advanced user.
- PIKAIA- a free genetic algorithm subroutine developed in Fortran. PIKAIA is also available in an Excel/VBA version and a parallel processing version.
- Introduction and Fortran Code - This document will serve as an introduction to genetic algorithms. There are numerous empirical tests that demonstrate the importance of the GA operators selection,crossover and mutation.