Genetic algorithm

From Esolang
Jump to navigation Jump to search

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