The Azimuth Project
Genetic algorithm

Contents

Idea

The article in Wikipedia states:

A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.

One way of understanding why genetic algorithms/programming are useful is that many practical situations involve a complicated structure

that maps to some value such as a numerical score. Many ways of doing effectively involve understanding the mapping from the score to the structure (even in its just as simple as looking at Jacobian matrices). However for typical complicated structures analyzing this dependence is very complicated and possibly intractable. The advantage of genetic algorithms/programming is that one only needs to be able to compute the mapping from an example of the structure to the score. This advantage is accompanied by a consequent lack of efficiency compared to methods that do take advantage of the structure of the mapping from score to structure.

Details

Method

In a genetic algorithm, a population of strings (called chromosomes or the genotype of the genome), which encode candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem, evolves toward better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population.

The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.

Genetic algorithms find application in bioinformatics, phylogenetics, computational science, engineering, economics, chemistry, manufacturing, mathematics, physics and other fields.

References

Genetic Algorithm

Genetic programming

  • R Poli, W.B. Langdon, McPhee A Field Guide to Genetic Programming, available under CC by NC ND. The authors are very known and active in this subarea of research.

Applications

Abstract: A technique to forecast spatiotemporal time series is presented. It uses a Proper Orthogonal or Karhunen–Loève transform to encode large spatiotemporal data sets in a few time-series, and Genetic

Algorithms to efficiently extract dynamical rules from the data. The method works very well for confined systems displaying spatiotemporal chaos, as exemplified here by forecasting the evolution of the onedimensional complex Ginzburg-Landau equation in a finite domain.