genetic algorithm
Genetic algorithm is an iterative optimization algorithm that simulates the evolution mechanism of natural organisms. By simulating the law of "survival of the fittest, survival of the fittest", it finds the most suitable solution among all possible solutions
Article directory
1. Basic principles
In genetic algorithm, after the initial population is formed by coding, the task of genetic operation is to realize the evolution process of "survival of the fittest" by evaluating the fitness of each individual in the population and then screening. From the perspective of optimization search, genetic operation can optimize the solution of the problem generation by generation, so as to approach the optimal solution
Genetic algorithm consists of three basic genetic operators: selection, crossover and mutation
It should be noted that although the operation of individual genetic operators is carried out under the condition of random disturbance, there is a difference between this kind of random operation and the traditional random search method: genetic operation is an efficient and directed search
The effect of genetic operation is closely related to the operation probability, coding method, population size, initial population and fitness function
1.1 choice
We call the operation of "selecting the superior individual from the group and eliminating the inferior individual" selection. The selection operator is also called the regeneration operator
The selection operation is based on the fitness evaluation of the individuals in the group
Roulette selection is the simplest and most commonly used method. In this method, the probability of each individual's selection is in direct proportion to its fitness value:
I f the population size is n n n, and the fitness of individual I I I is FIF {I} fi, then the probability of iii being selected is Pi=fi ∑ I = 1nfi. P {I} = \ frac {f {I}} {\ sum {I = 1} ^ {n} f {I}}}. Pi = ∑ i=1n fi
After calculating the selection probability of each individual in the group, in order to select "mating" individuals, multiple rounds of selection are needed. In each round of selection, a uniform random number between 0, 10, 10 and 1 will be generated, and it will be used as a pointer to determine the selected individual. After the individual is selected, the cross pairing can be formed randomly for subsequent cross operations
1.2 crossover
In the process of biological evolution in nature, recombination (including mutation) of biological genetic factors plays a key role. Correspondingly, crossover operator of genetic operation plays a key role in genetic algorithm. Crossover refers to the operation of replacing and recombining part of the structure of two parent individuals to generate new individuals
Crossover operators randomly exchange some "genes" between two individuals in the population according to the crossover rate, according to the difference of "gene" coding representation. There are discrete recombination, intermediate recombination, linear recombination, extended linear recombination, single point / multipoint crossover, uniform crossover, shuffle crossover, reduced proxy crossover and other operators. The most commonly used crossover operator is single point crossover. Its specific operation is: random in the individual string When a crossing point is set, the partial structure of two individuals before or after the point is exchanged, and two new individuals are generated
1.3 variation
The mutation operator changes the "gene value" of some "loci" on the individual string in a population. According to the different representation methods of individual coding, there are the following algorithms: real value mutation and binary mutation
In general, the basic operation steps of mutation operator are as follows:
 All the individuals in the group are judged to be mutated by the preset mutation probability
 The individuals who are determined to be mutated are randomly selected to mutate
The purpose of introducing the concept and function of "mutation" into genetic algorithm is as follows:
 The genetic algorithm has the ability of local random search. When the genetic algorithm approaches the neighborhood of the optimal solution through crossover operator, the local random search ability of mutation operator can accelerate the convergence to the optimal solution
 The genetic algorithm can maintain population diversity and avoid premature convergence
In the genetic algorithm, the crossover operator is the main operator because of its strong global search ability, and the mutation operator is the auxiliary operator because of its outstanding local search ability. Through the combination of these two operators, the genetic algorithm can give consideration to the uniform search ability of global search and local search
When a population is trapped in a hyperplane of search space in evolution, and can't get rid of it only by crossing, the hyperplane can be got rid of by mutation operation
When the expected "algorithm block" has been formed by crossover operator, mutation operation may destroy it
1.4 termination conditions
When the fitness of the optimal individual reaches the set threshold, or the fitness and group fitness of the optimal individual no longer rise, or the number of iterations reaches the threshold, the algorithm terminates. The preset number of iterations is generally 100 − 500100500100 − 500 generations
2. Program design
This section explains the program design of genetic algorithm and MATLAB Toolbox:
The adaptive values of individuals in P(t)P(t)P(t) P (T) P(t)P(t)P(t) P (T) P(t)P(t)P(t) P (T) P(t)P(t)P(t) P (T) P(t)P(t)P(t) P (T) P (T) were calculated
Begin t = 0 initialize P(t) calculate the fitness value of P(t) while(Not satisfied with the stopping critiria) do begin t += 1 choose P(t) from P(t+1) reassemble P(t) calculate the fitness value of P(t) end
[case]
Seeking function:
f(x)=9sin(5x)+8cos(4x), x∈[0,15]f(x) = 9sin(5x) + 8cos(4x),\ \ \ \ x \in [0,15]f(x)=9sin(5x)+8cos(4x), x∈[0,15]
The maximum value of
[solution]

