tsp_sa_main.m

用MATLAB开发的旅行商问题

%*************************************************************************%
%                             TSP_SA_main                                 %
%           本程序实现旅行商问题TSP,在主程序中调用TSP_SA_T                %
%           该函数实现在同一温度下,循环迭代TrialNum次,最后                %
%           返回迭代的解和目标函数值。在子函数中又调用函数                %
%           TSP_SA_F,该程序计算目标函数值，返回目标函数值.                %
%*************************************************************************%

clear all
clc
%*************************************************************************%
%                       城市坐标赋值                                      %
%*************************************************************************%

n=30;                           % 城市总数
[x,y]=circle(n);                % 由函数circle生成圆周形城市坐标
Location=[x',y'];               % 主要用于验证程序的正确性

% %  由文献资1-004提供的城市坐标
% Location=[0.37,0.75,0.45,0.76,0.71,0.07,0.42,0.59,0.32,0.60,...
% 0.30,0.67,0.62,0.67,0.20,0.35,0.27,0.94,0.82,0.37,0.61,...
% 0.42,0.60,0.39,0.53,0.40,0.63,0.50,0.98,0.68;0.91,0.87,...
% 0.85,0.75,0.72,0.74,0.71,0.69,0.64,0.64,0.59,0.59,0.55,...
% 0.55,0.50,0.45,0.43,0.42,0.38,0.27,0.26,0.25,0.23,...
% 0.19,0.19,0.13,0.08,0.04,0.02,0.85];
% Location=Location';                 % 数组的每一行代表一个城市坐标
  
%  Location=[0,0;0,1;1,1;1,0];        % 用于调试

%*************************************************************************%
%                     计算任意两个城市间的距离                            %
%*************************************************************************%

CityNum=length(Location);                                   % 城市总数
for I=1:CityNum
    for J=1:CityNum
        Distance(I,J)=norm(Location(I,:)-Location(J,:));    % 求范数即距离
    end
end

%*************************************************************************%
%                            产生或设置初始值                             %
%*************************************************************************%

Path=randperm(CityNum);                    % 随机置换向量，产生初始路径
Path_init=Path;                            % 保存为初始路径
minPath=Path;                              % 保存为最小路径
Energy=TSP_SA_F(Path_init,Distance);       % 计算路径的目标函数值
Energy_init=Energy;                        % 保存为初始路径的函数值
minE=inf;                                  % 设定最小目标函数值为无穷大
Ratio=0.9;                                 % 退火因子
T=1e5;                                     % 起始温度
TrialNum=1000;                              % 控制在同一温度时的子循环次数,
                                           % 该数值不宜太小,否则不易得到最优解 
N=0;                                       % 外循环计数器

%*************************************************************************%
%                          开始模拟退火循环过程                           %
%*************************************************************************%

while (N<=2000)
     N=N+1
    [Path,minPath,Energy,minE]=TSP_SA_T(Path,minPath,Energy,minE,T,Distance,TrialNum);
     T=T*Ratio;                                               % 退火策略
end

%*************************************************************************%
%                          显示初始路径和最后路径                         %
%*************************************************************************%

Path_init(CityNum+1)=Path_init(1);                         % 形成闭合路径
figure(1)                                                  % 显示初始的路径
plot(Location(Path_init,1),Location(Path_init,2));         % 画折线
hold on
scatter(Location(Path_init,1),Location(Path_init,2),'filled');  % 画离散点
str=strcat('迭代初始的路径',num2str(Energy_init));
title(str);

Path(CityNum+1)=Path(1);                         
figure(2)                                            % 显示迭代结束的路径
plot(Location(Path,1),Location(Path,2))             
hold on
scatter(Location(Path,1),Location(Path,2),'filled'); 
str=strcat('迭代结束的路径',num2str(Energy));
title(str)

minPath(CityNum+1)=minPath(1);                   
figure(3)                                            % 显示迭代结束的路径
plot(Location(minPath,1),Location(minPath,2));             
hold on
scatter(Location(minPath,1),Location(minPath,2),'filled');  
str=strcat('最小路径',num2str(minE));
title(str)