trav.m

来自「求解TSP（旅行商）问题的模拟退火程序」· M 代码 · 共 55 行

function [pmin,lenmin]=trav(npts,distmatrix,p)
%模拟退火算法用于求解旅行商问题（TSP）
%npts为城市总数或节点数
%distmatrix为权矩阵，行和列都为城市标号，对应位置的数值为该行号代表的城市与列号代表的城市之间的距离
%p为初始解，如有10个城市，初始解可为[1 2 3 4 5 6 7 8 9 10 1]
%输出pmin为总路程最小的行走方案
%输出lenmin为最小的总路程

%------------------initial--------------------------
   T=10;   %初始温度，总循环结束条件，初温越高，结束越慢
   tem0=10;
   tem=tem0;
   temconfig=7;  %内循环结束条件，数值越小结束越快
   distmatrix=[distmatrix zeros(npts,1);zeros(1,npts+1)];
   npts = npts+1;
   len=LocalPathLength(p,distmatrix);
   lenmin=len;pmin=p; 
   
while (1)
    while(1)
        lenmin
        swpt1=floor(npts*rand)+1;
        swpt2=floor((npts-1)*rand)+1;    
        order=1:npts;
        order(swpt1)=[];
        order=[order(1:swpt2) swpt1 order((swpt2+1):(npts-1))];
        pnew = p(order);
        lennew=LocalPathLength(pnew,distmatrix);
        if lennew<lenmin
            lenmin=lennew;
            pmin=pnew;
        end
        if exp(-(lennew-len)/T)>=rand
                p=pnew;
                len=lennew;
                tem=tem0;
            else  tem=tem-1;
        end
        
        if tem<=temconfig
            break;
        end
    end
    T=T*0.8;
    temconfig=temconfig-1;
    temconfig=abs(temconfig);
    if T<0.1
        break;
    end
end

%------------------------代价计算程序----------------------
function total=LocalPathLength(p,distmatrix);
npts = size(p,2);
total=sum(distmatrix([(p-1)*npts + p([end 1:(end-1)])]));