A list,
Genetic Algorithm (GA) is a part of evolutionary computing. It is a computational model that simulates Darwin’s Genetic selection and natural selection of biological evolution process. It is a method to search for optimal solution by simulating natural evolution process. The algorithm is simple, universal, robust and 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 traditional optimization algorithm, it has the following characteristics: (1) The encoding of decision variables is taken 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 search rather than 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 is not dependent on the specific domain of the problem, and has strong robustness to the type of the problem, so it is widely used in a variety of fields, including: function optimization, combinational optimization production scheduling problems, automatic control, robotics, image processing (image recovery, image edge feature extraction…) Artificial life, genetic programming, machine learning.
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
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.
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.
The collection of genetically manipulated individuals (replication, crossover, mutation) forms a new generation of population until the stop criterion (evolutionary algebra GEN>=?) is satisfied. ;
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.
3.2.1 coding
(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
3.2.2 Fitness function
The fitness function should effectively reflect the gap between each chromosome and the optimal solution chromosome of the problem.
3.2.3 Selecting the operator
3.2.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
3.2.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.
3.2.6 Operating Parameters
4 Basic principles of genetic algorithm
4.1 Pattern Theorem
4.2 Building block hypothesis
Patterns with low order, short definition length, and fitness values higher than the population average are called gene blocks or building blocks.
Building block hypothesis: individual gene blocks can be spliced together to form individual coding strings with higher fitness through selection, crossover, mutation and other genetic operators.
The building block hypothesis illustrates the basic idea of solving all kinds of problems with genetic algorithms, that is, better solutions can be produced by directly joining the building blocks together.
Ii. Source code
%%%%%%%%%%%%%%%% Application of genetic algorithm in road image threshold segmentation %%%%%%%%%%%%function main(a)
clear all
close all
clc
global chrom oldpop fitness lchrom popsize cross_rate mutation_rate yuzhisum
global maxgen m n fit gen yuzhi A B C oldpop1 popsize1 b b1 fitness1 yuzhi1
A=imread('1.jpg'); % A=imresize(A,0.4); B=rgb2gray(A); % grayscale C=imresize(B,0.1); % Shrink the read image lchrom=8; % Chromosome length POPsize =10; % Population size cross_rate=0.7; % cross probability mutation_rate=0.4; % mutation probability maxgen=150; % Max algebra [m,n]=size(C);'Just a moment, please... 'initpop; % initial populationfor gen=1:maxgen generation; % Genetic operation end findresult; % image segmentation results %%% output evolution curve figure; gen=1:maxgen;
plot(gen,fit(1,gen));
title('Optimal fitness value evolution curve');
figure;
plot(gen,yuzhi(1,gen));
title('Optimal threshold evolution curve for each generation'); %%%%%%%%%%%%%%%%%%% Initialize the population %%%%%%%%%%%%%%%%%%%%function initpop(a)
global lchrom oldpop popsize chrom C
imshow(C);
for i=1:popsize
chrom=rand(1,lchrom);
for j=1:lchrom
if chrom(1,j)<0.5
chrom(1,j)=0;
else
chrom(1,j)=1;
end
end
oldpop(i,1:lchrom)=chrom; End % % % % % % % % % % % % % % % % % to produce a new generation of individuals % % % % % % % % % % % % % % % % % % % % % %function generation(a)
fitness_order; % calculate fitness value and sort select; % Select operation crossover; % crossover mutation; % variation %%%%%%%%%%%%%%%%% calculates moderation values and sorts %%%%%%%%%%%%%%%%%%%function fitness_order(a)
global lchrom oldpop fitness popsize chrom fit gen C m n fitness1 yuzhisum
global lowsum higsum u1 u2 yuzhi gen oldpop1 popsize1 b1 b yuzhi1
if popsize>=5
popsize=ceil(popsize0.03*gen);
end
if gen==75% Adjust population size and crossover and mutation probability when evolution reaches the end0.3; % cross probability mutation_rate=0.3; % Mutation probability End % If it is not the first generation, the population after the operation of the previous generation will be put into the population of this generation according to the population size of this generationif gen>1
t=oldpop;
j=popsize1;
for i=1:popsize
if j>=1
oldpop(i,:)=t(j,:);
end
j=j- 1; End end % evaluates the moderation value and sorts itfor i=1:popsize
lowsum=0;
higsum=0;
lownum=0;
hignum=0;
chrom=oldpop(i,:);
c=0;
for j=1:lchrom
c=c+chrom(1,j)*(2^(lchrom-j));
end
b(1,i)=c*255/ (2^lchrom- 1); % to gray valuefor x=1:m
for y=1:n
if C(x,y)<=b(1,i)
lowsum=lowsum+double(C(x,y)); % Indicates the sum of gray values below the threshold lownum=lownum+1; % Count the total number of pixels below the threshold gray valueelse
higsum=higsum+double(C(x,y)); % The sum of gray values higher than the threshold hignum=hignum+1; % Count the total number of pixels whose gray value is higher than the thresholdif lownum~=0u1=lowsum/lownum; % U1 and U2 are the average gray values corresponding to the two categorieselse
u1=0;
end
if hignum~=0
u2=higsum/hignum;
else
u2=0;
end
fitness(1,i)=lownum*hignum*(u1-u2)^2; % calculates the moderation value endif gen==1% If it is the first generation, sort it from smallest to largestfor i=1:popsize
j=i+1;
while j<=popsize
if fitness(1,i)>fitness(1,j)
tempf=fitness(1,i);
tempc=oldpop(i,:);
tempb=b(1,i);
b(1,i)=b(1,j);
b(1,j)=tempb;
fitness(1,i)=fitness(1,j);
oldpop(i,:)=oldpop(j,:);
fitness(1,j)=tempf;
oldpop(j,:)=tempc;
end
j=j+1;
end
end
for i=1:popsize
fitness1(1,i)=fitness(1,i);
b1(1,i)=b(1,i);
oldpop1(i,:)=oldpop(i,:);
end
popsize1=popsize;
elseWhen % is greater than one generation, the following order is conducted from smallest to largestfor i=1:popsize
j=i+1;
while j<=popsize
if fitness(1,i)>fitness(1,j)
tempf=fitness(1,i);
tempc=oldpop(i,:);
tempb=b(1,i);
b(1,i)=b(1,j);
b(1,j)=tempb;
fitness(1,i)=fitness(1,j);
oldpop(i,:)=oldpop(j,:);
fitness(1,j)=tempf;
oldpop(j,:)=tempc;
end
j=j+1; End end % end %for i=1:popsize1
j=i+1;
while j<=popsize1
if fitness1(1,i)>fitness1(1,j)
tempf=fitness1(1,i);
tempc=oldpop1(i,:);
tempb=b1(1,i);
b1(1,i)=b1(1,j);
b1(1,j)=tempb;
fitness1(1,i)=fitness1(1,j);
oldpop1(i,:)=oldpop1(j,:);
fitness1(1,j)=tempf;
oldpop1(j,:)=tempc;
end
j=j+1; The best threshold value and best fitness value of each generation are counted belowif gen==1
fit(1,gen)=fitness(1,popsize);
yuzhi(1,gen)=b(1,popsize);
yuzhisum=0;
else
if fitness(1,popsize)>fitness1(1,popsize1)
yuzhi(1,gen)=b(1,popsize); % Optimal threshold for each generation fit(1,gen)=fitness(1,popsize); % Optimum fitness per generationelse
yuzhi(1,gen)=b1(1,popsize1);
fit(1,gen)=fitness1(1,popsize1); End end % % % % % % % % % % % % % % % % % % % elitist selection % % % % % % % % % % % % % % % % % % % %function select(a)Global Fitness POPSize OldPop Temp Popsize1 OldPOP1 Gen B B1 Fitness1% The number of fitness values in the previous population that are greater than the current population fitness s=popsize1+1;
for j=popsize1:- 1:1
if fitness(1,popsize)<fitness1(1,j)
s=j;
end
end
for i=1:popsize
temp(i,:)=oldpop(i,:);
end
if s~=popsize1+1
if gen<50% less than the50Substitute the previous generation and randomly replace the current generation with individuals whose fitness values are greater than the current generationfor i=s:popsize1
p=rand;
j=floor(p*popsize+1);
temp(j,:)=oldpop1(i,:);
b(1,j)=b1(1,i);
fitness(1,j)=fitness1(1,i);
end
else
if gen<100 %50~100Substitute the last generation replace the worst individual in the current generation with an individual whose fitness value is greater than the current generation j=1;
for i=s:popsize1
temp(j,:)=oldpop1(i,:);
b(1,j)=b1(1,i);
fitness(1,j)=fitness1(1,i);
j=j+1;
end
else% is greater than the100J =popsize1; j=popsize1;for i=1:floor(popsize/2)
temp(i,:)=oldpop1(j,:);
b(1,i)=b1(1,j);
fitness(1,i)=fitness1(1,j);
j=j- 1;
end
end
end
end
Copy the code3. Operation results
Fourth, note
Version: 2014 a