Ant Colony Optimization (ACO) to solve traveling salesman problem (TSP)

This code presents a simple implementation of Ant Colony Optimization (ACO) to solve traveling salesman problem (TSP). TSP is an NP-hard (non-deterministic polynomial-time hard) problem in combinatorial optimization. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once. The problem was firstly formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization [Wikipedia]. I wrote this code as a mini project of one of my master course in KSU. I hope this code can help you to learn how to implement a simple ACO in Matlab.  I have received a lot of emails regarding this code (previously there are some missing parts in the code,  I have fix it). If you have a question please write in the comment.  (You can download this code from MATLAB central here)

Output:

MATLAB CODE (4 Files)

This is file#1: Main program of ACO (save as myaco.m) %************************************************************************** %                 Solving TSP Problem Using ACO % ————————————————————————- % By     : Sutrisno % Contact: xxxxx             Last update: May 2, 2011 % ————————————————————————- % This program is developed to find shortest path (minimum cost)between % some cities. % % There are 4  parts in this program: % 1.Main program of ACO (myaco.m) % 2.Function to generate solution (ant_tour.m) % 3.Function to calculate the cost (distance) (calculate_cost.m) % 4.Function to update the traces (update_the_trace.m) %************************************************************************** %************************************************************************** %                   The Program Start Here %*———————————————————————— % function  myaco(num_of_nodes,num_of_ants, max_iteration) function  myaco() % inputs miter=10; m=10; n=10; % parameters e=.15;            % evaporation coefficient. alpha=1;          % effect of ants’ sight. beta=4;           % trace’s effect. t=0.0001*ones(n); % primary tracing. el=.97;           % common cost elimination. % ————————————————————————- % Generate coordinates of cities and plot for i=1:n x(i)=rand*20; y(i)=rand*20; end subplot(3,1,1); plot(x,y,’o’,’MarkerFaceColor’,’k’,’MarkerEdgeColor’,’b’,’MarkerSize’,10); title(’Coordinates of Cities’); xlabel(’x  (km)’); ylabel(’y  (km)’); % generating distace between cities matrix. for i=1:n for j=1:n d(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2); end end % generating sight matrix. for i=1:n for j=1:n if d(i,j)==0 h(i,j)=0; else h(i,j)=1/d(i,j); end end end % ———————————————————————— %             Main Algorithm: ACO Meta heuristic procedure % a.  Probabilistic solution construction biased by %     pheromone trails, without forward pheromone %     updating % b.  Deterministic backward path with loop elimination %     and with pheromone updating–>update_the_trace % c.  Evaluation of the quality of the solutions %     generated and use of the solution quality in %     determining the quantity of pheromone to deposit–>calculate_cost % ————————————————————————- for i=1:miter % Step 1: Forward ants and solution construction % Generate places for each ant for j=1:m start_places(j,1)=fix(1+rand*(n-1)); end % Step 2:probabilistic solution contruction [tour]=ant_tour(start_places,m,n,h,t,alpha,beta); tour=horzcat(tour,tour(:,1)); % Step 3: Calculate the cost –> total distace [cost,f]=calculate_cost(m,n,d,tour,el); [t]=update_the_trace(m,n,t,tour,f,e); average_cost(i)=mean(cost); % Step 4: Determine the best route [min_cost(i),best_index]=min(cost); besttour(i,:)=tour(best_index,:); iteration(i)=i; end % ————————————————————————- % Plot Average of tour distance vs Number of Iterations subplot(3,1,2);plot(iteration,average_cost); title(’Average of tour distance vs Number of iterations’); xlabel(’iteration’); ylabel(’distance (km)’); % Plot the best route [k,l]=min(min_cost); for i=1:n+1 X(i)=x(besttour(l,i)); Y(i)=y(besttour(l,i)); end subplot(3,1,3);plot(X,Y,’–o’,… ‘MarkerEdgeColor’,’k’,… ‘MarkerFaceColor’,’g’,… ‘MarkerSize’,10) xlabel(’x (km)’);ylabel(’y (km)’); title([’minimum cost (total length)= ‘,num2str(k)]); end %************************************************************************** %                   Ending of Program %************************************************************************** This is m file # 2: (save as ant_tour.m ) %************************************************************************** %      Function to calculate ants tour matrix during one cycle %————————————————————————– %                     The function Start Here %————————————————————————– function [new_places]=ant_tour(start_places,m,n,h,t,alpha,beta); for i=1:m mh=h; for j=1:n-1 c=start_places(i,j); mh(:,c)=0; temp=(t(c,:).^beta).*(mh(c,:).^alpha); s=(sum(temp)); p=(1/s).*temp; r=rand; s=0; for k=1:n s=s+p(k); if r<=s start_places(i,j+1)=k; break end end end end new_places=start_places; %************************************************************************** %                   Ending of Function %**************************************************************************  This is m file # 3:  (save as calculate_cost.m) %************************************************************************** %      Function to calculate cost (distance) of ants’ touring %————————————————————————– %                     The function Start Here %————————————————————————– function [cost,f]=calculate_cost(m,n,d,at,el); for i=1:m s=0; for j=1:n s=s+d(at(i,j),at(i,j+1)); end f(i)=s; end cost=f; f=f-el*min(f); %************************************************************************** %                   Ending of Function %**************************************************************************   This is m file # 4:  (save as update_the_trace.m) %************************************************************************** %                    Function to update the traces %————————————————————————– %                     The function Start Here %————————————————————————– function [t]=update_the_trace(m,n,t,tour,f,e); for i=1:m for j=1:n dt=1/f(i); t(tour(i,j),tour(i,j+1))=(1-e)*t(tour(i,j),tour(i,j+1))+dt; end end %************************************************************************** %                   Ending of Function %**************************************************************************