 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 3 | 1/1 | 返回列表 |
| 查看: 2216 | 回復: 2 | |||
[交流]
【轉(zhuǎn)帖】退火算法_基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程 已有2人參與
|
|
Simulate Anneal Arithmetic (SAA,模擬退火算法) 模擬退火算法 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。 1 . 模擬退火算法的模型 模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。 模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數(shù)L (2) 對k=1，……，L做第(3)至第6步： (3) 產(chǎn)生新解S′ (4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數(shù) (5) 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解. (6) 如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。 (7) T逐漸減少，且T->0，然后轉(zhuǎn)第2步。 算法對應動態(tài)演示圖： 模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： 第一步是由一個產(chǎn)生函數(shù)從當前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。 第二步是計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。 第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropo1is準則: 若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S。 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代�？稍诖嘶A上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。 模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 2 模擬退火算法的簡單應用 作為模擬退火算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，用數(shù)碼1,…,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.。 求解TSP的模擬退火算法模型可描述如下： 解空間 解空間S是遍訪每個城市恰好一次的所有回路，是{1，……，n}的所有循環(huán)排列的集合，S中的成員記為(w1,w2 ,……，wn)，并記wn+1= w1。初始解可選為(1，……，n) 目標函數(shù) 此時的目標函數(shù)即為訪問所有城市的路徑總長度或稱為代價函數(shù)： 我們要求此代價函數(shù)的最小值。 新解的產(chǎn)生 隨機產(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). 上述變換方法可簡單說成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。 也可以采用其他的變換方法，有些變換有獨特的優(yōu)越性，有時也將它們交替使用，得到一種更好方法。 代價函數(shù)差 設將(w1, w2 ,……，wn)變換為(u1, u2 ,……，un), 則代價函數(shù)差為： 根據(jù)上述分析，可寫出用模擬退火算法求解TSP問題的偽程序： 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); { 從當前回路S產(chǎn)生新回路S′} Δt:=f(S′))-f(S);{f(S)為路徑總長} 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 模擬退火算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調(diào)度問題(Scheduling Problem)等等。 3 模擬退火算法的參數(shù)控制問題 模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點： (1) 溫度T的初始值設置問題。 溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據(jù)實驗結果進行若干次調(diào)整。 (2) 退火速度問題。 模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質(zhì)和特征設置合理的退火平衡條件。 (3) 溫度管理問題。 溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式： T(t+1)＝k×T(t) 式中k為正的略小于1.00的常數(shù)，t為降溫的次數(shù) |
回復此樓» 猜你喜歡
焦慮
已經(jīng)有13人回復
-
一志愿985，本科211，0817化學工程與技術319求調(diào)劑
已經(jīng)有8人回復
-
0817 化學工程 299分求調(diào)劑 有科研經(jīng)歷 有二區(qū)文章
已經(jīng)有9人回復
-
346求調(diào)劑[0856]
已經(jīng)有5人回復
-
285化工學碩求調(diào)劑（081700）
已經(jīng)有11人回復
-
267一志愿南京工業(yè)大學0817化工求調(diào)劑
已經(jīng)有9人回復
-
274求調(diào)劑
已經(jīng)有6人回復
-
求材料調(diào)劑
已經(jīng)有10人回復
-
本科鄭州大學物理學院，一志愿華科070200學碩，346求調(diào)劑
已經(jīng)有4人回復
-
國自科面上基金字體
已經(jīng)有8人回復
» 本主題相關價值貼推薦，對您同樣有幫助:
- 反應溶劑中有水，反應過程有無機鹽生成，怎樣后處理去掉無機鹽和水
已經(jīng)有24人回復
- 算法之道，全本，共313頁
已經(jīng)有195人回復
- 誰懂迭代加權最小二乘法，能否給講下原理
已經(jīng)有6人回復
- 有個求解微分方程用到高斯賽德爾迭代的，算不太明白啊，各位幫忙看看
已經(jīng)有5人回復
- 簡單的蒙特卡羅問題？（關于多孔介質(zhì)的隨機分形）
已經(jīng)有3人回復
- fluent迭代流動曲線呈直線狀態(tài)
已經(jīng)有6人回復
- [求助}關于EXCEL迭代嵌套問題
已經(jīng)有4人回復
- 多相流穩(wěn)態(tài)計算，迭代20000多步，不收斂，怪異問題各位請進～
已經(jīng)有14人回復
- fluent迭代時候出現(xiàn)的問題
已經(jīng)有7人回復
- 【求助】ANSYS或abaqus 等CAE軟件的迭代求解的初值問題
已經(jīng)有7人回復
yahoohoo
鐵桿木蟲 (著名寫手)
- 模擬EPI: 10
- 應助: 0 (幼兒園)
- 貴賓: 1.55
- 金幣: 7632.4
- 散金: 251
- 紅花: 4
- 帖子: 1176
- 在線: 167小時
- 蟲號: 74894
- 注冊: 2005-06-15
- 性別: GG
- 專業(yè): 理論和計算化學
2樓2010-09-16 21:52:07
|
感謝分享 [ 發(fā)自手機版 http://www.gaoyang168.com/3g ] |
3樓2013-01-07 08:51:02
相關版塊跳轉(zhuǎn)
我要訂閱樓主 zyj8119 的主題更新
| 3 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 0703化學調(diào)劑，求各位老師收留 +10 | 秋有木北 2026-03-14 | 10/500 |
|
|---|---|---|---|---|
|
|
[考研] 一志愿吉林大學材料學碩321求調(diào)劑 +4 | Ymlll 2026-03-18 | 6/300 |
|
|
[考研] 354求調(diào)劑 +4 | Tyoumou 2026-03-18 | 7/350 |
|
|
|
[考研] 一志愿中國海洋大學，生物學，301分，求調(diào)劑 +4 | 1孫悟空 2026-03-17 | 4/200 |
|
|
|
[考研] 286求調(diào)劑 +6 | lemonzzn 2026-03-16 | 9/450 |
|
|
|
[考研] 工科材料085601 279求調(diào)劑 +6 | 困于星晨 2026-03-17 | 6/300 |
|
|
|
[考研] 268求調(diào)劑 +6 | 簡單點0 2026-03-17 | 6/300 |
|
|
|
[考研] 268求調(diào)劑 +7 | 好運連綿不絕 2026-03-12 | 8/400 |
|
|
|
[考研] 278求調(diào)劑 +3 | Yy7400 2026-03-13 | 3/150 |
|
|
|
[考研] 機械專碩325，尋找調(diào)劑院校 +3 | y9999 2026-03-15 | 5/250 |
|
|
|
[基金申請]
今年的國基金是打分制嗎？
 50+3
|
zhanghaozhu 2026-03-14 | 3/150 |
|
|
|
[考研] 中科院材料273求調(diào)劑 +4 | yzydy 2026-03-15 | 4/200 |
|
|
|
[考研] 085600材料與化工 求調(diào)劑 +13 | enenenhui 2026-03-13 | 14/700 |
|
|
|
[考研] 285求調(diào)劑 +6 | ytter 2026-03-12 | 6/300 |
|
|
|
[考研] 070303 總分349求調(diào)劑 +3 | LJY9966 2026-03-15 | 5/250 |
|
|
|
[考研] 26考研一志愿中國石油大學(華東)305分求調(diào)劑 +3 | 嘉年新程 2026-03-15 | 3/150 |
|
|
|
[考研] 0856專碩279求調(diào)劑 +5 | 加油加油！? 2026-03-15 | 5/250 |
|
|
|
[考研] 304求調(diào)劑 +6 | Mochaaaa 2026-03-12 | 7/350 |
|
|
|
[考研] 290求調(diào)劑 +7 | ADT 2026-03-12 | 7/350 |
|
|
|
[考研] 0817化學工程與技術考研312分調(diào)劑 +3 | T123 tt 2026-03-12 | 3/150 |
|