satsp.m

模拟退火解决tsp问题

%模拟退火求解TSP问题
clc
clear
%参数设置
t0=1000;%初始温度
tf=0.01;%程序终止的温度
N=500;%城市的个数，
L=100*N;%同一温度下的迭代次数
T=t0;%温度的参数控制
pi0=1:N;%随机初始一个样本
min_f=0;
%随机初始城市坐标
A=randperm(N);
B=randperm(N);
%生成距离矩阵
% TR=[ 1 , 3639 , 1315 
%  2 , 4177 , 2244 
%  3 , 3712 , 1399 
%  4 , 3569 , 1438 
%  5 , 3757 , 1187 
%  6 , 3493 , 1696 
%  7 , 3904 , 1289 
%  8 , 3488 , 1535 
%  9 , 3791 , 1339 
%  10 , 3506 , 1221 
%  11 , 3374 , 1750 
%  12 , 3376 , 1306 
%  13 , 3237 , 1764 
%  14 , 3326 , 1556 
%  15 , 3188 , 1881 
%  16 , 3089 , 1251 
%  17 , 3258 , 911 
%  18 , 3814 , 261 
%  19 , 3238 , 1229 
%  20 , 3646 , 234 
%  21 , 3583 , 864 
%  22 , 4172 , 1125 
%  23 , 4089 , 1387 
%  24 , 4297 , 1218 
%  25 , 4020 , 1142 
%  26 , 4196 , 1044 
%  27 , 4116 , 1187 
%  28 , 4095 , 626 
%  29 , 4312 , 790 
%  30 , 4252 , 882 
%  31 , 4403 , 1022 
%  32 , 4685 , 830 
%  33 , 4386 , 570 
%  34 , 4361 , 73 
%  35 , 4720 , 557 
%  36 , 4643 , 404 
%  37 , 4634 , 654 
%  38 , 4153 , 426 
%  39 , 4784 , 279 
%  40 , 2846 , 1951 
%  41 , 2831 , 2099 
%  42 , 3007 , 1970 
%  43 , 3054 , 1710 
%  44 , 3086 , 1516 
%  45 , 1828 , 1210 
%  46 , 2562 , 1756 
%  47 , 2716 , 1924 
%  48 , 2061 , 1277 
%  49 , 2291 , 1403 
%  50 , 2751 , 1559 
%  51 , 2788 , 1491 
%  52 , 2012 , 1552 
%  53 , 1779 , 1626 
%  54 , 2381 , 1676 
%  55 , 682 , 825 
%  56 , 1478 , 267 
%  57 , 1777 , 892 
%  58 , 518 , 1251 
%  59 , 278 , 890 
%  60 , 1064 , 284 
%  61 , 1332 , 695 
%  62 , 3715 , 1678 
%  63 , 3688 , 1818 
%  64 , 4016 , 1715 
%  65 , 4181 , 1574 
%  66 , 3896 , 1656 
%  67 , 4087 , 1546 
%  68 , 3929 , 1892 
%  69 , 3918 , 2179 
%  70 , 4026 , 2220 
%  71 , 3751 , 1945 
%  72 , 3972 , 2136 
%  73 , 4061 , 2370 
%  74 , 4207 , 2533 
%  75 , 4029 , 2498 
%  76 , 4201 , 2397 
%  77 , 4139 , 2615 
%  78 , 3766 , 2364 
%  79 , 3777 , 2095 
%  80 , 3780 , 2212 
%  81 , 3896 , 2443 
%  82 , 3888 , 2261 
%  83 , 3594 , 2900 
%  84 , 3796 , 2499 
%  85 , 3678 , 2463 
%  86 , 3676 , 2578 
%  87 , 3478 , 2705 
%  88 , 3789 , 2620 
%  89 , 4029 , 2838 
%  90 , 3810 , 2969 
%  91 , 3862 , 2839 
%  92 , 3928 , 3029 
%  93 , 4167 , 3206 
%  94 , 4263 , 2931 
%  95 , 4186 , 3037 
%  96 , 3486 , 1755 
%  97 , 3492 , 1901 
%  98 , 3322 , 1916 
%  99 , 3334 , 2107 
%  100 , 3479 , 2198 
%  101 , 3429 , 1908 
%  102 , 3587 , 2417 
%  103 , 3301 , 2408 
%  104 , 3176 , 2150 
%  105 , 3507 , 2376 
%  106 , 3296 , 2217 
%  107 , 3229 , 2367 
%  108 , 3264 , 2551 
%  109 , 3394 , 2643 
%  110 , 3402 , 2912 
%  111 , 3360 , 2792 
%  112 , 3101 , 2721 
%  113 , 3402 , 2510 
%  114 , 3439 , 3201 
%  115 , 3792 , 3156 
%  116 , 3468 , 3018 
%  117 , 3526 , 3263 
%  118 , 3142 , 3421 
%  119 , 3356 , 3212 
%  120 , 3012 , 3394 
%  121 , 3130 , 2973 
%  122 , 3044 , 3081 
%  123 , 2935 , 3240 
%  124 , 2765 , 3321 
%  125 , 3140 , 3550 
%  126 , 3053 , 3739 
%  127 , 2545 , 2357 
%  128 , 2769 , 2492 
%  129 , 2284 , 2803 
%  130 , 2611 , 2275 
%  131 , 2348 , 2652 
%  132 , 2577 , 2574 
%  133 , 2860 , 2862 
%  134 , 2778 , 2862 
%  135 , 2592 , 2820 
%  136 , 2801 , 2700 
%  137 , 2126 , 2896 
%  138 , 2401 , 3164 
%  139 , 2370 , 2975 
%  140 , 1890 , 3033 
%  141 , 1304 , 2312 
%  142 , 1084 , 2313 
%  143 , 3538 , 3298 
%  144 , 3470 , 3304 
% ];
% A=TR(:,2)';
% B=TR(:,3)';
TT=[A;B]
plot(A,B,'bd')
hold on
for i=1:N
    for j=1:N
        d(i,j)=sqrt((A(i)-A(j))^2+(B(i)-B(j))^2);
    end
