Matlab 模拟退火算法解决经典旅行商问题

复制来的，浏览器关掉之后找不到原文链接了，非常抱歉。例子非常的简单，很容易理解。

clear;
clc;

n=200;                 %城市个数
temperature=120*n;     %初始温度  乘上n是考虑城市越多迭代次数应该越多？
iter=100;              %内部蒙特卡洛循环迭代次数  

%随机初始化城市坐标
city=struct([]);
for i=1:n
    city(i).x=floor(1+100*rand()); 
    city(i).y=floor(1+100*rand());
end

l=1;                            %统计迭代次数
len(l)=computer_tour(city,n);   %每次迭代后的路线长度  
netplot(city,n);                %初始旅行路线

while temperature>0.001     %停止迭代温度  
    for i=1:iter     %多次迭代扰动，一种蒙特卡洛方法，温度降低之前多次实验
        len1=computer_tour(city,n);         %计算原路线总距离
        tmp_city=perturb_tour(city,n);      %产生随机扰动
        len2=computer_tour(tmp_city,n);     %计算新路线总距离
        
        delta_e=len2-len1;  %新老距离的差值，相当于能量
        if delta_e<0        %新路线好于旧路线，用新路线代替旧路线
            city=tmp_city;   %???结构体可以直接相等复制吗
        else                        %温度越低，越不太可能接受新解；新老距离差值越大，越不太可能接受新解
            if exp(-delta_e/temperature)>rand() %以概率选择是否接受新解
                city=tmp_city;      %可能得到较差的解
            end
        end        
    end
    l=l+1;
    len(l)=computer_tour(city,n);   %计算新路线距离
    temperature=temperature*0.99;   %温度不断下降 
end  
figure;
netplot(city,n);    %最终旅行路线

figure;
plot(len)

function len=computer_tour(city,n)   %计算路线总长度，每个城市只计算和下家城市之间的距离。
    len=0;
    for i=1:n-1
        len=len+sqrt((city(i).x-city(i+1).x)^2+(city(i).y-city(i+1).y)^2);        
    end
    len=len+sqrt((city(n).x-city(1).x)^2+(city(n).y-city(1).y)^2);
end

function city=perturb_tour(city,n)  
    
    %随机置换两个不同的城市的坐标
    %产生随机扰动
    p1=floor(1+n*rand());
    p2=floor(1+n*rand());

    while p1==p2
        p1=floor(1+n*rand());
        p2=floor(1+n*rand());    
    end
    
    tmp=city(p1);
    city(p1)=city(p2);
    city(p2)=tmp;

end

function netplot(city,n)        %连线各城市，将路线画出来
    hold on;
    for i=1:n-1
        plot(city(i).x,city(i).y,'r*');  
        line([city(i).x city(i+1).x],[city(i).y city(i+1).y]);  %只连线当前城市和下家城市     
    end

    plot(city(n).x,city(n).y,'r*');  
    line([city(n).x city(1).x],[city(n).y city(1).y]);     %最后一家城市连线第一家城市
    hold off;
end

初始旅行路线 最终路线 随着迭代次数路线总长的变化