時間：2019.8.19
老師：self
內(nèi)容：模擬退火
個性：横侦。奕塑。之前在劉記川老師的MATLAB PPT里有放上模擬退火的代碼，之前也有所了解妒蛇，只是一直沒有在代碼上進行突破，借此機會楷拳，一舉搞懂模擬退火绣夺！
模擬退火算法及MATLAB實現(xiàn)
1.模擬退火起源
源于物理退火過程：
（1）加溫過程
（2）等溫過程
（3）冷卻過程
2.參數(shù)說明
- 控制參數(shù)的初值
；冷卻開始的溫度
- 控制參數(shù)T的衰減函數(shù)：因計算機能夠處理的都是離散數(shù)據(jù)欢揖，因此需要把連續(xù)的降溫過程離散化成降溫過程中的一系列溫度點陶耍，衰減函數(shù)即計算這一系列溫度的表達式
- 控制參數(shù)T的終值
（停止準(zhǔn)則）
- Markov鏈的長度
；任一溫度T的迭代次數(shù)
3.metropolis準(zhǔn)則
一新解與當(dāng)前解的目標(biāo)函數(shù)差定義接受概率她混，即
4.MATLAB代碼
clc %清空環(huán)境中的變量
tic
iter = 1; % 迭代次數(shù)初值
a=0.99; %溫度衰減系數(shù)
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]'; %讀入城市的坐標(biāo)
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)
%交換兩個數(shù)的順序
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;
%對最優(yōu)路線和距離更新
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
%% 結(jié)果顯示
toc
Route=[best_route best_route(1)];
plot([city(Route ,1)], [city(Route ,2)],'o-');
disp('最優(yōu)解為：')
disp(best_route)
disp('最短距離：')
disp(best_length)
disp('最優(yōu)解迭代次數(shù)：')
disp(iter)
for i = 1:n
%對每個城市進行標(biāo)號
text(city(i,1),city(i,2),[' ' num2str(i)]);
end
xlabel('城市位置橫坐標(biāo)')
ylabel('城市位置縱坐標(biāo)')
title(['模擬退火算法(最短距離）:' num2str(best_length) ''])
