Ziji Shengguang q1564658423 2021-08-05 09:13:19 阅读数:816
1 Overview of genetic algorithm
Genetic algorithm (ga) （Genetic Algorithm,GA） It's part of evolutionary computing , It is a computational model that simulates the biological evolution process of Darwin's genetic selection and natural elimination , It is a method to search the optimal solution by simulating the natural evolution process . The algorithm is simple 、 Universal , Strong robustness , Suitable for parallel processing .
2 Characteristics and application of genetic algorithm
Genetic algorithm is a kind of robust search algorithm which can be used for complex system optimization , Compared with the traditional optimization algorithm , It has the following characteristics ：
（1） Take the code of decision variable as the operation object . Traditional optimization algorithms often directly use the actual value of decision variables to optimize calculation , But genetic algorithm uses some form of coding of decision variables as the operation object . This coding method for decision variables , So we can learn from the concepts of chromosome and gene in Biology , It can imitate the genetic and evolutionary incentives of organisms in nature , Genetic operators can also be easily applied .
（2） Directly use fitness as search information . The traditional optimization algorithm not only needs to use the value of the objective function , Moreover, the search process is often constrained by the continuity of the objective function , There may be a need to meet “ The derivative of the objective function must exist ” To determine the search direction . The genetic algorithm only uses the fitness function value transformed by the objective function value to determine the further search range , No other auxiliary information such as derivative value of objective function is required . Directly using the objective function value or individual fitness value can also focus the search range into the search space with higher fitness , To improve search efficiency .
（3） Search information using multiple points , With implicit parallelism . The traditional optimization algorithm is often an iterative search process starting from an initial point in the solution space . A single point provides little search information , So the search efficiency is not high , It is also possible to fall into the local optimal solution and stop ; Genetic algorithm starts the search process of the optimal solution from the initial population composed of many individuals , Instead of searching from a single individual . Of the initial population 、 choice 、 cross 、 Mutation and other operations , Produce a new generation of groups , It includes a lot of group information . This information can avoid searching some unnecessary points , So as to avoid falling into local optimization , Gradually approach the global optimal solution .
（4） Use probabilistic search instead of deterministic rules . Traditional optimization algorithms often use deterministic search methods , The transfer from one search point to another has a definite transfer direction and transfer relationship , This certainty may make the search less than optimal , It limits the application scope of the algorithm . Genetic algorithm is an adaptive search technology , Its choice 、 cross 、 Operations such as mutation are carried out in a probabilistic way , Increases the flexibility of the search process , And it can converge to the optimal solution with a large probability , It has good global optimization ability . but , Crossover probability 、 Mutation probability and other parameters will also affect the search results and search efficiency of the algorithm , Therefore, how to select the parameters of genetic algorithm is an important problem in its application .
Sum up , Because the overall search strategy and optimization search method of genetic algorithm do not depend on gradient information or other auxiliary knowledge , Only the objective function affecting the search direction and the corresponding fitness function need to be solved , Therefore, genetic algorithm provides a general framework for solving complex system problems . It does not depend on the specific area of the problem , Strong robustness to the types of problems , So it is widely used in various fields , Include ： Function optimization 、 Combinatorial optimal production scheduling problem 、 Auto-Control
、 Robotics 、 The image processing （ Image restoration 、 Image edge feature extraction …)、 Artificial life 、 Genetic programming 、 machine learning .
3 The basic flow and implementation technology of genetic algorithm
Basic genetic algorithm （Simple Genetic Algorithms,SGA） Use only the selection operator 、 Crossover operator and mutation operator are three genetic operators , Evolution is simple , It is the basis of other genetic algorithms .
3.1 The basic flow of genetic algorithm
Generate a number of randomly determined lengths （ The length is related to the accuracy of the problem to be solved ） The initial population of coding ;
Each individual is evaluated by fitness function , Individuals with high fitness value were selected to participate in genetic operation , Individuals with low fitness are eliminated ;
Genetically manipulated （ Copy 、 cross 、 variation ） A new generation of population is formed by the collection of individuals , Until the stop criteria are met （ Evolution algebra GEN>=?）;
The best realized individual in the offspring is taken as the execution result of the genetic algorithm .
among ,GEN Is the current algebra ;M It's population size ,i Represents the number of populations .
3.2 Implementation technology of genetic algorithm
Basic genetic algorithm （SGA） Coded by 、 Fitness function 、 Genetic operators （ choice 、 cross 、 variation ） And operation parameters .
（1） Binary code
The length of binary coded string is related to the accuracy of the problem . We need to ensure that every individual in the solution space can be encoded .
advantage ： Ed 、 The decoding operation is simple , inheritance 、 Crossover is easy to achieve
shortcoming ： The length is large
（2） Other coding methods
Gray code 、 Floating point code 、 Symbolic encoding 、 Multi parameter coding, etc
3.2.2 Fitness function
The fitness function should effectively reflect the gap between each chromosome and the chromosome of the optimal solution of the problem .
3.2.3 Selection operator
3.2.4 Crossover operator
Cross operation refers to the exchange of some genes between two paired chromosomes in some way , And two new individuals ; Crossover operation is an important feature that distinguishes genetic algorithm from other evolutionary algorithms , Is the main way to produce new individuals . Before crossing, individuals in the group need to be paired , Generally, the principle of random pairing is adopted .
Commonly used crossover ：
A single point of intersection
Two point intersection （ Multi-point crossover , The more cross points , The more likely the individual's structure is to be destroyed , Generally, multi-point intersection is not adopted ）
3.2.5 Mutation operator
The mutation operation in genetic algorithm refers to replacing the gene values at some loci in the individual chromosome coding string with other alleles at this locus , So as to form a new individual .
In terms of the ability to generate new individuals in the operation of genetic algorithm , Cross operation is the main method to generate new individuals , It determines the global search ability of genetic algorithm ; Mutation is only an auxiliary method to generate new individuals , But it is also an essential operation step , It 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 , Thus, the genetic algorithm can complete the optimization process of the optimization problem with good search performance .
3.2.6 Operation parameters
4 The basic principle of genetic algorithm
4.1 Pattern theorem
4.2 Building block hypothesis
With low order 、 The definition length is short , The pattern whose fitness value is higher than the average fitness value of the population is called gene block or building block .
Building block hypothesis ： Individual gene blocks are selected 、 cross 、 The role of genetic operators such as mutation , Can be spliced together , Form individual coding strings with higher fitness .
The building block hypothesis illustrates the basic idea of using genetic algorithm to solve various problems , That is, better solutions can be produced by directly splicing building blocks together .
clc clear %-------------------- get data ----------------------- PBase=fopen('PBase.txt'); Pbase(1,:)=fscanf(PBase,'%g',[1,inf]); %Pbase Power grid basic load power 96 Time periods fclose(PBase); carnum=100; %carnumal Given the number of connected cars % carnum0=0.25*carnumal; %carnum0 Number of emergency charging vehicles % carnum=carnumal-carnum0; %carnum Number of cars with regular charging ET=36; %ET Given car battery capacity ptSOC0=normrnd(0.2,0.05,1,carnum); %ptSOC0 Battery state following normal distribution pch=[7,1.5]; %pch Constant power charging Pmax=2400; %Pmax The maximum allowable power of a given grid tin=normrnd(19,1,1,carnum); %tin Access time of each electric vehicle Te=normrnd(7,0.5,1,carnum); %Te The user sets the charging completion time timeT=zeros(1,carnum); %timeT Time required for charging each electric vehicle ptSOC=ptSOC0; for i=1:carnum while ptSOC(1,i)<0.9 % Charging power SOC<90% ptSOC(1,i)=ptSOC(1,i)+0.25*pch(1)/ET; timeT(1,i)=timeT(1,i)+0.25; end % Charging power SOC>=90% timeT(1,i)=timeT(1,i)+(1-ptSOC(1,i))*ET/pch(2); end %-------------------- Disorderly charging ----------------------- cartime=carT(carnum,tin,timeT); % Take the vehicle access time as the charging start time a=sum(cartime,2); Ptotal=zeros(1,96); for i=1:96 Ptotal(1,i)=Pbase(i)+pch(1)*a(i); end PTotal=fopen('d:\PTotal.txt','wt'); fprintf(PTotal,'%g \n',Ptotal); fclose(PTotal); %-------------------- Emergency charging ----------------------- % % tsSOC0=normrnd(0.3,0.05,1,carnum0); %tsSOC0 Battery state following normal distribution % tin0=24.*rand(1,carnum0); %tin0 Random distribution of access time of special electric vehicles % tsSOCe=normrnd(0.8,0.05,1,carnum0); %tsSOCe The user sets the desired battery state % timeT0=zeros(1,carnum0); %timeT0 Constant power charging duration % for i=1:carnum0 % timeT0(1,i)=ET*(tsSOCe(i)-tsSOC0(i))/pch(1); % end % cartime=carT(carnum0,tin0,timeT0); % Take the vehicle access time as the charging start time % a=sum(cartime,2); % for i=1:96 % Pbase(i)=Pbase(i)+pch(1)*a(i); % end %------------------ Genetic algorithm optimization --------------------- maxgen=8000; %maxgen Terminate evolutionary algebra sizepop=20; %sizepop Population size pcross=0.8; %pcross Hybridization probability pmutation=0.05; %pmutation Mutation probability bound=[tin;Te-timeT+24]; %bound Constraint range % Population initialization ton=zeros(1,carnum); %ton Charging start time of each electric vehicle carpop=struct('fitness',zeros(1,sizepop),'chrom',); for i=1:sizepop %carpop The initial population is randomly assigned a=rand(1,carnum); for j=1:carnum ton(1,j)=bound(1,j)+a(j)*(bound(2,j)-bound(1,j)); end carpop.chrom(i,:)=ton; %chrom Chromosome group , namely ton aggregate %carpop.fitness(i)=fit1(carnum,ton,timeT,Pbase,pch); carpop.fitness(i)=fit2(carnum,ton,timeT,Pbase,pch); end % Find the current optimal solution （ The chromosome with the least Fitness ） [bestfit,bestindex]=min(carpop.fitness); bestton=carpop.chrom(bestindex,:); %bestton Optimal charging start time avgfit=sum(carpop.fitness)/sizepop; %avgfit Average fitness % Evolution begins for i=1:maxgen carpopC=struct('fitness',,'chrom',); carpopC.chrom=Cross(pcross,carnum,carpop.chrom,sizepop,bound); carpopM.chrom=Mutation(pmutation,carnum,carpop.chrom,sizepop,[i,maxgen],bound); for j=1:sizepop ton=carpopC.chrom(j,:); %carpopC.fitness(1,j)=fit1(carnum,ton,timeT,Pbase,pch); carpopC.fitness(1,j)=fit2(carnum,ton,timeT,Pbase,pch); end for j=1:sizepop ton=carpopM.chrom(j,:); %carpopM.fitness(1,j)=fit1(carnum,ton,timeT,Pbase,pch); carpopM.fitness(1,j)=fit2(carnum,ton,timeT,Pbase,pch); end carpop=Select0(carpop,carpopC,carpopM,sizepop); [newbestfit,newbestindex]=min(carpop.fitness); if bestfit>newbestfit bestfit=newbestfit; end avgfit=sum(carpop.fitness)/sizepop; end % bestfit=Pmax; % maxgen=5000; % for i=1:maxgen % carpopC=struct('fitness',,'chrom',); % carpopC.chrom=Cross(pcross,carnum,carpop.chrom,sizepop,bound); % carpopM=struct('fitness',,'chrom',); % carpopM.chrom=Mutation(pmutation,carnum,carpop.chrom,sizepop,[i,maxgen],bound); % for j=1:sizepop % ton=carpopC.chrom(j,:); % carpopC.fitness(1,j)=fit1(carnum,ton,timeT,Pbase,pch); % %carpopC.fitness(1,j)=fit2(carnum,ton,timeT,Pbase,pch); % end % for j=1:sizepop % ton=carpopM.chrom(j,:); % carpopM.fitness(1,j)=fit1(carnum,ton,timeT,Pbase,pch); % %carpopM.fitness(1,j)=fit2(carnum,ton,timeT,Pbase,pch); % end % carpop=Select0(carpop,carpopC,carpopM,sizepop); % [newbestfit,newbestindex]=min(carpop.fitness); % if bestfit>newbestfit % bestfit=newbestfit; % bestton=carpop.chrom(newbestindex,:); % end % avgfit=sum(carpop.fitness)/sizepop; % end function ret=Cross(pcross,carnum,chrom,sizepop,bound) % Cross progeny for i=1:sizepop pick=rand(1,2); % Two chromosomes were randomly selected as crossing parents while prod(pick)==0 pick=rand(1,2); end index=ceil(pick.*sizepop); pick=rand; % Comparison between random number and crossover probability Decide whether to cross while pick==0 pick=rand; end if pick>pcross continue; end flag=0; while flag==0 % Randomly select the intersection location pick=rand; while pick==0 pick=rand; end pos=ceil(pick*carnum); pick=rand; % Start crossing x1=chrom(index(1),pos); x2=chrom(index(2),pos); x1=pick*x2+(1-pick)*x1; x2=pick*x1+(1-pick)*x2; flag1=test(x1,bound(:,pos)); % Check the feasibility flag2=test(x2,bound(:,pos)); if flag1*flag2==0 flag=0; else flag=1; chrom(index(1),pos)=x1; chrom(index(2),pos)=x2; end end end ret=chrom;
版权声明：本文为[Ziji Shengguang q1564658423]所创，转载请带上原文链接，感谢。 https://car.inotgo.com/2021/08/20210805091214389d.html