模擬退火算法原理及應用

1、模擬退火算法原理及應用研究模擬退火算法原理及應用研究主講: 陳陳 華華 根根同濟大學海洋與地球科學學院同濟大學海洋與地球科學學院 一 模擬退火算法及VFSA算法模擬退火算法在反演中的應用：模擬退火算法在反演中的應用： 非線性組合優(yōu)化算法：模型擾動，模擬退火，全局尋優(yōu)。 能量函數(shù)目標函數(shù) 模擬退火過程反演迭代傳統(tǒng)模擬退火流程圖YesNo隨機選擇初始模型m0計算能量函數(shù)E(m0)模型擾動產(chǎn)生新模型m1=m0+m0計算能量函數(shù)E(m1)E= E(m1) -E(m0)E0?m0= m1新模型按Metropolis準則接受緩慢降低溫度滿足收斂條件為止Metropolis接受準則： E，新模型被接受，否則

2、被舍棄。 接受能量值較大狀態(tài)，從而在模擬退火溫度控制下全局尋優(yōu)。VFSA算法分析： 模型擾動：831/115 . 0sgn7312uiiiiiiTuTyABymm 接收概率：93/111/1hTEhP 退火計劃： 103/10NckExpTkTVFSA的溫度衰減曲線： VFSA的降溫速度是比較快的1020304050607080901001020304050607080901000.980.80.50.2衰 減 率 系 數(shù) 遞 增 方 向初 始 溫 度 ： 100迭 代 次 數(shù) ： 100參 數(shù) 個 數(shù) N: 2溫 度迭 代 次 數(shù)高溫下VFSA算法模型狀態(tài)分布圖：高溫下VFSA算法的狀態(tài)空間

3、遍歷能力遜于隨機數(shù)發(fā)生器的遍歷能力-3-2.5-2-1.5-1-0.500.511.522.53-3-2.5-2-1.5-1-0.500.511.522.53xyVFSA方 式 擾 動全 局 隨 機 擾 動VFSA算法迭代次數(shù)k與系數(shù)yi的關系示意圖：低溫下模型擾動的空間過大，擾動后模型被接受的機率必然降低，勢必影響尋優(yōu)效率，最終影響算法完成后最終解的精度-1-0.500.51yi高 溫 帶過 渡 帶低 溫 帶010203040506070809010005101520迭 代 次 數(shù)退 火 溫 度VFSA二 改進的VFSA算法MVFSA算法MVFSA有以下改進： 過程一：較高的初始溫度，VFS

