模拟退火法衰减参数什么意思
发布网友
发布时间：2022-12-23 04:15
共1个回答
热心网友
时间：2023-06-27 20:54
原理
模拟退火：是一种随机算法，用于解决最优化问题。要求求解的问题对应的函数要有连续性。
模拟退火算法是模拟物理过程，有如下参数：
（1）温度t：即步长。分为初始温度和终止温度，对应代码中就是初始搜索范围和终止搜索的范围。
（2）衰减系数：每次搜索范围减小的比例，是(0, 1)中的一个数，可以取0.999，需要手动调节。
在每次迭代的过程中，我们在给定步长区间内随机一个新点，令dt = f(新点)-f(当前点)，如果求函数极小值的话，分为两种情况：
（1）dt<0，则跳到新点；
（2）dt>0，则以一定该概率跳到该点，且dt越大，跳过去的概率越低。
跳过去的概率值可以取为 e − d t / t e^{-dt/t} e−dt/t。
模拟退火的过程可能会收敛到局部最优解，但是这个过程我们可以做多次，这样收敛到局部最优解的概率就很小了。比如达到局部最优解的概率是0.99，则我们做1000次，达到局部最优解的概率是： 0.9 9 1000 ≈ 4.3 × 1 0 − 5 0.99^{1000} \approx 4.3 \times 10^{-5} 0.991000≈4.3×10−5。
2. AcWing上的模拟退火题目
AcWing 3167. 星星还是树
问题描述
问题链接：AcWing 3167. 星星还是树
分析
本题求解的这个点是费马点，即到所有点距离和最小的点。如果是一维的，排个序找中位数即可。
可以证明，这个函数是个凸函数，具有连续性。使用模拟退火求解即可。
代码
C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 110;
int n;
PDD q[N];
double ans = 1e8;
// 返回[l, r]之间的随机小数
double rand(double l, double r) {
return (double)rand() / RAND_MAX * (r - l) + l;
}
double get_dist(PDD a, PDD b) {
double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
// 计算p到给定点的距离和
double calc(PDD p) {
double res = 0;
for (int i = 0; i < n; i++)
res += get_dist(p, q[i]);
ans = min(ans, res);
return res;
}
void simulate_anneal() {
PDD cur(rand(0, 10000), rand(0, 10000));
for (double t = 1e4; t > 1e-4; t *= 0.9) {
PDD np(rand(cur.x - t, cur.x + t), rand(cur.y - t, cur.y + t));
double dt = calc(np) - calc(cur);
if (exp(-dt / t) > rand(0, 1)) cur = np;
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
for (int i = 0; i < 100; i++) simulate_anneal();
printf("%.0lf\n", ans);
return 0;
}
登录后复制
AcWing 2424. 保龄球
问题描述
问题链接：AcWing 2424. 保龄球
分析
本题需要求解最大值，相当于求全排列中的最大值。
每次我们可以随机交换两个轮次，计算交换前后的差距，更新答案。
代码
C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
int n, m; // n: 规定的轮次 m: 实际的轮次
PII q[N];
int ans;
int calc() {
int res = 0;
for (int i = 0; i < m; i++) {
res += q[i].x + q[i].y;
if (i < n) {
if (q[i].x == 10) res += q[i + 1].x + q[i + 1].y;
else if (q[i].x + q[i].y == 10)
res += q[i + 1].x;
}
}
ans = max(ans, res);
return res;
}
void simulate_anneal() {
for (double t = 1e4; t > 1e-4; t *= 0.99) {
auto a = rand() % m, b = rand() % m;
int x = calc();
swap(q[a], q[b]);
// 交换后进行的轮次 n + (q[n - 1].x == 10) 等于 实际轮次m
if (n + (q[n - 1].x == 10) == m) {
int y = calc();
int dt = y - x;
// 如果dt>0, 则不用恢复原状
if (exp(dt / t) < (double)rand() / RAND_MAX)
swap(q[a], q[b]);
} else swap(q[a], q[b]);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
if (q[n - 1].x == 10) m = n + 1, cin >> q[n].x >> q[n].y;
else m = n;
// for (int i = 0; i < 100; i++) simulate_anneal();
// 卡时写法: 卡0.1秒
while ((double)clock() / CLOCKS_PER_SEC < 0.1) simulate_anneal();
cout << ans << endl;
return 0;
}
登录后复制
AcWing 2680. 均分数据
问题描述
问题链接：AcWing 2680. 均分数据
分析
这里可以随机将这些数据放置到某个组中，为了使得收敛的速度更快，可以采用贪心的策略将n个数据放置到m个组中。
每次找到和最小的组，将该数据放到该组中。
代码
C++
