Genetic algorithm is an artificial intelligence algorithm that simulates the process of natural selection. It seeks the optimal solution through heuristic random search. It can be seen that genetic algorithm is a perfect fusion of cross disciplines.

A few days ago, I used the genetic algorithm on the mathematical modeling national competition, associating with the neural network, ant colony algorithm contact before, can not help feeling the enlightenment of the biological world to the development of computer science.

If you’ve never worked with genetic algorithms, you’ll be amazed at the wonders of nature by the end of this article.

Biological basis of genetic algorithm

Just now, genetic algorithm is to simulate a process of natural selection. Imagine that in the development of nature, any species is following the process of “natural selection, survival of the fittest”. Those with good genes survive and produce better offspring, while those with bad genes are eliminated.

As one species evolves, so do its competitors (such as foxes and rabbits), a mechanism (coevolution) that drives nature as a whole.

This is the essence of modern evolution, with natural selection at its core:

  1. Population is the basic unit of biological evolution
  2. Mutations and genetic recombination produce the raw materials of evolution
  3. Natural selection determines the direction of biological evolution
  4. Isolation leads to the formation of new species
  5. Coevolution and the formation of biodiversity

Genetic algorithm steps

Simple genetic Algorithm (SGA) is a milestone in the development of genetic algorithm. Genetic algorithms for improving and integrating new technologies are based on SGA.

coding

Using binary to simulate chromosome sequence, so as to carry on heredity, variation and so on processing.

Unknown:

decoding

For any binary string, it can be converted to decimal using the decoding formula, which is not derived here.

For example, a five-digit binary code yields 32 chromosomes. If, the corresponding decimal value is 21.

mating

Firstly, a random number was generated as the mating site, and then part of gene sequences were exchanged at the mating site of two individuals to form two sub-individuals.

This is the result of swapping the last four bits to form two daughter chromosomes.

mutation

In order to avoid premature convergence of population after algorithm iteration, genetic algorithm flips gene sequence with small probability (0 becomes 1,1 becomes 0) to simulate gene mutation.

inversion

Inversion is the 180-degree reversal of a normal segment of a chromosome

Assessment of individual fitness

Genetic algorithms determine the chances that individuals in the current population will pass on to the next generation in proportion to their fitness. Individuals with greater fitness are more likely to be passed on to the next generation.

In general, the problem of maximizing the objective function can be directly used as a function to detect individual fitness.

copy

The possibility of inheriting offspring is determined by individual fitness. If an individual has a high fitness, it has a high chance of being selected, it may be selected multiple times, and its genes will spread through the population; Otherwise it will gradually be phased out.

A lot of people on the Internet have written about using genetic algorithms to solve optimization problems, so you can learn a couple of examples.