目录

一,模拟退火算法

二,基本步骤

三,一些细节

四,应用实例

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;
};

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