# 模拟退火

## 引入

### 爬山算法

爬山算法, 即**贪心算法**, 在当前解得临近空间中选择一个最优解作为新的当前解. 因此, 最后得到的解是一个**局部最优解**, 往往不是全局最优的

### 模拟退火算法

模拟退火算法可以有效地解决**陷入局部最优解的问题**, 从而找到一个全局最优解. 模拟退火算法也是一种贪心算法, 只不过对爬山算法进行了改造, 在其基础上增加了**随机因素**, 即**以一定的概率接受一个比当前解更差的解**, 通过这个随机因素, 使得算法有可能跳出这个局部最优解.

## 算法

### Metropoils算法

此算法是模拟退火算法的核心, 前面说道以一定的概率接受一个更差的解, 从而可能跳出局部最优, 这个概率的计算就是靠此算法.

Metropoils算法定义了一个**转移概率**$$P$$, 由状态$$i$$转移到状态$$j$$时, 接受的概率为:

$$P(i,j)=\begin{cases}1, \quad f(j)\ge f(i) \ \exp(\frac{f(i)-f(j)}{t}), \quad \text{otherwise} \end{cases}$$

即当新的解表现比之前好时, 一定接受新解. 当表现不如之前时, 根据表现的差距, 以及一个**退火温度**计算得到一个概率, 以这个概率接受这个新解.

### 温度t

现实中, 冶炼固体退火的时候, 温度是要徐徐下降, 使得温度在每个阶段达到平衡, 最后趋于稳定. 模拟这种情况, 模拟退火算法中, 温度$$t$$需要满足以下几点:

* 初始温度较高, 保证初始阶段可以搜索到全局最优点, 如果太小, 就无法跳出局部最优解
* 温度是要一直衰减的. 温度的衰减也是有各种策略的, 一般使用线性的衰减函数, 即$$t:=at$$, 其中$$a$$一般取小于1且又很接近与1的数.

### 停止条件

* 温度$$t$$降低到某个阈值
* 连续多个解对应的表现没有变化

## 关键问题

模拟退火算法更像是一种思想, 通过灵活的设计, 可以应用在很多情景中. 设计时需要考虑一下几点:

* 新解产生的策略: 根据当前解的表现, 生成新解, 如使用**后验概率**
* 退火策略: 温度随着迭代的进行逐渐降低的策略
* 接受策略: 往往使用Metropoils算法, 也可以根据实际的情况, 进行调整

## 例子

甚至在[TSP问题](https://mp.weixin.qq.com/s?src=3\&timestamp=1542641634\&ver=1\&signature=DQSWlMsyL3Lph69znfkghF-DXRyy2PHcKo3UqjnGoebTnokBE2oehDS3zUe34MOCE7AXJM7kT3RreNixCypA2sJO-tDjB7GFxw2*HrZzcniZ4t8qnQhWv4JZtisLj2ntT6-eygCNzN0viyvGo5cYqvRlHxKY0X6*qNDmH*di9Ks=)都可以使用, 可以根据上面的几个点, 对应地查看在该例子中是如何使用模拟退火算法的, 理解算法细节.

## 参考资料

[模拟退火](https://www.cnblogs.com/GuoJiaSheng/p/4192301.html)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/ji-qi-xue-xi/you-hua-suan-fa/tui-huo-suan-fa/mo-ni-tui-huo.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.