## 1. Introduction

1 The origin and development of ant colony algorithm (ACA)

. In the process of researching new algorithms, Marco Dorigo and others found that when ant colonies are looking for food, they exchange foraging information by secreting a biological hormone called pheromone. So that the target can be found quickly, so in his doctoral thesis in 1991, he first systematically proposed a new intelligent optimization algorithm based on ant population "Ant system (AS)". Later, the proponent and many researchers Various improvements have been made to the algorithm and applied to a wider range of fields, such as coloring problems, secondary allocation problems, workpiece sequencing problems, vehicle routing problems, job shop scheduling problems, network routing problems, and large-scale integrated circuits. Design etc. In recent years, M.Dorigo and others have further developed the ant algorithm into a general optimization technology "Ant Colony Optimization (ACO)", and called all algorithms that conform to the ACO framework "Ant Colony Optimization Algorithm" ACO algorithm)".

Specifically, each ant started looking for food without telling where the food was in advance. When a person finds food, it releases a volatile secretion pheromone (called pheromone, which will gradually evaporate and disappear over time. The concentration of pheromone indicates the distance of the path). Let other ants perceive and play a guiding role. Generally, when there are pheromone on multiple paths, the ants will preferentially select the path with high pheromone concentration, so that the path with high concentration has higher pheromone concentration, forming a positive feedback. Some ants do not always repeat the same path like other ants. They will find another way. If the new road is shorter than the original other roads, then gradually, more ants will be attracted to this shorter road. . Finally, after running for a period of time, there may be a shortest path repeated by most ants. In the end, the path with the highest pheromone concentration is the optimal path ultimately selected by the ants.

Compared with other algorithms, ant colony algorithm is a relatively young algorithm. It has the characteristics of distributed computing, no central control, asynchronous and indirect communication between individuals, and is easy to combine with other optimization algorithms. Exploring, a variety of improved ant colony algorithms have been developed to this day, but the principle of ant colony algorithm is still the backbone.

2 The solution principle of the ant colony algorithm

Based on the above description of the foraging behavior of the ant colony, the algorithm mainly simulates the foraging behavior in the following aspects:

(1) The simulated picture scene contains two kinds of pheromone, one is a representation Home, a place that represents food, and both pheromones are evaporating at a certain rate.

(2) Each ant can only perceive information in a small part of its surroundings. When ants are looking for food, if they are within the range of perception, they can go directly. If they are not within the range of perception, they have to move towards a place with a lot of pheromone. There is a small probability that the ant will not go to a place with a lot of pheromones. Taking another approach, this small probability event is very important, represents a way-finding innovation, and is important for finding a better solution.

(3) The rules for ants returning to their nest are the same as those for finding food.

(4) When the ant moves, it will first follow the guidance of the pheromone. If there is no guidance of the pheromone, it will go inertially according to its own moving direction, but there is a certain chance to change its direction. The ant can also remember the way it has traveled. , To avoid repeating one place.

(5) Ants leave the most pheromones when they find food, and then the farther away the food is, the less pheromones are left. The rules for finding the amount of pheromone left in the nest are the same as food. Ant colony algorithm has the following characteristics: positive feedback algorithm, concurrency algorithm, strong robustness, probabilistic global search, not relying on strict mathematical properties, long search time, and easy to stop.

Ant transfer probability formula: In the

formula: is the probability of ant k transferring from city i to j; and are the relative importance of pheromone and heuristic factor respectively; is the amount of pheromone on edge (i, j); is Heuristic factor; is the city that ant k is allowed to choose in the next step. The above formula is the pheromone update formula in the ant system, which is the amount of pheromone on the edge (i, j); is the pheromone evaporation coefficient, 0< <1; is the kth ant staying in this iteration The amount of pheromone on the edge (i, j); Q is a normal coefficient; is the path length of the k-th ant in this trip.

In the ant system, the pheromone update formula is:

3 Solving steps of the ant colony algorithm:

(1) Initialization parameters At the beginning of calculation, relevant parameters need to be initialized, such as ant colony size (number of ants) m, pheromone importance factor , heuristic function importance factor , pheromone will send silver , pheromone Release the total amount Q, the maximum number of iterations iter_max, and the initial value of the number of iterations iter=1.

(2) Construct a solution space and place each ant randomly at a different starting point. For each ant k (k=1,2,3...m), calculate the next city to be visited according to (2-1) until all ants are The ants have visited all the cities.

