Genetic Algorithms

Author

Mattheos Protopapas1

Keywords

Heuristics, Genetic, Algorithm, optimization, chromosome, crossover, mutation, population.

Review Status

Unreviewed


Body

A genetic algorithm [1], is a heuristic algorithm, inspired by evolutionary processes of ecological systems, that finds optimal (or near-optimal) solutions to complex optimization problems. In a genetic algorithm, the potential solutions of the problem at hand are coded in chromosomes. a chromosome is a string of binary digits or other symbols, that corresponds to a given solution of the problem (e.g. if our goal is to find the x that minimizes a function f(x) in a given interval [a,b], chromosomes correspond to real numbers that belong in the interval [a,b]). The usual genetic algorithm (also called "canonical" genetic algorithm [2]) use sets of these chromosomes, called "populations" that evolve through "generations" (usually, the initial population is chosen at random), by the operators of "crossover" and "mutation", in order to discover the chromosome-solution that corresponds to the optimal solution to the problem.

A "fitness function" measures the eligibility of a chromosome to become a "parent" for the chromosomes of the next generation. The fitness function is linked to the value of the objective function (the value of the f(x) in the previous example) by either a mathematical transformation that ensures that the fitness of the chromosomes is an increasing function of their performance in the problem in hand (i.e. in our minimization example, lower values of f(x), should imply higher values for the fitness of x), or simply by ordering the chromosomes of the current population in terms of their performance ("ordered fitness" - if we had a population of 50 chromosomes in the minimization example, the chromosome that corresponds to the x that leads to the lower value of f(x) should have fitness equal to 50, the chromosome with the second lower f(x), fitness equal to 49, and so on).

The usual rule for selecting parents is the "roulette wheel selection" [2], meaning that the probability of a chromosome to be selected as a parent is proportional to its fitness. So for a total of half the number of chromosomes in the populations, two parents are selected, using sampling with replacement, and probability proportional to fitness, that are used to form two children.

The children chromosomes may be formed by operating the "crossover" operator to the two parents, with a given probability (probability of crossover). In the usual form of crossover (single point crossover [1]), the (usually) binary strings of the two parents are cut at a specific point and the two sub-strings are exchanged. So assuming that the first chromosome is "01110001", the second is "11001110" and the cutting point is the fifth binary digit (bit), the first child should have "0111" in the first four bits (from the second parent) and "1110" in the last four bits. So it should be "01111110". The second child is formed by the other two sub-strings: "1100" from the second parent and "0001" taken from the first, and is "11000001". The cutting point may be selected randomly (random point crossover [1]), two or more cutting points may be used (multi-point crossover [1]), or for any given bit, a parent is selected at random and its corresponding bit is assigned to the corresponding bit of the first child, while the other parent's bit is assigned to the corresponding bit of the second child (uniform crossover).

Finally, the "mutation" operator is performed upon the children chromosomes, to create the final chromosomes of the new generation. Each binary digit of the chromosome is subject to inversion (from 1 to 0 and vice versa) under a given (small) probability. That resembles the mutation of animal chromosomes, which can change due to chance only, and allows the introduction of new genetic material into the "gene pool". If all the chromosomes in a population have for example, "0" at their first position-gene, there is no way that a "1" at the first position of any of the children chromosomes, is introduced by the sole use of the crossover operator. So, mutation gives the opportunity for entirely new genes to be introduced in the population and be tested.

Pseudo code for "canonical" genetic algorithm

  1. Set the values of the parameters regarding population size, probability of crossover, probability of mutation, number of generations, and all the other parameters relevant to the application.
  2. Generate random initial population of chromosomes.
  3. Select two of the chromosomes as parents, with probability proportional to their fitness.
  4. If crossover is used (depending on the probability for crossover mentioned above), combine the genes of these chromosomes using the crossover operator to form two children chromosomes. In the case no crossover is applied, the children chromosomes will be initially, just copies of the parent chromosomes.
  5. Then apply the mutation operator to the children chromosomes, so that some (if any) random bits of the children chromosomes are inverted.
  6. Repeat steps 4-6, until children chromosomes have been formed.
  7. Repeat steps 3-7 until the specified number of generations have passed.

Internal Links

Concepts
Tutorials
Tips
Related Articles

External links

References
1. Holland J.H. (1975). Adaption in Natural and Artificial Systems. University of Michigan Press.
2. Goldberg DE (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison - Wesley, Reading MA.
Weblinks

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License