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

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:

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: sutrisno_link@yahoo.com             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 %**************************************************************************

33 thoughts on “Ant Colony Optimization (ACO) to solve traveling salesman problem (TSP)

  1. Pingback: Kuliah Artificial Intelligence (Kecerdasan Buatan) | Sutrisno W. Ibrahim

  2. Hi, thanks for the files but there are some errors I get.
    1. I copied the main program into matlab m file and named it myaco.
    2. I copied the subsequent files and has 4 files all in .m.
    3. I opened myaco.m and run it.
    4. I get the error:
    ??? Input argument “max_iteration” is undefined.

    Error in ==> myaco at 3
    miter = max_iteration;
    Note all the files ar in the same working directory.

    I am new to matlab, may you kindly assist me. I want to understand the code so that i can implement MMAS. Can send reply to chagwizag@gmail.com

  3. Actually, there is no error in your code. To run the code just write in the Matlab command window :
    >> myaco(10,10,10) (then ENTER)

    You will get the results.

    Or to make simple, just modify the beginning of the program become:
    % function myaco(num_of_nodes,num_of_ants, max_iteration)
    function myaco()
    % inputs
    miter=10;
    m=10;
    n=10;

    • MATLAB CODE
      ‎%**************************************************************************‎
      ‎% Minimize Periodical Function using GAs‎
      ‎% ————————————————————————-‎
      ‎% By : Sutrisno‎
      ‎% Contact: sutrisno_link@yahoo.com Last update: April 19, 2011‎
      ‎% ————————————————————————- ‎
      ‎% This program is developed to find minimal value of periodical function: ‎
      ‎% f(x)=tan(sin(x))-sin(tan(x))‎
      ‎% ‎
      ‎% There are 3 parts in this program:‎
      ‎% 1.Main program of GAs (ga1.m)‎
      ‎% 2.Function definition (objfunction.m)‎
      ‎% 2.Plotting the function (plotting.m)‎
      ‎% 3.Plotting the results (rplotting.m)‎
      ‎%**************************************************************************‎
      ‎ ‎
      ‎%**************************************************************************‎
      ‎% The Program Start Here ‎
      ‎%*————————————————————————‎
      function ga1‎
      clear all;‎
      clc;‎
      ‎ ‎
      ‎% GA‎
      options = gaoptimset(@ga);‎
      options = gaoptimset(‘PopulationSize’,100,…‎
      ‎ ‘SelectionFcn’,@selectionstochunif,…‎
      ‎ ‘CrossoverFraction’,0.8,…‎
      ‎ ‘Generations’,100,…‎
      ‎ ‘PlotFcns’,@gaplotbestf);‎
      ‎ ‎
      ‎ [r, fval, reason, output, population, scores] = …‎
      ‎ ga(@objfunction,1,[],[],[],[],-3.14,3.14,[],options);‎
      ‎% result‎
      rplotting(r)‎
      end
      ‎%**************************************************************************‎
      ‎% Ending of Program ‎
      ‎%**************************************************************************‎

      File: obcjfunctio.m
      ‎%**************************************************************************‎
      ‎% The Program Start Here ‎
      ‎%*————————————————————————‎
      ‎% Objectif Function: y = tan(sin(x)) – sin(tan(x));‎
      function y = obcjfunction(x)‎
      y = tan(sin(x)) – sin(tan(x));‎
      end
      ‎%**************************************************************************‎
      ‎% Ending of Program ‎
      ‎%**************************************************************************‎
      File: plotting.m
      ‎%**************************************************************************‎
      ‎% The Program Start Here ‎
      ‎%*————————————————————————‎
      function plotting
      x= -10.14:0.1:10.14;‎
      y=objfunction(x);‎
      plot(x,y)‎
      xlabel(‘x (rad)’);‎
      ylabel(‘f(x)’);‎
      title(‘Function f(x)=tan(sin(x))-sin(tan(x))’)‎
      grid on
      end
      ‎%**************************************************************************‎
      ‎% Ending of Program ‎
      ‎%**************************************************************************‎

      File: rplotting.m
      ‎%**************************************************************************‎
      ‎% The Program Start Here ‎
      ‎%*————————————————————————‎
      function rplotting(r)‎
      x= -3.14:0.025:3.14;‎
      y=objfunction(x);‎
      plot(x,y)‎
      xlabel(‘x (rad)’);‎
      ylabel(‘f(x)’);‎
      title(‘Function f(x)=tan(sin(x))-sin(tan(x))’)‎
      hold on
      plot(r,objfunction(r),’o’)‎
      text(1.0,- 1.75,[‘at x =’,num2str(r)])‎
      text(1.0,-1.5,[‘minimum value=’,num2str(objfunction(r))])‎
      hold off
      end
      ‎%**************************************************************************‎
      ‎% Ending of Program ‎
      ‎%**************************************************************************‎

    • You can extract the sequence of cities from the coordinate of each city in the XY. The coordinate of the first city is X(1)Y(1), and the last is X(n)Y(n).

      See:
      % 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

  4. hi..assalamualaikum, i got error at
    ??? Error using ==> plot
    Error in color/linetype argument

    Error in ==> myaco at 193
    plot(X,Y,’–o’,’MarkerEdgeColor’,’k’,’MarkerFaceColor’,’g’,’MarkerSize’,10)

    can u please guide me to embed this aco into my own path. i already hve the path and i want to use aco to find the shortest path. how can i embed the path into ur code? tq

  5. Hi, I have a question. What is
    -t=0.0001*ones(n); % primary tracing.
    -el=.97; % common cost elimination.
    exactly mean, why we use this? I have a problem to recognize it. Please explain it like to damn🙂 Thank you very much

  6. Hi, I have a big promis… I have a matrix with 3 cities (0,15,59;15,0,47;59,47,0), only one ant… please, please please, could you create solution for this in matlab? I would be realy realy grateful….

  7. in my_aco file [ start_places(j,1) ] has order j*1 but how do you use this matrix in ant_tour file as [c=start_places(i,j); ] i.e. i*j

    in my file its showing error as “Attempted to access start_places(1,2); index out of bounds because size(start_places)=[10,1].”

    why this is occuring… plzz help i am new in matlab

  8. Hello,

    Could you tell me what exactly does this do?
    d(at(i,j),at(i,j+1))

    Because when I execute this in Scilab, it gives me an index error

  9. >> myaco(10,10,10)
    ??? Error using ==> myaco
    Too many input arguments.

    am getting this error… am completely new to MATLAB Coding… so please help

  10. thank you for the ACO codes of TSP and i need some help for mobile robot path planning using Ant Colony System.

  11. Hi, in function ant_tour.m, can i know what do you refer by mh=h? and why we need to set r=rand. thank you.

  12. Hi.by using the code bestour(1:i),=tour(best_index), i will get the matrix of bestour..how we can know which one is the best tour?tq..

  13. Hi, thank you for this ACO codes.
    Can i ask you something? what algorithms of ACO do you used in this code? Ant System (AS) or Ant Colony System (ACS)?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s