模拟退火学习笔记

随机化算法没有前途

简介

模拟退火是一种随机化（玄学）算法。广泛应用于各类求最值问题的骗分方法中。简单来说，对于一个多峰函数，要求它的最值，就可以用模拟退火解决。

当然，如果直接随机，正确率显然很低。但是一般的实际问题中，函数即使没有确定的单调性，在一个区间内函数的差值不会太大。于是就可以用到模拟退火来优化这个过程（可以理解为启发式搜索算法）。

概念

温度

在模拟退火中，最重要的概念是温度，也可以理解为当前随机化的区间。温度是一个不断降低的过程，那么每一次随机的区间就会不断缩小，最终就会趋近于一个点。

初始温度、终止温度、衰减系数

初始温度就是最开始的初始温度（如初始区间为 \(10^5\)，就可以将初始温度设为 \(5 \times 10^4\)），终止温度就是算法结束时的温度，而衰减系数就是每次温度降低的系数。一般来说，衰减系数会取 \(0 \sim 1\) 中的一个小数（所谓的调参就是改变衰减系数，一般来说可以通过调参的方法来增加正确率）。

当然，在正式比赛的时候，由于每次程序运行的时间也是随机的，所以可以采用卡时的方法来决定随机次数。

随机选择一个点

以求全局最小值为例，在每次退火的过程中，会在当前的温度范围内随机取一个点，计算该点的函数值，记新点的函数值与原函数值的差值为 \(\Delta E\)。接下来根据 \(\Delta E\) 的值进行分类讨论：

1.\(\Delta E <0\)，则新点一定比原点优，跳到该点上。

2.\(\Delta E >0\)，那么以一定概率跳到新点上。因为原函数不是单峰的，如果只跳比当前点函数值小的点那么可能会跳到一个局部最小值上，而不是全局最小值。此时跳过去的概率根据经验值就可以设为 \(e^{\frac{-\Delta E}{T}}\)，其中 \(T\) 表示当前的温度。（根据指数函数的性质，这样设定的概率一定在 \(0 \sim 1\) 之间，同时差值越低，跳过去的概率也就越高，反之越低。这样也符合实际的过程）。

【模板】A Star not a Tree?

给定一个多边形，求一个点，使得这个点到所有顶点的距离和最小。

数据范围

\(n \leq 100\)。

思路

通过各种证明可以得知，本题的函数图像是一个凸函数，可以用三分套三分求解。但是为了贯彻乱搞的精神学习模拟退火算法，这里就采用模拟退火解决本题。

可以直接按照前面提到的概念来写。也可以通过多次模拟来降低出错的概率。

code：

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=110;
struct node{double x,y;}p[N];
int n;double ans=1e15;
double dis(node a,node b){double dx=a.x-b.x,dy=a.y-b.y;return sqrt(dx*dx+dy*dy);}
double calc(node a){double res=0;for(int i=1;i<=n;i++) res+=dis(a,p[i]);ans=min(ans,res);return res;}//别忘了每次更新答案 
double rand(double l,double r)//在l和r中随机一个数 
{
	return 1.0*rand()/RAND_MAX*(r-l)+l;
}
void simulate_anneal()
{
	node now=node{rand(0,10000),rand(0,10000)};
	double S=1e4,T=1e-14,K=0.995;//起始温度，终止温度，衰减系数 
	for(double t=S;t>T;t*=K)
	{
		node tmp=node{rand(now.x-t,now.x+t),rand(now.y-t,now.y+t)};
		double delta=calc(tmp)-calc(now);
		if(exp(-delta/t)>rand(0,1)) now=tmp;
	}
}
int main()
{
	srand(time(0));int T;scanf("%d",&T);
	while(T--)
	{
		ans=1e18;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
		for(int i=0;i<=10;i++) simulate_anneal();printf("%.0lf\n",ans);if(T) puts("");
	}
	return 0;
}

【应用】保龄球

本题的题目背景较为复杂，建议直接看原题背景。理解了题意以后，可以发现就是将原来的二元组重新排列使得总分最大。

思路

模拟退火也可以解决方案最优的问题，但是需要保证每一次操作不会使函数值发生太大变化。如本题中交换两次游戏之后对于答案的变化量不会特别大。那么就可以按照一般的想法，每次随机两个下标交换，再根据交换前后的差值和随机化来判断是否可以进行交换。

code：

#include
#include
#include
#include
#include
#include 
using namespace std;
const int N=110;
int n,m,ans;
struct node{int a,b;}q[N];
int calc()
{
	int res=0;
	for(int i=1;i<=m;i++)
	{
		res+=q[i].a+q[i].b;if(i==m) continue;
		if(q[i].a==10) res+=q[i+1].a+q[i+1].b;
		else if(q[i].a+q[i].b==10) res+=q[i+1].a;
	}
	ans=max(ans,res);return res;
}
double rand(double l,double r){return 1.0*rand()/RAND_MAX*(r-l)+l;}
void simulate_anneal()
{
	double S=1e5,T=1e-10,K=0.99;
	for(double t=S;t>T;t*=K)
	{
		int x=rand()%m+1,y=rand()%m+1,delta=-calc();swap(q[x],q[y]);
		if(n+(q[n].a==10)==m)//题意
		{
		    delta+=calc();
			if(exp(1.0*delta/t)

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=110;
double ans=1e15;
int n,m,a[N],s[N];
double ave;
double calc()
{
	memset(s,0,sizeof(s));
	for(int i=1;i<=n;i++)
	{
		int k=1;
		for(int j=2;j<=m;j++)
		    if(s[j]=T;t*=K)
	{
		int x=rand()%n+1,y=rand()%n+1;double delta=-calc();swap(a[x],a[y]);delta+=calc();
		if(exp(-1.0*delta/t)