Biology teacher: Math teacher, please go away, I will solve this problem!

Nature is an inexhaustible source of inspiration for human innovation. Creatures in nature have extraordinary adaptability and wisdom: how do ants find the shortest path to food sources, how do geese fly the shortest distance when foraging, how do organisms evolve various traits... By making reasonable use of these laws, can we solve...mathematical problems?

(Photo source: veer photo gallery)

That’s right, and it deals with problems that are difficult to solve with traditional mathematical theory.

Optimization Problems and Heuristic Algorithms

First, let's look at a math problem:

Calculate the maximum value of the following quadratic function

For this simple objective function, we can directly apply the formula: when the independent variable x=-b/2a, the maximum value of the objective function is (4ac-b^2)/4a (if you forget, please contact your high school math teacher). This kind of solution that can be directly expressed as a formula is called an analytical solution .

For simple questions, you can get the answer in one step

This problem of finding the maximum/minimum value of a function is an optimization problem, and this function is called the objective function . The optimization algorithm is the algorithm that calculates the maximum value of the objective function.

In practice, the objective function of the optimization problem is often complex and cannot be solved analytically. Therefore, gradients (derivatives of multivariate functions) are often used for iterative solutions.

However, for some more complex objective functions, gradient methods cannot be used. For example, to calculate the minimum value of the following function

Complex objective function, formula cannot be applied

If conventional gradient methods are used, they tend to converge to the local optimum (Local Optimum) , that is, the maximum point within a certain range, rather than the global optimum (Global Optimum) , that is, the maximum point within the global range.

Gradient methods are prone to falling into local optimality

Optimizing similar complex functions has always been a difficult problem. Inspired by certain natural laws, scientists simulated natural algorithms and proposed several heuristic algorithms to deal with optimization problems that are difficult to solve using traditional mathematical theories.

For example, by simulating the laws of ant colonies in finding and transporting food, the Ant Colony Algorithm was proposed; by simulating the laws of geese foraging in the air, the Particle Swarm Optimization Algorithm was proposed; by simulating the laws of biological inheritance and evolution, the Genetic Algorithm was proposed...

What do algorithmic scientists think about biological genetics and evolution?

The heuristic algorithm introduced in this article is proposed by simulating the laws of biological inheritance and evolution. So, what is inheritance and evolution in the eyes of algorithm scientists? Here we take the evolution of giraffes as an example (note that genetic algorithms only imitate known evolutionary laws and are not necessarily equivalent to biological laws).

There are many different kinds of creatures in nature, and their characteristics are determined by both genes and external factors, but genes play a dominant role, so external factors are ignored here. For example, the length of a giraffe's neck is determined by genes.

Genes are the genetic material of organisms, consisting of multiple nucleotides, similar to "AaBbCc". The evolution of a population inevitably means changes in genes.

Natural selection does not act directly on genes, but on traits. Different traits of individuals have different survival abilities. For example, the longer the deer's neck, the more leaves it can eat, and the stronger its survival ability. The quantification of survival ability is called fitness .

Fitness should be determined by multiple factors, such as the length of the deer's neck, physical strength, vision, etc. However, only the length of the neck is considered here. The longer the neck, the higher the fitness.

(This article assumes that genes determine traits, which in turn determine survival ability)

Once upon a time, there was a group of ordinary deer. Each deer had different genes and therefore different traits (the traits here specifically refer to the length of the neck). This generation of deer was recorded as "Deer Herd 0".

In "deer herd 0", individuals with long necks can eat more leaves and are more likely to survive, so their fitness is high. Individuals with short necks are more likely to be eliminated and have low fitness. This process is called selection , and only the deer that survive the selection can mate.

(Photo source: Wang Moyi, a soul painter)

When a male deer mates with a female deer, it does not simply copy its own genes, but crosses them with the female's genes and then combines them (here we think of genes = chromosomes). For example, "Aa BbCc" + "aa bbcc" = "Aa bbcc" + "aa BbCc".

Of course, when two genes combine, one or more nucleotides of the gene may mutate . For example, a gene B mutates into B.

Genetic crossover

Genetic variation

In this way, "herd 0" produces a new generation, recorded as "herd 1". Generally speaking, the maximum and average values ​​of fitness of "herd 1" after selection will increase, that is, the maximum and average values ​​of neck length will increase.

After generations of reproduction, due to genetic changes, the necks of "deer herd N" will be significantly longer than those of "deer herd 0", and their fitness will be higher. At this point, we can say that the species has evolved.

