时间：2019.8.19
老师：self
内容：模拟退火
个性：。。之前在刘记川老师的MATLAB PPT里有放上模拟退火的代码，之前也有所了解，只是一直没有在代码上进行突破，借此机会，一举搞懂模拟退火！
模拟退火算法及MATLAB实现
1.模拟退火起源
源于物理退火过程：
（1）加温过程
（2）等温过程
（3）冷却过程
2.参数说明
- 控制参数的初值
；冷却开始的温度
- 控制参数T的衰减函数：因计算机能够处理的都是离散数据，因此需要把连续的降温过程离散化成降温过程中的一系列温度点，衰减函数即计算这一系列温度的表达式
- 控制参数T的终值
（停止准则）
- 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) ''])
