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

模拟退火

时间:2023-01-15 10:46:55浏览次数:32  
标签:状态 tx rd01 模拟退火 Delta 转移

概述

  • 模拟退火是一种模拟物理学中材料退火现象的近似算法。

  • 在物理的退火过程中,随着温度的逐渐降低,各粒子的能量会趋向性地稳定在最小值附近(但也有概率反常升高)。

  • 于是我们尝试构建一种算法来模拟退火过程,对于每个状态,其估价函数越好,“能量”越低,反之亦然。

  • 而温度就是体系活跃程度,即愿意改变状态的程度的标量。

思路

  • 爬山算法的一个致命问题就在于,找到局部最优解后难以跳出其局限。

  • 投放大量状态固然不失为一种选择,但显然只是一种补救而已。

  • 我们能不能设法设计某种算法,其中的状态有一定的概率向不优(指估价函数)的状态转移过去?

  • 于是有了模拟退火。

实现原理

  • 开始时随机生成多个初始状态,并设置初始温度 \(T_0\),降温系数 \(D\)(通常 \(\in [0.985,0.999]\)),终止温度 \(T_k\)。

    • 模拟退火算法的表现基本不依赖初始状态的状态,但可能依赖数量。

    • 温度 \(T\) 是当前体系的一个标量,它标示着当前体系的活跃程度,也即愿意转移的程度(即使转移目标是一个较差解)。

    • 模拟退火算法的表现比较依赖初始温度,原则上讲总体退火轮数越多效果会越好,但也越慢。

  • 每轮我们依次枚举所有状态,从它们出发尝试扩展下一轮的状态。

  • 对于每个被扩展出的状态,转移到它的概率是如下的函数:

\[P(\Delta E)=e^\frac{-\Delta E}{T} \]

  • 其中 \(e\) 为自然对数的底,\(\Delta E=E_{to}-E\)。模拟退火中我们认为 \(E\) 越小的状态越优。

  • 观察公式会发现,

    • 当 \(\Delta E\leqslant 0\),即目标状态不劣于当前状态:一定转移,因为 \(P\geqslant e^0=1\)。

    • 当 \(\Delta E>0\),即目标状态劣于当前状态:

      • \(e^\frac{-\Delta E}{T}=\dfrac{1}{e^\frac{\Delta E}{T}}=\dfrac{1}{\sqrt[T]{e^{\Delta E}}}\)

      • 可以看出,\(\Delta E\) 越大即这一转移越差,分母越大,转移概率越小。

      • \(T\) 越大即温度越高,体系越活跃,分母越小,转移概率越大。

  • 每轮结束时,令 \(T=T\times D\)。若 \(T<T_k\) 则结束。

  • 由于模拟退火有可能最终解没有过程解优,我们一般维护遇到过的所有解的最优解。

  • 由于最后的解可能不够精确,一般在退火完毕后做少量随机扰动。

例题

P1337 [JSOI2004] 平衡点

  • 直接放代码吧。充当一个模拟退火的示范代码。
ld x,y;
il void SA(){
	ld T=1e7,D=0.997,Tk=1e-9,tx,ty,delta;
	x=rd01(),y=rd01();
	while(T>Tk){
		tx=x+zfrd()*rd01()*T;
		ty=y+zfrd()*rd01()*T;
		
		delta=calc(tx,ty)-calc(x,y);
		if(exp(-delta/T)>rd01()) x=tx,y=ty;
		
		T*=D;
	}
	For(i,1,10000) calc(x+zfrd()*rd01()*0.1,y+zfrd()*rd01()*0.1);
	return;
}

标签:状态,tx,rd01,模拟退火,Delta,转移
From: https://www.cnblogs.com/weixin2024/p/17053170.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代码实现)
    ......
  • 模拟退火
    模拟退火很多时候我们会被要求求一些函数的最值问题,但是又因为值域很大,是连续的乃至无穷的,那么搜索是搜不出来的,对于这种问题,一般来说爬山算法是很可以的,比如下边的图......