算法——仿真篇"/>

模拟退火算法——仿真篇

理论部分不再赘述，详情请查看我以往文章。

(19条消息) 模拟退火算法——理论篇_talkAC的博客-CSDN博客

1 仿真问题

旅行商问题（TSP问题）。

假设1个旅行商要对31个省会城市进行拜访，要求距离最短，不能重复拜访，且最终要回到出发城市。

31个城市坐标：

  [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;
    3238 1229;4196 1044;4312 790  ;4386 570  ;3007 1970;2562 1756;
    2788 1491;2381 1676;1332 695  ;3715 1678;3918 2179;4061 2370;
    3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;
    3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;
    2370 2975]；

2 仿真过程

初始化参数 -> 初温T、初始访问顺序city即初解

在温度t上进行充分探索 -> 迭代L次

        在city上随机交换2个城市访问顺序，产生新解

        计算新解增量ΔE

        基于ΔE和Metropolis 采样算法，选择是否更新解

降温或终止 ->     减小接受劣质解的概率    

3 Metropolis 采样算法

关键点是，当没有增量时并不完全抛弃劣质解，而是以一个概率P接受劣质解，以避免陷入局部最优的情况， 达到全局探索。

当T很大时，接受劣质解的概率达到最大，以保证全局搜索能力；当不断降温，T变小，接受劣质解的概率趋近0， 争取最快的收敛速度。

影响劣质解被接受的还有增量ΔE，ΔE越大，负贡献越大，P越小，被接受的概率越小，反之亦然。

4 求解代码

 初始化参数

close all;
clear all;
clc;
%%%%%初始化参数
C = [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1044;4312 790 ;4386 570 ;3007 1970;2562 1756;2788 1491;2381 1676;1332 695 ;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975];
n=size(C,1);
T=n*100;
L=100;
K=0.99;
l=1;
%%%%%初始化访问城市顺序
D=zeros(n);
for i=1:nfor j=1:nD(i,j)=((C(i,1)-C(j,1))^2 + (C(i,2)-C(j,2))^2)^0.5;end
end
city=randperm(n);
len(l)=func1(D,city,n);

 产生新解

%%%%%算法循环
while T>0.001%%%%%每个温度的探索for i=1:Llen1=func1(D,city,n);%%%%%随机交换位置，产生新的访问顺序p1=floor(1+rand*n);p2=floor(1+rand*n);while p1==p2p1=floor(1+rand*n);p2=floor(1+rand*n);endtemp_city=city;temp=temp_city(p1);temp_city(p1)=temp_city(p2);temp_city(p2)=temp;

Metropolis 采样

%%%%%计算新路径长度及增量Elen2=func1(D,temp_city,n);delta_E=len2-len1;%%%%%判断是否接受新的访问顺序if delta_E<0city=temp_city;elseif exp(-delta_E/T)>randcity=temp_city;endendend

降温、画变化图 

    l=l+1;len(l)=func1(D,city,n);%%%%%降温T=T*K;%%%%%画图for i=1:n-1plot([C(city(i),1),C(city(i+1),1)],[C(city(i),2),C(city(i+1),2)],'o-');hold on;endplot([C(city(n),1),C(city(1),1)],[C(city(n),2),C(city(1),2)],'ro-');title([num2str(l),'次最短距离：',num2str(len(l))]);hold off;pause(0.01); 
end

 结果输出

%%%%%输出优化结果
figure;
plot(len);
xlabel('迭代次数');
ylabel('目标函数值');
title('适应度进化曲线');
%%%%%路径长度函数
function result = func1(D,f,N)len=D(f(1),f(N));for j=2:Nlen=D(f(j),f(j-1))+len;endresult=len;
end

5 仿真结果