clear all
clc
load cities_data;
n = size(cities,1);
d = zeros(n);
for i = 1:n
for j = 1:n
if i == j
d(i,j) = 1e-4;
else
d(i,j) = sqrt(sum(cities(i,:) - cities(j,:)).^2);
end
end
end
m = 31;
alpha = 1;
beta = 5;
rho = 0.1;
q = 1;
eta = 1 ./ d;
tau = ones(n);
table = zeros(m,n);
iter = 1;
iter_max = 100;
route_best = zeros(iter_max,n);
length_best = zeros(iter_max,1);
length_ave = zeros(iter_max,1);
while iter <= iter_max
start = zeros(m,1);
for i = 1:m
temp = randperm(n);
start(i) = temp(1);
end
table(:,1) = start;
cities_index = 1:n;
for i = 1:m
for j = 2:n
tabu = table(i,1:(j-1));
allow_index = ~ismember(cities_index,tabu);
allow = cities_index(allow_index);
p = allow;
for k = 1:length(allow)
p(k) = tau(tabu(end),allow(k))^alpha * eta(tabu(end),allow(k))^beta;
end
p = p/sum(p);
pc = cumsum(p);
target_index = find(pc >= rand);
target = allow(target_index(1));
table(i,j) = target;
end
end
Length = zeros(m,1);
for i = 1:m
route = table(i,:);
for j = 1:(n-1)
Length(i) = Length(i) + d(route(j),route(j+1));
end
Length(i) = Length(i) + d(route(n),route(1));
end
if iter == 1
[min_length,min_index] = min(Length);
length_best(iter) = min_length;
length_ave(iter) = mean(Length);
route_best(iter,:) = table(min_index,:);
else
[min_length,min_index] = min(Length);
length_best(iter) = min(min_length,length_best(iter-1));
length_ave(iter) = mean(Length);
if length_best(iter) == min_length
route_best(iter,:) = table(min_index,:);
else
route_best(iter,:) = route_best((iter - 1),:);
end
end
delta_tau = zeros(n);
for i = 1:m
for j = 1:(n-1)
delta_tau(table(i,j),table(i,j+1)) = delta_tau(table(i,j),table(i,j+1))+q/Length(i);
end
delta_tau(table(i,n),table(i,1)) = delta_tau(table(i,n),table(i,1))+q/Length(i);
end
tau = (1-rho) * tau +delta_tau;
iter = iter + 1;
table = zeros(m,n);
end
length_best(iter_max,1)
route_best(iter_max,:)
评论1