 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 3 | 1/1 | 返回列表 |
| 查看: 2217 | 回復(fù): 2 | |||
[交流]
【轉(zhuǎn)帖】退火算法_基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程 已有2人參與
|
|
Simulate Anneal Arithmetic (SAA,模擬退火算法) 模擬退火算法 模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。 1 . 模擬退火算法的模型 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L (2) 對(duì)k=1，……，L做第(3)至第6步： (3) 產(chǎn)生新解S′ (4) 計(jì)算增量Δt′=C(S′)-C(S)，其中C(S)為評(píng)價(jià)函數(shù) (5) 若Δt′<0則接受S′作為新的當(dāng)前解，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解. (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。 終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法。 (7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。 算法對(duì)應(yīng)動(dòng)態(tài)演示圖： 模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟： 第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過(guò)簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。 第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。 第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則: 若Δt′<0則接受S′作為新的當(dāng)前解S，否則以概率exp(-Δt′/T)接受S′作為新的當(dāng)前解S。 第四步是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(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)。 模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 2 模擬退火算法的簡(jiǎn)單應(yīng)用 作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問(wèn)題(Travelling Salesman Problem，簡(jiǎn)記為TSP)：設(shè)有n個(gè)城市，用數(shù)碼1,…,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．TSP問(wèn)題是要找遍訪每個(gè)域市恰好一次的一條回路，且其路徑總長(zhǎng)度為最短.。 求解TSP的模擬退火算法模型可描述如下： 解空間 解空間S是遍訪每個(gè)城市恰好一次的所有回路，是{1，……，n}的所有循環(huán)排列的集合，S中的成員記為(w1,w2 ,……，wn)，并記wn+1= w1。初始解可選為(1，……，n) 目標(biāo)函數(shù) 此時(shí)的目標(biāo)函數(shù)即為訪問(wèn)所有城市的路徑總長(zhǎng)度或稱為代價(jià)函數(shù)： 我們要求此代價(jià)函數(shù)的最小值。 新解的產(chǎn)生 隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，若k (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 變?yōu)椋? (w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn). 如果是k>m，則將 (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 變?yōu)椋? (wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk). 上述變換方法可簡(jiǎn)單說(shuō)成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。 也可以采用其他的變換方法，有些變換有獨(dú)特的優(yōu)越性，有時(shí)也將它們交替使用，得到一種更好方法。 代價(jià)函數(shù)差 設(shè)將(w1, w2 ,……，wn)變換為(u1, u2 ,……，un), 則代價(jià)函數(shù)差為： 根據(jù)上述分析，可寫出用模擬退火算法求解TSP問(wèn)題的偽程序： Procedure TSPSA: begin init-of-T; { T為初始溫度} S={1，……，n}; {S為初始值} termination=false; while termination=false begin for i=1 to L do begin generate(S′form S); { 從當(dāng)前回路S產(chǎn)生新回路S′} Δt:=f(S′))-f(S);{f(S)為路徑總長(zhǎng)} IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) S=S′; IF the-halt-condition-is-TRUE THEN termination=true; End; T_lower; End; End 模擬退火算法的應(yīng)用很廣泛，可以較高的效率求解最大截問(wèn)題(Max Cut Problem)、0-1背包問(wèn)題(Zero One Knapsack Problem)、圖著色問(wèn)題(Graph Colouring Problem)、調(diào)度問(wèn)題(Scheduling Problem)等等。 3 模擬退火算法的參數(shù)控制問(wèn)題 模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問(wèn)題，但其參數(shù)難以控制，其主要問(wèn)題有以下三點(diǎn)： (1) 溫度T的初始值設(shè)置問(wèn)題。 溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。 (2) 退火速度問(wèn)題。 模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來(lái)說(shuō)，同一溫度下的“充分”搜索(退火)是相當(dāng)必要的，但這需要計(jì)算時(shí)間。實(shí)際應(yīng)用中，要針對(duì)具體問(wèn)題的性質(zhì)和特征設(shè)置合理的退火平衡條件。 (3) 溫度管理問(wèn)題。 溫度管理問(wèn)題也是模擬退火算法難以處理的問(wèn)題之一。實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問(wèn)題，常采用如下所示的降溫方式： T(t+1)＝k×T(t) 式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù) |
回復(fù)此樓» 猜你喜歡
材料與化工求調(diào)劑
已經(jīng)有7人回復(fù)
-
304求調(diào)劑
已經(jīng)有3人回復(fù)
-
0817 化學(xué)工程 299分求調(diào)劑 有科研經(jīng)歷 有二區(qū)文章
已經(jīng)有12人回復(fù)
-
085600材料與化工調(diào)劑 324分
已經(jīng)有12人回復(fù)
-
286求調(diào)劑
已經(jīng)有10人回復(fù)
-
324分 085600材料化工求調(diào)劑
已經(jīng)有3人回復(fù)
-
317求調(diào)劑
已經(jīng)有6人回復(fù)
-
307求調(diào)劑
已經(jīng)有5人回復(fù)
-
求調(diào)劑
已經(jīng)有3人回復(fù)
-
求調(diào)劑，一志愿:南京航空航天大學(xué)大學(xué) ，080500材料科學(xué)與工程學(xué)碩，總分289分
已經(jīng)有3人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 反應(yīng)溶劑中有水，反應(yīng)過(guò)程有無(wú)機(jī)鹽生成，怎樣后處理去掉無(wú)機(jī)鹽和水
已經(jīng)有24人回復(fù)
- 算法之道，全本，共313頁(yè)
已經(jīng)有195人回復(fù)
- 誰(shuí)懂迭代加權(quán)最小二乘法，能否給講下原理
已經(jīng)有6人回復(fù)
- 有個(gè)求解微分方程用到高斯賽德爾迭代的，算不太明白啊，各位幫忙看看
已經(jīng)有5人回復(fù)
- 簡(jiǎn)單的蒙特卡羅問(wèn)題？（關(guān)于多孔介質(zhì)的隨機(jī)分形）
已經(jīng)有3人回復(fù)
- fluent迭代流動(dòng)曲線呈直線狀態(tài)
已經(jīng)有6人回復(fù)
- [求助}關(guān)于EXCEL迭代嵌套問(wèn)題
已經(jīng)有4人回復(fù)
- 多相流穩(wěn)態(tài)計(jì)算，迭代20000多步，不收斂，怪異問(wèn)題各位請(qǐng)進(jìn)～
已經(jīng)有14人回復(fù)
- fluent迭代時(shí)候出現(xiàn)的問(wèn)題
已經(jīng)有7人回復(fù)
- 【求助】ANSYS或abaqus 等CAE軟件的迭代求解的初值問(wèn)題
已經(jīng)有7人回復(fù)
yahoohoo
鐵桿木蟲 (著名寫手)
- 模擬EPI: 10
- 應(yīng)助: 0 (幼兒園)
- 貴賓: 1.55
- 金幣: 7632.4
- 散金: 251
- 紅花: 4
- 帖子: 1176
- 在線: 167小時(shí)
- 蟲號(hào): 74894
- 注冊(cè): 2005-06-15
- 性別: GG
- 專業(yè): 理論和計(jì)算化學(xué)
2樓2010-09-16 21:52:07
|
感謝分享 [ 發(fā)自手機(jī)版 http://www.gaoyang168.com/3g ] |
3樓2013-01-07 08:51:02
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 zyj8119 的主題更新
| 3 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 求調(diào)劑 +3 | Mqqqqqq 2026-03-19 | 3/150 |
|
|---|---|---|---|---|
|
|
[考研] 0703化學(xué)調(diào)劑 +5 | pupcoco 2026-03-17 | 8/400 |
|
|
|
[考研] 328求調(diào)劑，英語(yǔ)六級(jí)551，有科研經(jīng)歷 +4 | 生物工程調(diào)劑 2026-03-16 | 12/600 |
|
|
|
[考研] 0703化學(xué)調(diào)劑，求各位老師收留 +10 | 秋有木北 2026-03-14 | 10/500 |
|
|
|
[考研]
 271材料工程求調(diào)劑
+5
|
.6lL 2026-03-18 | 5/250 |
|
|
|
[考研] 材料工程專碩調(diào)劑 +5 | 204818@lcx 2026-03-17 | 6/300 |
|
|
[考研] 311求調(diào)劑 +11 | 冬十三 2026-03-15 | 12/600 |
|
|
|
[考研] 收復(fù)試調(diào)劑生 +4 | 雨后秋荷 2026-03-18 | 4/200 |
|
|
|
[考博] 環(huán)境領(lǐng)域全國(guó)重點(diǎn)實(shí)驗(yàn)室招收博士1-2名 +3 | QGZDSYS 2026-03-13 | 5/250 |
|
|
|
[考研] 296求調(diào)劑 +5 | 大口吃飯 身體健 2026-03-13 | 5/250 |
|
|
|
[碩博家園] 湖北工業(yè)大學(xué) 生命科學(xué)與健康學(xué)院-課題組招收2026級(jí)食品/生物方向碩士 +3 | 1喜春8 2026-03-17 | 5/250 |
|
|
|
[考研] 302求調(diào)劑 +4 | 小賈同學(xué)123 2026-03-15 | 8/400 |
|
|
|
[考研] 機(jī)械專碩325，尋找調(diào)劑院校 +3 | y9999 2026-03-15 | 5/250 |
|
|
|
[考研] 求老師收留調(diào)劑 +4 | jiang姜66 2026-03-14 | 5/250 |
|
|
|
[考研] 26考研一志愿中國(guó)石油大學(xué)(華東)305分求調(diào)劑 +3 | 嘉年新程 2026-03-15 | 3/150 |
|
|
|
[考研] 085601材料工程315分求調(diào)劑 +3 | yang_0104 2026-03-15 | 3/150 |
|
|
|
[考研] 中科大材料與化工319求調(diào)劑 +3 | 孟鑫材料 2026-03-14 | 3/150 |
|
|
|
[考研] 材料與化工 323 英一+數(shù)二+物化，一志愿：哈工大 本人本科雙一流 +4 | 自由的_飛翔 2026-03-13 | 5/250 |
|
|
|
[考研] 學(xué)碩285求調(diào)劑 +13 | Wisjxn 2026-03-12 | 46/2300 |
|
|
|
[考研] 0856材料與化工301求調(diào)劑 +5 | 奕束光 2026-03-13 | 5/250 |
|