end
%================样本的各城市间的总距离
min_f=0;
for k=1:(N-1)
    min_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(N),pi0(1))
1/min_f
%==========================================
p_min=pi0;
while T>tf
    for k=1:L%在同一温度下进行迭代
        %生成新样本，对原样本随机进行逆转中间或者逆转两端的操作
        p_1=0;
        for k=1:(N-1)
            p_1=p_1+d(pi0(k),pi0(k+1));
        end
        p_1=p_1+d(pi0(N),pi0(1));
        rr=rand;
         C=randperm(N);
        s1=C(1);
            s2=C(2);
            if(s1>s2)
                temp1=0;
                temp1=s1;s1=s2;s2=temp1;
            end    
        if(rr>0.5)          
            pi_1=pi0;
            for i=0:(s2-s1)*0.5
                if(s1+i<s2-i)
                    temp2=0;
                    temp2=pi_1(s1+i);pi_1(s1+i)=pi_1(s2-i);pi_1(s2-i)=temp2;
                end
            end
        else
            pi_1=pi0;
            for i=0:(s1-1)*0.5
                if(i+1<s1-i)
                    temp3=0;
                    temp3=pi_1(i+1);pi_1(i+1)=pi_1(s1-i);pi_1(s1-i)=temp3;
                end
            end
            for i=0:(N-s2)*0.5
                if(s2+i<N-i)
                    temp=0;
                    temp4=pi_1(s2+i);pi_1(s2+i)=pi_1(N-i);pi_1(N-i)=temp4;
                end
            end
        end
        p_2=0;
        for k=1:(N-1)
            p_2=p_2+d(pi_1(k),pi_1(k+1));
        end
        p_2=p_2+d(pi_1(N),pi_1(1));
        d_f=p_2-p_1;
        %如果能量函数E<0;则接受新样本，如果E>0，则依概率进行取舍
        r_r=rand;
        if d_f<0
            pi0=pi_1;
        elseif exp(-d_f/T)>r_r
            pi0=pi_1;
        else 
            pi0=pi0;
        end
    end
    f_temp=0;
    for k=1:N-1
        f_temp=f_temp+d(pi0(k),pi0(k+1));
    end
       f_temp=f_temp+d(pi0(N),pi0(1));
       if min_f>f_temp
           min_f=f_temp;
           p_min=pi0;
       end
       T=0.95*T;
        
end
f=min_f
        TE=p_min
        for g=1:N-1
            plot([TT(1,TE(g)) TT(1,TE(g+1))],[TT(2,TE(g)) TT(2,TE(g+1))]);
         hold on
        end
        plot([TT(1,TE(1)) TT(1,TE(N))],[TT(2,TE(1)) TT(2,TE(N))])