All living things are made up of cells, and each cell contains the same chromosome. Chromosome is composed of a string of DNA, and we can simply represent a biological individual as a chromosome. Each chromosome contains genes, and genes are composed of multiple DNA. Each gene controls the expression of certain personality, such as eye color, single eyelid and double eyelid, etc. In the process of species reproduction, crossover occurs first, and chromosomes from parents undergo division and recombination to form chromosomes of offspring. After that, the offspring have a certain probability of gene mutation, that is, the gene at a certain position on the chromosome has a certain probability of change. After that, the two steps of crossover and mutation are repeated for each generation. For each offspring, we can measure its fitness in some way. The better the fitness, the greater the probability of being selected in the next crossover, and the easier it is for the genes to be passed on to the next generation. In this way, the fitness of future generations will get better and better until it converges to a stable value.
In the optimization problem, there are always many feasible solutions, and we hope to find an optimal solution, which has better fitness (that is, the objective function value is larger or smaller) than other feasible solutions. Every feasible solution is a "biological individual", which can be expressed as a point and fitness in the state space. Each solution is a coded sequence. For example, each solution is a binary sequence. So every chromosome is a binary sequence. Genetic algorithm starts with a set of feasible solutions, called population, and randomly selects chromosomes from the population for hybridization to produce the next generation. This practice is based on the adaptability of the next generation will be better than the previous generation. The process of genetic algorithm is as follows:
The termination condition can be that the maximum number of iterations is reached, or the fitness difference of the optimal chromosomes in successive generations is less than the threshold. The above algorithm description may not be intuitive enough. Let's take an example. Assuming that the solution can be represented by binary code, then each chromosome is a binary sequence. Suppose the sequence length is 16, and each chromosome is a binary sequence of 16:
First, we randomly generate a group. Suppose the population size is 20 and there are 20 binary sequences with the length of 16. Calculate the fitness of each chromosome, and then select two chromosomes for hybridization, as shown in the figure below. The picture below shows the recombination of the sixth row of chromosomes, and the position of the breakage can be randomly selected. Of course, there can be more than one fracture site. The specific crossover mode can be selected according to specific problems to improve the performance of the algorithm.
Then randomly select a gene on the chromosome of the offspring for gene mutation, and randomly select the mutation position. Moreover, gene mutation does not occur in every offspring, but it has a certain probability. For binary coding, the way of gene mutation is inversion:
The above example is about binary coding, such as finding the maximum and minimum values of a unary function in a certain interval. For example, find the minimum value of the function f(x)=x+sin(3x)+cos(3x) in the interval. Suppose we need the minimum point x to keep 4 decimal places, then the solution interval is discretized into 60000 numbers. Because 2 {15}
However, the sorting problem can't be coded by binary, but by permutation coding. For example, there are the following two chromosomes:
Crossover: Randomly select an intersection from which two chromosomes will be disconnected. The front of chromosome A constitutes the front of the offspring 1, and then chromosome B is scanned. If there are genes that are not included in the progeny 1, add them to the progeny 1 in sequence. Similarly, the front part of chromosome B constitutes the front part of progeny 2, and the rear part of progeny 2 is obtained by scanning chromosome A. Note that there are many ways of crossing, and here is just one of them.
( 1 5 3 2 6 | 4 7 9 8)+(8 5 6 7 2 | 3 1 4 9)= >( 1 5 3 2 6 8 7 4 9) + ( 8 5 6 7 2 1 3 4 9)
Mutation: For a chromosome, two gene exchange positions are randomly selected. For example, the third gene and the penultimate gene are interchanged:
( 1 5 3 2 6 8 7 4 9) = >( 1 5 4 2 6 8 7 3 9)
In addition, there are value coding and tree coding. For specific examples, please refer to this link:/tutorials/genetic-algorithms/encoding.php.
In the actual genetic algorithm, a few elites in the previous generation are often retained, that is, the chromosomes with the best fitness in the previous generation are added to the reproduction of future generations, and the chromosomes with the worst fitness are removed. Through this strategy, if an optimal solution is generated in an iteration, the optimal solution can be maintained until the end of the iteration.
Use ga:/jiaxiao/ga _ test to find the Democode of the minimum value of the function.
References:
[1] Introduction to Genetic Algorithms,/tutorials/genetic-algorithms/index.php.
[2] Holland J.H. "Adaptation in Natural and Artificial Systems"