当前位置：首页 > article >正文

【算法】模拟退火算法学习记录

article 2025/1/5 13:51:36

写这篇博客的原因是博主本人在看某篇文章的时候，发现自己只是知道SGD这个东西，但是到底是个啥不清楚，所以百度了一下，然后在通过博客学习的时候看到了退火两个字，想到了本科做数模比赛的时候涉猎过，就上bilibili搜索讲解视频学习了退火的算法，感觉看完之后收获还蛮大的，所以写下这篇博客作为记录。话不多说，上正文——

一、算法介绍

模拟退火算法（Simulated Annealing, SA）是一种概率型优化算法，它受到物理学中固体物质退火过程的启发。退火过程是指将固体加热后再慢慢冷却，使其达到能量最低的稳定状态。模拟退火算法将这一过程应用于组合优化问题，通过模拟退火过程来寻找问题的全局最优解。

举个栗子，逼近下图函数的最大值，利用退火的思想就是经过多次迭代（退火），逼近函数上的A点。

因为模拟退火算法借鉴的是固体的退货原理，相信理科生都能很快get到，温度越高，固体内部的分子能量越高，均处于快速无序的运动，当温度慢慢降低时，分子的能量降低，慢慢地趋于有序，到最后达到常温的时候，能量达到最小，此时内部的分子最为稳定。从前面这段话我们可以解析出几个点——

温度越高，分子越乱，放在退火算法里就是温度越高，x的跳变范围越大
温度变化是缓慢的，特别特别慢那种
温度不再变化之后，也就是趋于有序，放在退火算法里也就是达到了最优

二、算法大框架

模拟退火算法本质上就是一个循环算法。（博主本人在练习代码的时候，感觉核心有点像暴力枚举，啊哈哈哈哈）

设定一个初始的温度T
每个循环就是退火一次
降低T（通过将T和一个降温系数相乘来达到慢慢降温的效果）
T无限接近于0的时候退出循环

将上面的流程以伪代码的形式展示：

double T; //初始温度
double dt; //降温系数，小于1但是趋于1，类似0.99这种
const double eps = 1e-4; //用于判断T是否趋于0

while(T > eps)
{
    //退火流程
    //……
    

    T = T * dt; //降温
}

三、退火算法详解

这一部分主要是来详细介绍模拟退火算法的核心部分。首先需要现在定义域中随机取一个自变量x，这样根据函数又可以得到f(x)。下一步，自变量根据当前温度进行随机变化得到x0，又得到f(x0)。最后，根据我们的具体需要来决定是一定接受还是按概率接受。

可能有的同学看完上面这段脑袋都大了，我们就拿上面的函数求最大值来举个栗子——

图中的x就是随机选择的一个自变量，x0是根据当前温度随机跳变后的自变量。在俺们这个例子中，我们是想要找到函数的最大值，如果随机跳变后的自变量对应的函数值大于当前自变量的函数值是百分百接受的，也就是直接进行数据更新，也就是上图中从x跳变到x1的情况；但是如果跳变后的自变量对应的函数值小于当前自变量的函数值，这样的情况是按概率接受的（这种情况也很好理解，如果小于就直接拒绝，这样很容易就陷入到局部最优了）。

那么这个按概率接受又是啥嘞？我们用一个公式来表示，具体的推导大家感兴趣可以自己找一下，俺在这里就不详细展开了。

$e^{\tfrac{\Delta f}{KT}}$

其中， $\Delta f$ 是函数值的变化量，K是一个物理学常数，T是当前温度。根据指数函数的性质，整个指数部分小于0时函数值是小于1的，才满足概率小于等于1的条件，所以同学们在判断接受的时候要尤其注意指数部分的形式。

所以总结一下就是：

随机跳变后的函数值如果结果更好，我们一定接受它(即x=x0,f(x)=f(x0))
随机跳变后的函数值如果结果更差，我们以的概率 $e^{\tfrac{\Delta f}{KT}}$ 接受它

将模拟退火算法以伪代码形式展示：

//三板斧
double T = 2000; //初始温度
double dt = 0.993;  //退火率（温度下降率）
const double eps = 1e-14;  //用来判定T是否无限趋近于0

//函数，传入自变量参数x，得到f(x)
double func(double x)
{
	return f(x);//函数内部的功能具体问题具体分析
}

//退火算法的核心
void SA()
{
	//先随机生成一个x值，这里的x值不是说只能是一个参数，可以是一组参数，也是具体情况具体分析
	double x = rand();
	//得到随机数对应的f(x)
	double y = func(x);
    //退火算法开始
	while (T > eps)
	{
		//先算出随机跳变后的自变量，可以是减小，也可以增大
		double dx = x + (2 * rand() - RAND_MAX) * T; //因为是与当前温度相关的跳变，所以要乘以T

		double dy = func1(dx);//计算得到跳变后自变量对应的函数值
		//退火函数的关键！！
		if (满足百分百接受的条件) 
		{
			y = dy;
			x = dx;
		}
		else if(exp((y-dy)/T) * RAND_MAX > rand())//否则按一定概率接受
		{
			y = dy;
			x = dx;
		}
		else
		{
			T = T * dt; //温度缓慢降低
		}
	}
	cout << x << endl; //打印结果
}

四、应用举例

利用模拟退火算法来实现计算一个数的平方根，给出完整的c++代码，方便同学们学习调试。（因为博主也是从其他博主那里学习的，我感觉这块的代码还有蛮多可以改进的，因为c++很少使用全局变量，会破坏封装性，而且使得代码不好迁移）

#include<iostream>
using namespace std;

double n;
//三板斧
double T = 2000; //初始温度
double dt = 0.993;  //退火率（温度下降率）
const double eps = 1e-14;  

double func1(double x)
{
	return abs(x * x - n);
}

void SA1()
{
	//先随机生成一个x值
	double x = rand();
	//得到随机数对应的f(x)
	double y = func1(x);
	while (T > eps)
	{
		//先算出x的跳变数，可正可负
		double dx = x + (2 * rand() - RAND_MAX) * T;
		//保证dx为正数，因为只有正数才有平方根
		while (dx < 0)
		{
			dx = x + (2 * rand() - RAND_MAX) * T;
		}
		double dy = func1(dx);
		//退火函数的关键！！
		//需要计算得到的func函数值足够小
		if (dy < y) //当得到的函数值小于原来的函数值时百分百接受 
		{
			y = dy;
			x = dx;
		}
		else if(exp((y-dy)/T) * RAND_MAX > rand())//否则按一定概率接受
		{
			y = dy;
			x = dx;
		}
		else
		{
			T = T * dt;
		}
	}
	cout << x << endl;
}

void testSA1()
{
	cout << "请输入要计算的数：" << endl;
	cin >> n;
	SA1();
}

int main()
{
	testSA1();
	return 0;
}

整体的流程跟前两点讲的是完全吻合的，同学们可以结合着前面的理论内容、代码以及注释来理解学习，整个的学习脉络还是非常清楚的。

模拟退火算法就先写到这，有任何问题欢迎同学们指出，大家一起学习进步嗷~

参考：

详解随机梯度下降法（Stochastic Gradient Descent，SGD）_随机梯度下降公式-CSDN博客

速通模拟退火 - 分享今天心情

查看全文

http://www.kler.cn/a/464223.html