# 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.

×