tsp.m

用模拟退火算法求解TSP问题 [1]主函数tsp.m [2]计算路径长度的子函数 route_long.m [3]随机交换两个节点的顺序函数exchange.m

% 用模拟退火算法求解TSP问题
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 主函数tsp.m
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [long,route] = tsp(d,th,tl,a)
% 输入：
% d         - 邻接矩阵；
% th        - 初始温度；
% tl        - 终止温度；
% a         - 控制温度系数；
% 输出：
% long      - 路径长度；
% path      - 路径编号.
n = length(d);
L = 100*n;
route = randperm(n);            % 初始化路径
long  = route_long(route,d)     % 初始化路径长度
t = th;
i = 0;
tic                             % 开始计时
while t>tl,
    for j = 1:L
        [long_new,route_new] = exchange(route,d);
        if long_new<long,
            route = route_new;
            long  = long_new;
        elseif exp((long-long_new)*2/t)>rand;
            route = route_new;
            long  = long_new;
        else 
            route = route;
            long  = long;
        end
    end
    t = a*t;
    i = i+1;
    long_sequence(i) = long;
    long_sequence;
end
toc                             % 结束计时
plot(1:i,long_sequence);        % 绘制算法效果图

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 计算路径长度的子函数 route_long.m
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function long = route_long(route,d)
% 输入：
% route     - 路径编号；
% d         - 邻接矩阵；
% 输出：
% long      - 路径长度.
n = length(d);
long = 0;
for i = 1:n-1,
    long = long+d(route(i),route(i+1));
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 随机交换两个节点的顺序函数 exchange.m
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [long_new,route_new] = exchange(route,d);
% 输入：
% route     - 初始路径；
% d         - 邻接矩阵；
% 输出：
% long_new  - 新路径长度；
% route_new - 新路径经由节点.
n = length(d);
temp1 = ceil(n*rand);
temp2 = ceil(n*rand);
tem1  = min(temp1,temp2);
tem2  = max(temp1,temp2);
route_temp = fliplr(route(tem1:tem2));  % 左右翻转矩阵
route_new  = [route(1:(tem1-1)) route_temp route(tem2+1:n)];	% 交换后产生新路径
long_new   = route_long(route_new,d);   % 重新计算路径长度