目录

一，模拟退火算法

二，基本步骤

三，一些细节

四，应用实例

1，爬山算法实例

2，货物运输问题

3，力扣1815. 得到新鲜甜甜圈的最多组数

---

一，模拟退火算法

模拟退火算法（Simulate Anneal Arithmetic，SAA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的近似最优解。

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。

二，基本步骤

首先把问题抽象成，在一个确定的解空间内，每个点都对应一个权值，寻找使得权值最小的点。

1，产生一个初始解

2，根据当前解产生一个新的解

3，如果新解的权值更小，则接受新解，替换掉上一个解，如果权值变大，则以某个小概率接受新解

4，迭代若干次或者新解满足特定条件时，迭代结束，否则跳转到第2步

三，一些细节

1，初始解如何产生，对最终解影响不大，如何产生新解的方法影响比较大。

2，权值变大时的接受准则也很重要。

常用的有Metropolis准则：以exp(-(y1-y2)/y1)的概率接受，

还有一种准则是以exp(-(y1-y2)/t)的概率接受，其中t是温度，随着迭代进行衰减。

四，应用实例

1，爬山算法实例

在爬山算法一文中，如果搜索起点是（1,1），求出来的局部最优解（0,0）不是全局最优解。

我们用模拟退火来求解。

每次在当前点的邻域内随机选取一点，并按照概率接受这个新点。

int main()
{
	double x = 1, y = 1;
	double ans = f(x, y);
	for (int k = 0; k < 1000; k++)
	{
		double r1 = rand() % 100 / 100.0 * 2 - 1;
		double r2 = rand() % 100 / 100.0 * 2 - 1;
		double p = exp((f(x + r1, y + r2) - f(x, y)) / f(x, y));
		double pr = rand() % 100 / 100.0;
		if (pr < p) {
			x += r1, y += r2;
			cout << x << " " << y << " " << f(x, y) << endl;
			if (ans < f(x, y))ans = f(x, y);
		}
	}
	cout << "ans=" << ans;
	return 0;
}

输出：

......前面省略很多行

3.62 4 0.109563
4.54 4.06 0.668945
4.14 4.92 0.94852
4.12 5 0.921961
4.32 5.88 0.580623
3.98 5.8 0.372599
4.4 5.36 1.22574
4.72 5.02 1.84845
5.12 4.6 1.67992
ans=1.996

和爬山算法对比，同样是以（1,1）作为起点，只要迭代次数够，就有可能找到更好的局部最优解甚至是全局最优解。

2，货物运输问题

货物运输算法——贪心、蒙特卡洛、模拟退火

3，力扣1815. 得到新鲜甜甜圈的最多组数

有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。

当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。

你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。

示例 1：

输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。
示例 2：

输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4
 

提示：

1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 109

class Solution {
public:
    int maxHappyGroups(int batchSize, vector<int>& v) {
        bs = batchSize;
        int ret = 0;
        for (int i = 0; i < 200; i++) {
            random_shuffle(v.begin(), v.end());
            ret = max(ret, maxHappyGroups(v));
        }
        return ret;
    }
    int maxHappyGroups(vector<int>& v) {
        for (auto& vi : v)vi %= bs;
        int ans = num(v), ret = ans;
        for (double t = 10000; t>=0.0001; t=t*0.98) {
            int i = rand() % v.size(), j = rand() % v.size();
            if (v[i] == v[j])continue;
            v[i] ^= v[j] ^= v[i] ^= v[j];
            int ans2 = num(v);
            ret = max(ret, ans2);
            if (ans <= ans2) {
                ans = ans2;
                continue;
            }
            double p = exp(-(ans - ans2) * 1.0 / t);
            if (rand() % 1024 < p * 1024)ans = ans2;
            else v[i] ^= v[j] ^= v[i] ^= v[j];
        }
        return ret;
    }
    int num(vector<int>& v)
    {
        int s = 0, ans = 0;
        for (auto vi : v) {
            if (s == 0)ans++;
            s = (s + vi) % bs;
        }
        return ans;
    }
    int bs;
};