大學(xué)物理學(xué)-計算物理-模擬退火

1、計算物理學(xué)模擬退火概論n模擬退火算法是物理學(xué)當(dāng)中的重要應(yīng)用。n主要應(yīng)用于光學(xué)領(lǐng)域n主要講模擬退火，順帶先講一下“散射光角分散射光角分布布”反演微粒粒徑分布。根據(jù)吸收定律 稱為光學(xué)厚度 ，反應(yīng)了被測顆粒物的消光能力。取值范圍：0-無窮大。稱為消光截面。反應(yīng)了的消光能力?？梢杂蒑ie散射理論計算獲得。rQ, )2()(),(maxmindrrnrQrr ) 1 (expioII rn 真實分布 分50等分離散后n如果分成50分，那么可以這樣處理： 0.1-0.2um的微粒用0.1um近似代替 0.2-0.3um的微粒用0.2um近似代替 。 ) 3(),(1iKiinrQ drrnrQrr)(),

2、(maxmin 那么：變?yōu)榱藗€區(qū)間是一個常量，例如，第近似認(rèn)為，每一個子區(qū)間個分為若干子區(qū)間將半徑區(qū)間,)(,maxmininrnirnKrr變?yōu)榱薾問題轉(zhuǎn)化為了解矩陣：但該矩陣嚴(yán)重病態(tài)，普通方法得到的結(jié)果可能不可靠，需要選一種合適的方法。 KKSSSKKSnnnrQrQrQrQrQrQrQrQrQ2121222121211121, KKSSSKKSnnnrPrPrPrPrPrPrPrPrPFFF2121222121211121, drrnrPFrr)(),(maxmin模擬退火算法n全局隨機(jī)搜索n局部搜索n模擬退火算法 模擬退火算法模擬退火算法(Simulated Annealing Alg

3、orithm, SAA)是一種適合解決大規(guī)模組合優(yōu)化問題，特別是是一種適合解決大規(guī)模組合優(yōu)化問題，特別是NP完全類問題的通用有效近似算法。模擬退火算法完全類問題的通用有效近似算法。模擬退火算法的特點可概括為：高效、穩(wěn)健、通用、靈活。與局部的特點可概括為：高效、穩(wěn)健、通用、靈活。與局部搜索算法相比，模擬退火算法可望在較短時間里求得搜索算法相比，模擬退火算法可望在較短時間里求得更優(yōu)近似解。模擬退火算法與遺傳算法一樣，采用隨更優(yōu)近似解。模擬退火算法與遺傳算法一樣，采用隨機(jī)的初始解為起點，因此大大降低了求解組合優(yōu)化問機(jī)的初始解為起點，因此大大降低了求解組合優(yōu)化問題的前期工作量。模擬退火算法的解和題的前

4、期工作量。模擬退火算法的解和CPU時間均隨時間均隨問題規(guī)模的增大而趨于穩(wěn)定，且不受初始解和隨機(jī)數(shù)問題規(guī)模的增大而趨于穩(wěn)定，且不受初始解和隨機(jī)數(shù)序列的影響，其性能不因問題的不同而蛻變。序列的影響，其性能不因問題的不同而蛻變。模擬退火算法（起源）物理退火原理n物理退火過程物理退火過程 什么是退火：什么是退火： 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。 n物理退火過程物理退火過程 加溫過程加溫過

5、程增強(qiáng)粒子的熱運動，消除系統(tǒng)原先可能增強(qiáng)粒子的熱運動，消除系統(tǒng)原先可能存在的非均勻態(tài)；存在的非均勻態(tài)； 等溫過程等溫過程對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時，系統(tǒng)達(dá)到平衡態(tài)；當(dāng)自由能達(dá)到最小時，系統(tǒng)達(dá)到平衡態(tài)； 冷卻過程冷卻過程使粒子熱運動減弱并漸趨有序，系統(tǒng)能使粒子熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。模擬退火算法起源n物理退火過程：q加溫過程q等溫過程q冷卻（退火）過程n等溫下熱平衡過

6、程可用Monte Carlo方法模擬，計算量大。n1953年，Metropolis提出重要性采樣法，即以概率接受新狀態(tài)，稱Metropolis準(zhǔn)則，計算量相對Monte Carlo方法顯著減少。n1983年，Kirkpatrick等提出模擬退火算法，并將其應(yīng)用于組合優(yōu)化問題的求解。模擬退火算法與物理退火過程的相似關(guān)系模擬退火物理退火解粒子狀態(tài)最優(yōu)解能量最低態(tài)設(shè)定初溫熔解過程Metropolis采樣過程 等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量模擬退火一般過程n1，設(shè)置一個較高溫度T，降溫速度S，終止溫度。n2，給出解的初始值P1，計算該初始值的適應(yīng)度值f1n3，令T=T*S，得到一個新的較低溫度

7、T，此時給P1一個微擾，得到P2，計算出P2所對應(yīng)的適應(yīng)度值f2n4，如果f2優(yōu)于f1，則無條件接收P2為新的解；如果f2f1，則按照。這個概率可以是類似于如下的形式： exp-(1/ T)n重復(fù)3,4步，當(dāng)溫度降到足夠低的時候，有希望獲得全局優(yōu)化解。n注意，要求隨著溫度降低，接收惡化解的概率越來越小，最后趨近于0。n不難看出，實際上所謂模擬退火算法，其實就是在局部搜索的基礎(chǔ)之上加入了一個安一定的概率接收惡化解。n局部搜索一般過程： 1，給出解的初始值P1，計算該初始值的適應(yīng)度值f1 2，給P1一個微擾，得到P2，計算出P2所對應(yīng)的適應(yīng)度值f2 3，如果f2優(yōu)于f1，則無條件接收P2為新的解；如果f2劣于f1，則無條件放棄P2，當(dāng)前解依然是P1。 重復(fù)2,3步。 那么為什么通過一定的概率接收惡化解，可以進(jìn)一步逼近全局最優(yōu)解？很簡單，因為在惡化解所在的那個局部可能存在好的解。n模擬退火的直觀理解：在一定程度上接收惡化解是SA具有全局搜索能力的一個主要原因。n當(dāng)x=？，y最大？n全局隨機(jī)搜索： 隨機(jī)給出若干組解，計算這些解的適應(yīng)度值，取適應(yīng)度最好的那組解。n下面看看，全局隨機(jī)搜索，局部搜索和模擬退火的算法在30個城市的貨郎擔(dān)問題中的應(yīng)用。n貨郎擔(dān)問題： N個城市，走遍所有城