时间：2019.8.19
老师：self
内容：模拟退火
个性：。。之前在刘记川老师的MATLAB PPT里有放上模拟退火的代码，之前也有所了解，只是一直没有在代码上进行突破，借此机会，一举搞懂模拟退火！

模拟退火算法及MATLAB实现

1.模拟退火起源

源于物理退火过程：
（1）加温过程
（2）等温过程
（3）冷却过程

2.参数说明

1. 控制参数的初值；冷却开始的温度
2. 控制参数T的衰减函数：因计算机能够处理的都是离散数据，因此需要把连续的降温过程离散化成降温过程中的一系列温度点，衰减函数即计算这一系列温度的表达式
3. 控制参数T的终值（停止准则）
4. Markov链的长度；任一温度T的迭代次数

3.metropolis准则

一新解与当前解的目标函数差定义接受概率，即

4.MATLAB代码

clc       %清空环境中的变量
tic
iter = 1;                                                                                   % 迭代次数初值
a=0.99;                                                                                    %温度衰减系数
t0=120;                                                                                    %初始温度
tf=1;                                                                                          %最后温度
t=t0;
rand('seed',0)
Markov=10000;                                                                     %Markov链长度
data1=[565.0 575.0; 25.0 185.0;345.0 750.0;945.0 685.0;845.0 655.0;880.0 660.0;25.0 230.0; 525.0 1000.0;580.0 1175.0;
    650.0 1130.0;1605.0 620.0 ;1220.0 580.0;1465.0 200.0;1530.0 5.0;845.0 680.0;725.0 370.0; 145.0 665.0; 415.0 635.0; 
    510.0 875.0  ;560.0 365.0;300.0 465.0; 520.0 585.0;480.0 415.0;835.0 625.0; 975.0 580.0; 1215.0 245.0;1320.0 315.0;
    1250.0 400.0; 660.0 180.0; 410.0 250.0; 420.0 555.0;575.0 665.0; 1150.0 1160.0; 700.0 580.0; 685.0 595.0; 685.0 610.0;
    770.0 610.0;795.0 645.0; 720.0 635.0; 760.0 650.0;475.0 960.0;95.0 260.0; 875.0 920.0; 700.0 500.0;555.0 815.0;830.0 485.0;
    1170.0 65.0; 830.0 610.0; 605.0 625.0; 595.0 360.0; 1340.0 725.0;1740.0 245.0];



% data1=[37,49,52,20,40,21,17,31,52,51,42,31,5,12,36,52,27,17,13,57,62,42,16,8,7,27,30,43,58,58,37,38,46,61,62,63,32,45,59,5,10,21,5,30,39,32,25,25,48,56,30;
%     52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,52,38,68,48,67,48,27,69,46,10,33,63,69,22,35,15,6,17,10,64,15,10,39,32,55,28,37,40]';                                                                        %读入城市的坐标
city=data1;
n = size(city,1);                                                                      %城市距离初始化
D = zeros(n,n);                                                   
for i = 1:n
    for j = 1:n
            D(i,j) = sqrt(sum((city(i,:) - city(j,:)).^2));
    end    
end                                                                                
route=1:n;   
route_new=route;
best_length=Inf;
Length=Inf;
best_route=route;%%
while t>=tf
           for j=1:Markov
                    %进行扰动,长生新的序列route_new;
                    if (rand<0.7)
                        %交换两个数的顺序
                           ind1=0;ind2=0;
                           while(ind1==ind2&&ind1>=ind2)
                                    ind1=ceil(rand*n);
                                    ind2=ceil(rand*n);
                           end                      
                                      temp=route_new(ind1);
                                      route_new(ind1)=route_new(ind2);
                                      route_new(ind2)=temp;
                    else
                          ind=zeros(3,1);
                          L_ind=length(unique(ind));
                          while (L_ind<3)
                                    ind=ceil([rand*n rand*n rand*n]);
                                    L_ind=length(unique(ind));
                          end
                          ind0=sort(ind);
                          a1=ind0(1);b1=ind0(2);c1=ind0(3);
                         route0=route_new;
                         route0(a1:a1+c1-b1-1)=route_new(b1+1:c1);
                         route0(a1+c1-b1:c1)=route_new(a1:b1);
                         route_new=route0;    
                    end
                     %计算路径的距离,Length_new 
                          length_new = 0;
                        Route=[route_new route_new(1)];
                              for j = 1:n
                                  length_new = length_new+ D(Route(j),Route(j + 1));
                              end
                     if length_new<Length      
                              Length=length_new;
                              route=route_new;
                           %对最优路线和距离更新
                           if       length_new<best_length
                                    iter = iter + 1;    
                                     best_length=length_new;
                                     best_route=route_new;
                           end
                     else
                             if rand<exp(-(length_new-Length)/t)
                                  route=route_new;
                                  Length=length_new;
                              end
                     end
                       route_new=route; 
            end              
                        t=t*a
end
%% 结果显示 
toc
Route=[best_route best_route(1)];
plot([city(Route ,1)], [city(Route ,2)],'o-');
    disp('最优解为：')
    disp(best_route)
    disp('最短距离：')
    disp(best_length)
    disp('最优解迭代次数：')
    disp(iter)
for i = 1:n
    %对每个城市进行标号
    text(city(i,1),city(i,2),['   ' num2str(i)]);
end
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['模拟退火算法(最短距离）:' num2str(best_length) ''])