Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- tours = 5;
- alpha = 1;
- beta = 5;
- ro = 0.5; %evaporation coeff
- %cities 3
- x = [0 3 6 7 15 10 16 5 8 1.5];
- y = [1 2 1 4.5 -1 2.5 11 6 9 12];
- N = 10; %number of cities
- %number of ants is equal to number of cities
- m = N;
- %xy = [3,1; 2,4; 12,2; 7,4.5; 9,9; 3,1.5; 16,11; 11,8; 9,10;2,7];
- %distance between cities
- D = zeros(N);
- for i=1:N
- for j=1:N
- D(i,j) = pdist([x(i),y(i); x(j),y(j)]);
- end
- end
- %display(D);
- tau0 = 1/(min(max(D))); %initial pheromones
- tau = zeros(N);
- for i=1:N
- for j=1:N
- if(i~=j) %if not the same city
- tau(i,j) = tau0;
- end
- end
- end
- for t=1:tours
- %creating ants
- ant = zeros(m,3+N); %starting city = 1, current city = 2, distance traveled = 3
- for i=1:m
- ant(i,1) = randi([1 10],1,1); %choosing starting city
- ant(i,2) = ant(i,1); %ant is in the same city
- ant(i,3+ant(i, 1)) = 1; %first city in sequence
- end
- dtau = zeros(N); %increase of pheromone
- for iant=1:m
- for icity=2:N+1
- if(icity<N+1)
- numerator = zeros(N);
- denominator = zeros(N,1);
- A = zeros(N);
- for city=1:N
- for dest=1:N
- if(city==dest)
- numerator(city,dest) = 0; %can't go to city you're in
- else
- if(ant(iant,3+dest)>0)
- numerator(city,dest) = 0; %can't go to city you've been
- else
- numerator(city,dest) =(tau(city,dest)^alpha)*((1/D(city,dest))^beta);
- denominator(city) =denominator(city)+numerator(city,dest);
- end
- end
- end
- end
- for city=1:N
- for dest=1:N
- if(numerator(city,dest)==0)
- A(city,dest)=0;
- else
- A(city,dest)=numerator(city,dest)/denominator(city);
- end
- end
- end
- p = zeros(N);
- pd = zeros(N,1);
- %probability matrix
- for city=1:N
- for dest=1:N
- if(ant(iant,3+dest)==0) %if city not yet visited
- pd(city)=pd(city)+A(city,dest);
- %denominator sum for probability
- end
- end
- end
- for city=1:N
- for dest=1:N
- p(city,dest)=A(city,dest)/pd(city);
- %probability
- end
- end
- %choosing destination
- choice = 0;
- prob = 0;
- for dest=1:N
- if(ant(iant,3+dest)==0) %if city not visited
- if(choice==0)
- prob = prob + p(ant(iant,2),dest);
- %probability of current -> dest
- if(prob>rand
- choice = dest; %chosen destination
- break
- end
- end
- end
- end
- dest=choice;
- else
- dest=ant(iant,1); %no cities left, go home
- end
- ant(iant,3) = ant(iant,3) + D(ant(iant,2),dest);
- %distant increases
- ant(iant,2) = dest; %new current city
- if(icity < 11) %end of journey, return to starting city
- ant(iant, 3+dest) = icity;
- end
- end
- %pheromone trail
- for city=1:N
- for dest=1:N
- if(city~=dest)
- if(ant(iant, 3+dest)-ant(iant, 3+city)==1)
- dtau(city, dest) = dtau(city, dest) + (1/ant(iant, 3));
- dtau(dest, city) = dtau(dest, city) + (1/ant(iant, 3)); %direction doesn't matter
- end %calc of pheromone increase after total distance for ant is known
- end
- end
- end
- end
- %pheromone update
- for city=1:N
- for dest=1:N
- tau(city, dest) = (1 - ro) * tau(city, dest) + dtau(city, dest);
- end
- end
- end
- %mrufka miszcz
- best = 1;
- for iant=1:m
- if(ant(iant, 3)<ant(best, 3))
- best = iant;
- end
- end
- %result
- %ant(best, :)
- distance = ant(best, 3);
- x1 = zeros(11, 1);
- y1 = zeros(11, 1);
- sequence = zeros(1, 10);
- for city=1:N
- for i=4:13
- if(ant(best, i)==city)
- sequence(city) = i-3;
- x1(city) = x(i-3);
- y1(city) = y(i-3);
- end
- end
- end
- x1(11) = x1(1); %back to starting city
- y1(11) = y1(1);
- sequence
- distance
- %plot
- hold on
- scatter(x, y, 'm')
- a = [1:10]'; %labels
- b = num2str(a);
- c = cellstr(b);
- text(x+0.1, y+0.1, c); %0.1 not to overlap
- plot(x1, y1, 'c');
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement