模拟退火首先从某个初始候选解开始,当温度大于0时执行循环。
在循环中,通过随机扰动产生一个新的解,然后求得新解和原解之间的能量差,如果差小于0,则采用新解作为当前解。
如果差大于0,则采用一个当前温度与能量差成比例的概率来选择是否接受新解。温度越低,接受的概率越小,差值越大,同样接受概率越小。
是否接受的概率用此公式计算:p=exp(-ΔE/T)。这里ΔE为新解与原解的差,T为当前的温度。
由于温度随迭代次数逐渐降低,因此获得一个较差的解的概率较小。
典型的模拟退火算法还使用了蒙特卡洛循环,在温度降低之前,通过多次迭代来找到当前温度下比较好的解。
这里使用模拟退火解旅行商问题,因为这个问题本身是一个NP难问题,所以也就求不到最优解,不过应该可以求得一个比较好的解,然后再手工优化。
具体到程序中,这里的随机扰动就是随机置换两个城市的位置,能量就是旅行商路线的总长度。
算法结果如下:
初始旅行商路线:
![](https://images0.cnblogs.com/blog/340413/201307/02193244-374b2daf92254773835e6b49bfc24d5e.jpg)
最终求得的旅行商路线:
![](https://images0.cnblogs.com/blog/340413/201307/02193324-6ed21e67b89547539308fce8f20a5abc.jpg)
每次迭代求得的旅行距离:
![](https://images0.cnblogs.com/blog/340413/201307/02193427-ac444012b7cb4241b1142be681f1f77c.jpg)
matlab代码如下:
main.m
clear all;close all;clc
n=20; %城市个数
temperature=100*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)
computer_tour.m
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
perturb_tour.m
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
netplot.m
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