The natural world is an inexhaustible source of inspiration for human innovation. Creatures in nature have extraordinary adaptability and intelligence: how do ant colonies find the shortest path to food sources, how do geese fly the shortest distances when foraging, how do organisms evolve various traits...... Rational use of these rules, can be dealt with...... Math problems?
(图片来源:veer图库)
That's right, and it's a problem that is not easy to solve with traditional mathematical theories.
Optimization problems and heuristics
First, let's look at the math:
Calculate the maximum value of the quadratic function as follows
For this simple objective function, you can directly apply the formula: when the independent variable x=-b/2a, the maximum value of the objective function is (4ac-b2)/4a (please contact your high school math teacher if you forget it). This kind of solution, which can be directly expressed as a formula, is called an analytic solution.
For simple questions, you can get answers in one step
This problem of finding the maximum/minimum value of a function is called an optimization problem, and this function is called an objective function. The optimization algorithm is the algorithm that calculates the maximum value of the objective function.
In practice, the objective function of optimization problems is often complex and cannot be solved analytically, so gradients (derivatives of multivariate functions) are often used to iteratively solve them.
However, for some of the more complex objective functions, the gradient method cannot be used. For example, calculate the minimum value of the following function
Complex objective functions that cannot be applied to formulas
If the conventional gradient method is used, it is easy to converge to the local optimum, that is, the maximum value point in a certain range, rather than the global optimum, that is, the maximum value point in the global range.
Gradient methods tend to fall into local optimals
Optimizing similar complex functions has always been a difficult problem. After being inspired by some natural laws, scientists simulated natural body algorithms and proposed several heuristic algorithms to deal with optimization problems that are not easy to solve by traditional mathematical theories.
例如，模拟蚁群寻找、搬运食物的规律，提出蚁群算法（Ant Colony Algorithm）；模拟大雁在空中觅食的规律，提出粒子群优化算法（Particle Swarm Optimization Algorithm）；模拟生物遗传与进化规律，提出遗传算法（Genetic Algorithm）……
What do algorithm scientists think about biological genetics and evolution?
The heuristic algorithm introduced in this article is proposed to simulate the laws of biological heredity and evolution, so what is the heredity and evolution in the eyes of algorithm scientists? Here is an example of the evolution of giraffes (note that genetic algorithms are only imitations of known evolutionary laws, and are not necessarily equivalent to biological laws).
There are many kinds of organisms in nature, and their traits are determined by both genes and external factors, but genes are dominant, so external factors are ignored here. For example, when the gene is determined, the length of the giraffe's neck is also determined.
A gene is the genetic material of an organism and is made up of multiple nucleotides, similar to "AaBbCc". The evolution of a population inevitably means a change in genes.
Natural selection does not act directly on genes, but on traits. Individuals have different traits and different ability to survive. For example, the longer the deer's neck, the more leaves it eats, and the more survivable it is. The quantification of survivability, known as fitness.
Fitness is supposed to be determined by a combination of factors, such as the length of the deer's neck, physical strength, eyesight, and other factors. But only the length of the neck is considered here, and the longer the neck, the higher the fitness.
(The default in this article is: genes determine traits, and then determine viability)
Once upon a time, there was a group of ordinary deer, and everyone had different genes, so the traits were also different (the trait here specifically refers to the length of the neck), and the deer herd of this generation was recorded as "deer herd 0".
In "Deer Herd 0", individuals with long necks are more likely to survive and are more likely to survive. 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 are able to mate.
(Image 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 with the female deer's genes and then combines them (here it is considered that gene = chromosome). For example, "Aa BbCc" + "aa bbcc" = "Aa bbcc" + "aa BbCc".
Of course, when two genes are combined, one or more nucleotides of the gene may mutate. For example, gene b mutates to b.
Gene crossing
Genetic variation
In this way, "Deer Herd 0" gives rise to a new generation, which is denoted as "Deer Herd 1". Generally speaking, the maximum and average values of fitness will be increased for "Deer Herd 1" after selection treatment, that is, the maximum and average values of neck length will be improved.
After generations of reproduction, due to genetic changes, the neck of "Deer Group N" will be significantly longer than that of "Deer Group 0", and the adaptability 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, which in this case refers to the height of the canopy. The neck is higher than the canopy, which has no benefit but disadvantage. As long as there is no significant change in the environment, after "deer herd N", the genes of the population will not change significantly, and the fitness will not change significantly, and the population will be stable at the optimal solution.
Genetic algorithm, how to calculate it?
John Holland of the United States simulated the natural selection and genetic mechanism of Darwin's biological evolutionary theory, and proposed a heuristic optimization algorithm, genetic algorithm.
The algorithm converts the independent variables into individuals, corresponds the individuals to genes through coding, and takes the objective function to be solved as the fitness function, retains the intersection and variation, and after multiple iterations, the population (multiple individuals) can tend to the optimal solution.
Taking solving 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 treats the possible values of the independent variable as an individual, and generates an initialized population after setting the total number of populations. For example, if there are 100 individuals in the population, 100 initial values are randomly selected in the interval [0,8].
Within an interval of the independent variable, the initial population is randomly generated
2. Encoding and decoding
The independent variable individual itself cannot be regarded as a gene, and it needs to be converted in some way, usually by converting the individual into a string of binary numbers, called coding, and this string of binary numbers can be regarded as genes.
For example, if the integer part is represented by 4-bit binary and the decimal part is represented by 2-bit binary, then 3.25 can be expressed as "001101", and "001101" is the individual's gene.
The binary representation of an individual's 3.25 001101 is a simulation of genes
The purpose of coding is to mimic genes, so that subsequent crossovers and mutations can be carried out. Decoding, on the other hand, is the conversion of genes (binary) into individuals (decimal). The decimal number can be substituted into the fitness function to calculate the fitness.
3. Fitness calculation
However, after converting the gene (binary) into an individual (decimal), the fitness can be obtained by substituting the decimal individual 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 according to the size of the fitness. Those with greater fitness are more likely to be retained, and those with less fitness are more likely to be eliminated. This process is usually carried out using the "roulette" model.
Of course, in the selection process, we also have to ensure that the number of individuals remains the same. To ensure this, the adaptable ones are not only retained, but also replicated.
Individuals with greater adaptation are naturally more likely to survive
5. Crossover and mutation
The individuals are retained, and the genes are coded and crossed. For example, "001 101" + "010 010" = "001 010" + "010 101". In general, intersections are chosen randomly.
Here, two genes are crossed to get two new genes (equivalent to the parents' destined twins). Therefore, crossover does not change the population size.
Each gene may also mutate after crossing. In general, the point of variation is also random. For example, a bit of 1 becomes 0, or 0 becomes 1.
The crossing of binary numbers
Variation of binary numbers
After selection, the maximum and average values of population fitness were improved compared to the previous generation. Specifically, all individuals will concentrate on the higher part of the objective function. After many iterations, it is concentrated at the maximum.
6. Whether it is over or not
Since it is an optimization algorithm, it is necessary to set the end condition, and the algorithm cannot be looped indefinitely (endless loop). The easiest way to do this is to set the number of times the algorithm runs. For example, let the algorithm loop 50 times before it ends.
Here is a general flowchart of the genetic algorithm
As evolution progresses, i.e., the algorithm cycles, the average fitness of the population is bound to increase from generation to generation, and eventually converge to a certain maximum, 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 is iterated, the average fitness of the population also increases
There are small strategies at every step
If you want to improve the efficiency of the genetic algorithm, there are actually small tricks in the above steps.
1. Initialization
If a priori information about the maximum point is available, i.e. the approximate range in which the maximum point is located. The initial population can be generated within this range. If not, it needs to be randomly generated over a larger area.
The selection of the initial value will affect the convergence speed of the algorithm. The closer the initial value is selected to the optimal solution, the faster the convergence speed. In addition, an inappropriate initial value may cause the algorithm to fall into a local optimum.
Isn't it possible to find the optimal solution faster~?
2. Encoding and decoding
In digital signal processing, there must be a minimum and a maximum value in the measurement, that is, the value of the variable is not continuous and infinite, but discontinuous and finite, and the error caused by the measurement is called Quantization Error.
For example, if we use 4-bit binary for the integer part and 2-bit binary for the decimal part, then the independent variable can only be taken up to 15.75 (corresponding to the binary 111111), and the decimal part can only distinguish the difference of 0.25. The minimum value of a measure is also known as 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, with 100-bit binary for the integer part and 10-bit binary for the decimal part, so as to expand the range of independent variable values and improve the resolution. However, this will increase the amount of computation and storage of the algorithm.
3. Select
In the selection process, if the individuals with the highest adaptability are retained or replicated, it is called Elite Reservation, and if the individuals with the highest adaptability are not necessarily retained, they are still likely to be eliminated, and they are called no elite reservations.
Experiments show that the genetic algorithm with elite retention has a faster convergence speed to the optimal value and is more stable.
4. Crossover and mutation
Crossover can be divided into single-point crossover or multi-point crossing, and variation can also be divided into single-point variation and multi-point variation. Crossover and mutation are designed to improve gene diversity, accelerate convergence speed, and jump out of local optimum.
For example, when all individuals are concentrated near the local optimum, and suddenly one individual mutates and "jumps" to the global optimum, the population can evolve further.
For populations, stability is more important than diversity, so crossovers and mutations are often carried out at a single point, and the probability of variation is often very low.
5. Whether it is over or not
Although it is simple to control the end of the algorithm by setting the number of times the algorithm runs, there are two problems:
(1) If the convergence of the algorithm is slow, for example, 50 times does not make the population concentrate to an optimal solution, then the result must be incorrect;
(2) If the algorithm converges quickly, for example, 20 times can make the population concentrate to a certain optimal solution, then a lot of computing resources are wasted.
A more reliable method is to determine the size of the average fitness difference between two adjacent operations, i.e., whether it 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.
It is more reliable to control the termination of the algorithm according to the difference in average fitness
Genetic algorithms don't just draw, they tell you that
Heuristic algorithms, such as genetic algorithms, do not have extremely rigorous mathematical derivations, but nature has used these laws to solve countless problems. Genetic algorithms are now widely used in many areas of our lives, such as how to design vehicle shapes to reduce air resistance, how to arrange robot workflows to improve work efficiency, and how to plan routes to minimize the distance of express delivery......
Last year, someone uploaded a project on GitHub, which is to use the genetic algorithm to draw a specific picture, and the following is a simulation example to see how the genetic algorithm "draws" the following works against the above photos:
(Image source: https://github.com/anopara/genetic-drawing)
Firstly, a plurality of initial color bars are given to form a color bar picture, and the difference between the color bar picture and the original image is taken as the objective function. Then, the genetic algorithm is used to iteratively solve the arrangement of the color bars, so that the objective function is the smallest, that is, the color bar picture is "most like" to the original picture, so as to realize the "drawing" of the original picture with multiple color bars.
PS: If you are not a coder, 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, and to ensure accuracy, the amount of computation must be increased. 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, and 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.
●Elite retention is important, but it must not be taken lightly as an ordinary individual outside of the elite. Without ordinary individuals, mutation loses the soil, and the population becomes monotonous. And monotony, often means vulnerability.
Bibliography:
[1] Zheng Shuquan. Industrial intelligence technology and application[M]. Shanghai: Shanghai Science and Technology Press.
[2] Li Deyi, Yu Jian. Introduction to Artificial Intelligence in the New Generation Information Technology Series of China Association for Science and Technology[M]. Beijing: China Science and Technology Press.
Author: Wang Moyi
Author Affilications:School of Navigation, Northwestern Polytechnical University
(This article was first published on July 26, 2021 in the Science Compound)