Can "genetic mating" also be an algorithm? There is also matlab code?

is true, "genetic mating" can also be made into an algorithm. Think about it, in the evolutionary history of our human beings, the sea is our home! From the evolution of marine organisms to terrestrial organisms, from simple organisms to complex organisms... I can't help but think of the college entrance examination points for biology. Genes, chromosomes, mating, mutation... these all contribute to biological evolution. Perhaps it is an optimization algorithm derived from the evolution theory of Darwin -genetic algorithm ( Genetic Algorithm, referred to as GA ). This algorithm is currently the most easy to understand algorithm for me.

1. Introduction to genetic algorithm

Genetic algorithm was proposed by American professor John holland in around 1975. It is a random search based on natural selection and natural genetic mechanisms in the biological world. Algorithms have a vigorous atmosphere of "survival of the fittest" and "survival of the fittest". Genetic algorithms are commonly used to solve complex and nonlinear optimization problems that are difficult to solve by traditional search algorithms.

2. The core concept of genetic algorithm

Let me add some simple knowledge of the biology book:

Individual : This concept is very simple. The individual in, that is, the solution with a complete set of chromosomes.

Group : As a group, we humans can mate with each other. Under ideal circumstances, it is impossible for different groups to mate, that is, the evolutionary process between different groups does not interfere with each other. .

gene : A unit in a chromosome, which can also be called a characteristic component.

chromosome : In biology, it can be simply understood that chromosomes will change only when mating occurs, that is, only when mating, the chromosome types of the population will be more diversified and the population can evolve . In the genetic algorithm, it is interpreted as a vector or string formed by encoding according to the type of problem.

encoding method : There are binary encoding, floating-point number encoding, decimal encoding, ordered string encoding, structural encoding, etc. Like the TSP problem, it is related to the order of the cities visited, which is called ordered string coding.

fitness : fitness is calculated by fitness function, and its value indicates the degree of adaptation of the corresponding individual to the environment. The larger the value, the better it is.

selection : select excellent individuals from the current population according to a certain probability (selection probability), so that they have the opportunity to reproduce the next generation of offspring as parents. The greater the fitness of an individual, the greater the probability that it will be selected as the parent, and excellent genes will definitely be inherited! Next, introduce three selection methods!

(1) Roulette method: A roulette wheel is generated according to the individual's selection probability. The angle of each area of ​​the roulette is proportional to the individual's selection probability, and then a number from 0 to 1 is randomly generated, and the first in the roulette is selected. An individual that is larger than the random number, as shown in the figure below, the first random number is 0.81 , and the number 6 individual is selected, and the second random number is 0.32 , and the number 2 individual is selected.

(2) Championship method: randomly select several individuals from the group,Save the individuals with the highest fitness to the next generation. This process is repeated until the number of individuals saved to the next generation reaches a preset number

(3) The best individual preservation method group of individuals with the highest fitness is directly copied to the next generation without crossover. It is guaranteed that the final result obtained when the genetic algorithm is terminated must be the highest fitness individual in the past.

mutation : Similar to gene mutation in biology, the probability of performing mutation operation is called mutation operator. The following introduces 6 mutation methods in genetic algorithms.

(1) Locus variation: Individual code string in the population, randomly select one or more genes, and change the gene value of these genes with the mutation probability.

(2) Reverse transformation difference: randomly select two points (reversal points) in the individual code string, and then insert the gene values ​​between the two points into the original position in reverse order.

(3) Insertion mutation: randomly select a code in the individual code string, and then insert this code in the middle of the randomly selected insertion point.

(4) Interchange mutation: randomly select two genes of chromosome for simple interchange.

(5) Moving mutation: Randomly select a gene and move it to the left or right by a random number of digits.

(6) Adaptive mutation: similar to site mutation, but the mutation probability is adaptively adjusted according to the diversity of individuals in the population.

crossover : refers to the exchange of some genes between two paired chromosomes in a certain way to form two new individuals. Crossover operation is the key step of genetic algorithm to generate new individuals. The probability of performing crossover operation is called crossover operator. The main crossover methods are as follows:

(1) Single-point crossover: randomly set a crossover point in the individual string. When the crossover is performed, the partial structures of the two individuals before or after the point are exchanged, and two new ones are generated. Individual.

(2) Two-point cross: randomly set two cross points, and exchange the code strings between the two cross points.

(3) Uniform crossover: extract some bits according to the uniform probability,Whether each bit is selected is random and independent of other bits. Then the two individuals are exchanged to form two new individuals.

(4) Sequential crossing: randomly select the start and end positions in the two parent chromosomes, copy the gene in the region of the parent chromosome 1 to the same position in the offspring 1, and then place it on the parent chromosome 2. The missing genes in offspring 1 are filled in in order.

3. Genetic algorithm process

(1) Initialize GA parameters and randomly generate the initial population;

(2) Calculate the fitness value of each individual in the population;

(3) Select, cross, Mutation operation to generate a new population;