The population tends to be optimal

Of course, the optimal neck length is also related to the environment, specifically the height of the tree canopy. A neck higher than the tree canopy has no advantages but disadvantages. As long as the environment does not change significantly, after the "deer herd N", the genes of the population will not change significantly, and the fitness will not change significantly, and the population will stabilize at the optimal solution.

How does genetic algorithm work?

John Holland from the United States simulated the natural selection and genetic mechanisms of Darwin's theory of biological evolution and proposed a heuristic optimization algorithm - genetic algorithm .

The algorithm converts independent variables into individuals, matches individuals with genes through encoding, takes the objective function to be solved as the fitness function, retains crossover and mutation, and after multiple iterations, the population (multiple individuals) can approach the optimal solution.

Taking the maximum value of the objective function F(x)=x+8sin(5x)+5cos(4x) as an example, the genetic algorithm will solve the problem in six steps:

1. Initialization

The genetic algorithm regards the possible values ​​of the independent variable as individuals, and generates an initial population after setting the total number of populations. For example, set the population to 100 individuals and randomly select 100 initial values ​​in the interval [0,8].

Randomly generate the initial population within a certain interval of the independent variable

2. Encoding and Decoding

The independent variable individual itself cannot be regarded as a gene, and it needs to be transformed in some way. Usually, the individual is converted into a string of binary numbers, called coding , and this string of binary numbers can be regarded as a gene.

For example, if 4 bits of binary are used to represent the integer part and 2 bits of binary are used to represent the decimal part, then 3.25 can be represented as "001101", and "001101" is the gene of the individual.

The binary representation of the individual's 3.25 is 001101, which is a simulation of the gene.

Encoding is to simulate genes so as to carry out subsequent crossover and mutation. Decoding is to convert genes (binary) into individuals (decimal). Decimal numbers can be substituted into the fitness function to calculate fitness.

3. Fitness calculation

However, after converting the gene (binary) into individuals (decimal), the fitness can be obtained by substituting the decimal individuals into the objective function.

It is not difficult to understand that the fitness function is often the objective function to be solved F(x)=x+8sin(5x)+5cos(4x).

4. Select

Each individual is selected based on its fitness. Those with greater fitness are more likely to be retained, while those with less fitness are more likely to be eliminated. This process is usually carried out using the "roulette wheel" model.

Of course, in the selection process, we have to ensure that the number of individuals remains unchanged. To ensure this, those with high fitness are not only retained, but also copied.

Individuals with greater fitness are more likely to survive

5. Crossover and mutation

The individuals that remain are coded to obtain genes and then crossover is performed. For example, "001 101" + "010 010" = "001 010" + "010 101". Generally speaking, the crossover point is randomly selected.

Here, two genes are crossed to produce two new genes (equivalent to the parents having twins). Therefore, crossover does not change the population size.

After crossover, each gene may also mutate. Generally speaking, the mutation point is also random. For example, a 1 in a certain position becomes 0, or a 0 becomes 1.

Binary number cross

Variation of binary numbers

After selection, the maximum and average values ​​of the population fitness will be improved compared to the previous generation. Specifically, all individuals will be concentrated at the high point of the objective function. After multiple iterations, they will be concentrated at the maximum value.

6. Is it over?

Since it is an optimization algorithm, it is necessary to set an end condition. The algorithm cannot be allowed to loop infinitely (dead loop). The simplest way is to set the number of times the algorithm runs. For example, let the algorithm end after 50 loops.

Here is a general flowchart of the genetic algorithm

As evolution proceeds, that is, the algorithm cycles, the average fitness of the population is bound to increase from generation to generation and eventually converge to a maximum value, which is the maximum point of the objective function we are looking for.

Population distribution after 50 cycles of genetic algorithm: concentrated at one point

As the algorithm iterates, the average fitness of the population is also improving.

There are small strategies at every step

In order to improve the efficiency of the genetic algorithm, there are actually some tricks in the above steps.

1. Initialization

If prior information about the maximum point is available, that is, the approximate range of the maximum point, then the initial population can be generated within this range. If not, it is necessary to generate randomly within a larger range.

The choice of initial value will affect the convergence speed of the algorithm. The closer the initial value is to the optimal solution, the faster the convergence speed. In addition, inappropriate initial value may cause the algorithm to fall into the local optimum.

Can this help us find the optimal solution faster?

2. Encoding and Decoding