(3) Update information Su calculate the length of each ant's path Lk (k=1,2,...,m), and record the optimal solution (shortest path) in the current iteration times. At the same time, according to formula (2-2) and (2-3), the pheromone concentration on the connection path of each city is updated.

(4) Determine whether to terminate. If iter<iter_max, set iter=iter+1, clear the record table of the ant's path, and return to step 2; otherwise, terminate the calculation and output the optimal solution.

(5) Determine whether to terminate. If iter<iter_max, set iter=iter+1, clear the record table of the ant's path, and return to step 2; otherwise, terminate the calculation and output the optimal solution. 3. Determine whether to terminate. If iter<iter_max, set iter=iter+1, clear the record table of the ant's path, and return to step 2; otherwise, terminate the calculation and output the optimal solution.

## 2. the source code

```
function varargout = untitled(varargin)
% UNTITLED MATLAB code for untitled.fig
% UNTITLED, by itself, creates a new UNTITLED or raises the existing
% singleton*.
%
% H = UNTITLED returns the handle to a new UNTITLED or the handle to
% the existing singleton*.
%
% UNTITLED( 'CALLBACK' ,hObject,eventData,handles,...) calls the local
% function named CALLBACK in UNTITLED.M with the given input arguments.
%
% UNTITLED( 'Property' , 'Value' ,...) creates a new UNTITLED or raises the
% existing singleton*. Starting from the left, property value pairs are
% applied to the GUI before untitled_OpeningFcn gets called. An
% unrecognized property name or invalid value makes property application
% stop. All inputs are passed to untitled_OpeningFcn via varargin.
%
% *See GUI Options on GUIDE ' s Tools menu. Choose "GUI allows only one
% instance to run (singleton)" .
%
% See also: GUIDE, GUIDATA, GUIHANDLES
% Edit the above text to modify the response to help untitled
% Last Modified by GUIDE v2 .5 24 -May -2021 11 : 38 : 42
% Begin initialization code-DO NOT EDIT
gui_Singleton = 1 ;
gui_State = struct( 'gui_Name' , mfilename, ...
'gui_Singleton' , gui_Singleton, ...
'gui_OpeningFcn' , @untitled_OpeningFcn, ...
'gui_OutputFcn' , @untitled_OutputFcn, ...
'gui_LayoutFcn' , [] ,. ..
'gui_Callback' , []);
if nargin && ischar (varargin{ 1 })
gui_State.gui_Callback = str2func(varargin{ 1 });
end
if nargout
[varargout{ 1 :nargout}] = gui_mainfcn(gui_State, varargin{:});
else
gui_mainfcn(gui_State, varargin{:});
end
% End initialization code-DO NOT EDIT
% --- Executes just before untitled is made visible.
function untitled_OpeningFcn (hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject handle to figure
% eventdata reserved-to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% varargin command line arguments to untitled (see VARARGIN)
% Choose default command line output for untitled
handles.output = hObject;
% Update handles structure
guidata (hObject, handles) ;
% UIWAIT makes untitled wait for user response (see UIRESUME)
% uiwait ( handles.figure1 ) ;
% --- Outputs from this function are returned to the command line.
function varargout = untitled_OutputFcn(hObject, eventdata, handles)
% varargout cell array for returning output args (see VARARGOUT);
% hObject handle to figure
% eventdata reserved-to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
% Get default command line output from handles structure
varargout { 1 } = handles.output ;
% --- Executes on button press in pushbutton1.
function pushbutton1_Callback (hObject, eventdata, handles)
% hObject handle to pushbutton1 (see GCBO)
% eventdata reserved-to be defined in a future version of MATLAB
% handles structure with handles and user data (see GUIDATA)
%function main ()
G =[ 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ;
0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 ;
0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 ;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 ;
0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 ;
0 1 1 1 1 1 0 1 1 1 1 0 0 0 00 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ;
0 1 1 1 0 0 1 0 ;
0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 ;
0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 ;
0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 ;
0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 ;
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 ;
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 ;
1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 ;
1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 ;
0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 ;
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 ;
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 ;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 ;];
MM=size(G, 1 );% G topographic map is 01 matrix, 1 means obstacle
Tau=ones(MM*MM,MM*MM);% Tau initial pheromone matrix
Tau = 8. *Tau;
K= 200 ;% K iteration number (referring to how many waves the ants send out)
M = 80 ;% number of ants
%S = 1 ;% starting point of the shortest path
%S=str2num(mat2str(cell2mat(get(handles.edit1, 'string' ))));
%E=str2num(mat2str(cell2mat(get(handles.edit2, 'string' ))));
S=str2num(get(handles.edit1, 'string' ));
E=str2num(get(handles.edit2, 'string' ));
%E=MM*MM;% Destination point of the shortest path
Alpha = 1 ;% Alpha is a parameter that characterizes the importance of pheromone
Beta = 8 ;% Beta is a parameter that characterizes the importance of heuristic factors
Rho = 0.4 ;% Rho pheromone evaporation coefficient
Q = 1 ;% Q pheromone increase intensity coefficient
minkl=inf;
mink = 0 ;
minl = 0 ;
D=G2D(G);
N=size(D, 1 ); %N represents the size of the problem (number of pixels)
a = 1 ;% side length of small square pixels
Ex=a*(mod(E,MM) -0.5 );% abscissa of end point
if Ex== -0.5
Ex=MM -0.5 ;
end
Ey=a*(MM+ 0.5 - ceil (E/MM));% ordinate of end point
Eta=zeros(N);% heuristic information, taken as the reciprocal of the straight-line distance to the target point
% Following heuristic information matrix
for i = 1 :N
ix=a*(mod(i,MM) -0.5 );
if ix== -0.5
ix=MM -0.5 ;
end
iy=a*(MM+ 0.5 - ceil (i/MM));
if i~=E
Eta(i) = 1/((ix-Ex)^ 2 + (iy-Ey)^ 2 )^ 0.5 ;
else
Eta(i) = 100 ;
end
end
ROUTES=cell(K,M);% uses the cell structure to store the crawling route of each ant in each generation
PL=zeros(K,M); %Use a matrix to store the crawling route length of each ant in each generation
%Start K rounds of ant foraging activities, dispatch M ants in each round
for k = 1 :K
for m = 1 :M
% State initialization
W=S; %The current node is initialized as the starting point
Path=S;% Initialization of crawling route
PLkm = 0 ;% initialization of crawling route length
TABUkm=ones(N);% taboo table initialization
TABUkm(S) = 0 ;% is already at the initial point, so it must be excluded
DD=D;% adjacency matrix initialization
% Nodes you can go to next
DW=DD(W,:);
DW1=find(DW);
for j = 1 :length(DW1)
if TABUkm(DW1(j))== 0
DW(DW1(j))= 0 ;
end
end
LJD=find(DW);
Len_LJD=length(LJD);%The number of optional nodes
%The ants did not encounter food or fell into a dead end or stopped foraging
while W~=E&&Len_LJD>= 1
%Roller gambling method to choose the next step
PP=zeros(Len_LJD);
for i = 1 :Len_LJD
PP(i)=(Tau(W,LJD(i))^Alpha)*((Eta(LJD(i)))^Beta);
end
sumpp=sum(PP);
PP=PP/sumpp;% establish probability distribution
Pcum( 1 )=PP( 1 );
for i= 2 :Len_LJD
Pcum(i)=Pcum(i -1 )+PP(i);
end
Select=find(Pcum>=rand);
to_visit=LJD(Select( 1 ));
% Status updates and records
Path=[Path,to_visit];% path increase
PLkm=PLkm+DD(W,to_visit);% path length increase
W=to_visit;% ants move to the next node
for kk = 1 :N
if TABUkm(kk) == 0
DD(W,kk) = 0 ;
DD(kk,W) = 0 ;
end
end
TABUkm (W) = 0 ;% visited nodes are deleted from the taboo table
DW=DD(W,:);
DW1=find(DW);
for j = 1 :length(DW1)
if TABUkm(DW1(j))== 0
DW(j)= 0 ;
end
end
LJD=find(DW);
Len_LJD=length(LJD);%The number of optional nodes
end
% Write down the foraging route and route length of each ant in each generation
ROUTES{k,m}=Path;
if Path (end) ==E
PL(k,m)=PLkm;
if PLkm<minkl
mink=k;minl=m;minkl=PLkm;
end
else
PL (k,m) = 0 ;
end
end
Copy code
```

## 3. running results

## 4. remarks

Version: 2014a