MATLAB禁忌搜索算法求解TSP问题

通过禁忌搜索算法求解经典的TSP问题（MATLAB源代码），TSP问题为假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

% Travelling Sales man problem using Tabu Search使用禁忌搜索的旅行商问题
% This assumes the distance matrix is symmetric假设距离矩阵是对称的
% Tour always starts from node 1旅行总是开始从节点1开始
% **********Read distance （cost） matrix from Excel sheet “data.xls“******读取距离（成本）矩阵从Excel表”数据.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;最后访问节点为K
%shortest path from last visited node is always 1 where the tour旅行商最后一次访问节点的最短路径总是1
%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节点1总是固定为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初始化禁忌表”tabu_tenure”给出的迭代次数
% 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:100%迭代次数
fprintf（‘\n*****iteration number = %d*****\n‘ iter）;
nbr =[];
% *******************Find all neighbours to current tour by an exchange通过变换寻找当前位置的所有邻居
%******************between each pair of nodes**************