What is Genetic Algorithm? An example of a simple and easy to understand genetic algorithm

Genetic algorithm is a kind of randomized search method that draws on the evolutionary laws of the biological world (survival of the fittest, survival of the fittest, genetic mechanism).

Genetic algorithms (GA) were created by Professor John Holland of Michigan University in the United States in the late 60s of the 20th century. It is based on Darwin's theory of evolution and Mendel's and Morgan's theories of genetics, and constructs artificial systems by simulating the mechanisms of biological evolution. As a global optimization method, genetic algorithm provides a general framework for solving complex system optimization problems, which does not depend on the specific domain of the problem, has low requirements for optimization functions and is highly robust to different kinds of problems, so it is widely used in computer science, engineering technology and social sciences.

Professor John Holland designed the original genetic algorithm, which we call the Standard Genetic Algorithm, by mimicking the process of biological evolution.

The standard genetic algorithm process is as follows:

1) Initialization of the population of the genetic algorithm, including the generation of the initial population and the coding of the individual.

2) Calculate the fitness of each individual in the population, and the fitness of the individual reflects its strength and inferiority.

3) Select some individuals through the selection operation, which are the mother individuals, which are used to reproduce offspring.

4) The selected maternal individuals are paired in pairs, and the offspring are crossed according to a certain crossing probability to produce offspring individuals.

5) According to a certain probability of mutation, the resulting offspring individuals are mutated.

6) The offspring individuals who have completed the crossover and mutation operations will replace some individuals in the population to achieve the purpose of renewing the population.

7) Calculate the fitness of the population again to find the current optimal individual.

8) Judge whether the termination condition is satisfied, if it is not satisfied, return to step 3) to continue iteration, and if it is satisfied, it will exit the iteration process, and the current optimal individual obtained in step 7) will be used as the approximate optimal solution of the algorithm through decoding.

You can also refer to the encyclopedia's introduction to genetic algorithms.

This should be done by drawing a genetic ** and combining probability.

Examples of genetic algorithms are as follows:

Solve the maximum value of the function f(x) x 10 sin(5 x) 7 cos(4 x) in the interval 0,9.

For solving the function maximum problem, binary encoding is generally chosen:

Real number coding: directly using real numbers to represent genes, which is easy to understand and does not require a decoding process, but is easy to converge prematurely, thus falling into local optimum;

Binary encoding: high stability and large population diversity, but requires large storage space, needs to be decoded and is difficult to understand.

Take the objective function f(x) x 10sin(5x) 7cos(4x), x 0,9 as an example.

Setting the accuracy of the solution to 4 decimal places, the solution space of x can be divided into (9 0) (1e 4) 90000 equal parts.

2 16 90000 2 17, 17 binary numbers are required to represent these solutions. In other words, the encoding of a solution is a 17-bit binary string.

These binary strings are randomly generated. One such binary string represents a string of chromosomes, and here the length of the string of chromosomes is 17. For any such chromosome, restore (decode) it to the interval 0,9.

The following formula can be used to decode:

x 0 decimal(chromosome) (9 0) (2 17 1)decimal( ) converts binary numbers to decimal numbers. ）

General decoding formula:

f（x）， x lower bound， upper bound x lower bound decimal（chromosome） （upper bound lower bound） （2 chromosome size 1）f（x）， x lower bound， upper bound x lower bound decimal（chromosome） （upper bound lower bound) (2 chromosome size 1) lower bound: the lower bound of the domain defined by the function.

upper bound: the upper limit of the domain defined by the function.

chromosome size: The length of the chromosome.

With the above formula, we can successfully decode the binary chromosome string into a decimal real number solution in the 0,9 interval.

Genetic algorithms. In essence, it is a series of operations on chromosome patterns, that is, the good patterns in the current population are inherited to the next population through the selection operator, the pattern recombination is carried out by the cross operator, and the pattern mutation is carried out by the mutation operator.

Steps. Basic framework.

1.Encode. Since genetic algorithms cannot directly deal with the parameters of the problem space, the problem to be solved must be represented as a chromosome or individual in the genetic space through encoding.

This conversion is called encoding, which can also be called a representation.

There are three common criteria used to evaluate coding strategies:

a) Completeness.

completeness): All points in the problem space (candidate solutions) can be represented as points (chromosomes) in the GA space.

b) Soundness: Chromosomes in the GA space correspond to all candidate solutions in the problem space.

c) Nonredundancy: chromosomes and candidate solutions correspond one-to-one.

2.Fitness function.

Evolutionism. Adaptability is the ability of an individual to adapt to the environment, and also indicates the ability of the individual to reproduce offspring. The fitness function of genetic algorithm, also known as the evaluation function, is an index used to judge the superiority and inferiority of individuals in a group, and it is evaluated according to the objective function of the problem sought.

Genetic algorithms generally do not need other external information in the process of searching for evolution, and only use evaluation functions to evaluate the advantages and disadvantages of individuals or solutions, and use them as the basis for future genetic operations. Since in the genetic algorithm, the fitness function is to be compared and sorted and the selection probability is calculated on this basis, so the value of the fitness function should be positive. It can be seen that in many cases, it is necessary to map the objective function to a fitness function in the form of a maximal value and a non-negative function value.

The design of the fitness function mainly satisfies the following conditions:

a) Single-value, continuous, non-negative, maximized.

b) Reasonableness and consistency.

c) Small amount of calculation.

d) Strong versatility.

In specific applications, the design of the fitness function should be combined with the requirements of the problem itself. The fitness function design has a direct impact on the performance of genetic algorithms.

3.Initial population selection.

Individuals in the initial population in genetic algorithms are randomly generated. Generally speaking, the following strategies can be adopted for the initial group setting:

a) According to the inherent knowledge of the problem, try to grasp the distribution range of the space occupied by the optimal solution in the whole problem space, and then set the initial population within this distribution range.

b) A certain number of individuals are randomly generated, and then the best individuals are selected and added to the initial group of jujube sensitives. This process is iterative until the number of individuals in the initial population reaches a predetermined size.