打卡第一天 模拟退火

找个地方帮自己mark一下

⭕️打卡

我昨天计划在今天看遗传算法，但是翻开黄书发现，现代优化算法这一章节里，模拟退火排在遗传的前面。所以今天就先学模拟退火了。在这之前要提一下什么是现代优化算法，这个问题会涉及到复杂度、什么是nph问题、局部最优与全剧最优，我把查的资料都整理到了一起，在截图里面。

了解完了之后我去看黄书里面模拟退火的部分，之前一直很好奇为什么这个算法名字这么酷。看了才知道是把材料学的研究思想套用过来了。材料学里，从高温开始缓慢降温的过程就叫退火。而用这种思想，把一些要解决的问题视作粒子，用这个思想去解决问题就是模拟退火的过程～所以叫模拟退火。我bb的有点多hhhh 因为我之前一直觉得这个名字很神奇。

那么，退火的思想是什么样子的呢。这个我觉得黄书真的非常理论，非常严谨，但是实在不容易理解。我看了几个视频翻了博客之后，感觉有一个博主说的非常好。假设有一个凹凸不平的平底锅（凹陷的深度和凸起的高度都不一样），我们在任意一个凸起上扔一个豆子下去，豆子会在锅里来回的滚动，滚过一个个的凹陷（更有解）又滚出来，最终停在最低的那个凹陷（最优解）里面。而在豆子滚的这个过程里，刚开始它具有的能量是最多的（重力势能转化，后面就摩擦了），所以它也会出现往凸起的地方走（向上走，较差解）。这个豆子这一次往下/上之后，再进入下一次的向上/下，中间这个过程就是状态的转移。模拟退火的重点就在状态转移上。翻开黄书看那个非常华丽的公式，虽然看起来很费劲，但是就主要说明了一件事：每一次转移，如果往上跑，有一定的概率接受；如果往下跑，直接接受。

这个过程现在说起来感觉比较简单……当时看黄书的我真的是如读天书啊，感觉我都看懂了，但是让我说这个算法的核心啥也说不出来。查了半天资料才搞明白。

关于写代码，我实现了最简单的模拟退火，见第三张截图。我想通过模拟退火来找一个多项式函数在区间[0,10]上的最大值。figure1记录了每一次转移发现的局部最优（通过内部的for1:10实现找每一轮转移的局部最优），figure2是对每次找出最大值对记录，画出图可以看到，由于初始温度的选择是随机的，所以模拟退火刚开始可能出现较差解，但到后面就趋向稳定了。这里涉及到一个出口的问题。看figure2可以看到60之后基本就没什么提升了，设置的出口条件不到还会跑。如果最低温度（出口）设的太高就找不到最优，如果太低就会像figure2一样，后面跑的几十轮都是没什么用的，拉低性能。

退火 模拟退火