A list,

1. Ant colony algorithm is proposed

Ant Colony Optimization algorithm (ACO), also known as ant algorithm, is a probabilistic algorithm used to find optimal paths. It was proposed by Marco Dorigo in his PhD thesis in 1992 and was inspired by the behavior of ants in finding their way to food. Genetic algorithm has been applied in pattern recognition, neural network, machine learning, industrial optimal control, adaptive control, biological science, social science and so on.

2. Basic principles of the algorithm





Ii. Source code

% Initialize clear; tic; % program running time t1=clock; alpha=1; % Pheromone importance parameter beta=5; % heuristic factor importance parameter rho=0.5; % pheromone evaporation coefficient Max =100; % Maximum number of iterations q=100; % pheromone increased intensity coefficient cityNum=50; % Problem size (number of cities) [disList,Clist]= TSP (cityNum); m=cityNum; % Ants Eta=1./dislist; %Eta is the heuristic factor, which is set as the reciprocal of distance Tau=ones(cityNum,cityNum); %Tau is the pheromone matrix Tabu= Zeros (M,cityNum); % stores and records path generation NC=1; % iteration counter R_best=zeros(Max,cityNum); % L_best=inf.*ones(Max,1); % L_ave=zeros(Max,1); % Average length of routes of each generation Figure (1);
whileNC<= Max % One of the stopping conditions: to reach the maximum number of iterations % put m ants on cityNum cities Randpos=[];for i=1: (ceil(m/cityNum))
        Randpos=[Randpos,randperm(cityNum)];
    end
    Tabu(:,1)=(Randpos(1.1:m))'; For j=2:cityNum for I =1:m visited=Tabu(I,1: j-1)); % Visited city J=zeros(1,(cityNum-j+1)); % City to be visited P=J; % Selection probability distribution of cities to be visited Jc=1; for k=1:cityNum if length(find(visited==k))==0 J(Jc)=k; Jc=Jc+1; For K =1:length(J) P(k)=(Tau(visited(end),J(k))^alpha)*(Eta(visited(end),J(k))^beta); end P=P/(sum(P)); % Select the next city according to probability principle Pcum=cumsum(P); Select=find(Pcum>=rand); to_visit=J(Select(1)); Tabu(i,j)=to_visit; end end if NC>=2 Tabu(1,:)=R_best(NC-1,:); End % records the optimal route of this iteration L=zeros(m,1); for i=1:m R=Tabu(i,:); L(i)=CalDist(dislist,R); end L_best(NC)=min(L); pos=find(L==L_best(NC)); R_best(NC,:)=Tabu(pos(1),:); L_ave(NC)=mean(L); drawTSP(Clist,R_best(NC,:),L_best(NC),NC,0); for i=1:m for j=1:(cityNum-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+q/L(i); end Delta_Tau(Tabu(i,cityNum),Tabu(i,1))=Delta_Tau(Tabu(i,cityNum),Tabu(i,1))+q/L(i); end Tau=(1-rho).*Tau+Delta_Tau; %pause; endCopy the code

3. Operation results



Fourth, note

Version: 2014 a