模擬退火學習筆記

1.簡介

模擬退火演算法來源於固體退火原理，是一種基於概率的演算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。 　　  ————百度百科

簡而言之，模擬退火是一種隨機化演算法，常用於資訊學競賽中騙取高分，但因為其為隨機化演算法，所以不是很穩定，少則10分，多則AC，這取決於你的RP了（doge）。 它與爬山演算法最大的不同是，在尋找到一個局部最優解時，賦予了它一個跳出去的概率，也就有更大的機會能找到全局最優解。

2.原理

原理在這裡就不過多說了，因為可能對於程式的編寫沒有多大的影響，下面直接給出百度百科的原理介紹：

模擬退火的原理也和金屬退火的原理近似：將熱力學的理論套用到統計學上，將搜尋空間內每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有「能量」，以表示該點對命題的合適程度。演演算法先以搜尋空間內一個任意點作起始：每一步先選擇一個「鄰居」，然後再計算從現有位置到達「鄰居」的概率。

 簡單來說就是，隨機生成一個新的解，然後將其與先前的最優解進行比較，若生成的新解更優，則更新最優解，否則以exp（-ΔT/T）的概率接受它，exp是計算以自然底數為底的指數的函數，而這裡的接受並不是指將新解作為最優解，而是更新步驟。

3.過程

　　1）降溫

　　　　模擬退火有三個重要的參數，分別為初溫t、降溫係數ΔT和終溫Tk，這三個參數關係到你的程式結果的準確性，當然，如何選擇恰當的參數需要你的經驗和RP了。

　　　　其中，t 是一個比較大的數，ΔT 是一個略小於 11 的正數，Tk​ 是一個略大於 00 的正數。我們先設當前溫度T為初溫，然後每次降溫時 T 乘上 ΔT，直到 T≤Tk​ 為止。

　　　　大致過程如下：

　　　　

　　　　可以看出，隨著溫度的降低，解逐漸穩定下來，並逐漸集中在最優解附近。

　　2）生成新解

　　　　生成新解的基本思想就是使用rand隨機生成一個值，並帶入對應的計算函數就可以得出一個新解了，而計算函數是根據對應題目來決定的，往往都不相同。

　　3）調參

　　　　這可能是模擬退火中最重要的一步了，一個好的參數可一讓你AC你所作的題，而一個壞的參數，可能讓你的分數比暴力還低，一般來講，如果答案不是最優，有以下幾種調法：調大ΔT，調整t和Tk或多跑即便退火，如果太非的話，這邊還是建議您直接打正解吧（

　　4）調整

　　　　如果新解更優，接受這個解。否則我們以一定概率接受這個解。設 ΔW 為新解和當前解的差（ΔW>0）。我們希望的是：T 越大時概率越大，ΔW 越小時概率越小。我們選擇 e^{-\frac{\Delta W}{rT}}e−rTΔW​ 作為概率，這裡的 r 是一個隨機數。當然，如　　　　　　　　       果  Δ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~

Tags:

VirMach 便宜 VPS

QNews

QNews