In digital signal processing, measurements must have minimum and maximum values, that is, the value of the variable is not continuous and infinite, but discontinuous and finite. The error caused by measurement is called quantization error .

For example, if we use 4 bits of binary to represent the integer part and 2 bits of binary to represent the decimal part, then the maximum value of the independent variable can only be 15.75 (corresponding to 111111 in binary), and the decimal part can only distinguish a difference of 0.25. The minimum value of the measurement is also called the resolution ratio .

The optimal solution of F(x)=x+8sin(5x)+5cos(4x) is at 7.860, but the algorithm can only converge to 7.875

Of course, we can make the length of the gene very long, for example, using 100 bits of binary to represent the integer part and 10 bits of binary to represent the decimal part, so as to expand the range of independent variables and improve the resolution. However, this will increase the amount of calculation and storage of the algorithm.

3. Choose

In the selection process, if the individuals with the highest fitness are retained and replicated, it is called elite reservation ; if the individuals with the highest fitness are not necessarily retained and may still be eliminated, it is called no elite reservation.

Experiments show that the genetic algorithm with elite retention converges to the optimal value faster and is more stable.

4. Crossover and mutation

Crossover can be divided into single-point crossover and multi-point crossover, and mutation can be divided into single-point mutation and multi-point mutation. Crossover and mutation are used to improve gene diversity, accelerate convergence speed, and escape from local optimum.

For example, when all individuals are concentrated near the local optimum, suddenly one individual mutates and "jumps" to the vicinity of the global optimum, then the population can evolve further.

For a population, stability is more important than diversity, so crossover and mutation can often be performed at a single point, and the probability of mutation is often very low.

5. Is it over?

Although it is simple to control the end of the algorithm by setting the number of algorithm runs, there are two problems:

(1) If the algorithm converges slowly, for example, if the population does not converge to an optimal solution after 50 iterations, then the result is necessarily incorrect;

(2) If the algorithm converges quickly, for example, it only takes 20 iterations for the population to converge to an optimal solution, then a lot of computing resources will be wasted.

Another more reliable method is to determine whether the difference in the average fitness of the population between two adjacent operations is less than a certain threshold. If so, the algorithm is considered to have converged and can be terminated; if not, the algorithm is considered to have not converged and the cycle should continue.

Controlling the termination of the algorithm based on the average fitness difference is more reliable

Genetic algorithms can not only draw pictures, but also tell you these

Heuristic algorithms, such as genetic algorithms, do not have extremely strict mathematical derivations, but nature has used these laws to solve countless problems. Now, genetic algorithms have been widely used in many fields of our lives, such as how to design the shape of vehicles to reduce air resistance; how to arrange the workflow of robots to improve work efficiency; how to plan routes to minimize the distance of express delivery...

Previously, someone uploaded a project on GitHub that used genetic algorithms to draw specific pictures . The following is a simulation example to see how the genetic algorithm "draws" the following work based on the photo above:

(Image source: https://github.com/anopara/genetic-drawing)

First, multiple initial color bars are given to form a color bar picture, and the difference between the color bar picture and the original picture is used as the objective function. Then, a genetic algorithm is used to iteratively solve the arrangement of the color bars so that the objective function is minimized, that is, the color bar picture is "most similar" to the original picture, so as to achieve the goal of "drawing" the original picture with multiple color bars.

PS: If you are not a programmer, you don’t need to use genetic algorithms for the time being, but you can still learn some wisdom from genetic algorithms:

●There is no perfect algorithm. To ensure accuracy, you have to increase the amount of calculation. All strategies are the art of finding a balance between multiple factors.

●If we only pursue stability, we will not be able to make progress; if we only pursue diversity, we will not be able to accumulate advantages. Therefore, we need to find a balance between stability and diversity. However, in the long run, stability (accumulation, inheritance) is often more important than diversity.

●It is important to retain elites, but we must never underestimate ordinary individuals outside the elites. Without ordinary individuals, there will be no soil for mutation, and the population will become monotonous. Monotony often means fragility.

References:

[1] Zheng Shuquan. Industrial Intelligence Technology and Application[M]. Shanghai: Shanghai Science and Technology Press.

[2] Li Deyi, Yu Jian. Introduction to Artificial Intelligence, China Association for Science and Technology New Generation Information Technology Series [M]. Beijing: China Science and Technology Press.

Author: Wang Moyi

Author's unit: School of Navigation, Northwestern Polytechnical University

This article is from the "Science Academy" public account. Please indicate the source of the public account when reprinting.