"Mathematical Modeling Algorithms and Applications Second Edition" - chapter12. Modern Optimization Algorithms

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.