模擬退火法ppt

1、模擬退火法模擬退火法Simulated Annealing義守大學(xué)工業(yè)工程與管理研究所報(bào)告人：洪永耀簡(jiǎn)介簡(jiǎn)介 模擬退火法（ Simulated Annealing；SA） 最早的想法是由N.Metropolis 等人於1953 年所提出，在當(dāng)時(shí)並沒(méi)有受到重視。 直到1983 年由Kirkpatrick et al. 提出蒙地卡羅模擬（MonteCarlo Simulated）概念的隨機(jī)搜尋技巧，利用此方法來(lái)求解的組合最佳化問(wèn)題時(shí)，才使此演算法受到重視。簡(jiǎn)介簡(jiǎn)介 SA的觀念主要來(lái)自於固體加熱至一定的溫度後，固體間的分子結(jié)構(gòu)會(huì)被打散瓦解變?yōu)橐簯B(tài)結(jié)構(gòu)， 接著再對(duì)其降溫過(guò)程加以控制，當(dāng)完全冷卻能使其分

2、子在液態(tài)結(jié)構(gòu)轉(zhuǎn)變?yōu)楣腆w結(jié)構(gòu)時(shí)，重新排列成我們所預(yù)期的穩(wěn)定狀態(tài)簡(jiǎn)介簡(jiǎn)介 當(dāng)目前狀況是落於區(qū)域的最佳解時(shí)，模擬退火法會(huì)藉由重新加熱的動(dòng)作，透過(guò)隨機(jī)的過(guò)程，以機(jī)率性質(zhì)來(lái)接受一個(gè)暫劣解使其演算法能跳脫目前的區(qū)域最佳解，而有機(jī)會(huì)能達(dá)到另一個(gè)最佳解簡(jiǎn)介簡(jiǎn)介 模擬退火法採(cǎi)用Metropolis的 接受法則（Accepting Rule） 並用退火程序（Annealing Schedule）的參數(shù)演算法的進(jìn)行 而Metroplis 接受法則的概念則在於能使求解時(shí)跳脫陷入?yún)^(qū)域最佳解 而模擬退火法能否成功應(yīng)用在於退火程序的合理選擇簡(jiǎn)介簡(jiǎn)介 假設(shè)在搜尋最佳解的過(guò)程中 若令i 代表在時(shí)間k 的現(xiàn)有解，其成本為C(i)

3、 下一個(gè)搜尋到的解，其成本為C(j) D E = C(j) - C(i)為兩個(gè)解之間的成本差，如圖所示簡(jiǎn)介簡(jiǎn)介 當(dāng)j 的成本大於i 時(shí)，SA 會(huì)根據(jù)一機(jī)率決定是否要接受j來(lái)取代i 成為時(shí)間k+1 的新解 因此當(dāng)搜尋到的新解比現(xiàn)有解之成本大時(shí)，會(huì)有一個(gè)機(jī)率值來(lái)決定是否接受交換。 SA 基本上是以Metrolopis 接受法則為基礎(chǔ)，再配合退火程序，藉由溫度逐漸的降低來(lái)?xiàng)l整是否接受成本較差新解的機(jī)率，當(dāng)溫度越低時(shí)，機(jī)率值也跟著降低SA 的運(yùn)作流程的運(yùn)作流程 包含了四個(gè)基本要素 系統(tǒng)狀態(tài)（Configuration）：即在某一個(gè)溫度下，系統(tǒng)產(chǎn)生的初始解，並當(dāng)作目前的現(xiàn)行解 搜尋法則（Search r

4、ule）：在退火的過(guò)程中，由目前系統(tǒng)狀態(tài)經(jīng)由隨機(jī)擾動(dòng)而產(chǎn)生變化跳至另一種狀態(tài) 一般而言，SA 較常用的有梯度搜尋法（ Gradient Type） 和疊代改善法（ IterativeImprovement）SA 的運(yùn)作流程的運(yùn)作流程 包含了四個(gè)基本要素 成本函數(shù)（Cost Function）：用來(lái)衡量某一系統(tǒng)狀態(tài)下之能量函數(shù) 退火程序（Annealing Process）：退火程序中包含的參數(shù)有初始溫度、降溫機(jī)制、冷卻率和終止溫度 在退火的過(guò)程中，在溫度高的時(shí)候，雖然是較差的目標(biāo)值，但有可能被接受當(dāng)成目前的目標(biāo)值，但隨著溫度慢慢的降低，接受較差目標(biāo)值的機(jī)率逐漸降低SA 的運(yùn)作流程的運(yùn)作流程N(yùn)o

5、退火程序之參數(shù)設(shè)定退火程序之參數(shù)設(shè)定 初始溫度 為了防止落入?yún)^(qū)域極小的陷阱，在模擬退火法中初始溫度的設(shè)定必須使得大部份的轉(zhuǎn)移均可被接受 初始溫度的設(shè)定可以是一個(gè)定值， 如Kirkpatrick等學(xué)者 ( 1983 ) 將初始溫度定為10 Heragu 以及 Alfa ( 1992 ) 將初始溫度定為999 初始溫度亦可由所設(shè)定之移轉(zhuǎn)接受機(jī)率的門(mén)檻值 P 0來(lái)反推求得，如Kouvelis 以及 Chiang( 1992 ) 將初始溫度定為退火程序之參數(shù)設(shè)定退火程序之參數(shù)設(shè)定 終止條件 終止條件最簡(jiǎn)單的設(shè)定方式是指定一個(gè)固定的終止溫度，一般是一個(gè)接近於零較小的數(shù)，或是限制降溫次數(shù)不超過(guò)預(yù)定值 其它

6、方式則為檢查所求得的解是否有所改善，如在1992 年Kouvelis 與 Chiang設(shè)定若經(jīng)過(guò)數(shù)次降溫後所得的解仍未改善或移轉(zhuǎn)接受比率低於一個(gè)定值，則將終止模擬退火法的運(yùn)算。退火程序之參數(shù)設(shè)定退火程序之參數(shù)設(shè)定 降溫時(shí)機(jī) 降溫時(shí)機(jī)乃指馬可夫鏈長(zhǎng)度，亦即在同一溫度下所應(yīng)反覆進(jìn)行Metropolis 演算的次數(shù) 最直接的方式是設(shè)定一個(gè)固定長(zhǎng)度，但此長(zhǎng)度與問(wèn)題規(guī)模有關(guān)，如在1992 年Kouvelis 與Chiang 將其設(shè)定為鄰近解個(gè)數(shù)之比率。 此外亦可設(shè)定降溫時(shí)機(jī)為移轉(zhuǎn)接受次數(shù)已達(dá)一定值，如Heragu 以及 Alfa（1992）所使用的方式便是 但此一方式當(dāng)溫度降至很低時(shí)，移轉(zhuǎn)接受之機(jī)率將會(huì)很小，進(jìn)而導(dǎo)致馬可夫鏈過(guò)長(zhǎng)，因此必須同時(shí)限定馬可夫鏈的長(zhǎng)度，以免造成求解時(shí)間過(guò)長(zhǎng)退火程序之參數(shù)設(shè)定退火程序之參數(shù)設(shè)定 溫度控制參數(shù) 溫度控制參數(shù)是指在演算過(guò)程中，若達(dá)到降溫時(shí)機(jī)時(shí)，由目前溫度減少到次一溫度的下降比率 若溫度控制參數(shù)愈小，則溫度下降的差距愈大，那麼會(huì)造成在次一溫度達(dá)成均衡