你真的懂模拟退火吗？「上」

· · 个人记录

前言

本文将以个人题目 少女，细雨和最终结局？ （旅行商问题）的板子题为例，深入探讨模拟退火相关问题。难度由浅至深，熟悉模拟退火的同学可以快速跳过前面的部分。本篇为「上」，主要讲解模拟退火的基本知识，技巧优化等问题会放在「下」篇中。

小小说一句，上篇废话很多而干货比较少，确实写的有点臭（）。可以看快一点的说。

什么是模拟退火？——浅层次了解模拟退火

退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。 ----《百度百科》

于是我们可以回答——模拟退火是以计算机形式模拟现实中退火的过程解决问题方案数极大且非单峰函数的随机化算法。

怎么去模拟现实中的退火过程？在咱心目中，模拟退火的概率接受次优解公式是这个算法的核心，而也正是这个公式模拟了现实中退火的过程。我们将马上介绍这个公式，但是更深入的理解还在下文，请稍安勿躁。

p = e ^ {- \frac {\Delta ans} {temp}}

其中 p 表示接受次优解的概率；

$temp$ 表示当前温度，或者你可以形象地理解为“混沌程度”。在温度越高时，原子/分子（完了孩子 WHK 没学好，说错了别笑咱）运动更剧烈，在宏观上就表现为不稳定（这个宏观表现是乱编的，意思差不多就行）。表现在代码里，就是更容易接受没那么优秀的解，在部分随机变化需要一个区间的时候，它还代表了当前状态和下一个随机状态的距离。 然后还有一个退温公式 $temp \leftarrow temp \times \Delta t$，它的意思就是温度逐渐降低，即程序越来越不乐于接受次优解（因为我们马上就要跳出了，这个时候以稳为重。或许你还可以从机器学习的“学习接受度”参数来理解它） 在这个公式的指导下，我们每次由当前状态随机前往下一个状态，由公式决定是否前往下一个状态。答案的总体变化趋势是越来越优秀的，因为我们一定会接受更优解，同时概率接受较劣解以便检查跨过这个较劣解之后是否有更优的解。 ## 为什么是（模拟）退火？——深层次理解模拟退火 为什么「模拟退火」不是「模拟地震」，「模拟火山爆发」？我们都知道退火只是一个比喻，真正的精髓在于模拟退火的公式，我们来分析这个公式。 首先常数 $e$，咱认为选取它的原因只是为了接近现实（？），另外不知道计算机计算以 $e$ 为底的幂是否更快（应该是有的）。事实上我们可以选取任意一个合理的数，不过我们一般不调参它。 然后是 $\Delta ans$，观察它对 $p$ 的影响（控制变量，此时 $temp$ 不变），$\Delta ans$ 越大，$p$ 越小，这是很好理解的——当答案只是差一点点的时候，我们愿意去尝试一下看能不能找到一个更优的解，但是当答案差太多的时候，我们很大概率是掉入了一个无底深渊。 $temp$ 对 $p$ 是正贡献，这个并没有什么好说的，因为温度的定义就是接受次优解的泉值。 为什么是退火？这个问题等价于为什么概率公式是这样一个指数函数（咱一直强调，模拟退火的本质就是这个概率公式）？浅显的来讲，因为当“答案相差太远”或者“温度太低”的时候，我们都不希望接受次优解，而指数函数是一个符合我们预期的模型（这也许可以叫做拟合？）。与此同时，$e^x$ 在负定义域上，值域为 $(0,1)$，刚好符合我们的要求。你可能觉得其他函数可以通过等比缩放，平移等方式做到同样的效果，但是那往往会导致很多问题，比如平移需要导入一个常数，而这个常数很可能会对接受概率造成不可控的影响。 而退温公式也是指数形式的，这个具体原因咱不是很清楚。一个猜测是，为了和概率公式的指数形式对应。考虑温度和概率是一个映射关系，可能温度 $(1,10)$ 对应了 $(1\%,5\%)$，但是必须要温度 $(100,10000)$ 才能对应 $(50\%,55\%)$，如果是温度不断减去某一个数的话，看似它是平均降温，实则映射在概率轴上是指数降温；温度指数级下降，反而对应的是平均降温。**这一段为个人的感性理解，在数学上并没有证明。** 但是个人认为应该是正确的，有无大佬来证明一下（）。 ## 什么时候适合使用模拟退火？ 在讨论怎样使用模拟退火前，我们一定要先明确哪些情形适合使用模拟退火。看到一个最优化问题就无脑甩退火上去是非常低效的行为，因为很多时候 退火 $\ll$ 暴力，而退火调参常常是个无底洞——咱就是一个经典的反面例子，打到一道题可以退火就开始调参到考试结束，最后暴力没写完是非常亏的。一般来说，适合模拟退火的题目符合以下几个特点。 1. 范围值域小。一般正解复杂度在 $O(n^4)$ 左右导致 $n$ 的范围只有 $100$ 的题是最适合模拟退火的，正解是指数复杂度就更好了！（$n$ 大约在 $20$ 左右） 2. 状态少。其实就是“范围值域小”的本质，因为最优状态只有（或接近只有）一个，状态越少肯定越容易得到正解。 3. 函数连续。例如 [平衡点问题](https://www.luogu.com.cn/problem/P1337) 的两个坐标和答案之间的函数显然是一个非常连续的函数，这种情况下就算状态很多（算上精度应该有几百亿组状态？）也可以使用模拟退火。反例可以拿咱今天刚好遇到的一道题来讲。给定序列 $a$，求 $r-l+1$ 最大（长度最长）的区间使得 $\max \limits ^{r} _{i=l} + \min \limits ^{r} _{i=l} \gt r-l+1$。我们选取的估价函数（下文仔细讲）会陡增陡降，导致容易求不出来最优解（我们模拟退火的原理就是逐步“逼近”最优解，在没有根本规律的情况下怎么“逼近”呢）。 4. 答案可以作为估价函数。可以注意到上文我们直接使用 $\Delta ans$ 表示估价函数，但是在部分题目中答案不等于估价函数。例如上面的例子，答案是 $r-l+1$，但是我们又要求某式子大于 $r-l+1$，于是咱将估价函数设为：当等式成立时为 $r-l+1$，不成立时为 $-1$ 的分段函数。这个估价函数显然非常有问题，也不满足上面要求的连续，但是咱设计不出来更好的估价函数了，所以说最好答案本身就可以当做估价函数。 5. 增量求解答案的复杂度低。模拟退火的正确率很大程度上和退火次数成正比，时间不变的情况下，求解答案的复杂度越低显然退火次数越多。前面的“增量”二字的意思是，有可能一个问题从零开始求答案需要很多时间，但是只是改变一部分策略重新计算答案就不需要那么多时间了。例如计算平面上路径长度，复杂度 $O(n)$，但是只是交换两个点，计算复杂度为 $O(1)$。但是如果计算一次答案都需要 $O(n^2)$ 的时间复杂度且 $n = 100$ 的话，模拟退火很可能行不通。 这意味着什么呢？首先当你可以写出一个较优的多项式时间复杂度的暴力的时候，可以优先考虑暴力！（显然不会有人放弃 $O(n^3),n=500$ 的暴力去写模拟退火吧）其次遇到 $n \gt 1000$ 基本可以放弃模拟退火了。即使是骗取部分分，阶乘或者指数级别的暴力（通常为搜索，全排列枚举或者状压）写起来比模拟退火也要更轻松，而且答案有确定性。 另外不要像某个小傻瓜一样在 Subtask 捆绑的题目中使用模拟退火。 总之，咱不鼓励你在大多数想拿部分分的时候使用模拟退火，因为真的效率很低；而模拟退火**通常**无法在正解的值域范围内成功求解，因此它的地位真的很尴尬，上不去下不来了属于是。 那么什么时候适合使用模拟退火呢？ 像[TJOI2010 分金币](https://www.luogu.com.cn/problem/P3878)一样值域范围很小（$n \le 20$）（不过这道题是多测，多测退火同样需要谨慎）。 [小 Y 和地铁](https://www.luogu.com.cn/problem/P4005) 这道题值域同样非常小。事实上它的正解是状压大分讨，如果值域看上去很状压但是因为某些原因写不出状压解的话，可以考虑模拟退火。 像[JSOI2004 平衡点](https://www.luogu.com.cn/problem/P1337)一样函数十分连续，且答案可以直接用于估价函数。（这道题的负面因素是，计算复杂度 $O(n)$ 太高了） 如果你能够参加各种大学夏令营，可能会遇到 [少女，细雨和最终结局？（旅行商问题）](https://www.luogu.com.cn/problem/U379702) 之类的近似问题（可能是 NP 问题）。但是 CNOI 貌似还没有出过近似问题？在 OI 赛场上大概率见不到吧。 ## 使用模拟退火的心态 使用模拟退火需要端正心态。不要期望能得到满分（尤其赛场上没时间没数据调参），但也不能抱着“就拿部分分”的心态去写模拟退火——因为通常部分分暴力反而比模拟退火好写。如果写一个模拟退火，能 $100\%$ 解决小数据，$50\%$ 解决中数据，$20\%$ 解决大数据，它就比纯暴力要优秀。然而要考虑时间问题（模拟退火再怎么说需要一点时间调参，不然很难正确），请把模拟退火放到暴力之后完成。如果能，请分类 Subtask 用暴力解决小数据（万一模拟退火写错了，亦或者是正确性太低），保证拿到该拿的分。 然后就是玄学问题咯，烧烧香什么的也许有用，把种子加上 $10181108$ 也或许有帮助（但是不要为了整活设置固定种子，防止黑心出题人针对）。不过始终记住一点——模拟退火的正确率和你的参数质量，算法质量是有关的，它是一个确定值。妄想赛场测试正确率不超过 $10\%$，交上去能拿 $90pts$ 是违反概率学的。说白了想要拿更多分就要更合理更科学地设计退火算法。具体怎么设计呢？这就是我们「下」篇的内容了~ ## 后记 本来是想写的正式一点的，结果越写到后面越口水话，语文水平着实不够啊（悲）。感觉知识含量太低了，咱下次一定改进。 本篇内容说来说去其实没啥实质性的内容，真正有用的内容都放到下篇咯（悄悄打广告）