paryz17

ANTS

Dec 3rd, 2019
662
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. clear all;
  2.  
  3. %cities2.txt
  4. x = [0 2 6 7 15 12 14 9.5 7.5 0.5];
  5. y = [1 3 5 2.5 -0.5 3.5 10 7.5 9 10];
  6.  
  7. City=10;  %number of cities
  8. Ant=10;   %number of ants
  9. Tour=10;  %number of tours
  10. Vap=0.2;  %vaporation factor
  11. alpha=1;  
  12. beta=5;
  13.  
  14. %calculating distances between cities and saving them in array
  15. dystans=zeros(City);
  16. for i=1:City
  17.   for j=1:City
  18.     dystans(i,j)=pdist([x(i),y(i);x(j),y(j)]);
  19.   end
  20. end
  21.  
  22. %calculating initial quantity of pheromone (same for all paths)
  23. maxdist=max(max(dystans));
  24. Pheromone=zeros(City);
  25. for i=1:City
  26.   for j=1:City
  27.     Pheromone(i,j)=(1/maxdist);
  28.   end
  29. end
  30.  
  31. Info=zeros(Ant,2); %Table with starting and current position for every ant
  32. %Randomly setting home towns for ants
  33. for j=1:Ant
  34.   Info(j,1)=randi([1,10]);
  35.   Info(j,2)=Info(j,1);
  36. end
  37.  
  38. %array with Distance made by each ant during each tour
  39. Distances=zeros(Tour,Ant);  
  40.  
  41. %main loop
  42. for c_tour=1:Tour
  43.   %array with already visitied cities for every ant during current tour
  44.   Visited=zeros(Ant,City);
  45.   %array with amount of pheromone left on paths by ants during current tour
  46.   delta_Pheromone=zeros(City);
  47.   %cities visited by each ant during current tour in order
  48.   Order=zeros(Ant,City+1);
  49.  
  50.   for c_ant=1:Ant
  51.     for c_city=1:City+1
  52.       Visited(c_ant,Info(c_ant,2))=1;
  53.       Order(c_ant,c_city)=Info(c_ant,2);
  54.      
  55.       if(c_city<=City) %when we still have cities to visit
  56.      
  57.         %calculating probability for choosing next city
  58.         Nominator=zeros(City);
  59.         Denominator=zeros(City,1);
  60.         Prob=zeros(City);
  61.         Prob_Denominator=zeros(City,1);
  62.         A=zeros(City);
  63.         for current=1:City
  64.           for Destination=1:City
  65.             if (Visited(c_ant,Destination)==0 )
  66.               Nominator(current,Destination)=power(Pheromone(current,Destination),alpha)*power((1/dystans(current,Destination)),beta);
  67.               Denominator(current)=Denominator(current)+Nominator(current,Destination);
  68.             elseif (current==Destination)
  69.               Nominator(current,Destination)=0;
  70.             else (Visited(c_ant,Destination)~=0)
  71.               Nominator(current,Destination)=0;
  72.             end
  73.           end
  74.         end
  75.         for current=1:City
  76.           for Destination=1:City
  77.             if (Nominator(current,Destination)==0)
  78.               A(current,Destination)=0;
  79.             else
  80.               A(current,Destination)=Nominator(current,Destination)/Denominator(current);
  81.             end
  82.           end
  83.         end
  84.         for current=1:City
  85.           for Destination=1:City
  86.             Prob_Denominator(current) = Prob_Denominator(current) + A(current,Destination);
  87.           end
  88.         end
  89.         for current=1:City
  90.           for Destination=1:City
  91.             if(A(current,Destination)~=0)
  92.               Prob(current,Destination)=(A(current,Destination)/Prob_Denominator(current));
  93.             end
  94.           end
  95.         end
  96.        
  97.         %choosing next city
  98.         Decision = 0;
  99.         X = 0;
  100.         for Destination=1:City
  101.           %if city was not visited
  102.           if(Visited(c_ant,Destination)==0)
  103.             if(Decision==0)
  104.              X=X+Prob(Info(c_ant,2),Destination);
  105.               if(X>rand)
  106.                 Decision=Destination;
  107.                 Distances(c_tour,c_ant)=Distances(c_tour,c_ant)+dystans(Decision,Info(c_ant,2));
  108.                 Info(c_ant,2)=Decision;
  109.                 break;
  110.               end
  111.             end
  112.           end
  113.         end
  114.        
  115.       else %when we visited all cities and we go back to homecity
  116.         Distances(c_tour,c_ant)=Distances(c_tour,c_ant)+dystans(Info(c_ant,1),Info(c_ant,2));
  117.         Decision=Info(c_ant,1);
  118.         Info(c_ant,2)=Decision;
  119.         Order(c_ant,c_city)=Decision;
  120.       end
  121.     end
  122.    
  123.     %calculating the amount of pheromone left on paths by each ant during current tour
  124.     for i=2:City+1
  125.       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);
  126.       delta_Pheromone(Order(c_ant,i),Order(c_ant,i-1))=delta_Pheromone(Order(c_ant,i-1),Order(c_ant,i));
  127.     end
  128.   end
  129.   %calculating the amount of pheromone on each path for next tour
  130.   for i=1:City
  131.     for j=1:City
  132.       Pheromone(i,j)=(1-Vap)*Pheromone(i,j)+delta_Pheromone(i,j);
  133.     end
  134.   end
  135. end
  136.  
  137. %Choosing best ant
  138. BEST = 1;
  139. for c_ant=1:Ant
  140.   if(Distances(Tour,c_ant)<Distances(Tour,BEST))
  141.     BEST = c_ant;
  142.   end
  143. end
  144. Finaldistance=Distances(Tour,BEST);
  145.  
  146. x1 = zeros(11,1);
  147. y1 = zeros(11,1);
  148.   for i=1:(City+1)
  149.       x1(i) = x(Order(BEST,i));
  150.       y1(i) = y(Order(BEST,i));
  151.    end
  152.    
  153. hold on
  154. scatter(x,y, 'm')
  155. a = [1:10]';
  156. b = num2str(a);
  157. c = cellstr(b);
  158. text(x+0.1,y+0.1,c);
  159. plot(x1,y1,'c');
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×