(4) whether the termination conditions are met, if yes, terminate, otherwise jump to (2);

(5) output the optimal solution;

4. Example and its matlab code

In order to explain the genetic algorithm more specifically, the same trick is to use it to solve the TSP problem. A person starts from one city, traverses all the given cities, and makes the overall travel distance as short as possible. The coordinate distribution map of the city is shown below.

  function TSP_gaout = TSPGA(xy,dmat,popSize,IterNum,showProg,showResult)%Using genetic algorithm to solve TSP problem tStart = tic;% algorithm timer nargs = 6;for i = nargin:nargs -1 %nargin represents the number of input parameters of the function switch i case 0% produces city coordinates% xy = round(500*rand(40,2));% randomly generates 40 city coordinates xy =(307,415;5,429;287,395; 395,159;118,226;224,376;285,55;31,55; 248,135;321,262;111,486;419,355;486,156;423,146;253,425;139,456; 373,320;118,128;479,44;310,419;300,292;86,474;45,31;128,292; 429,143; 456,414;350,95;363,221;115,197;288,413;405,338;202,104;494,159;45,67; 160,336;256,285;30,85;363,74;278,238;265,454]; case 1 %Calculate distance matrix N = size (xy,1); a =meshgrid(1:N);% Generate N*N ascending matrix dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2, 2)),N,N);%'is the transpose of the matrix, reshape  generate a N*N matrix from the data case 2% set the population size popSize = 100; case 3% set the number of algorithm iterations IterNum = 1e3; case 4% whether to show the iteration process showProg = 1; case 5% whether to show the final result showResult =1; otherwise endend% Check the input parameters [N,~] ​​= size(xy);% number of cities, dimension [nr,nc] = size(dmat);% number of rows and columns of distance matrix if N~=nr || N~=nc error('City coordinates or distance matrix input error') endshowProg = logical(showProg(1));% convert the value to a logical value showResult = logical(showResult(1)) ;% Draw the city location distribution map figure(1); plot (xy(:,1),xy(:,2),'k.','MarkerSize',14);title('City coordinate location'); %% GA operator, parameter setting SelectRate = 0.5;% selection probability crossRate = 0.9;% cross-probability mutationRate = 0.1;% mutation probability global_min = Inf; %Inf means infinity popRoute = zeros(popSize,N);% stores population individuals Path offspring = zeros(popSize,N);% store the offspring population totaldist = zeros(1, popSize);% record the path length of each individual minLhistory = zeros(IterNum,1);% store the optimal path in each generation of the population Length subPath = zeros(1,N);% offspring "son" BestPath = zeros(1,N);% record the best individual for i =1:popSize popRoute(i,:) = randperm(N); %initialization Population,Randomly generate route end%% population evolution for iter = 1: IterNum% calculate the path length and shortest length path of each individual in the population for i = 1: popSize d = 0; for j = 1: (N-1) d = d + dmat(popRoute(i,j),popRoute(i,j+1));% calculate the distance from the start to the end of the path end totaldist(1,i) = d + dmat(popRoute(i,N),popRoute(i ,1));% plus the straight-line distance from the end point to the starting point end [minPath,index] = min(totaldist);% find the shortest path length minPath, index minLhistory(iter,1) = minPath; %% draw Iterative process if minPath = random % If the crossover probability is greater than the random number,Then do the cross operation [~,length] = size(parent1Path); subPath = zeros(1,length); setsize = floor(length/2) -1; offset = randi(setsize);%% randomly generate two inserts Point for i = offset:setsize+offset-1 subPath(1,i) = parent1Path(1,i);% assign the middle segment gene of parent 1 to the offspring end iterator = i+1; j = iterator; while any(subPath == 0)% continues until all offspring genes are not 0 if j>length j =1; end if iterator> length iterator =1; end if ~any(subPath == parent2Path(1,j) )% Transfer the gene from parent 2 to the offspring without repeating subPath(1,iterator) = parent2Path(1,j); iterator = iterator+1; end j = j+1; endelse %If the random number is greater than Crossover probability, no crossover operation subPath = parent1Path; endend%% mutation operation function function subPath = mutate(subPath, mutationRate) random = rand;% generates a random number from 0 to 1 if mutationRate>=random% The mutation probability is greater than the random number Then mutation occurs [~,n] = size(subPath); C = ceil(n*rand(1,2));% randomly generates two random numbers C = sort(C);% ascending order subPath(1,[ C(2),C(1)]) = subPath(1,[C(1),C(2)]);% transfer the locations of the two cities else subPath =subPath ;endend  _pre1 The comments in the 37pre 
 code are relatively detailed,So I won’t explain if there are too many words. If you don’t understand, please discuss in the comments, or send me a private message, and directly upload the result picture. 
 
  
 
 
 
  
 
 
 
 If you have friends who are more interested in the robot task allocation algorithm, you can comment and exchange the wave below, it is pure learning from each other! 
.