initpop.m
initpop.m is used to initialize the population. popsize represents the population size, and chromlength represents the chromosome length. It depends on the binary encoding length of the variable
%Initialization function pop = initpop(popsize, chromlength) pop = round(rand(popsize, chromlength)); %rand The function randomly generates each element as {0,1} ,The number of rows is popsize ,The number of columns is chromlength Matrix %round Function to round every element in a matrix, So we have a random initial population end

decodechrom.m
Binary to decimal: the function of decodechrom.m is to convert chromosomes (binary encoding) to decimal
function pop2 = decodebinary(pop) [px,py] = size(pop); %seek pop Row,Column number for i = 1:py pop1(:,i) = 2.^(pyi).*pop(:,i); end pop2 = sum(pop1,2); %seek pop1 Elements and end %Intercept code length function pop2 = decodechrom(pop,spoint,length) pop1 = pop(:,spoint:spoint+length1); pop2 = decodebinary(pop1); end

calobjvalue.m
The function is to calculate the objective function
function[objvalue] = calobjvalue(pop) temp1 = decodechrom(pop,1,10); x = temp1*10/1023; objvalue = 10*sin(5*x)+7*cos(4*x); end

calfitvalue.m
The function is to calculate the fitness value of an individual
function fitvalue = calfitvalue(objvalue) global Cmin; Cmin = 0; [px,py] = size(objvalue); for i = 1:px if objvalue(i) + Cmin>0 temp = Cmin + objvalue(i); else temp = 0.0; end fitvalue(i) = temp; end fitvalue = fitvalue'

selection.m
The function function is to select replication. Selecting replication will determine which individuals can enter the next generation. The program uses roulette selection method to select individuals:
function [newpop] = selection(pop,fitvalue) totalfit = sum(fitvalue); %Calculate the sum of fitness values fitvalue = fitvalue/totalfit; %Calculate the probability of individual selection fitvalue = cumsum(fitvalue); [px,py] = size(pop); ms = sort(rand(px,1)); %Arrange from small to large fitin = 1; newin = 1; while newin <= px if(ms(newin))<fitvalue(fitin) newpop(newin) = pop(fitin); newin = newin + 1; else fitin = fitin + 1; end end

crossover.m
The function is to make every individual in the group cross with probability pc
function [newpop] = crossover(pop,pc) [px,py] = size(pop); newpop = ones(size(pop)); for i = 1:2:px1 if(rand<pc) cpoint = round(rand*py); newpop(i,:) = [pop(i,1:cpoint),pop(i+1,cpoint+1:py)]; newpop(i+1,:) = [pop(i+1,1:cpoint),pop(i,cpoint+1:py)]; else newpop(i,:) = pop(i); newpop(i+1,:) = pop(i+1); end end

mutation.m
The function is to realize mutation: every bit of every individual in the parent generation is flipped randomly with probability pm
function [newpop] = mutation(pop,pm) [px,py] = size(pop); newpop = ones(size(pop)); for i = 1:px if (rand<pm) mpoint = round(rand*py); if mpoint <=0 mpoint = 1; end newpop(i) = pop(i); if any(newpop(i,mpoint)) == 0 newpop(i,mpoint) = 1; else newpop(i,mpoint) = 0; end else newpop(i) = pop(i); end end

best.m
The function is to find out the maximum fitness and the most suitable individual
function [bestindividual,bestfit] = best(pop,fitvalue) [px,py] = size(pop); bestindividual = pop(1,:); bestfit = fitvalue(1); for i=2:px if fitvalue(i)>bestfit bestindividual = pop(i,:); bestfit = fitvalue(i); end end

main.m
Main program:
clc;clear all; popsize = 20; %Group size chromlength = 10; %String length pc = 0.7; %Crossover probability pm = 0.005; %Mutation probability pop = initpop(popsize, chromlength); for i = 1:20 [objvalue] = calobjvalue(pop); fitvalue = calfitvalue(objvalue); [newpop] = selection(pop,fitvalue); [newpop] = crossover(pop,pc); [newpop] = mutation(pop,pc); [bestindividual,bestfit] = best(pop,fitvalue); y(i) = max(bestfit); n(i) = i; pop5 = bestindividual; x(i) = decodechrom(pop5,1,chromlength)*10/1023; pop = newpop; end fplot('9*sin(5*x) + 8*cos(4*x)',[0 15]) hold on plot(x,y,'r*') hold off
Running the main program, the results are as follows: