模拟退火

小灰灰 2023-06-02 12:52 18阅读 0赞

# Summary #

退火总结.退火其实不难...难的是怎么调参.  
贡献两页提交才只有\\(55pts\\)的经历真是惨不忍睹.这就是调参的艰难.  
主要就是这么几个参数:  
\\(T\_0,T,d,T\_e\\).  
分别是初温,当前温度,降温系数,终止温度.  
主要就说一下降温系数叭.  
这个东西,呃,很玄乎,你改个\\(0.\\)几它可能人就没了,也可能就直接\\(AC\\)了.  
那么退火这个东西,实质上是个随机化算法,是对爬山算法的优化.  
爬山算法的流程就是随机状态,得到该状态解,更优则转移,否则跳过.  
这样很显然如果答案是多峰函数,很可能就死在一个峰出不来了.  
而退火,则有效地避免了这种情况.  
它的工作流程也是,随机状态,得到该状态解,更优则转移,否则以一定的概率去接受这个状态得到的不优解.  
为什么会有这个一定概率接受呢?  
因为这个不优解有可能来自于另一个峰的某个位置,而我们当前峰的峰顶很可能并不如另一个峰的峰顶要优.于是我们选择接受这个不优解,实际上是给了自己一个机会,不让自己死在一个峰上.  
那重点来了!这个一定概率是个啥啊?  
你想啊,退火是个玄学随机算法,那么不如这个概率也随个机算了.  
于是我们一般取这个概率\\(P\_c=rand()/RAND\\\_MAX\\).  
而这个概率是在这里了,那我们以什么为标准取和这个概率评判呢?  
以\\(e\\)的能量差次幂和当前温度的商作为标准比对,大于则接受否则拒绝(也有可能改变),这个能量差\\(\\Delta\\),要小于等于\\(0\\).  
为什么呢?显然,\\(P\_c\\le 1\\)且\\(e=2.718281828...\\),若\\(\\Delta>0\\),显然我们就只能一直接受或一直拒绝,具体接受还是拒绝取决于你前面的决策.  
至于那个著名的退火图...  
![图挂了][007X8olVly1g7byxxqvreg30dw04h1kx.gif]  
啊,清爽!唉...好像忘了说降温系数咋用了...  
一句话,每次降温用.当前温度乘上降温系数.  
显然,温度越低,就越稳定.(图也能说明问题)  
通用板子:

for (int T = T0 ; T >= Te ; T *= d) { // rand 一个合法状态 // Example:A permutation. int l = rand () % n + 1 , r = rand () % n + 1 ; // 得到该状态 swap ( v[l] , v[r] ) ; // 得出该状态的解 // Example: int res = get_ans () ; // 判断是否比当前解更优,若是,直接继承 // Example: if ( ans < res ) ans = res ; // 否则以一定概率接受该不优解 else if ( exp ( ( res - ans ) / T ) * RAND_MAX < rand () ) // 撤回操作. swap ( v[l] , v[r] ) ; }

重点就是快速得到某个状态的解,所以通常退火应用于\\(n\\)比较小,或者有其他美妙的性质可以使你快速得到一个解的情况.(所以最优性状压题经常被退过去,但也不是所有的最优性状压都能被退过去)  
例题的话,这个叭:  
[\[TJOI2010\]分金币][TJOI2010]  
代码的话,也有:

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define one first #define two second #define rint read<int> #define int long long #define pb push_back #define db double using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int N = 35 ; int Tot , n , v[N] , ans ; inline int mabs (int x) { return x < 0 ? - x : x ; } inline int initial () { int mid = ( n + 1 ) >> 1 ; int sum1 = 0 , sum2 = 0 ; rep ( i , 1 , mid ) sum1 += v[i] ; rep ( i , mid + 1 , n ) sum2 += v[i] ; return mabs ( sum1 - sum2 ) ; } signed main (int argc , char * argv[]) { srand ( time ( NULL ) ) ; srand ( rand () ^ rand () ) ; Tot = rint () ; while ( Tot -- ) { n = rint () ; ans = 0x7f7f7f7f ; rep ( i , 1 , n ) v[i] = rint () ; rep ( i , 1 , 100 ) { db T = 5e4 ; while ( T >= 1e-10 ) { int l = rand () % n + 1 , r = rand () % n + 1 ; swap ( v[l] , v[r] ) ; int res = initial () ; if ( ans > res ) ans = res ; else if ( exp ( ( ans - res ) / T ) * RAND_MAX < (db) rand () ) swap ( v[l] , v[r] ) ; T *= 0.98 ; } } printf ("%lld\n" , ans ) ; } system ("pause") ; return 0 ; }

什么?\\(n\\le500\\)?退就完了!

转载于:https://www.cnblogs.com/Equinox-Flower/p/11586969.html

[007X8olVly1g7byxxqvreg30dw04h1kx.gif]: /images/20230601/81924057510f4273b2cc35fe4c2a5de1.png
[TJOI2010]: https://www.luogu.org/problem/P3878