# 1. Simulated Annealing 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];
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.2 Model and Algorithm

```%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%For formatting problems please use matlab Auto-align function%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clc,clear
x=sj0(:,1:2:8); x=x(:);
y=sj0(:,2:2:8); y=y(:);
sj=[x y]; d1=[70,40];
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.