与贪心的区别
出现较好的解就使用，发现不了就形成解。缺点：跳不出局部最优解
模拟退火：与贪心类似，但可以以一定的概率跳出局部最优解，通过两个式子实现，Metropolis准则。玻尔兹曼分布
模拟退火算法和物理退火过程的对应
| 模拟退火算法 | 物理退火过程 |
|---|---|
| 解 | 粒子状态 |
| 目标函数 | 能量 |
| 最优解 | 能量最低态 |
| 设定初温 | 设置加温到几度 |
| 扰动 | 热涨落 |
| metropolis采样过程 | 热平衡，粒子状态满足玻尔兹曼分布 |
| 控制参数的下降 | 冷却 |
伪代码
缩进代表层级嵌套关系。
构造一个初始解，令当前解为该解。
设置初始温度，初始温度要设得比较高。
主要算法，while循环：
循环条件可以是温度的阈值或者是解不怎么变化了
for循环，设置一个步长
平衡过程，在该温度下，使达到平衡（metropolis），恒温下1到$T_L$步
- 根据当前解随机生成一个邻解，跟当前解非常接近（扰动，for循环就是多次扰动）
计算邻解的目标函数（花费、路程、大小、钱数等等），减去当前解的目标函数，求得目标函数变化量
如果变化量小于0（即优化了），使用该邻近解；如果没有优化，则用metropolis准则，看是不是要跳出坑，跳出则使用该邻解。（温度越高越容易跳出坑）
平衡后设置新温度，即降温。
模拟退火算法设计要素
初始解的生成
如果初始解比较好的话，收敛得就很快。
通常以一个随机解作为初始解，并保证理论上能生成解空间中任意的解。（一般要多做几次模拟退火，即试用不同的初始解，再取最优的）
也可以是一个挑出来的比较好的解。这种情况下，初始温度应当设置得较低（降低它扰动到其他不好的解的概率）。
初始解不宜“太好”，否则很难从这个解的邻域中跳出。
邻解生成函数
应尽可能保证产生的候选解能遍布整个解空间。
邻域应尽可能的小，能够在少量循环内充分探测，但每次的改变不应该引起太大的变化。
初始温度如何设定
初始温度应该尽可能的高，以确保最终解不受初始解影响，但过高又会增加计算时间。
均匀抽样一组状态，以各状态目标值的方差为初温。（随机生成一组解）
等等
※ 正式开始退火算法前，可进行一个升温过程确定初始温度：逐渐增加温度，直到所有尝试运动都被接受，将此时的温度设置为初始温度。
等等
等温步数如何确定
等温步数即同一个温度下，跑几个循环。
等温步数也称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目，通常取决于解空间和邻域的大小。如果解空间小，步数可以小一点。
等温过程是为了让系统达到平衡，因此可通过检验目标函数的均值是否稳定（或连续若干步的目标值变化较小，这个可以写一个函数来检测）来确定等温步数。等温步数可以长，也就是多平衡一会而已。
等温步数受温度的影响。高温时，等温步数可以较小；温度较小时，等温步数要大。随着温度降低，增加等温步数。（因为高温的时候比较混乱， 温度小的时候就在不停地收敛了），可以将等温步数设置成一个温度的函数。
有时为了考虑方便，也可以直接按一定的步数抽样。不区分高温和低温时的等温步数，大一点就好啦。
如何降温
一般要慢慢地降
经典模拟退火算法降温方式
快速模拟退火算法降温方式
常用的其他降温方式
后边两种比较常用
花费函数
不要太复杂，应该能被快速的计算，花费函数的计算是程序的可能瓶颈。
一般用目标函数构造花费函数即可。目标函数、目标函数的倒数/相反数经常直接作为花费函数
终止条件
理论上温度降为0才终止退火算法，因为此时没有概率跳出坑了。但实际温度较低时，尝试的接受概率就几乎为0了。
设置终止温度的阈值，或设置外循环循环迭代次数。
算法搜索到的最优值连续若干步保持不变。
其他
有人说这就是遗传算法+梯度下降。老师说这个算法属于一种蒙特卡洛算法，和蒙特卡洛算法类似。国赛和美赛几乎不会考TSP，太简单了，小比赛才有可能让选手练手。
作者：@臭咸鱼
转载请注明出处：https://chouxianyu.github.io
欢迎讨论和交流!