模拟退火:赛场可读模板与使用场景
模拟退火就是反复尝试“小改一下当前方案”:改好了就接受,改差了也偶尔接受;开始时比较敢接受变差,后来越来越谨慎。整个过程另外记住见过的最好方案,最后输出它。
接受变差,是为了给后续更好的改变留机会。例如现在的任务分配暂时比较均衡,但需要先把一个任务挪走,才能再挪另一个任务,得到更好的分配。只允许每一步立即改善,可能一直走不出当前分配。
本节先用文字和具体例子说明,再给一份有中文注释、能直接编译的单文件程序。代码中的“代价”统一为越小越好。退火属于尝试寻找好方案的方法,不保证找到真正最优解;在必须得到精确答案的普通比赛里,不能仅凭多跑几次就认为一定能过。AtCoder 官方入门题解的比赛形式与退火说明
1. 什么时候值得考虑
题目满足下面几件事,才适合继续考虑退火:
- 能先做出一个合法的完整方案。
- 给你一个方案,你能算出它有多好,例如总路程、完成时间、冲突数。
- 能只改变方案的一小部分,并且这种改变有机会让结果变好。
- 所有方案太多,暂时没有找到能保证最优的快速算法,而题目允许近似结果或按得分评价。
如果题目本来就能用排序、枚举、背包DP或其他确定算法解决,先用那些方法。尤其是“恰选几个数使总和最大”,排序后选最大的即可,不需要退火。
如果只有完整正确的方案得1分,其余全部得0分,大量尝试都没有区别,退火也很难判断该往哪里走。可以先看能否用“有几处冲突”“还违反几条要求”衡量接近程度,但最后仍必须检查输出是否合法。
2. 使用场景:分别存什么、算什么、改什么
下面的“方案”就是你在代码中保存的一组数、一个排列、几个坐标或每件物品的归属。
场景一:从很多候选中恰好选几个
例子。 从很多候选店址里选5个,让更多住户附近有店。两家店的覆盖可能重叠,因此不能只给每个店址独立打分后取前5名。
- 保存什么:当前选中的店址,以及其余未选店址。
- 怎样算好坏:统计住户被覆盖的总数;因为本模板比较的是“代价越小越好”,可以把覆盖数取负数作为代价。
- 随机改哪里:移除一个已选店址,加入一个未选店址。始终还是5个。
- 必须注意:不要只随机翻转一个“选/不选”标记,那样会改变选中数量。
本节完整代码就采用这种“一换一”的写法,不过评分换成“选中数的总和离目标多远”,方便手算和检查。
场景二:调整一个访问顺序或工作顺序
例子。 所有城市都要访问一次,调整访问顺序,使总路程更短。
- 保存什么:一个城市编号排列。
- 怎样算好坏:按排列顺序累加相邻城市的距离;如果题目要求回到起点,还要加最后一个城市到起点的距离。
- 随机改哪里:交换两个城市的位置,或把一段访问顺序反过来。
- 必须注意:固定起点、固定终点等限制要保留;如果单行道导致来回距离不同,反转一段后,里面每条路的代价也要重新计算。
开始时直接重算整条路线最容易写对。以后需要加速,再研究哪些边真的发生了变化;不用一开始就背一个看不懂的距离差公式。
场景三:把任务分给几台机器,尽量均衡
例子。 把若干任务分给3台机器,每个任务有耗时,希望最忙的机器也能尽快做完。
- 保存什么:每个任务分给哪台机器。
- 怎样算好坏:先累加每台机器的总耗时,再取其中最大值作为代价。
- 随机改哪里:把一个任务移到另一台机器,或交换两台机器上的各一个任务。
- 必须注意:若每台机器还有限额、不能空着或必须恰好分到几件任务,新方案也必须满足这些要求。
“让最长耗时最小”和“让各组耗时的平方和最小”是不同目标,要按题目要求评分,不能随便互换。若改动先破坏当前方案再检查,拒绝时很容易忘记恢复;本节使用候选副本,被拒绝后直接丢弃。
场景四:在一个区域里找一个合适的位置
例子。 在给定矩形里放一个点,希望它离最近的障碍点尽可能远。
- 保存什么:当前横坐标和纵坐标。
- 怎样算好坏:算出它到每个障碍点的距离,取最小距离;希望这个距离越大越好,因此评分时取负数。
- 随机改哪里:横坐标、纵坐标各随机加减一点。
- 必须注意:点不能跑出矩形;有禁入区域时也要检查。越界的候选可以直接丢弃,不必强行挤到边界。
坐标改动幅度和温度分开设。温度决定“多大的代价变差还能容忍”,坐标幅度决定“这一跳能移动多远”。例如区域宽1000,却每次只移动0.001,可能跑很久也走不到别处。
也不是所有找位置的题都需要退火:一条直线上最小化距离和,可以找中位数;最小化平方距离和,可以找平均位置;覆盖所有点的最小圆,本书有专门算法。先识别这些结构。
场景五:调整布局,减少冲突
例子。 在棋盘上摆放若干对象,希望相互冲突的对数尽量少。
- 保存什么:每个对象的位置。
- 怎样算好坏:统计冲突对数,越少越好。
- 随机改哪里:移动一个对象,或交换两个对象的位置。
- 必须注意:不能放在禁用格、不能重叠等硬性要求,要在生成候选时检查。不能把“冲突还剩1对”当成已经满足无冲突要求。
如果只移动一个对象总是无法改善,可以尝试同时移动少量对象,但每次都把整个布局随机重做,通常又很难保留已经得到的好部分。
场景六:方案要经过一段模拟才能评分
例子。 修改任务顺序后,要按题目规则模拟执行,才知道总完成时间。
- 保存什么:当前执行顺序或操作安排。
- 怎样算好坏:完整模拟得到的完成时间或题目给定得分。
- 随机改哪里:交换少量位置,或者只取出一小段任务重新安排。
- 必须注意:一次评分如果很慢,能尝试的次数就少。先估算运行量,再决定跑几轮;不要只把降温系数改得更接近1。
“改一小部分,再完整检查候选”是容易写对的起点。官方入门题解也建议,把以后加速用的局部评分与完整重算对照检查。AtCoder 官方入门题解,第4节
3. 接受规则:只需要看当前、候选、最好这三个词
假设代价越小越好:
- 候选代价比当前小,接受。
- 候选代价和当前相同,也可以接受,给下一次改变换一个起点。
- 候选代价比当前大,才按概率决定是否接受。
- 一旦遇到比历史最好还好的方案,就把它单独保存。
一定和当前比较。 假设最好代价是0,当前代价是10,候选代价是8。8比当前的10好,应当直接接受;不要因为它比历史最好的0差,就把它误判成一次变差。
代码使用下面这句计算“接受变差”的概率:
exp(-变差幅度 / 温度)
exp 是 C++ 的指数函数,这里你只需要掌握结果的变化方向:变差幅度越大,概率越小;温度越高,概率越大。注意前面的负号,且只在候选更差的分支计算。GSL 官方文档中的接受规则
例如当前代价100、候选代价110,变差了10:
| 温度 | 大约有多大概率接受 |
|---|---|
| 100 | 90% |
| 10 | 37% |
| 1 | 0.005% |
随机生成一个0到1的小数,若它小于上面算出的概率,就接受。rand() 的原始返回值是整数,不能直接拿来和这个概率比较。
4. 参数怎样在现场调
代码里有四个参数需要先看:
| 参数 | 示例设置 | 改动后有什么影响 |
|---|---|---|
| 开始温度 | 1000 | 越大,开始时越愿意接受变差 |
| 停止温度 | 0.01 | 越小,后期越不容易接受变差 |
| 每步降温系数 | 0.995 | 每尝试一次温度乘它;越接近1,尝试次数越多 |
| 重启次数 | 5 | 从几个不同起点分别跑,始终保存全程最好方案 |
这些只是示例值。先看看随机小改一次时,代价通常会变差多少:如果常常变差几万,开始温度1000可能太低;如果通常只变差1,开始温度1000就会非常宽松。不能把同一组数当作所有题的固定答案。
用当前参数,每轮大约尝试2300次,5轮共约1.2万次。本模板每次复制整个方案、重新计算代价,所用时间还要乘上方案大小。如果题目有很多数据组,所有数据组的运行量也要相加。
重启不是继续上一轮。 本例第一轮从原顺序开始,后面打乱顺序,换新的初始选择,再恢复开始温度。随机数生成器只初始化一次,不要每次重启都用同一种子重新创建,否则可能把同一条搜索过程重复跑几遍。
5. 完整模板在解决什么问题
例题:给出若干整数,恰好选出指定个数,让它们的总和尽量接近目标。
输入:
4 2 142 5 9 12意思是从4个数里选2个,希望总和接近14。可以选2和12,也可以选5和9,误差都是0。输出第一行是找到的最小误差,第二行是选中数的原下标,从1开始;例如:
01 4不同合法选择的输出顺序可以不同。误差必须和输出的选择对应。
这道例题只是方便展示退火的完整过程:实际遇到选数题,仍应先看能否枚举或用背包DP准确解决。本程序不把“运行结束”当成“已经证明最优”。
方案用一个下标排列保存:前面指定数量的位置表示选中,后面的位置表示未选中。例如排列 0 3 1 2 表示选中原下标0和3,也就是数2和12。随机从前半部分和后半部分各取一个位置交换,选中的数量始终不变。
输入前提:个数不能为负,选取数量在0到总个数之间;所有输入数的绝对值之和,再加目标的绝对值,不超过 10^15。代码按这个范围使用 long long,避免求和、做差和取绝对值溢出。
6. 带中文注释的完整单文件代码
代码里的三处“换题改这里”分别对应:计算代价、调整温度、生成一次合法的小改动。更换方案的数据结构时,也要同步修改初解和输出。
#include <bits/stdc++.h>using namespace std;using ll = long long;
// 完整例题:从 n 个整数中恰好选 k 个,让它们的总和尽量接近 target。// 输入:n k target,下一行 n 个整数。// 输出:找到的最小误差,下一行输出选中的原下标(从 1 开始)。// 数值前提:所有数的绝对值之和,再加上 target 的绝对值,不超过 10^15。// 因此下面的整数求和、相减和取绝对值都不会溢出。int n, k;ll target;vector<ll> value;
// 随机数生成器只初始化一次。固定种子方便本地复现。mt19937 rng(20261025);uniform_real_distribution<double> random01(0.0, 1.0);
vector<int> best_order; // 搜索过程中,见过的最好方案。ll best_cost = LLONG_MAX;
// 【换题改这里 1】如何计算一个方案的代价。这里代价越小越好。// order 存所有数的原下标,前 k 个位置表示选中,后面表示未选中。ll calculate_cost(const vector<int>& order) { ll sum = 0; for (int i = 0; i < k; ++i) sum += value[order[i]]; return abs(sum - target);}
void simulated_annealing(vector<int> current_order) { ll current_cost = calculate_cost(current_order); if (current_cost < best_cost) { best_cost = current_cost; best_order = current_order; }
// 全不选或全选时,选中的集合已经固定,不存在“一换一”的改变。 // 先返回,避免下面构造空范围的随机数分布。 if (k == 0 || k == n) return;
uniform_int_distribution<int> pick_selected(0, k - 1); uniform_int_distribution<int> pick_unselected(k, n - 1);
// 【换题改这里 2】根据一次变差的常见幅度调温,下面只是示例参数。 const double start_temperature = 1000.0; // 大:开始时较愿意接受变差。 const double stop_temperature = 0.01; // 小:结束前主要保留改善。 const double cooling = 0.995; // 每尝试一次,温度乘这个数。
for (double temperature = start_temperature; temperature > stop_temperature; temperature *= cooling) {
// 复制一份候选。若不接受它,直接丢弃,当前方案就不会被改坏。 vector<int> candidate_order = current_order;
// 【换题改这里 3】随机小改一次,并保证新方案仍然合法。 // 从选中区和未选中区各取一个位置,交换后仍然恰选 k 个数。 int selected_pos = pick_selected(rng); int unselected_pos = pick_unselected(rng); swap(candidate_order[selected_pos], candidate_order[unselected_pos]);
ll candidate_cost = calculate_cost(candidate_order);
// 必须和“当前方案”比较,不能和 best_cost 比较。 bool accept_candidate = candidate_cost <= current_cost;
if (!accept_candidate) { ll worse_by = candidate_cost - current_cost; // 到这里一定为正。
// exp 是 C++ 的指数函数。参数越负,返回的概率越接近 0。 // 变差越多,接受概率越低;温度越高,接受概率越高。 double probability = exp(-static_cast<double>(worse_by) / temperature); accept_candidate = random01(rng) < probability; }
if (accept_candidate) { current_order = std::move(candidate_order); current_cost = candidate_cost;
// 接受变差只是为了继续探索,最好方案必须另外保存。 if (current_cost < best_cost) { best_cost = current_cost; best_order = current_order; } } // 没接受:候选副本被丢弃,不需要再交换回去。 }}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
if (!(cin >> n >> k >> target)) return 0; if (n < 0 || k < 0 || k > n) return 0; value.resize(n); for (ll& x : value) cin >> x;
// order = [0, 1, ..., n-1],第一次从原顺序开始。 vector<int> order(n); iota(order.begin(), order.end(), 0);
const int restarts = 5; for (int run = 0; run < restarts; ++run) { // 后面几次打乱顺序,换一个起点;沿用同一个随机数生成器。 if (run > 0) shuffle(order.begin(), order.end(), rng); simulated_annealing(order); }
// 输出 best_order 对应的代价和方案,不输出最后停留的 current_order。 cout << best_cost << '\n'; for (int i = 0; i < k; ++i) { if (i) cout << ' '; cout << best_order[i] + 1; } cout << '\n';}在模板目录编译:
g++ -std=c++17 -O2 -Wall -Wextra ready/annealing_readable.cpp -o /tmp/cp-annealing/tmp/cp-annealing7. 改成自己的题时,按这个顺序检查
- 先确定代码里保存什么。例如选中的下标、城市顺序、每件物品的组别、点的坐标。
- 写一个完整评分函数,能手算的小例必须和它一致。若原目标越大越好,可用它的相反数作为代价;取负前先检查类型范围。
- 写一次随机小改动,确认它不会违反恰选数量、位置范围、容量等限制。非法候选直接丢弃,并继续降温。
- 始终比较候选与当前,接受后同时更新当前方案和当前代价;遇到全程最好时,把方案与代价一起保存。
- 先保持完整重算的写法。确实太慢时,再只计算受改动影响的部分,并与完整评分对照。
例如改成城市路线:方案仍然可以是编号排列,评分改成总路程,小改动改为交换两个允许移动的位置,输出改为访问顺序。改成点坐标:方案要改成横纵坐标,评分按题目要求计算,随机改动改为坐标加减,并检查范围。
这份程序会修改全局的最好方案;若改为多组数据,每组开始前重置 best_cost 并清空 best_order。
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
最后更新于 ,距今已过 22 天
部分内容可能已过时