4、A算法的退火計劃，模型作全局隨機擾動搜索并鎖定最優(yōu)解區(qū)間； 過程二：較低的初始溫度，適當回火的退火計劃，模型作局部隨機擾動-擾動在當前模型周圍進行在鎖定最優(yōu)解空間后，由于其搜索空間變得較小，以此提高模型接受效率。過程一：模擬退火，全局搜索iiiiABuBmT = T0*EXP(-*(j-1)1/2) 過程二：回火升溫，局部搜索)(/)5 . 0(jLABummiiii T = T0*EXP(-*(j-k0/)1/2)圖3-5 VFSA與MVFSA算法的退火溫度曲線比較0迭 代 次 數(shù)退 火 溫 度VFSA改 進 算 法過 程 一過 程 二MVFSA算法迭代次數(shù)k與系數(shù)yi的關系示意圖-1-0.

5、500.51yi高 溫 帶過 渡 帶低 溫 帶010203040506070809010005101520迭 代 次 數(shù)退 火 溫 度MVFSA模型試驗Z=f(x,y)Z=f(x,y)型： 模擬退火計劃表 表 3-1算法初試溫度溫度衰減率疊代次數(shù)擾動次數(shù)初始位置VFSA2000.9985003x0=2.5,y0=2.5MVFSA2000.9985003x0=2.5,y0=2.5VFSA算法擾動狀態(tài)分布和尋優(yōu)軌跡圖-3-2.5-2-1.5-1-0.500.511.522.53-3-2.5-2-1.5-1-0.500.511.522.53起 點最 優(yōu) 解xy尋 優(yōu) 軌 跡接 受 狀 態(tài)MVFSA算

6、法擾動狀態(tài)分布和尋優(yōu)軌跡圖-3-2.5-2-1.5-1-0.500.511.522.53-3-2.5-2-1.5-1-0.500.511.522.53起 點最 優(yōu) 解xy尋 優(yōu) 軌 跡接 受 狀 態(tài)VFSA算法目標函數(shù)之差與迭代次數(shù)關系圖501001502002503003504004505000510目標函數(shù)之差迭 代 次 數(shù)擾 動 狀 態(tài)接 受 狀 態(tài)尋 優(yōu) 軌 跡204060800510局 部 放 大MVFSA算法目標函數(shù)之差與迭代次數(shù)關系圖501001502002503003504004505000510目標函數(shù)之差迭 代 次 數(shù)擾 動 狀 態(tài)接 受 狀 態(tài)尋 優(yōu) 軌 跡2040608

7、00510局 部 放 大 VFSA及MVFSA算法在退火計劃十分完備的情況下,表現(xiàn)相當完美：算法起點相同，尋優(yōu)路徑不同，最終找到的都是同一最優(yōu)解 VFSA與MVFSA算法的模型狀態(tài)均分布這個狀態(tài)空間，但VFSA模型狀態(tài)在最優(yōu)解點出現(xiàn)一個十字型狀態(tài)，MVFSA算法在整個最優(yōu)解區(qū)域形成一個矩形，這與它們的模型擾動方式有關。 在相同的退火計劃下兩種算法的時間，VFSA算法約為103秒，而MVFSA算法只用時約75秒，多次試驗表明：MVFSA算法計算時間約比VFSA算法少20-30%。算法穩(wěn)健性試驗：模擬退火計劃表 表 3-3算法初試溫度溫度衰減率疊代次數(shù)擾動次數(shù)初始位置VFSA20.98301x0=

8、2.5,y0=2.5MVFSA20.98301x0=2.5,y0=2.5VFSA算法擾動狀態(tài)分布和尋優(yōu)軌跡圖-3-2.5-2-1.5-1-0.500.511.522.53-3-2.5-2-1.5-1-0.500.511.522.53起 點xy尋 優(yōu) 軌 跡接 受 狀 態(tài)擾 動 狀 態(tài)最 終 解最 優(yōu) 解 位 置MVFSA算法擾動狀態(tài)分布和尋優(yōu)軌跡圖-3-2.5-2-1.5-1-0.500.511.522.53-3-2.5-2-1.5-1-0.500.511.522.53起 點最 優(yōu) 解xy尋 優(yōu) 軌 跡接 受 狀 態(tài)擾 動 狀 態(tài)穩(wěn)健性試驗結論： 多次試驗表明：在同等退火計劃下，VFSA算法較

9、易落入了局部極值區(qū)，而MVSFA算法則比較穩(wěn)健。應用 一 從簡單入手-重力模擬退火反演研究MT-重力聯(lián)合反演研究重力正演計算：計算單元：2.5度體的多邊形截面棱柱體g(x,y,z)=GcosiF1(y2-y,i)+ F1(y1-y,i) 重力目標函數(shù)： MiobsicaligMgxg12/1目標函數(shù)的含義：正演值與實測值的相對均方誤差。優(yōu)點：無量綱，并與測點數(shù)無關，便于與MT方法共同開展聯(lián)合反演重力反演的等值效應現(xiàn)象km-5-4-3-2-10012345678910161820222426g(mGal)km實 際 數(shù) 據(jù)反 演 結 果實 際 界 面反 演 界 面等 效 密 度 界 面2.70(

10、g/cm )32.30(g/cm )3消除鋸齒狀界面的方法： 人機聯(lián)作方式 修正在反演程序執(zhí)行過程中進行，不需暫停反演程序9/ )232(2112jjjjjiTTTTTT)2/()(11nTnTTTjjji垂直側(cè)邊梯形的MVFSA反演結果ABCD-2-1.5-1-0.500102030405060708090100012345678MVFSAkmkmg(mGal)實 際 模 型反 演 結 果模 型 計 算反 演 結 果密 度 差 0.28(g/cm )3垂直側(cè)邊梯形組合的MVFSA反演結果ABCDEFGHIJ-2-10010203040506070809010002468模 型 計 算反 演

11、結 果kmkmg(mGal)實 際 模 型反 演 結 果MVFSA密 度 差 0.28(g/cm )3背斜-向斜模型的模擬退火反演結果-7-6-5-4-3-2-1002468101214161820246模 型 計 算反 演 結 果模 型 界 面反 演 結 果g(mGal)(km)(km)2.70(g/cm )32.30(g/cm )32.52(g/cm )3MVFSA算法的實際資料處理：-8-6-4-202.342.542.702.542.602.6005101520253035510g(mGal)(km)(km)Q - J2.60D-SAnST - C2.60Q - J實 測 點擬 合 曲

12、 線N12新 87反 演 界 面MT解 釋綜 合 解 釋目標函數(shù)與迭代關系曲線圖200400600800100012001400123迭 代 次 數(shù)目 標 函 數(shù)50100150200123模 型 修 正 階 段放 大二 MT-重力聯(lián)合反演研究聯(lián)合反演研究現(xiàn)狀： 線性反演算法居多、非線性算法少，用模擬退火算法進行聯(lián)合反演研究更少。 盡管目前開展的聯(lián)合反演研究已有多種，但研究內(nèi)容主要集中在地震與重力、地震與MT聯(lián)合反演的研究。 有關電磁測深與重力的聯(lián)合反演研究只查閱到一篇相關的論文，因此對這方面的研究基本上還是空白。 1.MT與重力聯(lián)合可以使兩方法相互彌補 MT縱向分辨率與重力橫向的分辨率的互補

13、 實際工作中MT方法的測點點距一般較稀，而野外重力數(shù)據(jù)的采集點較密。MT-MT-重力聯(lián)合反演必要性重力聯(lián)合反演必要性: :2.充分利用野外資料：在生產(chǎn)實際中，非地震方法一般同時開展。 MT-MT-重力聯(lián)合反演可能性重力聯(lián)合反演可能性: : 電性與密度同源界面是兩種方法聯(lián)合的前提 地下結構有可能以同源或部分同源的形式出現(xiàn) 示例: 海安海安-鹽城地區(qū)密度與電阻率統(tǒng)計表鹽城地區(qū)密度與電阻率統(tǒng)計表 表 5-1地地 層層密密 度度( (10103 3kg/mkg/m3 3 ) )電電 阻阻 率率( (m)m)Q16N2.138.7E2.30-2.313.9K2t4.8K2p2.4611.9T1s150T

14、1x84P1Q2.60275C3c3000C2n1617C1h100C1g18C1j2.58600D3w2.5387S3m58S2f66S1g2.5427.5O3d118O2d5218O1I2.67100513g2.70-2.732785電性與密度界面有幾個是一致的： 上第三系-下第三系的物性界面 下第三系-白堊系的物性界面 侏羅系-三疊系物性界面等。開展MT與重力兩者的聯(lián)合反演是可能的。MT與重力聯(lián)合反演技術難點： 如何處理電性與密度界面的不一致情況是首先要遇到的技術難點 如何構筑一個共同的目標函數(shù)因為地下界面的變化使MT與重力兩者的場值變化幅度是不同的MT的正演可以寫為以下變分問題：經(jīng)比較

15、，本文選用有限元法作為二維MT正演方法，既保持較高的計算精度，又適應于復雜結構的地電模型。 max2222211zzGdyVdydzVzVyVVI電性與密度界面的界面的GISGIS編碼技術編碼技術 若是共同的物性界面，MT與重力均需要作正演計算 若是單獨的電性界面，只參加MT正演計算 若是單獨的密度界面，只參加重力正演計算對考慮三種情況：對考慮三種情況：由此產(chǎn)生的三個問題： 如何記錄由MT與重力合成的模型，這個模型中有兩者一致和不一致的物性界面 如何擾動由兩種不同地球物理方法合成的模型 如何讓擾動后模型分別參加MT與重力正演計算以求得有關的目標函數(shù)解決辦法：借鑒GIS中的屬性編碼思想 記錄模型

16、數(shù)據(jù)的MTG(i,j),按照MVFSA算法的具體要求進行全局或在當前模型周圍擾動產(chǎn)生新模型 編碼數(shù)組Code(k)（k=1,2N)，對記錄電性與密度界面情況的數(shù)組MTG(i,j)進行界面屬性編碼 各自的正演計算具體的界面屬性編碼方法： 電性與密度界面一致：Code(k)0，MT與重力均作正演計算； 只是電性界面：Code(k)1，只有MT作正演計算； 只是密度界面：Code(k)1，只有重力作正演計算；目標函數(shù)及其加權聯(lián)合：WMT+Wg=1，體現(xiàn)了聯(lián)合后的目標函數(shù)與mtg的尺度相同，以防止目標函數(shù)的發(fā)散。 WMT、Wg的大小決定了何者為主反演方法，相應的權系數(shù)越大，則該方法為主反演方法。 落實

