ANTS

clear all;

%cities2.txt
x = [0 2 6 7 15 12 14 9.5 7.5 0.5];
y = [1 3 5 2.5 -0.5 3.5 10 7.5 9 10];

City=10;  %number of cities
Ant=10;   %number of ants
Tour=10;  %number of tours
Vap=0.2;  %vaporation factor
alpha=1;
beta=5;

%calculating distances between cities and saving them in array
dystans=zeros(City);
for i=1:City
  for j=1:City
    dystans(i,j)=pdist([x(i),y(i);x(j),y(j)]);
  end
end

%calculating initial quantity of pheromone (same for all paths)
maxdist=max(max(dystans));
Pheromone=zeros(City);
for i=1:City
  for j=1:City
    Pheromone(i,j)=(1/maxdist);
  end
end

Info=zeros(Ant,2); %Table with starting and current position for every ant
%Randomly setting home towns for ants
for j=1:Ant
  Info(j,1)=randi([1,10]);
  Info(j,2)=Info(j,1);
end

%array with Distance made by each ant during each tour
Distances=zeros(Tour,Ant);

%main loop
for c_tour=1:Tour
  %array with already visitied cities for every ant during current tour
  Visited=zeros(Ant,City);
  %array with amount of pheromone left on paths by ants during current tour
  delta_Pheromone=zeros(City);
  %cities visited by each ant during current tour in order
  Order=zeros(Ant,City+1);

  for c_ant=1:Ant
    for c_city=1:City+1
      Visited(c_ant,Info(c_ant,2))=1;
      Order(c_ant,c_city)=Info(c_ant,2);

      if(c_city<=City) %when we still have cities to visit

        %calculating probability for choosing next city
        Nominator=zeros(City);
        Denominator=zeros(City,1);
        Prob=zeros(City);
        Prob_Denominator=zeros(City,1);
        A=zeros(City);
        for current=1:City
          for Destination=1:City
            if (Visited(c_ant,Destination)==0 )
              Nominator(current,Destination)=power(Pheromone(current,Destination),alpha)*power((1/dystans(current,Destination)),beta);
              Denominator(current)=Denominator(current)+Nominator(current,Destination);
            elseif (current==Destination)
              Nominator(current,Destination)=0;
            else (Visited(c_ant,Destination)~=0)
              Nominator(current,Destination)=0;
            end
          end
        end
        for current=1:City
          for Destination=1:City
            if (Nominator(current,Destination)==0)
              A(current,Destination)=0;
            else
              A(current,Destination)=Nominator(current,Destination)/Denominator(current);
            end
          end
        end
        for current=1:City
          for Destination=1:City
            Prob_Denominator(current) = Prob_Denominator(current) + A(current,Destination);
          end
        end
        for current=1:City
          for Destination=1:City
            if(A(current,Destination)~=0)
              Prob(current,Destination)=(A(current,Destination)/Prob_Denominator(current));
            end
          end
        end

        %choosing next city
        Decision = 0;
        X = 0;
        for Destination=1:City
          %if city was not visited
          if(Visited(c_ant,Destination)==0)
            if(Decision==0)
             X=X+Prob(Info(c_ant,2),Destination);
              if(X>rand)
                Decision=Destination;
                Distances(c_tour,c_ant)=Distances(c_tour,c_ant)+dystans(Decision,Info(c_ant,2));
                Info(c_ant,2)=Decision;
                break;
              end
            end
          end
        end

      else %when we visited all cities and we go back to homecity
        Distances(c_tour,c_ant)=Distances(c_tour,c_ant)+dystans(Info(c_ant,1),Info(c_ant,2));
        Decision=Info(c_ant,1);
        Info(c_ant,2)=Decision;
        Order(c_ant,c_city)=Decision;
      end
    end

    %calculating the amount of pheromone left on paths by each ant during current tour
    for i=2:City+1
      delta_Pheromone(Order(c_ant,i-1),Order(c_ant,i))=delta_Pheromone(Order(c_ant,i-1),Order(c_ant,i))+1/Distances(c_tour,c_ant);
      delta_Pheromone(Order(c_ant,i),Order(c_ant,i-1))=delta_Pheromone(Order(c_ant,i-1),Order(c_ant,i));
    end
  end
  %calculating the amount of pheromone on each path for next tour
  for i=1:City
    for j=1:City
      Pheromone(i,j)=(1-Vap)*Pheromone(i,j)+delta_Pheromone(i,j);
    end
  end
end

%Choosing best ant
BEST = 1;
for c_ant=1:Ant
  if(Distances(Tour,c_ant)<Distances(Tour,BEST))
    BEST = c_ant;
  end
end
Finaldistance=Distances(Tour,BEST);

x1 = zeros(11,1);
y1 = zeros(11,1);
  for i=1:(City+1)
      x1(i) = x(Order(BEST,i));
      y1(i) = y(Order(BEST,i));
   end

hold on
scatter(x,y, 'm')
a = [1:10]';
b = num2str(a);
c = cellstr(b);
text(x+0.1,y+0.1,c);
plot(x1,y1,'c');