Overview of genetic algorithm

Genetic Algorithm (GA), a part of evolutionary computing, is a computational model that simulates Darwin’s Genetic selection and natural selection of biological evolution. It is a method to search for optimal solutions by simulating natural evolution process. The algorithm is simple, universal, robust and suitable for parallel processing.

Second, the characteristics and application of genetic algorithm

Genetic algorithm is a kind of robust search algorithm that can be used for complex system optimization. Compared with traditional optimization algorithm, genetic algorithm has the following characteristics:

1. Take the encoding of decision variables as the operation object.

Traditional optimization algorithms often directly use the actual value of the decision variable itself to optimize the calculation, but genetic algorithm uses a certain form of the decision variable encoding as the operation object. This method of encoding decision variables makes it possible for us to use the concepts of chromosomes and genes in biology for reference in optimization calculation, to imitate the genetic and evolutionary incentives of organisms in nature, and to easily apply genetic operators.

2. Directly use fitness as search information.

The traditional optimization algorithm not only needs to use the value of the objective function, but also needs to satisfy the requirement of “the derivative of the objective function must exist” in order to determine the search direction.

Genetic algorithm can only use the fitness function value transformed from the objective function value to determine the further search range, without the derivative value of the objective function and other auxiliary information. The objective function value or individual fitness value can be directly used to concentrate the search scope into the search space with higher fitness, so as to improve the search efficiency.

3. Search information of multiple points is used with implicit parallelism.

Traditional optimization algorithms usually start from an initial point in the solution space to search the optimal solution iteratively. The search information provided by a single point is not much, so the search efficiency is not high, and there may be local optimal solution and stagnation.

Genetic algorithms start the search process for optimal solutions from an initial population consisting of many individuals rather than from a single individual. The operation of selection, crossover and mutation on the initial population produces a new generation of population, which contains a lot of population information. This information can avoid searching some unnecessary points, so as to avoid falling into the local optimal solution and gradually approach the global optimal solution.

4. Use probabilistic searches instead of deterministic rules.

Traditional optimization algorithms often use deterministic search methods, the transfer of a search point to another search point has a certain direction and transfer relationship, such deterministic search may not reach the optimal shop, limit the scope of application of the algorithm.

Genetic algorithm (GA) is a kind of adaptive search technology. Its selection, crossover, mutation and other operations are carried out in a probabilistic way, which increases the flexibility of the search process, and can converge to the optimal solution with a large probability, and has a good global optimization capability. However, crossover probability, mutation probability and other parameters can also affect the search results and search efficiency of the algorithm, so how to choose the parameters of genetic algorithm is a relatively important problem in its application.

To sum up, genetic algorithm provides a general framework for solving complex system problems because the overall search strategy and optimal search mode of genetic algorithm do not depend on gradient information or other auxiliary knowledge in calculation, but only require the solution of objective function that affects the search direction and the corresponding fitness function. It does not depend on the specific field of the problem and has strong robustness to the type of the problem, so it is widely used in various fields, including:

  • Function optimization
  • Combinatorial optimization production scheduling problem
  • The automatic control
  • robotics
  • Image processing (image restoration, image edge feature extraction……)
  • Artificial life
  • Genetic programming
  • Machine learning

The basic process and implementation technology of genetic algorithm

Simple Genetic Algorithms (SGA) only uses selection operator, crossover operator and mutation operator. It is the basis of other Genetic Algorithms because of its Simple evolution process.

3.1 Basic flow of genetic algorithm

  1. A number of initial populations encoded by a certain length (length is related to the accuracy of the problem to be solved) are generated in a random way.
  2. Each individual was evaluated by fitness function, and the individuals with high fitness were selected to participate in genetic operation, while the individuals with low fitness were eliminated.
  3. The collection of genetically manipulated individuals (replication, crossover, mutation) forms a new generation of population until the stop criterion (evolutionary algebra GEN>=?) is satisfied. ;
  4. The best cashed individual in the offspring is taken as the execution result of the genetic algorithm.

                                                   

