『笔记』模拟退火

部分图片转自：RPChe_

引言

日常生活中，我们经常会遇到一些函数求最值的问题，例如单峰函数求最值问题此处输入图片的描述

就例如上面的图片，那么现在就可以引入一个新算法：爬山算法
顾名思义，爬山算法可以形象的理解为人在山坡上上向着坡顶爬去的一个场景，可以通过左右比较范围内的值，通过找到更优解，进而缩小范围，直到找到单峰函数的最大值。（显然可以用三分）

然而这个算法还是存在缺陷的，很可能会让我们陷入局部最优解导致无法找到最终的全局最优解，就例如下面的图片此处输入图片的描述

特别明显的能看出很容易就会陷入局部最优解中

那么此时，就引入了一个玄学算法--模拟退火！此处输入图片的描述

简介

模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明此演算法。模拟退火算法是解决TSP问题的有效方法之一。

模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。

原理

模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

简化来说就是用来求多峰函数的最值问题的一种算法，通过温度的降低，可以得到新的解，温度越大，解得变化量也就越大，随着温度的降低，解也越来越稳定，当最后达到最终温度的时候，即物理上的结晶，此时求出来的即为最优解。

实现方法

首先引入一些变量，当前的最优解 (E_0) ,通过降温的到的解 (E) ,两个解的差值 (Delta E) 。以及当前的温度 (T)，初始温度 (T_0),最终温度 (T_k)，降温系数 (d) 。

(d) 是一个十分接近 (1) 但是小于 (1) 的小数，(T_k) 是一个十分接近 (0) 但是大于 (0) 的小数。

(T_0) 一般设置在(2000-5000)之内，(d) 设置在1e-8~1e-15之内

首先可以用公式来判断是否进行更新当前的解。

1、如果当前的 (Delta E) 满足条件，直接转换。
2、反之如果不符合，那么根据Metropolis准则进行判定是否接受。

拿找最小值为例

首先经过降温我们得出了新解，和当前最优解的差值 (Delta E) 如果 (<0),那么直接转换最优解就好了，因为当前的解一定是比之前更优的，反之，并不符合条件，那就根据公式以一定概率来接受他,其概率为:

[e^{frac{-Delta E}{T}} iff exp(-Delta E/T) ]

至于为什么会有接受它一说，谈一下个人理解，首先，我们所求的是要找全局的最优解，如果仅仅趋向于当前最优，那么很有可能找到的是一个局部最优解，那么就和爬山算法没有什么区别了。通过一定概率接受它，那么就可以从另外一个点去出发，来找它的解，增加了找到全局最优解的可能性。

对于接受的概率（假定当前(Delta E) 为正），当 (Delta E) 较大时，也就是我们遇到了一个十分劣的解，那么此时的 (-Delta E) 就会相对的较小，那么接受的概率就越小；如果当前的 (Delta E) 较小的话，那么我们遇到了一个有些劣的解，显然此时的 (-Delta E) 会大一些，那么接受的概率也就会大一些。当 (T) 大的时候，那么此时接受的概率也就会增大，大部分的解都会别接受，如果当温度降到很低的时候，那么此时接受的概率会大大减少，也就稳定在了一个最优解内，当然为了保证解更加正确，当退火完成之后，考虑一下在时间允许的范围内，在当前解的一个范围内继续尝试退火。

列出一个图清晰形象的观摩一下退火的全过程
OI-wiki-photo

算法改进

（1）设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性；

（2）设计高效的退火策略；

（3）避免状态的迂回搜索；

（4）采用并行搜索结构；

（5）为避免陷入局部极小，改进对温度的控制方式；

（6）选择合适的初始状态；

（7）设计合适的算法终止准则。

列出几个我的常用数据，实战效果较好

(T=2000,d=0.996)
退火一般进行 (6) 为最佳

模板

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
...
const double T_begin=..;//退火初温
const double T_end=..;//末温
const double V=..;//速率
void fz()
{
	... //若题目有关序列操作模拟退火常需要随机生成一个序列(random_shuffle)
}
void calc()//模拟退火最耗时的函数，写的好题就A了
{
	...//有一个解，需算出答案，后与已知最优解比较
}
void SA()//模拟退火主要函数
{
 	fz()
  	...//改变当前解，得到一个新答案,常用rand()；
  	int del=tmp-ans;//tmp：当前接，ans：已知最优解
  	if (del>0) 更新最优解，当前值//当前解更优
	else if (exp(del/T)/RAND_MAX>(double)rand()) 更新当前值，以一定概率接受劣解
	else // 讨论情况
}
int mian()
{
  	srand((int)time(0))；//玄学随机种子,随便改数->逆天改命
	...
  	while(clock()/CLOCKS_PER_SEC<0.9) SA();//计算时间的
   ...//输出答案
	return 0;
}
//还有两种经常用的随机生成格式

1、矩阵中坐标版： nowx=rand%n,nowy=rand%m;
2、不规则平面内坐标版：nowx=ansx+((rand()<<1)-RAND_MAX)*T
                     nowy=ansy+((rand()<<1)-RAND_MAX)*T

例题

P3936 Coloring 矩阵中两个位置微调问题，恶心调参数

P2503 [HAOI2006]均分数据序列随机打乱，随机贪心

P4035 [JSOI2008]球形空间产生器多维空间找点，数论（高斯消元可过）

P5544 [JSOI2016]炸弹攻击1 二维空间不规则找点