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

模拟退火

时间:2024-07-30 14:28:42浏览次数:16  
标签:模退 cur rand double 模拟退火 ans

模拟退火

必须要单独开一个专题来讲模拟退火了。

看到身边很多同学写的模退都是不标准的,步长没有随温度的降低而减小,只能叫随机爬山。

系统的学习模退是跟着 Acwing 的 yxc,他写的模退给人一看就有一种豁然开朗,神清气爽的感觉,让你惊叹天下竟然还有如此精妙的算法。

是的,优雅的模退写出来就是令人心旷神怡,而不是某些同学暴力算法的代言,像一坨屎山一样。


image

一谈起模退,我脑中就回想起这幅经典的动图,如他的定义一般精妙:

而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

可以发现波动程度逐渐变小,最后趋于稳定。

例题:星星还是树

其实就是费马点。

核心代码:

void simulate_anneal(){
    pdd cur(rand(0,1e4),rand(0,1e4));// 初始点(当前点)
    for (double t = 1e4; t > 1e-4; t *= 0.95){// 初始温度,终止温度,温度 * 衰减系数
        pdd rand_point(rand(cur.x - t,cur.x + t),rand(cur.y - t,cur.y + t));
        double delta = calc(rand_point) - calc(cur);
        if (exp(-delta / t) > rand(0,1)) cur = rand_point; // 满足条件则跳到新点
    }
}

关于 rand 函数

yxc 老师很巧妙的处理的直接使用rand()值域过小的问题。

double random(double l,double r){
    return (double) rand() / RAND_MAX * (r - l) + l;
}

当然我们有性能更好的 mt19937 也完全可以使用

mt19937 rnd(random_device{}());
int random(int l,int r){
	return rnd()%(r-l+1)+l;
}

关于 exp 函数

image

众所周知,模拟退火很重要的一个特点就是对于不优的解也以一定概率接受,防止陷入局部最优解的深坑中,定义 \(delt=contmeprorary-ans\) ,如果 \(ans\) 的值越小越优,那么以 \(exp(-delt/T)\) 的概率接受该解,注意如果 \(delt\) 为负数,则该函数值一定大于 \(1\) ,意味着一定接受。为整数则以一定概率接受。

关于 clock 函数

众做周知,我们在时间允许的情况下我们希望进行经可能多的模拟退火次数以保证答案的正确性,clock()/CLOCK_PER_CEC 可以帮我们解决这个问题。

for(;(double)clock()/CLOCK_PER_SEC;){
	fire();
}

完结撒花✿✿ヽ(°▽°)ノ✿

void fire(){
	double T=1e9,d=0.997;
	int x=rnd();
	ans=min(ans,check(x));
	while(T>1){
	//	cout<<x<<endl;
		int nx=x+random(-T,T);
		long long temp=check(nx);
		double delt=temp-ans;
		if(exp((double)-delt/T)*T>random(0,T)){
			x=nx;
		}
		ans=min(temp,ans);
		T*=d;
	}
}

标签:模退,cur,rand,double,模拟退火,ans
From: https://www.cnblogs.com/alloverzyt/p/18332298

相关文章

  • [OI] 模拟退火
    模拟退火是一种适合求样本点较大的多峰函数极值的方法.模拟退火有几个参数:初始温度(\(T_{0}\)),终止温度(\(T_{e}\))和降温参数\(d\),具体地,模拟退火是让每次的当前温度\(T\)变为\(d\timesT\),直到终止,因此\(T_{e}\)应为一个很接近\(0\)的正数,\(d\)应该为一个很接近\(1\)的......
  • 模拟退火学习笔记
    模拟退火学习笔记前言不知道为啥突然有闲情学这个...模拟退火(SimulatedAnnealing),简称\(SA\).是一种基于随机化的算法,无门槛,主要是为了骗分...不是正解!!!!根据爬山算法的过程,我们发现:对于一个当前最优解附近的非最优解,爬山算法直接舍去了这个解。而很多情况下,我们需......
  • 【搜索】【模板】模拟退火
    前置知识自然对数、分数次幂、概率。前言模拟退火可以在我们想不到题目正解的时候试一试其实就是骗分方法。因为纯随机得出正确答案的概率非常低,所以我们就可以加一定的优化,使找到答案概率增大。算法思想温度(步长):每次选择一个范围进行搜索,在搜索过程中范围不断缩小,最后到很......
  • 【人工智能】高级搜索技术(模拟退火搜索算法和遗传算法解决旅行商问题)
    目录一、旅行商问题1.需求分析2.数据结构、功能模块设计与说明2.1数据结构(1)模拟退火搜索算法(2)遗传算法2.2功能模块设计(1)模拟退火搜索算法(2)遗传算法3.核心代码与测试结果说明(1)模拟退火搜索算法(2)遗传算法4.心得体会一、旅行商问题现有一个商人,准备从广州......
  • 模拟退火算法(Simulated Annealing, SA)及微优化(入门)
    模拟退火算法(SimulatedAnnealing,SA)是一种启发式搜索算法,常用于解决优化问题。该算法以概率的方式搜索问题的解空间,并在搜索过程中逐渐降低温度,从而有助于找到全局最优解。模拟退火算法的基本原理如下:初始化:随机生成一个初始解。迭代过程:生成一个新解,这个新解通过一......
  • 利用遗传算法(GA)与模拟退火算法(SA)求目标函数最小值
    要求实现一个演化计算的算法,求测试函数的最小值。要求:群体规模NP=100;最大迭代次数不超过3000代。或者,总的计算次数小于100*3000。算法需独立运行30次,并记录进化的过程。一、遗传算法原理        遗传算法(GeneticAlgorithm,GA)是模拟达尔文生物进化论的自然选择和......
  • 模拟退火(Simulated Annealing, SA)算法是
    模拟退火(SimulatedAnnealing,SA)算法是一种概率型启发式搜索算法,用于寻找优化问题中的全局最优解。它受到冶金学中退火过程的启发,通过模拟金属冷却过程中的退火过程来寻找问题的最优解。以下是使用MATLAB实现模拟退火算法的一个简单示例。这个例子中,我们将使用模拟退火算法来......
  • 基于改进模拟退火(HDSA)优化无人机紧急着陆时的轨迹最优研究(Matlab代码实现)
     ......
  • 模拟退火
    模拟退火一个基于随机的算法,多用于求解最优解问题。对于一个多峰函数,该算法会在函数上不断跳跃并记录最优。#include<bits/stdc++.h>#definedoudoubleconstdoulim=1e-15,D=0.9996;usingnamespacestd;douansx,ansy,ansd;douclac(doux,douy){}voidS......
  • 68文章解读与程序——电力自动化设备EI\CSCD\北大核心《基于混沌模拟退火粒子群优化
    ......