(1) Determine the decision variables and various constraints, that is, determine the individual phenotype X and the solution space of the problem
(2) Establish an optimization model and determine the type of objective function and its mathematical description form or quantification method.
(3) Determine the chromosome encoding method that represents the feasible solution, that is, determine the individual genotype X* and the search space of the genetic algorithm.
Coding is a prerequisite and key step for genetic algorithm to solve problems
① Not only determines the arrangement form of individual genes (thereby determining the way operations such as selection and reproduction work), but also determines the decoding method from the genotype in the search space to the phenotype in the solution space (thereby determining the translation and interpretation of the solution obtained by GA). understand);
②Determine the difficulty and complexity of GA search;
③Determine the accuracy of solving the problem.
Commonly used genetic algorithm encoding methods mainly include: binary encoding, floating point number encoding, etc. It can be proved that binary encoding has stronger search ability than floating point encoding, but floating point encoding can maintain better population diversity in mutation operations than binary encoding.
Standard genetic algorithms mostly use binary coding methods to represent decision variables as binary strings. The length of the binary coding string is determined by the required accuracy. Then the binary coding strings of each decision variable are concatenated together to form a chromosome.
(4) Determine the decoding method, that is, determine the correspondence and conversion method from individual genotype X* to individual phenotype X.
For example: for binary encoding, the decoding process is as follows: If the value range of X* is [Xl,
In the formula, [Xl,Xr]——the minimum and maximum values of parameters;
L——Parameter encoding length;
k——The real value corresponding to the binary string.
(5) The quantitative evaluation method for determining individual fitness is to determine the conversion rule from the objective function value to individual fitness.
There are three commonly used fitness functions of standard genetic algorithms:
Ⅰ. Directly use the objective function to be solved as the fitness function
If the objective function is a maximum value problem, then Fit(f(X))=f(X)
If the objective function is a minimum value problem, then Fit(f(X))=-f(X)
Advantages: simple and intuitive;
Disadvantages: First, the non-negative requirement may not be met; second, the function value distributions solved for some generations vary greatly, and the average fitness obtained may not be conducive to reflecting the average performance of the population.
Ⅱ. Boundary construction method
Cmax is the maximum estimate of f(x).
Cmin is the minimum estimate of f(x).
This method is an improvement of the first method, but sometimes there are problems such as difficulty in pre-estimating the limit value or imprecise estimation.
Ⅲ. Reciprocal method
C is a conservative estimate of the bounds of the objective function.
(6) Determine the specific operation methods of each genetic
①Selection operator and selection operation
There are two common methods of assigning individual selection probabilities:
B. Rank-based Fitness Assignment In ranking-based fitness assignment, the population is sorted according to the target value. Fitness only depends on the individual's position in the population, not the actual target value.
The ranking method shows better robustness than the proportional method, and it can overcome the scale problem and premature convergence problem of proportional fitness calculation to a certain extent.
Several selection methods to improve the performance of genetic algorithms
ⅠSteady State Reproduction: In the iterative process, some high-quality new child individuals are used to update some parent individuals in the group as the next generation population.
ⅡSteady State Reproduction without Duplicates: On the basis of steady-state reproduction, when forming a new population of the next generation, the individuals in it are not repeated.
② Crossover rate and crossover operation
Crossover, also known as genetic recombination, is the most important means for genetic algorithms to obtain new excellent individuals, and determines the global search capability of genetic algorithms.
Generally, when the probability of random generation is greater than the crossover rate, the genetic algorithm will select two individuals according to certain rules and perform the crossover operation. The choice of crossover rate determines the frequency of crossover. A larger crossover rate allows each generation to fully cross, but the possibility of destroying the excellent patterns in the group increases, resulting in a larger generation gap, which makes the search random; The lower the crossover rate, the smaller the generation gap produced, which will cause more individuals to be directly copied to the next generation, and genetic search may stagnate. The generally recommended value range is 0.4~0.9.
For binary coding, commonly used crossover methods include: single-point crossover, multi-point crossover, and uniform crossover. In addition, there are also Partially Matched Crossover, Ordered Crossover, Shuffle Crossover and so on.
③Mutation rate and mutation operation
Mutation itself is a local random search, which enables the genetic algorithm to have local random search capabilities; at the same time, it allows the genetic algorithm to maintain the diversity of the population to prevent premature convergence.
Generally, the mutation operation will be triggered when the probability of random generation is greater than the mutation rate. The mutation rate generally takes 0.001~0.1. The mutation rate cannot be too large. If it is greater than 0.5, the genetic algorithm will degenerate into random search, and some important mathematical characteristics and search capabilities of the genetic algorithm will no longer exist.
Commonly used mutation operation methods include: real-valued mutation method and binary mutation method, etc.
(7) Determine the relevant operating parameters of the genetic algorithm, including population size, number of iterations (generally 100~500), selection operator, crossover rate, mutation rate, etc.
(8) Initialization group
The initial group is generally generated randomly
It is best for the initial value to be uniformly sampled in the solution space (the convergence speed is faster)
For non-binary encodings, also consider whether the generated chromosome is within the feasible region
(9) Calculate the decoded fitness value of individuals in the group
(10) According to the genetic strategy, use the selected selection, crossover and mutation operators to act on the population to generate the next generation population.
(11) Determine whether the group performance meets a certain indicator or completes the predetermined number of iterations. If not, return to (9).
Wondershare EdrawMind
