模拟退火算法SA求解TSP问题

算法SA求解TSP问题"/>

模拟退火算法SA求解TSP问题

目录

一、模拟退火算法原理

二、模拟退火算法思想

三、模拟退火算法流程

四、关键参数说明

五、例题

一、模拟退火算法原理

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大;而徐徐冷却时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度时趋于平衡的概率为，其中为温度T时的内能，为其改变量。用固体退火模拟组合优化问题，将内能E模拟为目标函数值，温度演控制参数，即得到解组合优化问题的模拟退火算法:由初始解和控制参数初值开始，对当前解重复“产生新解→计算目标函数差接受或舍弃”的迭代，并逐步减小值，算法终止时的当前解即为所得近似最优解，这是基于MonteCarlo迭代求解法的一种启发式随机搜索过程。 退火过程由冷却进度表控制，包括控制参数的初值。及其衰减因子、每个工值时的迭代次数工和停止条件。

二、模拟退火算法思想

模拟退火的主要思想是:在搜索区间随机游走(即随机选择点),再利用Metropolis抽样准则，使随机游走逐渐收敛于局部最优解。而温度是Metropolis算法中的一个重要控制参数，可以认为这个参数的大小控制了随机过程向局部或全局最优解移动的快慢。

Metropolis是一种有效的重点抽样法，其算法为:系统从一个能量状态变化到另一个状态时，相应的能量从变化到,其概率为

如果，系统接受此状态:否则，以一个随机的概率接受或丢弃此状态。状态2被接受的概率为

这样经过一一定次数的选代，系统会逐渐趋于一个稳定的分布状态。

三、模拟退火算法流程

模拟退火算法新解的产生和接受可分为如下三个步骤:

(1)由一个产生函数从当前解产生-一个位 于解空间的新解:为便于后续的计算和接受，减少算法耗时，通常选择由当前解经过简单变换即可产生新解的方法。注意，产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定 的影响。

(2)判断新解是否被接受，判断的依据是一个接 受准则，最常用的接受准则是Metropolis准则:若，则接受作为新的当前解;否则，以概率接受作为新的当前解。

(3)当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代，可在此基础上开始下一轮试验。若当新解被判定为舍弃，则在原当前解的基础上继续下一轮试验。

    模拟退火算法求得的解与初始解状态(算法迭代的起点)无关，具有渐近收敛性，已在理论上被证明是一种以概率 1收敛于全局最优解的优化算法。模拟退火算法可以分解为解空间、目标函数和初始解三部分。该算法具体流程如下:

(1)初始化:设置初始温度 (充分大)、初始解状态 (是算法迭代的起点)、每个值的迭代次数

(2)对做第(3)至第(6)步:

(3)产生新解;

(4)计算增量，其中为评价函数:

(5)若，则接受作为新的当前解，否则以概率接受作为新的当前解;

(6)如果满足终止条件，则输出当前解作为最优解，结束程序;

(7) 逐渐减小，且，然后转第(2)步。

模拟退火算法流程如图所示。

四、关键参数说明

状态产生函数

设计状态产生函数应该考虑到尽可能地保证所产生的候选解遍布全部解空间。一般情况下状态产生函数由两部分组成，即产生候选解的方式和产生候选解的概率分布。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一.定概率产生。

初温

温度T在算法中具有决定性的作用，它直接控制着退火的走向。由随机移动的接受准则可知:初温越大，获得高质量解的几率就越大，且Metropolis的接收率约为1。然而，初温过高会使计算时间增加。为此，可以均匀抽样一组状态，以各状态目标值的方差为初温。

退温函数

退温函数即温度更新函数，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数，即， 其中是一个非常接近于1的常数。

Markov链长度L的选取

Markov链长度是在等温条件下进行迭代优化的次数，其选取原则是在衰减参数T的衰减函数已选定的前提下，L应选得在控制参数的每一取值上都能恢复准平衡，一般L取100~ 1000.

