 # 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