1. Simulated Annealing Algorithm
1.1 Introduction to the algorithm
1.2 Application example
clc, clear sj0=load('sj.txt'); %Load the data of 100 targets, and save the data in a plain text file according to the position in the table sj.txt middle x=sj0(:,[1:2:8]);x=x(:); y=sj0(:,[2:2:8]);y=y(:); sj=[x y]; d1=[70,40]; sj=[d1;sj;d1]; sj=sj*pi/180; %angle into radian d=zeros(102); %distance matrix d initialization for i=1:101 for j=i+1:102 d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2))); end end d=d+d'; path=[];long=inf; %Cruise path and length initialization rand('state',sum(clock)); %Initialize the random number generator for j=1:1000 %find a better initial solution path0=[1 1+randperm(100),102]; temp=0; for i=1:101 temp=temp+d(path0(i),path0(i+1)); end if temp<long path=path0; long=temp; end end e=0.1^30;L=20000;at=0.999;T=1; for k=1:L %Annealing process c=2+floor(100*rand(1,2)); %generate new solutions c=sort(c); c1=c(1);c2=c(2); %Calculate the increment of the cost function value df=d(path(c1-1),path(c2))+d(path(c1),path(c2+1))-d(path(c1-1),path(c1))-d(path(c2),path(c2+1)); if df<0 %acceptance criteria path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long=long+df; elseif exp(-df/T)>rand path=[path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long=long+df; end T=T*at; if T<e break; end end path, long % Output cruise path and path length xx=sj(path,1);yy=sj(path,2); plot(xx,yy,'-*') %draw the cruise path
The calculation result is about 44h.
2. Genetic Algorithm
2.1 Introduction to the algorithm
2.2 Model and Algorithm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %For formatting problems please use matlab Auto-align function% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clc,clear sj0=load('sj.txt'); %Load data for 100 targets x=sj0(:,1:2:8); x=x(:); y=sj0(:,2:2:8); y=y(:); sj=[x y]; d1=[70,40]; sj=[d1;sj;d1]; sj=sj*pi/180; %Units in radians d=zeros(102); %distance matrix d the initial value of for i=1:101 for j=i+1:102 d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2))); end end d=d+d'; w=50; g=100; %w is the number of species, g algebra for evolution rand('state',sum(clock)); %Initialize the random number generator for k=1:w %Select initial population by improved circle algorithm c=randperm(100); %yields 1,...,100 a full permutation of c1=[1,c+1,102]; %generate initial solution for t=1:102 %The layer loop is the modification circle flag=0; %Modify circle exit sign for m=1:100 for n=m+2:101 if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1)) c1(m+1:n)=c1(n:-1:m+1); flag=1; %Modify circle end end end if flag==0 J(k,c1)=1:102; break %Record the better solution and exit the current layer loop end end end J(:,1)=0; J=J/102; %Convert a sequence of integers to[0,1]Real numbers on the interval, i.e. converted into chromosome codes for k=1:g %This layer loops through the operation of the genetic algorithm A=J; %mating to produce offspring A the initial chromosome c=randperm(w); %Generate the chromosome pairs for the following crossover operation for i=1:2:w F=2+floor(100*rand(1)); %The address that generates the crossover operation temp=A(c(i),[F:102]); %save value of intermediate variable A(c(i),[F:102])=A(c(i+1),[F:102]); %crossover A(c(i+1),F:102)=temp; end by=[]; %In order to prevent the generation of empty addresses below, initialize here first while ~length(by) by=find(rand(1,w)<0.1); %The address of the mutating operation end B=A(by,:); %The initial chromosome that generates the mutation operation for j=1:length(by) bw=sort(2+floor(100*rand(1,3))); %3 addresses that generate mutation operations B(j,:)=B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]); %swap places end G=[J;A;B]; %Parent and child populations combined [SG,ind1]=sort(G,2); %translate chromosome into 1,...,102 the sequence of ind1 num=size(G,1); long=zeros(1,num); %initial value of path length for j=1:num for i=1:101 long(j)=long(j)+d(ind1(j,i),ind1(j,i+1)); %Calculate the length of each path end end [slong,ind2]=sort(long); %Sort path lengths from smallest to largest J=G(ind2(1:w),:); %Before Featured w chromosomes corresponding to shorter paths end path=ind1(ind2(1),:), flong=slong(1) %Solution path and path length xx=sj(path,1);yy=sj(path,2); plot(xx,yy,'-o') %draw the path
3. Improved Genetic Algorithm
3.1 Introduction
The UAV route planning problem is actually a combinatorial optimization problem, which is an NP-hard problem in optimization theory. Because the solution space is discontinuous and the solution neighborhood is difficult to express, it is difficult to solve it with the usual algorithm. As one of the modern optimization algorithms, the genetic algorithm is mainly characterized in that it can jump out of the local optimal solution with probability 1 and find the global optimal solution for nonlinear extreme value problems. The genetic algorithm, which jumps out of the local optimum to find the global optimum, is based on the crossover and mutation in the algorithm. In the structure of the traditional genetic algorithm, the mutation operation is carried out on the basis of the crossover operation, emphasizing the crossover effect, and considering that the mutation is only a biological background mechanism. In specific crossover operations, people usually use single-point crossover (segment crossover), multi-point crossover and uniform crossover, where single-point crossover refers to randomly selecting a breakpoint in the gene sequence, and then exchanging all the right ends of the breakpoint on the parents. chromosome. In the mutation operation, the mutation operator is generally implemented by random mutation of the Guassian distribution. In recent years, some scholars have also tried to use the random sequence of the Cauchy distribution to achieve mutation, hoping to achieve a wider range of mutation through the wide wings of the Cauchy distribution, in order to find the global optimal solution. Rudolph theoretically analyzes the local convergence of the random mutation evolution algorithm using Cauchy distribution. Chelapilla further combines the two, using the linear superposition of the two distributions, but the simulation results show that the algorithm improvement effect is not very obvious. The biological evolution is regarded as randomness plus feedback, and it is pointed out that the randomness is mainly caused by the internal factors of the system, rather than by the random disturbance of the external environment. The chaotic system shows randomness in its chaotic domain, which is a reflection of the internal randomness of the determined system, which is different from the external randomness. This section improves the genetic algorithm based on solving route planning according to the above characteristics. First, the mutation operation is separated from the crossover operation, making it an independent optimization operation that is parallel to the crossover. In the specific genetic operation, chaos and genetic operation Linked together, in the crossover operation, the pairing of individuals is carried out according to the principle of "pairing with each other", using the chaotic sequence to determine the crossover point, and implementing the single-point crossover with the weakest strength to ensure the convergence accuracy of the algorithm, weaken and avoid the problem of optimization chattering; In mutation operation, chaotic sequences are used to mutate multiple genes in chromosomes to avoid premature algorithm.
3.2 Model and Algorithm
4. matlab Genetic Algorithm Toolbox
4.1 Overview of Genetic Algorithms and Search Toolbox
4.2 Preliminary Use of Genetic Algorithm Toolbox
4.3 Direct Search Tool
Original textbook exercises and codes
Click to download [textbook + source code] Extraction code: 92h8