数学建模【模拟退火】

一、模拟退火简介

模拟退火的基本思想，就是走出舒适圈，多去“试一试”，万一成了呢？

• 舒适区：当前处于局部最优解
• 试一试：随机试探新解，有更好的解就直接选择新解，没更好的则以一定概率选择新解
• 万一成了：找到了更优甚至最优解
• 也可能没成：求的新解反而更差了
• 一次没成，多试几次：继续随机试探

说到模拟退火，就要从贪心算法失效开始。这里以爬山为例子

• 假如小魏想要在日落前爬.上一座山的最高峰(求最优解)
• 但山中云雾缭绕、视野受限，只能看到当前位置附近一-定范围内的情况
• 贪心算法：在视野内选取一个点，如果更高，就过去；否则就不去
• 直到视野内没有更高的点，则输出当前解作为最终解
• 显然，当小魏走到某个小山峰时，四周看不到更高的点，就不会走下山去寻找更高的山峰从而陷入了局部最优解

但是以模拟退火的思想

• 那么在可见范围内，随机选择一点
• 如果该点比当前位置更高，就直接去该点(优化)
• 如果该点更低，那么就多掷几次硬币，结合该点与当前点的高度差决定去不去(一定概率)
• 在刚才的局部最优解的山峰，会有一定概率走下了当前山峰，从而发现另一个山峰的上坡
• 从而就有可能走上新的更高峰

模拟退火的关键点

• 时间有限，需设置终止条件(“退火”过程中温度不断降低，剩余时间不多时就别乱跑)
• 且算法需要做到：若当前所处的山峰越高，前往低点的概率越低(概率的表达式)
• 这样才能使求得最优解的概率更大
• 关键在于，“概率”怎么求

二、适用赛题

NP-hard问题

• 旅行推销员问题（Travelling salesman problem，TSP）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路
• TSP问题是组合优化中的一个NP-hard问题，该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，传统算法难以求解
• 此时就适合用模拟退火等启发式算法求近似解

适用赛题特点

• 有些规划类问题的可行解过多，传统算法运算时间过长
• 能够列出可行解的任一排列(例如题目要求最短回路，起码能先写出个回路作为初始化)

国赛题目：高等教育学费标准

• 假设高校所需1000万经费，涉及多种筹款路径，理论上的筹款组合方案过多，若暴力求解可能费时几十小时，此时就适合模拟退火求解

三、模型流程

四、流程分析

这里以一个例题贯穿流程分析：遍历全国省会

• 已知全国34个省会城市(包括直辖市、自治区首府和港澳台)的经纬度坐标(第一个为北京)
• 现在需要从北京出发，到所有城市视察
• 要求每个城市只能到达一次，并最终回到北京
• 求视察路线方案，使得总路径最短

问题分析

• 若把所有可能的路线方案都列出来再求最小值，则有33! 种方案
• 这是10的36次方数量级，运算时间会很长
• 此时可考虑使用模拟退火

所有可行解

• 本题的解空间就是固定起点和终点的所有可行路线的集合
• 题目要求以北京作为起点和终点，那么设起点北京为1号城市x1
• 余下需要遍历的33个城市依次设为2，3，.... 34号城市x34
• 最后还需回到北京，设终点北京为35号城市x35
• 因为起点与终点固定，则共有33!个可行解

1.目标函数

这道题的目标是总路程最短

• 从1号x1出发遍历34个城市最后回到1号x35
• 第i号城市xi与第i+1号城市xi+1之间的路径长度设为dxixi+1

则目标函数：

2.初始化

• 设定一个初始温度T0和问题的一个初始解x(0)
• 有那么多种可行解，可以随便选一个作为初始解
• 例如本题，可以把原始数据的排列直接作为初始解，解为x1x2 x...... x35
• 或利用蒙特卡罗法求一个较好的初始解

3.是否结束

这里是否结束有两个方面

同一温度是否结束，指的是在一个相同温度情况下，进行了多次产生新解，是否接受的过程，比如设置的一个温度进行100次，那么在进行100次后，这个温度下的操作就完成了，需要将温度按照一定比例下降，然后重复刚刚的操作。

温度是否足够小

在退火过程中需要选定降温系数α，求得新温度Ti+1 = αTi，一般都是设为0.999。直到温度足够小，设终止温度为e = 10的负30次方，当T ＜ e时终止迭代，输出最终解

在退火过程足够慢，每个温度下寻找新解的次数足够多，则最终解是全局最优解的概率越大

4.产生新解

在当前温度Ti下随机求一个新解，制定产生新解的准则不唯一，能确保随机即可

5.计算差值判断接受

当有了新解，需要判断是新解好还是当前解好，所以需要计算两个解的值，本题就是计算两个解的路程，然后用新解的路程减去当前解的路程得到差值△f

接下来判断是否接受新解

• 接受准则

• 表达式中判断准则exp(- △f/Ti)是由热力学得到的灵感，这里不作讲解
• 题目求总路径最短，如果△f < 0意味新解的总路径更短，则接受新解作为当前解
• △f > 0意味新解总路径更长不如当前解， 但为防止陷入局部最优解，仍以一定概率接受新解
• 显然，△f越小， 意味着新解的总路径比当前解的总路径短更多，那么接受新解的概率就更大

五、补充

理论上模拟退火可以找到全局最优，不过此证明需要深厚的数学功底。这里不作讲解。