1.簡介
模擬退火演算法來源于固體退火原理，是一種基于概率的演算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小， ————百度百科
簡而言之，模擬退火是一種隨機化演算法，常用于資訊學競賽中騙取高分，但因為其為隨機化演算法，所以不是很穩定，少則10分，多則AC，這取決于你的RP了（doge）， 它與爬山演算法最大的不同是，在尋找到一個區域最優解時，賦予了它一個跳出去的概率，也就有更大的機會能找到全域最優解，
2.原理
原理在這里就不過多說了，因為可能對于程式的撰寫沒有多大的影響，下面直接給出百度百科的原理介紹：
模擬退火的原理也和金屬退火的原理近似：將熱力學的理論套用到統計學上，將搜尋空間內每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度，演演算法先以搜尋空間內一個任意點作起始：每一步先選擇一個“鄰居”，然后再計算從現有位置到達“鄰居”的概率，
簡單來說就是，隨機生成一個新的解，然后將其與先前的最優解進行比較，若生成的新解更優，則更新最優解，否則以exp（-ΔT/T）的概率接受它，exp是計算以自然底數為底的指數的函式，而這里的接受并不是指將新解作為最優解，而是更新步驟，
3.程序
1）降溫
模擬退火有三個重要的引數，分別為初溫t、降溫系數ΔT和終溫Tk，這三個引數關系到你的程式結果的準確性，當然，如何選擇恰當的引數需要你的經驗和RP了，其中，t是一個比較大的數，ΔT 是一個略小于 1 的正數，Tk 是一個略大于 0 的正數，我們先設當前溫度T為初溫，然后每次降溫時 T 乘上 ΔT，直到 T≤Tk 為止
大致程序如下：
可以看出，隨著溫度的降低，解逐漸穩定下來，并逐漸集中在最優解附近，
2）生成新解
生成新解的基本思想就是使用rand隨機生成一個值，并帶入對應的計算函式就可以得出一個新解了，而計算函式是根據對應題目來決定的，往往都不相同，
3）調參
這可能是模擬退火中最重要的一步了，一個好的引數可一讓你AC你所作的題，而一個壞的引數，可能讓你的分數比暴力還低，一般來講，如果答案不是最優，有以下幾種調法：調大ΔT，調整t和Tk或多跑即便退火，如果太非的話，這邊還是建議您直接打正解吧（
4）調整
如果新解更優，接受這個解，否則我們以一定概率接受這個解，設ΔW為新解和當前解的差 ΔW>0 ，我們希望的是：T越大時概率越大，ΔW越小時概率越小，個亂數，當然，如果 ΔW很大或很小的話這樣子就可能會出問題，我們可以通過合理選擇r的范圍來解決問題，
5）其他
模擬退火中，還有一件重要的事就是選好亂數種子，和調參一樣，種子選好了收益整個比賽，種子太臭，像11451419就會出事，下面是我的慘痛教訓
程式開始時，我們要先srand(一個常數)，這個常數可以決定分數，你可以使用 233333，2147483647，甚至某個八位質數，
可以用一個全域變數記錄所有跑過的模擬退火的最優解，每次從那個最優解開始繼續模擬退火，可以減小誤差，
4.實際應用
這里以洛谷1337 [JSOI2004]平衡點 / 吊打XXX為例，講解模擬退火的實際應用，
題目要使整個系統的能量最小，那么我們只要用模擬退火跑出這個最小值即可，
代碼如下：
#include <bits/stdc++.h> #define re register using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); return X*w; } int n,sx,sy; double ansx,ansy; //全域最優解坐標 double ans = 1e18,t; //全域最優解，溫度t const double delta = 0.9913; struct node{ int x,y,w; }a[1010]; inline double calc_energy(double x,double y){ double rt=0; for (re int i=1;i<=n;i++) { double deltax=x-a[i].x,deltay=y-a[i].y; rt+=sqrt(deltax*deltax+deltay*deltay)*a[i].w; } return rt; } inline void simulate_anneal(){ double x = ansx,y = ansy; t = 2000; //設初溫 while (t>1e-14){ double X = x+((rand()<<1)-RAND_MAX)*t; double Y = y+((rand()<<1)-RAND_MAX)*t; double now = calc_energy(X,Y); double Delta = now-ans; //當前最優解與新解的差 if (Delta<0){ x = X; y = Y; ansx = x,ansy = y,ans = now; } else if (exp(-Delta/t)*RAND_MAX>rand()){ //若不是當前最優，則有一定概率接受它 x = X; y = Y; } t*=delta; } } inline void Solve() { //多跑幾遍模擬退火，減小誤差 ansx=(double)sx/n,ansy=(double)sy/n; //從平均值開始更容易接近最優解 simulate_anneal(); simulate_anneal(); simulate_anneal(); } int main(){ srand(11451411919); srand(rand()); srand(rand()); n = read(); for (re int i=1;i<=n;i++){ a[i].x = read(),a[i].y = read(),a[i].w = read(); sx+=a[i].x,sy+=a[i].y; } Solve(); printf("%.3f %.3f\n",ansx,ansy); return 0; }
Over~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/520643.html
標籤：其他