【算法】模拟退火算法解决TSP问题的matlab实现

%模拟退火算法
%TSP问题
clc,clear

T0 =500;%初始温度
Tend = 1e-4; %终止温度
L=200; %各个温度下的链长
q=0.98; %降温速率
cityNum = 30; %城市个数
City = rand(cityNum,2); %随机生成城市的坐标

%%%%%%%%%%%%%%主程序%%%%%%%%%%%%%%%%%%%%
D = Distance(City);
N = cityNum;
S1 = randperm(N); %产生一个随机解
%解方程，计算迭代次数
Time = ceil(double(solve([‘1000*(0.9)^x‘,num2str(Tend)])));
count = 0; %迭代计数器
Obj = zeros(Time,1);    %每代路径和
track = zeros(Time,N);  %每代最优解
%迭代
while T0>Tend
    count = count + 1;
    temp = zeros(L,N+1);
    for k = 1:L
        %产生L组新解
        S2 = newSolution(S1);
        [S1,R] = Metropolis(S1,S2,D,T0);
        temp(k,:)=[S1 R];
    end
    %记录每次迭代过程的最优路线
    [d0,index] = min(temp(:,end));
    if count == 1 || d0 <Obj(count-1)
        Obj(count) = d0;
    else
        Obj(count)=Obj(count - 1);
    end
    
    track(count,:)=temp(index,1:end-1);
    T0 = q*T0;
end
fprintf(‘迭代次数：%d\n‘,count);
fprintf(‘最短路径：%f\n‘,Obj(end));
%迭代图
figure
plot(1:count,Obj);
xlabel(‘迭代次数‘);
ylabel(‘距离‘);
title(‘优化过程‘);
DrawPath(track(end,:),City);


%%%%%%%%%%%%%%%%%子函数，共5个%%%%%%%%%%%%%%%%%%%%%

%函数功能：求解距离矩阵
%输入：城市坐标 输出：距离矩阵
function D = Distance(a)
    r = size(a,1);
    D = zeros(r,r);
    for i = 1:r
        for j = i+1:r
            D(i,j)=sqrt((a(i,1)-a(j,1))^2 + (a(i,2)-a(j,2))^2);
            D(j,i) = D(i,j);
        end
    end
end

%函数功能：生成新解
%输入：旧解 输出：新解
%随机选两个位置交换。
function S2 = newSolution(S1)
    N = length(S1);
    S2 = S1;
    a = round( rand(1,2)*(N-1)+1);  %产生两个随机位置用来交换
    temp = S2(a(1));
    S2(a(1))=S2(a(2));
    S2(a(2)) = temp;
end

%Metropolis准则函数
%输入：新解，旧解，距离矩阵，当前温度
%输出：判断后的解，解的路径
function [S,R] = Metropolis(S1,S2,D,T)
    R1 = pathLength(D,S1);
    R2 = pathLength(D,S2);
    dT = R2 - R1;
    if dT < 0
       S=S2;
       R=R2;
    elseif exp(-dT/T) >= rand
       S=S2;
       R=R2;
    else
       S=S1;
       R=R1;
    end
end

%画出路线轨迹图
%输入：最优路径，城市坐标 输出：路径图
function DrawPath(BestTrack,City)
    N = size(BestTrack,2);
    cityArray = zeros(N,2);
    for i = 1:N
        cityArray(i,1) = City(BestTrack(i),1);
        cityArray(i,2) = City(BestTrack(i),2);
    end
    figure;
    hold on
    plot(cityArray(:,1),cityArray(:,2),‘-o‘,‘color‘,[0.5 0.5 0.5]);
    plot([cityArray(1,1),cityArray(end,1)],[cityArray(1,2),cityArray(end,2)],...
        ‘-‘,‘color‘,[0.5 0.5 0.5]);
    hold off
    xlabel(‘横坐标‘);
    ylabel(‘纵坐标‘);
    title(‘TSP图‘);
    box on
end

%计算路线长度的函数
%输入：距离矩阵，行走的顺序  输出：路径和
function len = pathLength(D,S)
    [r,c] = size(D);
    NIND = size(S,1);
    for i = 1:NIND
        p = [S(i,:) S(i,1)];
        i1 = p(1:end-1);
        i2 = p(2:end);
        len(i,1) = sum(D((i1-1)*c + i2));
    end
end