[Path planning] Solve the shortest path planning problem based on matlab GUI ant colony algorithm [including Matlab source code 927]

[Path planning] Solve the shortest path planning problem based on matlab GUI ant colony algorithm [including Matlab source code 927]

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