原來就聽說過模擬退火，然后一直覺得神奇，但是沒有真正的去實(shí)現(xiàn)這個(gè)算法。
模擬退火對TSP之類的問題很實(shí)用。

1.概念：模擬退火算法（Simulate Anneal，SA）是一種通用概率演算法，用來在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發(fā)明的。V.?erny在1985年也獨(dú)立發(fā)明此演算法。模擬退火算法是解決TSP問題的有效方法之一。

模擬退火的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法是一種通用的優(yōu)化算法，其物理退火過程由加溫過程、等溫過程、冷卻過程這三部分組成。

實(shí)際上模擬退火是一個(gè)很好理解的東西。簡單地說，就是將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對命題的合適程度。演算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。
與之相對的是爬山算法，爬山算法是找到一個(gè)局部最優(yōu)值之后就不會再往下搜索下去了。但是模擬退火會有一定的概率再去往下搜索下去，然后就會越來越接近最優(yōu)值。

2.模擬退火的基本要素
狀態(tài)空間與狀態(tài)產(chǎn)生函數(shù)
(1).搜索空間（又叫狀態(tài)空間）。一般范圍比較大，事我們自定義的可行解的集合。

(2).狀態(tài)函數(shù)。狀態(tài)函數(shù)將決定你是否要選用當(dāng)前的解，對于一個(gè)好的退火來說，狀態(tài)函數(shù)的搜索空間應(yīng)該足夠大。

(3).候選解。一般采用隨機(jī)數(shù)來在一定密度內(nèi)隨機(jī)選取。

(4).概率分布。大多采取均勻分布或指數(shù)分布。

狀態(tài)轉(zhuǎn)移概率
(1).狀態(tài)轉(zhuǎn)移概率是指從一個(gè)狀態(tài)向另一個(gè)狀態(tài)的轉(zhuǎn)移概率。

(2).通俗的理解是接受一個(gè)新解為當(dāng)前解的概率。

(3).它與當(dāng)前的溫度參數(shù)T有關(guān)，隨溫度下降而減小。

(4).一般采用Metropolis準(zhǔn)則。

3.模擬退火模型
第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進(jìn)度表的選取有一定的影響。

第二步是計(jì)算與新解所對應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。

第三步是判斷新解是否被接受，判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropolis準(zhǔn)則: 若Δt′<0則接受S′作為新的當(dāng)前解S，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解S。

第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代。可在此基礎(chǔ)上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。

模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。
4.參數(shù)控制
模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點(diǎn)：

(1) 溫度T的初始值設(shè)置問題。 溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。

(2) 退火速度問題。 模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來說，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間。實(shí)際應(yīng)用中，要針對具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件。

(3) 溫度管理問題。 溫度管理問題也是模擬退火算法難以處理的問題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問題，常采用如下所示的降溫方式：式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù)。

5.算法改進(jìn)
（1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)，使其根據(jù)搜索進(jìn)程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性；

（2）設(shè)計(jì)高效的退火策略；

（3）避免狀態(tài)的迂回搜索；

（4）采用并行搜索結(jié)構(gòu)；

（5）為避免陷入局部極小，改進(jìn)對溫度的控制方式；

（6）選擇合適的初始狀態(tài)；

（7）設(shè)計(jì)合適的算法終止準(zhǔn)則。
對于洛谷這個(gè)題目。系統(tǒng)最穩(wěn)定的時(shí)候就是系統(tǒng)的整體能量最小的時(shí)候，系統(tǒng)能量就是整體的重力勢能。因?yàn)槲镏匾欢?#xff0c;繩子越短，重物越低，勢能越小，勢能又與物重成正比，所以，只要使得也就是總的重力勢能最小，就可以使系統(tǒng)平衡。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define esp 1e-15 using namespace std;const int maxx=1e3+100; struct node{double x;double y;double w; }p[maxx]; int n;node ans;inline double dis(node a,node b)//返回兩點(diǎn)的距離 {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } inline double dev(node ans)//計(jì)算當(dāng)前節(jié)點(diǎn)的整體重力勢能 {double a=0.0;for(int i=1;i<=n;i++) a+=(dis(p[i],ans)*p[i].w);return a; } inline void SA() {double t=3000;//起始溫度double delta=0.996;node a;while(t>esp){a.x=ans.x+(rand()*2-RAND_MAX)*t;a.y=ans.y+(rand()*2-RAND_MAX)*t;//這樣坐標(biāo)的范圍是[-RAND_MAX,RAND_MAX]。//rand()的范圍是0~RAND_MAX-1//rand()*2-RAND_MAX的范圍是-RAND_MAX到RAND_MAX-1a.w=dev(a);if(a.w-ans.w<0) ans=a;else if(exp((ans.w-a.w)/t)*RAND_MAX>rand()) ans=a;//模擬退火的精髓（△t=ans-a,之前最優(yōu)值-當(dāng)前計(jì)算的值）t*=delta;} } inline void solve() {for(int i=1;i<5;i++) SA(); } int main() {while(~scanf("%d",&n)){ans.x=0.0;ans.y=0.0;for(int i=1;i<=n;i++) {scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w);ans.x+=p[i].x;ans.y+=p[i].y;}ans.x/=n;//起始值選取平均值。ans.y/=n;ans.w=dev(ans);solve();printf("%.3lf %.3lf\n",ans.x,ans.y);}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的模拟退火总结+洛谷模板题（P1337 [JSOI2004]平衡点 / 吊打XXX）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。