OI-wiki 模拟退火算法实战指南原理、调参与代码实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki模拟退火Simulated Annealing是 OI/ICPC 竞赛中处理多峰函数、高维搜索与复杂组合优化问题的随机化算法其核心思想是借助以一定概率接受更差解来跳出局部最优从而逼近全局最优解。本文以 OI-wiki 的docs/misc/simulated-annealing.md为主体结合仓库内完整示例代码与测试数据系统讲解模拟退火的状态转移概率、降温调度、参数选取、卡时与分块等实战技巧并给出可直接运行的 C 实现以带权类费马点问题为例。读完本文你将掌握模拟退火从建模、编码到调参优化的完整流程能够独立解决方案空间极大且非单峰的搜索类题目。引入为什么需要模拟退火当一个问题的方案数量极大甚至是无穷的并且目标函数不是单峰函数时我们常使用模拟退火求解。这类问题无法直接使用三分、二分等确定性方法求解退而求其次的常见选择是爬山算法。回顾爬山算法的过程可以发现爬山算法每次在当前找到的最优方案附近寻找一个新方案只有当新方案更优时才转移否则保持不变。这种只上不下的策略对单峰函数可行但当函数存在多个峰时算法极易停在一个局部最优解上——详见 docs/misc/hill-climbing.md 中劣势一节的论述当目标函数不是单峰函数时这个劣势是致命的。模拟退火的突破口在于接受爬山算法直接舍去的非最优解。对于当前最优解附近的非最优解爬山算法直接舍弃而模拟退火会以一定概率接受它从而跳出局部最优继续探索更广阔的解空间。什么是退火退火是一种金属热处理工艺将金属缓慢加热到一定温度保持足够时间然后以适宜速度冷却。其目的是降低硬度、消除残余应力、细化晶粒、调整组织等。模拟退火正是借鉴了这一物理过程——由于退火规律引入了更多随机因素我们得到最优解的概率会大大增加于是把目标函数作为能量函数来模拟这一过程。核心机制状态转移与接受概率转移准则先用一句话概括模拟退火的状态转移如果新状态的解更优则修改答案否则以一定概率接受新状态。定义当前温度为 $T$新状态 $S$ 与已知状态 $S$新状态由已知状态通过随机方式得到之间的能量值差为 $\Delta E$$\Delta E \geqslant 0$则发生状态转移修改最优解的概率为$$ P(\Delta E) \begin{cases} 1, S \text{ is better than } S,\ \mathrm{e}^\frac{-\Delta E}{T}, \text{otherwise}. \end{cases} $$这个概率公式常称为 Metropolis 准则蕴含了两个关键性质解更优时必然接受只要 $S$ 优于 $S$转移概率恒为 $1$保证算法始终朝着更优方向收敛解更差时概率接受接受概率 $\mathrm{e}^{-\Delta E/T}$ 随温差 $\Delta E$ 增大而减小差距越大越难接受随温度 $T$ 升高而增大温度越高越愿意冒险。正是第二条保证了算法能跳出局部最优高温阶段允许大幅横向/向下跳跃去探索陌生区域低温阶段则趋于保守、只做精细的局部微调。一个提升解质量的注意点为了得到的解更有质量有时会在模拟退火结束后以当前温度在得到的解附近多次随机状态尝试得到更优的解其过程与模拟退火相似。这在仓库示例代码中体现为simulateAnneal()末尾的循环for (int i 1; i 1000; i) { double nxtx ansx t * (Rand() * 2 - 1); double nxty ansy t * (Rand() * 2 - 1); calc(nxtx, nxty); }此时温度 $t$ 已经降到终止阈值附近约 $0.001$扰动幅度极小相当于对当前最优解做邻域精搜见下文实现详解。温度调度如何退火降温模拟退火有三个核心参数参数含义典型取值$T_0$初始温度一个比较大的数决定初始阶段的随机探索强度如 $10^5$$d$降温系数非常接近 $1$ 但小于 $1$ 的数决定降温速度通常取 $[0.985, 0.999]$与爬山算法的降温参数选取区间一致$T_k$终止温度接近 $0$ 的正数作为退火结束的阈值如 $0.001$退火流程为令温度 $T T_0$按上述状态转移准则进行一次转移尝试令 $T d \cdot T$指数降温当 $T T_k$ 时过程结束此时的最优解即为最终结果。重要实践为了使得解更精确通常不直接取当前解作为答案而是在退火过程中维护遇到的所有解的最优值。仓库代码中calc函数每次计算后都执行if (res dis) dis res, ansx xx, ansy yy;正是全程记录最优这一策略的体现——因为温度降低后算法可能收敛到局部极值但历史最优往往更接近全局最优。下面的动画直观展示了模拟退火随温度降低的搜索过程——随着温度降低跳跃越来越不随机最优解也越来越稳定完整实现以「BZOJ 3680」吊打 XXX 为例仓库在 docs/misc/code/simulated-annealing/simulated-annealing_1.cpp 提供了完整可编译的参考实现题目为「BZOJ 3680」吊打 XXX求 $n$ 个点的带权类费马点。下面是该代码的逐段剖析#include cmath #include cstdlib #include ctime #include iomanip #include iostream constexpr int N 10005; int n, x[N], y[N], w[N]; double ansx, ansy, dis; double Rand() { return (double)rand() / RAND_MAX; } double calc(double xx, double yy) { double res 0; for (int i 1; i n; i) { double dx x[i] - xx, dy y[i] - yy; res sqrt(dx * dx dy * dy) * w[i]; } if (res dis) dis res, ansx xx, ansy yy; return res; } void simulateAnneal() { double t 100000; double nowx ansx, nowy ansy; while (t 0.001) { double nxtx nowx t * (Rand() * 2 - 1); double nxty nowy t * (Rand() * 2 - 1); double delta calc(nxtx, nxty) - calc(nowx, nowy); if (exp(-delta / t) Rand()) nowx nxtx, nowy nxty; t * 0.97; } for (int i 1; i 1000; i) { double nxtx ansx t * (Rand() * 2 - 1); double nxty ansy t * (Rand() * 2 - 1); calc(nxtx, nxty); } } int main() { std::cin.tie(nullptr)-sync_with_stdio(false); srand(0); // 注意在实际使用中不应使用固定的随机种子。 std::cin n; for (int i 1; i n; i) { std::cin x[i] y[i] w[i]; ansx x[i], ansy y[i]; } ansx / n, ansy / n, dis calc(ansx, ansy); simulateAnneal(); std::cout std::fixed std::setprecision(3) ansx ansy \n; return 0; }关键设计点解读能量函数目标函数calc计算点 $(xx, yy)$ 到 $n$ 个给定点的带权距离之和 $\sum \sqrt{dx^2dy^2}\cdot w_i$这正是带权类费马点需要最小化的目标。注意calc内部在返回结果的同时用全局变量dis、ansx、ansy维护历史最优解——这就是前文强调的维护所有解的最优值。随机扰动Rand() * 2 - 1将 $[0,1)$ 均匀随机数映射到 $[-1,1)$再乘以当前温度 $t$ 得到邻域扰动幅度。温度高时扰动大大步探索温度低时扰动小局部精修。接受判断exp(-delta / t) Rand()与理论公式一一对应。当 $\Delta E \leqslant 0$新解更优时$\mathrm{e}^{-\Delta E/t} \geqslant 1$条件恒成立、必定接受当 $\Delta E 0$新解更差时以概率 $\mathrm{e}^{-\Delta E/t}$ 接受且该概率随温度下降而衰减。温度参数初始温度 $T_0 10^5$降温系数 $d 0.97$终止温度 $T_k 0.001$三者均落在文档给出的推荐取值区间内。初始化以所有点的坐标加权平均值重心作为起始位置可减少无效探索srand(0)固定随机种子便于复现调试但代码注释明确提醒实际使用中不应使用固定的随机种子应改为srand(time(0))之类的真随机种子否则每次运行结果完全相同退火会退化成确定性搜索。样例数据验证仓库在 docs/misc/examples/simulated-annealing/simulated-annealing_1.in 提供了测试数据3 0 0 1 0 2 1 1 1 1即三个等权点 $(0,0)$、$(0,2)$、$(1,1)$期望输出见同目录simulated-annealing_1.ans为0.577 1.000该答案对应对称位置处的带权费马点可用来验证代码实现的正确性在calc对答案取 $10^{-3}$ 精度下输出应稳定匹配。实战技巧分块模拟退火有时函数的峰很多单次模拟退火难以跑出最优解。此时可以把整个值域分成几段每段分别跑一遍模拟退火最后取各段最优解中的最佳者。分块相当于把一次大海捞针拆成多次局部攻坚显著提高覆盖到全局最优峰的概率尤其适合峰分布稀疏或集中于某些区间的目标函数。卡时用满时间限制模拟退火是随机算法跑得越久答案通常越好因此竞赛中常用卡时技巧吃满时限。C/C 标准库提供了clock()函数返回程序自启动以来的运行时间以时钟周期计配合CLOCKS_PER_SEC可换算为秒。可以把主程序中的simulateAnneal();替换为while ((double)clock() / CLOCKS_PER_SEC MAX_TIME) simulateAnneal();这样程序会持续反复运行模拟退火直到用时即将超过时间限制。其中MAX_TIME是一个自定义的略小于时限的数单位秒例如时限为 1s 时可设0.9留出约 $0.1$s 的余量给输入输出与程序启动开销。注意多轮退火之间全局最优dis、ansx、ansy会被持续维护每次simulateAnneal()都会从上轮最优解附近重新出发因此轮数越多历史最优解越可能被刷新。通用调参建议降温系数 $d$ 越大搜索越充分但越慢$d$ 越接近 $1$降温越缓慢同一温度下能进行更多次扰动尝试结果更优但耗时更长。建议在时限内尽量取大如 $0.99$ 以上配合卡时技巧使用。初始温度 $T_0$ 决定初期探索半径$T_0$ 过小会导致算法过早进入局部收敛无法跳出局部最优$T_0$ 过大则前期大量时间浪费在无意义的大幅跳跃上。可从解空间尺度出发估算令 $T_0$ 约为初始扰动范围的数量级。善用多次运行与随机种子正式提交时使用基于当前时间的随机种子多次独立运行取最优可有效摊平单次运行的随机波动。习题巩固「BZOJ 3680」吊打 XXX求 $n$ 个点的带权类费马点即本文示例所解决的题目适合作为模板题练习。「JSOI 2016」炸弹攻击二维平面上的覆盖优化问题可尝试用模拟退火枚举爆破中心位置。「HAOI 2006」均分数据将数据均分成若干组的组合优化问题可结合随机化初始排列与模拟退火求解。总结模拟退火以接受差解跳出局部最优为核心通过温度 $T$、降温系数 $d$ 与终止温度 $T_k$ 三个参数在全局探索与局部精修之间取得平衡。OI-wiki 的模拟退火文档及其配套的参考实现给出了一个可直接套用的模板先以重心初始化再按 $\mathrm{e}^{-\Delta E/T}$ 概率接受状态全程维护历史最优解退火结束后在低温邻域做精搜最后配合分块与卡时技巧进一步提升答案质量。掌握这套流程后面对非单峰、高维度、方案空间极大的搜索题你便多了一把强有力的随机化武器。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 模拟退火算法实战指南：原理、调参与代码实现
OI-wiki 模拟退火算法实战指南原理、调参与代码实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki模拟退火Simulated Annealing是 OI/ICPC 竞赛中处理多峰函数、高维搜索与复杂组合优化问题的随机化算法其核心思想是借助以一定概率接受更差解来跳出局部最优从而逼近全局最优解。本文以 OI-wiki 的docs/misc/simulated-annealing.md为主体结合仓库内完整示例代码与测试数据系统讲解模拟退火的状态转移概率、降温调度、参数选取、卡时与分块等实战技巧并给出可直接运行的 C 实现以带权类费马点问题为例。读完本文你将掌握模拟退火从建模、编码到调参优化的完整流程能够独立解决方案空间极大且非单峰的搜索类题目。引入为什么需要模拟退火当一个问题的方案数量极大甚至是无穷的并且目标函数不是单峰函数时我们常使用模拟退火求解。这类问题无法直接使用三分、二分等确定性方法求解退而求其次的常见选择是爬山算法。回顾爬山算法的过程可以发现爬山算法每次在当前找到的最优方案附近寻找一个新方案只有当新方案更优时才转移否则保持不变。这种只上不下的策略对单峰函数可行但当函数存在多个峰时算法极易停在一个局部最优解上——详见 docs/misc/hill-climbing.md 中劣势一节的论述当目标函数不是单峰函数时这个劣势是致命的。模拟退火的突破口在于接受爬山算法直接舍去的非最优解。对于当前最优解附近的非最优解爬山算法直接舍弃而模拟退火会以一定概率接受它从而跳出局部最优继续探索更广阔的解空间。什么是退火退火是一种金属热处理工艺将金属缓慢加热到一定温度保持足够时间然后以适宜速度冷却。其目的是降低硬度、消除残余应力、细化晶粒、调整组织等。模拟退火正是借鉴了这一物理过程——由于退火规律引入了更多随机因素我们得到最优解的概率会大大增加于是把目标函数作为能量函数来模拟这一过程。核心机制状态转移与接受概率转移准则先用一句话概括模拟退火的状态转移如果新状态的解更优则修改答案否则以一定概率接受新状态。定义当前温度为 $T$新状态 $S$ 与已知状态 $S$新状态由已知状态通过随机方式得到之间的能量值差为 $\Delta E$$\Delta E \geqslant 0$则发生状态转移修改最优解的概率为$$ P(\Delta E) \begin{cases} 1, S \text{ is better than } S,\ \mathrm{e}^\frac{-\Delta E}{T}, \text{otherwise}. \end{cases} $$这个概率公式常称为 Metropolis 准则蕴含了两个关键性质解更优时必然接受只要 $S$ 优于 $S$转移概率恒为 $1$保证算法始终朝着更优方向收敛解更差时概率接受接受概率 $\mathrm{e}^{-\Delta E/T}$ 随温差 $\Delta E$ 增大而减小差距越大越难接受随温度 $T$ 升高而增大温度越高越愿意冒险。正是第二条保证了算法能跳出局部最优高温阶段允许大幅横向/向下跳跃去探索陌生区域低温阶段则趋于保守、只做精细的局部微调。一个提升解质量的注意点为了得到的解更有质量有时会在模拟退火结束后以当前温度在得到的解附近多次随机状态尝试得到更优的解其过程与模拟退火相似。这在仓库示例代码中体现为simulateAnneal()末尾的循环for (int i 1; i 1000; i) { double nxtx ansx t * (Rand() * 2 - 1); double nxty ansy t * (Rand() * 2 - 1); calc(nxtx, nxty); }此时温度 $t$ 已经降到终止阈值附近约 $0.001$扰动幅度极小相当于对当前最优解做邻域精搜见下文实现详解。温度调度如何退火降温模拟退火有三个核心参数参数含义典型取值$T_0$初始温度一个比较大的数决定初始阶段的随机探索强度如 $10^5$$d$降温系数非常接近 $1$ 但小于 $1$ 的数决定降温速度通常取 $[0.985, 0.999]$与爬山算法的降温参数选取区间一致$T_k$终止温度接近 $0$ 的正数作为退火结束的阈值如 $0.001$退火流程为令温度 $T T_0$按上述状态转移准则进行一次转移尝试令 $T d \cdot T$指数降温当 $T T_k$ 时过程结束此时的最优解即为最终结果。重要实践为了使得解更精确通常不直接取当前解作为答案而是在退火过程中维护遇到的所有解的最优值。仓库代码中calc函数每次计算后都执行if (res dis) dis res, ansx xx, ansy yy;正是全程记录最优这一策略的体现——因为温度降低后算法可能收敛到局部极值但历史最优往往更接近全局最优。下面的动画直观展示了模拟退火随温度降低的搜索过程——随着温度降低跳跃越来越不随机最优解也越来越稳定完整实现以「BZOJ 3680」吊打 XXX 为例仓库在 docs/misc/code/simulated-annealing/simulated-annealing_1.cpp 提供了完整可编译的参考实现题目为「BZOJ 3680」吊打 XXX求 $n$ 个点的带权类费马点。下面是该代码的逐段剖析#include cmath #include cstdlib #include ctime #include iomanip #include iostream constexpr int N 10005; int n, x[N], y[N], w[N]; double ansx, ansy, dis; double Rand() { return (double)rand() / RAND_MAX; } double calc(double xx, double yy) { double res 0; for (int i 1; i n; i) { double dx x[i] - xx, dy y[i] - yy; res sqrt(dx * dx dy * dy) * w[i]; } if (res dis) dis res, ansx xx, ansy yy; return res; } void simulateAnneal() { double t 100000; double nowx ansx, nowy ansy; while (t 0.001) { double nxtx nowx t * (Rand() * 2 - 1); double nxty nowy t * (Rand() * 2 - 1); double delta calc(nxtx, nxty) - calc(nowx, nowy); if (exp(-delta / t) Rand()) nowx nxtx, nowy nxty; t * 0.97; } for (int i 1; i 1000; i) { double nxtx ansx t * (Rand() * 2 - 1); double nxty ansy t * (Rand() * 2 - 1); calc(nxtx, nxty); } } int main() { std::cin.tie(nullptr)-sync_with_stdio(false); srand(0); // 注意在实际使用中不应使用固定的随机种子。 std::cin n; for (int i 1; i n; i) { std::cin x[i] y[i] w[i]; ansx x[i], ansy y[i]; } ansx / n, ansy / n, dis calc(ansx, ansy); simulateAnneal(); std::cout std::fixed std::setprecision(3) ansx ansy \n; return 0; }关键设计点解读能量函数目标函数calc计算点 $(xx, yy)$ 到 $n$ 个给定点的带权距离之和 $\sum \sqrt{dx^2dy^2}\cdot w_i$这正是带权类费马点需要最小化的目标。注意calc内部在返回结果的同时用全局变量dis、ansx、ansy维护历史最优解——这就是前文强调的维护所有解的最优值。随机扰动Rand() * 2 - 1将 $[0,1)$ 均匀随机数映射到 $[-1,1)$再乘以当前温度 $t$ 得到邻域扰动幅度。温度高时扰动大大步探索温度低时扰动小局部精修。接受判断exp(-delta / t) Rand()与理论公式一一对应。当 $\Delta E \leqslant 0$新解更优时$\mathrm{e}^{-\Delta E/t} \geqslant 1$条件恒成立、必定接受当 $\Delta E 0$新解更差时以概率 $\mathrm{e}^{-\Delta E/t}$ 接受且该概率随温度下降而衰减。温度参数初始温度 $T_0 10^5$降温系数 $d 0.97$终止温度 $T_k 0.001$三者均落在文档给出的推荐取值区间内。初始化以所有点的坐标加权平均值重心作为起始位置可减少无效探索srand(0)固定随机种子便于复现调试但代码注释明确提醒实际使用中不应使用固定的随机种子应改为srand(time(0))之类的真随机种子否则每次运行结果完全相同退火会退化成确定性搜索。样例数据验证仓库在 docs/misc/examples/simulated-annealing/simulated-annealing_1.in 提供了测试数据3 0 0 1 0 2 1 1 1 1即三个等权点 $(0,0)$、$(0,2)$、$(1,1)$期望输出见同目录simulated-annealing_1.ans为0.577 1.000该答案对应对称位置处的带权费马点可用来验证代码实现的正确性在calc对答案取 $10^{-3}$ 精度下输出应稳定匹配。实战技巧分块模拟退火有时函数的峰很多单次模拟退火难以跑出最优解。此时可以把整个值域分成几段每段分别跑一遍模拟退火最后取各段最优解中的最佳者。分块相当于把一次大海捞针拆成多次局部攻坚显著提高覆盖到全局最优峰的概率尤其适合峰分布稀疏或集中于某些区间的目标函数。卡时用满时间限制模拟退火是随机算法跑得越久答案通常越好因此竞赛中常用卡时技巧吃满时限。C/C 标准库提供了clock()函数返回程序自启动以来的运行时间以时钟周期计配合CLOCKS_PER_SEC可换算为秒。可以把主程序中的simulateAnneal();替换为while ((double)clock() / CLOCKS_PER_SEC MAX_TIME) simulateAnneal();这样程序会持续反复运行模拟退火直到用时即将超过时间限制。其中MAX_TIME是一个自定义的略小于时限的数单位秒例如时限为 1s 时可设0.9留出约 $0.1$s 的余量给输入输出与程序启动开销。注意多轮退火之间全局最优dis、ansx、ansy会被持续维护每次simulateAnneal()都会从上轮最优解附近重新出发因此轮数越多历史最优解越可能被刷新。通用调参建议降温系数 $d$ 越大搜索越充分但越慢$d$ 越接近 $1$降温越缓慢同一温度下能进行更多次扰动尝试结果更优但耗时更长。建议在时限内尽量取大如 $0.99$ 以上配合卡时技巧使用。初始温度 $T_0$ 决定初期探索半径$T_0$ 过小会导致算法过早进入局部收敛无法跳出局部最优$T_0$ 过大则前期大量时间浪费在无意义的大幅跳跃上。可从解空间尺度出发估算令 $T_0$ 约为初始扰动范围的数量级。善用多次运行与随机种子正式提交时使用基于当前时间的随机种子多次独立运行取最优可有效摊平单次运行的随机波动。习题巩固「BZOJ 3680」吊打 XXX求 $n$ 个点的带权类费马点即本文示例所解决的题目适合作为模板题练习。「JSOI 2016」炸弹攻击二维平面上的覆盖优化问题可尝试用模拟退火枚举爆破中心位置。「HAOI 2006」均分数据将数据均分成若干组的组合优化问题可结合随机化初始排列与模拟退火求解。总结模拟退火以接受差解跳出局部最优为核心通过温度 $T$、降温系数 $d$ 与终止温度 $T_k$ 三个参数在全局探索与局部精修之间取得平衡。OI-wiki 的模拟退火文档及其配套的参考实现给出了一个可直接套用的模板先以重心初始化再按 $\mathrm{e}^{-\Delta E/T}$ 概率接受状态全程维护历史最优解退火结束后在低温邻域做精搜最后配合分块与卡时技巧进一步提升答案质量。掌握这套流程后面对非单峰、高维度、方案空间极大的搜索题你便多了一把强有力的随机化武器。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考