title: 学习常用模型及算法1.模拟退火算法
excerpt: 学习数学建模常用模型及算法
tags: [数学建模, matlab]
categories:
- [学习, 数学建模]
index_img: https://picture-store-repository.oss-cn-hangzhou.aliyuncs.com/PicGo/shujian.jpg
banner_img: https://picture-store-repository.oss-cn-hangzhou.aliyuncs.com/PicGo/sjban.jpg
date: 2020-08-08 10:39:11
comment: true
math: true
1. 算法简述
模拟退火适用的问题通常是一些求最优解的问题。
比如，把问题抽象地看成一个长成这样的毫无规律的函数，而最优解就是函数的最低点。
众所周知，对于一个没有办法在多项式复杂度的算法下完成求解的问题，我们通常会想到一种简单粗暴的方法——贪心。
选择问题的某一个状态，然后不断向更优的情况靠近。
比如从A出发，可以获得局部最优解B，但这显然不是全局最优解。
显然，这样做的局限性是，过于局限在局部的一个凹部分而无法跳出去去寻找更优的解。
2. 原理
为了解决这一问题，科学家们想到了物理的退火降温的过程——
一个处于很高温度的物体，现在要给它降温，使物体内能降到最低。
我们常规的思维是，越快越好，让它的温度迅速地降低。
然而，实际上，过快地降温使得物体来不及有序地收缩，难以形成结晶。而结晶态，才是物体真正内能降到最低的形态。
正确的做法，是徐徐降温，也就是退火，才能使得物体的每一个粒子都有足够的时间找到自己的最佳位置并紧密有序地排列。开始温度高的时候，粒子活跃地运动并逐渐找到一个合适的状态。在这过程中温度也会越降越低，温度低下来了，那么粒子也渐渐稳定下来，相较于以前不那么活跃了。这时候就可以慢慢形成最终稳定的结晶态了。
那么，我们可不可以把找到最优解，与形成结晶态，这两个过程联系在一起呢？
于是，模拟退火诞生了。
3. 模拟退火算法要求
- 初始温度足够高
- 降温过程足够慢
- 终止温度足够低
4. 实现过程
我们需要设定这几个参数，模拟退火过程
-
T——温度
ΔT——温度变化率，每次温度等于上一次温度乘上ΔT，实际应用时一般取0.95−0.99，模拟徐徐降温
再定义一些量 -
x——当前选择的解
-
Δx——解变动值
-
x1——当前的目标解，等于x+Δx
-
Δf——当前解的函数值与目标解函数值之差，等于f(x)−f(x1)
我们给一个初始解x，并让它不断变动。要模拟变动的大小随温度的降低而降低，我们每次的Δx应该在一个大小与T成正比的值域内随机取值。 这时候我们就要考虑是否将当前解变为目标解。因为我们还是需要贪心，所以如果f(x1)<f(x)，那么接受目标解，x=x1。 那如果f(x1)="">f(x)呢？我们当然要以一定概率接受它啦，这样才能跳出局部的限制，去搜寻更优的解，弥补贪心的局限性。那么这个概率应该是多少呢？同样要模拟变动的大小随温度的降低而降低。科学家经过理论分析，得出这个概率应该是eΔfT。 如此反复选择直到T趋近于0（可以设一个EPS）这时候我们认为我们当前的x就是最优解。
图中or random...即为metropolis准则，也是模拟退火和贪心算法的根本区别。
用图片来描述的话，就拿上面那个图像寻找最优解为例
首先经过大幅波动，当前解由A->B->C，找到了一个比较满意的解。
但还不能满足。由于温度还比较大，此时接受了一些不比当前解优的目标解，C->D->E，成功地爬了上去。而温度还在慢慢减小。
终于，发现了一个更优解F，成功跳出了那个非常宽的局部凹函数。
这时候，温度越来越小了，很难再次接受不比当前解优的目标解，再次翻出去。解终于渐渐趋于稳定，并最终到达了G，找到了最优解。
如此看来，基于随机的模拟退火能很大程度上提高正确率，但也不可能完全正确。上面的例子只是随意模拟出的一个情况。所以要多跑几遍，取每一次得到的解的最优值。
5. 关于参数
众所周知，模拟退火最麻烦的地方在调参，只有合适的参数才能在一定的时间内很大概率跑出最优解。
首先，根据数据范围和精度要求，可以基本确定EPS的大小了，不过也需要尝试手动微调。
比较麻烦的是温度和变动率。首先不必顾虑，都开大一点，先把最优解跑出来。
然后，手动二分吧，注意每个二分的值要多跑几遍，因为模拟退火有偶然性，一次跑出最优解不代表大部分时候都能。
不过因为有两个量，还不能直接二分，应该二分套二分比较合适
update:考试的时候写提答，总结了一种方法：观察法
一边退火一边输出当前的温度、解等信息，通过观察大致感受一下解的降低速率
一般来说，如果解的降低速率比较均匀，跑出来的最优解也就好一些
不均匀的话，就调整参数，将解的降低速率较快的时间段的ΔT变大一点，速率就能减慢一点。反之同理。
6. 经典问题：旅行商问题(TSP)
每个城市只有一个箭头指进，一个箭头指出，即入度和出度均为1。
文件介绍：
- swap.m文件用于邻解生成
- distance.m文件用于计算距离
- pathfare.m文件用于记录路线
clear;
% 程 序 参 数 设 定
Coord = ... % 城 市 的 坐 标 Coordinates
[ 0.6683 0.6195 0.4 0.2439 0.1707 0.2293 0.5171 0.8732 0.6878 0.8488 ; ...
0.2536 0.2634 0.4439 0.1463 0.2293 0.761 0.9414 0.6536 0.5219 0.3609 ] ;
t0 = 1 ; % 初 温 t0
iLk = 20 ; % 内 循 环 最 大 迭 代 次 数 iLk
oLk = 50 ; % 外 循 环 最 大 迭 代 次 数 oLk
lam = 0.95 ; % λ lambda
istd = 0.001 ; % 若 内 循 环 函 数 值 方 差 小 于 istd 则 停 止
ostd = 0.001 ; % 若 外 循 环 函 数 值 方 差 小 于 ostd 则 停 止
ilen = 5 ; % 内 循 环 保 存 的 目 标 函 数 值 个 数
olen = 5 ; % 外 循 环 保 存 的 目 标 函 数 值 个 数
% 程 序 主 体
m = length( Coord ) ; % 城 市 的 个 数 m
fare = distance( Coord ) ; % 路 径 费 用 fare
path = 1 : m ; % 初 始 路 径 path
pathfar = pathfare( fare , path ) ; % 路 径 费 用 path fare
ores = zeros( 1 , olen ) ; % 外 循 环 保 存 的 目 标 函 数 值
e0 = pathfar ; % 能 量 初 值 e0
t = t0 ; % 温 度 t
for out = 1 : oLk % 外 循 环 模 拟 退 火 过 程
ires = zeros( 1 , ilen ) ; % 内 循 环 保 存 的 目 标 函 数 值
for in = 1 : iLk % 内 循 环 模 拟 热 平 衡 过 程
[ newpath , v ] = swap( path , 1 ) ; % 产 生 新 状 态
e1 = pathfare( fare , newpath ) ; % 新 状 态 能 量
% Metropolis 抽 样 稳 定 准 则
r = min( 1 , exp( - ( e1 - e0 ) / t ) ) ;
if rand < r
path = newpath ; % 更 新 最 佳 状 态
e0 = e1 ;
end
ires = [ ires( 2 : end ) e0 ] ; % 保 存 新 状 态 能 量
% 内 循 环 终 止 准 则 ：连 续 ilen 个 状 态 能 量 波 动 小 于 istd
if std( ires , 1 ) < istd
break ;
end
end
ores = [ ores( 2 : end ) e0 ] ; % 保 存 新 状 态 能 量
% 外 循 环 终 止 准 则 ：连 续 olen 个 状 态 能 量 波 动 小 于 ostd
if std( ores , 1 ) < ostd
break ;
end
t = lam * t ;
end
pathfar = e0 ;
% 输 入 结 果
fprintf( '近似最优路径为：\n ' )
%disp( char( [ path , path(1) ] + 64 ) ) ;
disp(path)
fprintf( '近似最优路径路程\tpathfare=' ) ;
disp( pathfar ) ;
myplot( path , Coord , pathfar ) ;
7. TSP“旅行商问题”的应用领域
如何规划最合理高效的道路交通，以减少拥堵;如何更好地规划物流，以减少运营成本;在互联网环境中如何更好地设置节点，以更好地让信息流动等。