Where GEN is the current algebra; M is population size and I is population size.

3.2 Implementation technology of genetic algorithm

Basic genetic algorithm (SGA) consists of coding, fitness function, genetic operator (selection, crossover, variation) and operation parameters.

1. The encoding

(1) Binary coding

The length of the binary-encoded string depends on the precision of the problem being solved. It is necessary to ensure that every individual in the solved space can be coded.

Advantages: coding, decoding simple operation, inheritance, cross easy to achieve

Disadvantages: Large length

(2) Other coding methods

Gray code, floating point coding, symbol coding, multi – parameter coding and so on

2. Fitness function

The fitness function should effectively reflect the gap between each chromosome and the optimal solution chromosome of the problem.

3. Select operator

Through the selection operator simulation of “survival of the fittest”, individuals with high fitness are more likely to be inherited to the next generation, while operators with low fitness are less likely to be inherited to the next generation.

Commonly used selection algorithm: roulette selection method, that isRepresents the sum of the fitness function values of the population,Is the fitness value of the ith chromosome in the population, then its ability to produce offspring is just its share of the fitness value

4. Crossover operator

  • Crossover operation refers to two mutually paired chromosomes in a way to exchange part of their genes, so as to form two new individuals;
  • Crossover operation is an important feature of genetic algorithm which is different from other evolutionary algorithms and is the main method to generate new individuals.

Before crossover, individuals in the group need to be matched, generally adopting the principle of random pairing.

Common crossover methods:

  • A single point of intersection
  • Double point crossing (multi-point crossing, the more points of crossing, the more likely the individual’s structure will be damaged, generally, the multi-point crossing is not adopted)
  • Uniform cross
  • Arithmetic crossover

5. Mutation operator

Mutation operation in genetic algorithm refers to the replacement of gene values at some loci in the coding string of individual chromosome with other alleles of that loci, thus forming a new individual.

In terms of the ability to generate new individuals in the process of genetic algorithm, crossover operation is the main method to generate new individuals, which determines the global search ability of genetic algorithm. Mutation operation is only an auxiliary method to generate new individuals, but it is also an essential operation step, which determines the local search ability of genetic algorithm. The combination of crossover operator and mutation operator completes the global search and local search of the search space, so that the genetic algorithm can complete the optimization process with good search performance.

6. Running parameters

  • Code length. The coding length depends on the precision of the problem solution, the higher the precision, the longer the coding;
  • Population size. It’s small, it converges fast but it reduces the diversity of the population,;
  • Cross probability. The large crossover probability will destroy the excellent structure formed in the population and make the search have too much randomness. Small crossover probability is too slow to discover new individuals, and the general value is
  • Probability of variation. If the mutation probability is too small, the ability of mutation operation to produce new individuals and inhibit precocious phenomenon will be poor. The variation probability is too high and randomness is too high. The recommended value ranges from 0.005 to 0.01
  • Terminating evolutionary algebra. The value ranges from 100 to 1000

Iv. Source code

% % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- % by using genetic algorithm to optimize charging electric cars orderly; Optimization objectives include the lowest charging cost, charging time to meet the requirements (electric vehicles are charged enough) % Considering the impact of electric vehicle charging on power grid load, so as to minimize the peak-valley difference of load. % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- CLC clear warning off % real-time electricity price data import, Data source PJM The RP = [3.10000000000000, 3.05000000000000, 3,2.80000000000000, 2.60000000000000, 2.55000000000000, 2.50000000000000, 2.6000000000 0000,2.70000000000000, 2.80000000000000, 2.90000000000000, 3.20000000000000, 3.50000000000000, 3.60000000000000, 3.70000000000 000,3.67500000000000, 3.65000000000000, 3.70000000000000, 3.75000000000000, 3.82500000000000, 3.90000000000000, 3.925000000000 00,3.95000000000000, 4.02500000000000, 4.10000000000000, 4.15000000000000, 4.20000000000000, 4.20500000000000, 4.2100000000000 ,4.28000000000000 0, 4.35000000000000, 4.42500000000000, 4.50000000000000, 4.60000000000000, 4.70000000000000, 4.62000000000000 , 4.54000000000000, 4.39500000000000, 4.25000000000000, 4.22500000000000, 4.20000000000000, 4.05000000000000, 3.90000000000000, 3.60000000000000, 3.30000000000000, 3.20000000000000, 3.10000000000000, 3.10000000000000]. Price=[RP(35:48),RP(1:14)]; % Set the vehicle to return home after 17:00 every day to charge; Leave home after 7 o 'clock every day without charging Num=100; % Number of electric vehicles PEV=4; Global PEV % load SOC_start SOC_start=normrnd(0.3,0.05,1,Num); Global SOC_start SOC_end = 0.95 * ones (1, Num); global SOC_end C=35; global C number=Num; % number of individuals in population %% Genetic algorithm parameter set NP=300; % The total number of initial populations NG=80; % Total number of iterations Pc=0.8; Pm = 0.4; % variation COUNTER=10; For I =1:NP data(I).Initial=Initial(number); data(i).generation=data(i).Initial; End Fitness_initial= -INF; for i=1:NP if data(i).Fitness> Fitness_initial INDEX=i; Fitness_initial=data(I).fitness; Fitness_initial=data(I).fitness; Figure (1) plot(-maxium_fitness)% Plot the fitness of the optimal individuals of each generation xlabel(' genetic algebra ') ylabel(' combined objective function value ') title(' evolutionary process ') FITNESS_JY=-maxium_Fitness; save FITNESS_JY figure(2) EV_load=sum(data(INDEX).generation'); EV = [EV_load (15: end), zeros (1, 20), EV_load (1:14)]; plot(EV*PEV) set(gca, 'XLim',[1 48]); Set (gca, 'XTick',[8,16,24,32,40,48]); % X mark points set (gca, 'XTicklabel' {' 4 ', '8', '12', '16', '20', '24'}); Figure (3) xlabel(' time /h') ylabel(' load power /kW') figure(3) Residential_load = [1962.55433333333, 1617.09200000000, 1397.80300000000, 1240.56566666667, 1139.44666666667, 1087.19533333333, 1047.75966666667, 1039.21600000000, 1025.50600000000, 1055.46700000000, 1082.60533333333, 1130.10900000000, 1361.02566666667, 1 719.95200000000, 2047.19933333333, 2384.35633333333, 2527.08400000000, 2849.10700000000, 3038.91600000000, 3026.13366666667, 28 88.03833333333, 2787.28300000000, 2730.16333333333, 2762.67133333333, 2965.20133333333, 3403.65066666667, 3292.44533333333, 301 1.74400000000, 2804.51133333333, 2717.41300000000, 2834.95466666667, 3040.08966666667, 3160.87966666667, 3381.25666666667, 3864 43433333333421 8.04066666667, 4372.06066666667, 4467.65866666667, 4694.08000000000, 4610.18166666667, 4374.74966666667, 4266. 39233333333420, 0.47800000000, 4027.01666666667, 3845.33500000000, 3510.83266666667, 3183.25400000000, 2515.23000000000] * 0.1; plot(Residential_load,'r-'); Plot (EV+Residential_load,'k-')% Local load curve after superposition of EV EV_JY=EV; save EV_JY set(gca, 'YLim',[100 600]); % X axis data display range set(gCA, 'XLim',[1 48]); Set (gca, 'XTick',[8,16,24,32,40,48]); % X mark points set (gca, 'XTicklabel' {' 4 ', '8', '12', '16', '20', '24'}); Xlabel (' time /h') ylabel(' load power /kW') Legend (' Region load Power curve (excluding EV) ','location',' Northwest ',' Region load Power curve (excluding EV) ','location',' Northwest ')Copy the code

5. Operation results