禁忌搜索TSP

一种用matlab开发出来的禁忌算法解决TSP问题

% Travelling Sales man problem using Tabu Search
% This assumes the distance matrix is symmetric
% Tour always starts from node 1
% **********Read distance （cost） matrix from Excel sheet “data.xls“******
clearclc;
d = xlsread（‘tsp_data.xls‘）;
d_orig = d;
start_time = cputime;
dim1 = size（d1）;
dim12 = size（d）;
for i=1:dim1
d（ii）=10e+06;
end
% *****************Initialise all parameters**********************
d1=d;
tour = zeros（dim12）;
cost = 0;
min_dist=[ ];
short_path=[ ];
best_nbr_cost = 0;
best_nbr = [ ];
% *******Generate Initial solution - find shortest path from each node****
% if node pair 1-2 is selected make distance from 2 to each of earlier
%visited nodes very high to avoid a subtour
k = 1;
for i=1:dim1-1
min_dist（i） = min（d1（k:））;
short_path（i） = find（（d1（k:）==min_dist（i））1）;
cost = cost+min_dist（i）;
k = short_path（i）;
% prohibit all paths from current visited node to all earlier visited nodes
d1（k1）=10e+06;
for visited_node = 1:length（short_path）; 
d1（kshort_path（visited_node））=10e+06;
end
end
tour（1short_path（1））=1;
for i=2:dim1-1
tour（short_path（i-1）short_path（i））=1;
end
%Last visited node is k;
%shortest path from last visited node is always 1 where the tour
%originally started from
last_indx = length（short_path）+1;
short_path（last_indx）=1;
tour（kshort_path（last_indx））=1;
cost = cost+d（k1）;
% A tour is represented as a sequence of nodes startig from second node （as
% node 1 is always fixed to be 1
crnt_tour = short_path;
best_tour = short_path;
best_obj =cost;
crnt_tour_cost = cost;
fprintf（‘\nInitial solution\n‘）;
crnt_tour
fprintf（‘\nInitial tour cost = %d\t‘ crnt_tour_cost）;
nbr_cost=[ ];
% Initialize Tabu List “tabu_tenure“ giving the number of iterations for
% which a particular pair of nodes are forbidden from exchange
tabu_tenure = zeros（dim12）;
max_tabu_tenure = round（sqrt（dim1））;
%max_tabu_tenure = dim1;
penalty = zeros（1（dim1-1）*（dim1-2）/2）;
frequency = zeros（dim12）;
frequency（1:）=100000;
frequency（:1）=100000; 
for i=1:dim1
frequency（ii）=100000;
end
iter_snc_last_imprv = 0;
%*********Perform the iteration until one of the criteria is met***********
%1. Max number of iterations reached***************************************
%2. Iterations since last improvement in the best objective found so far
% reaches a threshold******************************************************
best_nbr = crnt_tour;
for iter=1:10000
fprintf（‘\n*****iteration number = %d*****\n‘ iter）;
nbr =[];
% *******************Find all neighbours to current tour by an exchange
%******************between each pair of nodes***********************
% ****Calculate the object value （cost） for each of the neighbours******
nbr_cost = inf（dim12）;
for i=1:dim1-2
for j=i+1:dim1-1
if i==1
if j-i==1
nbr_cost（crnt_tour（i）crnt_tour（j））=crnt_tour_cost-d（1crnt_tour（i））+...
d（1crnt_tour（j））- d（crnt_tour（j）crnt_tour（j+1））+d（crnt_tour（i）crnt_tour（j+1））;
best_i=i;
best_

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件       24576  2011-10-16 21:42  tsp_data.xls
     文件        9111  2011-10-16 22:11  taboo_tsp.m