首页 > 其他分享 >模拟退火

模拟退火

时间:2023-01-04 22:33:11浏览次数:57  
标签:rand cur 退火 模拟退火 Delta np

模拟退火
模拟退火是一类随机化玄学算法,当一个问题的方案数量极大而且不是一个单峰函数时,我们常使用其求解。

而且一些最优化问题如果想不到正解可以用其玄学骗分(这才是重点)

退火是什么?

退火是一种金属热处理工艺,指的是将金属缓慢加热到一定温度,保持足够时间,然后以适宜速度冷却。目的是降低硬度,改善切削加工性;消除残余应力,稳定尺寸,减少变形与裂纹倾向;细化晶粒,调整组织,消除组织缺陷。准确的说,退火是一种对材料的热处理工艺,包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。 —— 百度百科

概念:

  1. 温度(步长):每次从一个点开始随机,温度越大,考虑范围越大。
    两类:初始温度\(T_0\),终止温度\(T_{end}\)
  2. 衰减系数\(\lambda\):顾名思义。线性衰减效果不好,故采用指数级衰减,从零到一,越靠近一,找到正解概率越大,但也越接近无脑爆搜。

算法步骤:
简单来说,就是有更好的就把原来的丢了,如果没有就以一定概率跳到另一个上。

  1. 每一次迭代,在当前范围内随机一个点,求出该点函数值。
  2. 比较次随机点与当前函数值的大小关系\(\Delta=f_{new}-f_{present}\)
    • 情况\(1\): \(\Delta <0\),跳到新点上。
    • 情况\(2\): \(\Delta >0\),以一定概率(\(e^{-\frac{\Delta}{T}}\))跳到新点上。

为了更接近正解,减小误差,可以多跑几次。

code

void simulate_anneal()
{
    PDD cur(rand(0,10000),rand(0,10000));
    for(double t=1e4;t>1e-4;t*=0.99)
    {
        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;
    }
}

习题选做:
P1337 【JSOI2004】 平衡点 / 吊打XXX
P2503 【HAOI2006】 均分数据
P4035 【JSOI2008】 球形空间产生器
P3878 【TJOI2010】分金币
P4274 【NOI2004】 小H的小屋
P5544 【JSOI2016】 炸弹攻击1

标签:rand,cur,退火,模拟退火,Delta,np
From: https://www.cnblogs.com/sunruize/p/17026192.html

相关文章

  • 【图像增强】基于粒子群优化和模拟退火的图像增强算法研究Matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 【KNN分类】基于模拟退火优化KNN、蝗虫算法优化KNN实现数据分类附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 模拟退火
    \(1.\)作用找到函数的极值。\(2.\)原理为了解决这一问题,科学家们想到了物理的退火降温的过程——一个处于很高温度的物体,现在要给它降温,使物体内能降到最低。我们常......
  • codes for 模拟退火
    伪代码:#include<bits/stdc++.h>usingnamespacestd;signedmain(){ ios::sync_with_stdio(0); cin>>初始解; 认为当前为最优解; for(由前解扰动生成新......
  • 模拟退火(退役前怒学骗分)
    代码是\([这题](https://www.luogu.com.cn/problem/P3878)\)的。模拟一个退火的过程,最开始温度为\(100\)不断降低,常数可以自己设计这里为\(99\)。每次随机一个转移,如......
  • 【模板】模拟退火 Simulated Annealing
    postedon2021-05-0418:16:24|under学术|source模拟退火适用于:你不会正解能写出估价函数,而且最优解的估价最大/小估价函数不单调,不能二分人品好由于是个带......
  • 模拟退火
    模拟退火(SimulateAnneal)是一种通用概率演算法,在大的搜索空间内寻找最优解,若新的状态优于当前状态,则将新的状态作为最优解,否则以一定概率接受新的状态。模拟退火有三个因......
  • 基于粒子群优化和模拟退火算法增强传统聚类研究(Matlab代码实现)
    ......
  • 模拟退火
    模拟退火很多时候我们会被要求求一些函数的最值问题,但是又因为值域很大,是连续的乃至无穷的,那么搜索是搜不出来的,对于这种问题,一般来说爬山算法是很可以的,比如下边的图......
  • 模拟退火学习笔记
    1.简介模拟退火算法来源于固体退火原理,是一种基于概率的算法,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在......