算法停止准则

算法停止准则用于决定算法何时结束。可以简单地设置温度终值当时算法终止。然而，模拟火算法的收敛性理论中要求T，趋向于零，这其实是不实际的。常用的停止准则包:设置终止温度的國值，设置迭代次数阈值，或者当搜索到的最优值连续保持不变时停止搜索。 

五、例题

旅行商问题（TSP问题）。假设有一个旅行商人要拜访全国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]

解:仿真过程如下:
(1)初始化优化城市规模，Markov链长度为L = 100， 衰减参数为K = 0.99，初始温度为T= 100×n，计算初始解路径长度。
(2)随机交换初始解中的两个城市坐标，并计算新目标函数值；以Metropolis算法确定是否替代旧解，在一种温度下，迭代L次。
(3)判断是否满足终止条件:若满足，则结束搜索过程，输出优化值;若不满足，则减小温度，进行迭代优化。

优化路径如下

%%%%%%%%%%%%%%%%%%%%%%模拟退火算法解决TSP问题%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;                      %清除所有变量
close 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];                  %31个省会城市坐标
n=size(C,1);                     %TSP问题的规模,即城市数目
T=100*n;                         %初始温度
L=100;                           %马可夫链长度
K=0.99;                          %衰减参数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%城市坐标结构体%%%%%%%%%%%%%%%%%%%%%%%%%%
city=struct([]);
for i=1:ncity(i).x=C(i,1);city(i).y=C(i,2);
end
l=1;                             %统计迭代次数
len(l)=func3(city,n);            %每次迭代后的路线长度
figure(1); 
while T>0.001                    %停止迭代温度%%%%%%%%%%%%%%%%多次迭代扰动，温度降低之前多次实验%%%%%%%%%%%%%%%for i=1:L            %%%%%%%%%%%%%%%%%%%计算原路线总距离%%%%%%%%%%%%%%%%%%%%%%%%%len1=func3(city,n);         %%%%%%%%%%%%%%%%%%%%%%%%%产生随机扰动%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%随机置换两个不同的城市的坐标%%%%%%%%%%%%%%%%%p1=floor(1+n*rand());p2=floor(1+n*rand());while p1==p2p1=floor(1+n*rand());p2=floor(1+n*rand());endtmp_city=city;tmp=tmp_city(p1);tmp_city(p1)=tmp_city(p2);tmp_city(p2)=tmp;%%%%%%%%%%%%%%%%%%%%%%%%计算新路线总距离%%%%%%%%%%%%%%%%%%%%len2=func3(tmp_city,n);     %%%%%%%%%%%%%%%%%%新老距离的差值，相当于能量%%%%%%%%%%%%%%%%%delta_e=len2-len1;%%%%%%%%%%%%新路线好于旧路线，用新路线代替旧路线%%%%%%%%%%%%%%  if delta_e<0        city=tmp_city;else%%%%%%%%%%%%%%%%%%以概率选择是否接受新解%%%%%%%%%%%%%%%%%if exp(-delta_e/T)>rand()city=tmp_city;      endendendl=l+1;%%%%%%%%%%%%%%%%%%%%%%%%%计算新路线距离%%%%%%%%%%%%%%%%%%%%%%%%%%len(l)=func3(city,n); %%%%%%%%%%%%%%%%%%%%%%%%%%%温度不断下降%%%%%%%%%%%%%%%%%%%%%%%%%%T=T*K;   for i=1:n-1plot([city(i).x,city(i+1).x],[city(i).y,city(i+1).y],'bo-');hold on;endplot([city(n).x,city(1).x],[city(n).y,city(1).y],'ro-');title(['优化最短距离:',num2str(len(l))]);hold off;pause(0.005);
end
figure(2);
plot(len)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%计算路线总长度%%%%%%%%%%%%%%%%%%%%%%%%
function len=func3(city,n)
len=0;
for i=1:n-1len=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