17、到WMT、Wg的具體取值則是一個非常復雜的問題。ggMTMTWW背斜模型的反演結果-5-4-3-2-1020024681012141618205101520模 型 計 算反 演 結 果500g(mGal)kmkm模 型 計 算反 演 結 果( m)( m)2.70(g/cm )32.30(g/cm )3二層模型的反演結果-6-4-2030105000246810121416182013579模 型 計 算反 演 結 果模 型 計 算反 演 結 果g(mGal)電 性 界 面電 性 -密 度 界 面2.70(g/cm )32.30(g/cm )3( m)( m)( m)(km)(km)三層模型反

18、演結果-6-4-203002468101214161820246g(mGal)(km)(km)電 性 界 面10500模 型 計 算反 演 結 果電 性 -密 度 界 面密 度 界 面( m)( m)( m)2.70(g/cm )32.50(g/cm )32.30(g/cm )3電阻率擬合曲線測 點 號681012141618202224-100105*Log(f)(Hz)模 型 計 算反 演 結 果三層模型相位擬合曲線510152025-100105*Log(f)(Hz)測 點 號模 型 計 算反 演 結 果三層模型目標函數(shù)與迭代次數(shù)關系曲線010203040506051015迭代次數(shù)目標函數(shù)結 論GIS技術可為MT-重力模擬退火聯(lián)合反演建立初始模型。改進的MVFSA算法，計算速度比VFSA算法快20-30%；在同等條件下，MVFSA算法更穩(wěn)健。針對MT曲線與重力場共源與非共源的復雜情況，借鑒GIS中的屬性編碼技術，對電性與密度界面的一致性與否進行編碼，簡潔而有效地處理了兩者的正演計算。無論是重力