模擬退火算法

1、模擬退火算法模擬退火算法（Simulation Annealing）及其改進(jìn)及其改進(jìn)目錄目錄 搜索算法簡(jiǎn)介搜索算法簡(jiǎn)介模擬退火算法的原理模擬退火算法的原理模擬退火算法的應(yīng)用模擬退火算法的應(yīng)用英文文獻(xiàn)介紹英文文獻(xiàn)介紹參考文獻(xiàn)參考文獻(xiàn)搜索問(wèn)題最小最優(yōu)解的搜索局部最優(yōu)全局最優(yōu)除對(duì)當(dāng)前的位置外，對(duì)環(huán)境無(wú)任何感知。搜索算法 盲目搜索盲目搜索與啟發(fā)式搜索啟發(fā)式搜索 按照預(yù)定的控制策略實(shí)行搜索，在搜索過(guò)程中獲取的中間信息不用來(lái)改進(jìn)控制策略，稱(chēng)之為盲目搜索，反之，稱(chēng)為啟發(fā)式搜索。 盲目搜索 深度優(yōu)先、廣度優(yōu)先、代價(jià)優(yōu)先、向前、向后、雙向等 啟發(fā)式搜索 爬山法、模擬退火算法模擬退火算法、遺傳算法、蟻群算法、粒子

2、蟻群算法等等貪心算法模擬退火算法的 起源物理退火過(guò)程 加溫過(guò)程 等溫過(guò)程 冷卻（退火過(guò)程） 1953年，由Metropolis最早提出模擬退火算法的思想 1983年，由kirkpatrick等將模擬退火的思想成功引入組合優(yōu)化領(lǐng)域。 目前，模擬退火算法已經(jīng)應(yīng)用到各門(mén)學(xué)科中以解決非線(xiàn)性系統(tǒng)的優(yōu)化問(wèn)題。 理論上已證明，模擬退火算法是一個(gè)全局最優(yōu)算法，而且以概率1接近最優(yōu)值。Metropolis接受準(zhǔn)則Metropolis模擬退火算法與物理退火的關(guān)系模擬退火算法模擬退火算法物理退火物理退火解解粒子狀態(tài)粒子狀態(tài)最優(yōu)解最優(yōu)解能量最低態(tài)能量最低態(tài)設(shè)定初溫設(shè)定初溫熔解過(guò)程熔解過(guò)程Metropolis采樣過(guò)程采

3、樣過(guò)程等溫過(guò)程等溫過(guò)程控制參數(shù)控制參數(shù)T下降下降冷卻冷卻目標(biāo)函數(shù)目標(biāo)函數(shù)能量能量模擬退火算法的基本流程流程圖及偽代碼模擬退火算法的關(guān)鍵要素模擬退火算法的關(guān)鍵要素模擬退火算法的改進(jìn)算法本身的改進(jìn)，以提高算法的搜索效率1).設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù),使其根據(jù)搜索過(guò)程的需要表現(xiàn)出狀態(tài)的全空間分散性和局部區(qū)域性；2).設(shè)計(jì)高效的退火策略，改進(jìn)對(duì)溫度的控制方式；3).避免狀態(tài)的迂回搜索；4).采用并行搜索結(jié)構(gòu)；5).選擇合適的初始狀態(tài)與算法終止準(zhǔn)則。增加某些環(huán)節(jié)1).增加升溫或重升溫過(guò)程。在算法進(jìn)程的適當(dāng)時(shí)期，調(diào)整溫度。2).增加記憶功能。存儲(chǔ)算法過(guò)程中的較優(yōu)狀態(tài)，避免最優(yōu)解遺失。3).增加補(bǔ)充搜索過(guò)程。

4、即以最優(yōu)解為初始解在此執(zhí)行退火過(guò)程。4).結(jié)合其他搜索機(jī)制的算法，如遺傳算法，粒子蟻群算法等。5).綜合以上各個(gè)方法的應(yīng)用。算法的實(shí)現(xiàn)和應(yīng)用TSP問(wèn)題求解問(wèn)題求解旅行商問(wèn)題（TSP，Traveling Salesman Problem)：有N個(gè)城市，要求從其中某個(gè)城市出發(fā)，一次走遍所有城市，最終返回出發(fā)的城市，求最短路線(xiàn)。TSP問(wèn)題屬于NP難問(wèn)題，精確解決的方法只能通過(guò)窮舉所有路徑組合。使用模擬退火算法可以比較快的求出TSP的一條近似最優(yōu)路徑。幾個(gè)城市間的最短路線(xiàn)問(wèn)題TSP問(wèn)題解決思路1.選擇一組初始路徑P(i)，并計(jì)算L(P(i).2.產(chǎn)生一條新的遍歷路徑P(i+1)的長(zhǎng)度，計(jì)算路徑P(i+

5、1)的長(zhǎng)度L(p(i+1)；3.若L(P(i+1)L(P(i),則接受P(i+1)為新的路徑，否則以Metropolis準(zhǔn)則接受P(i+1),然后降溫。4.重復(fù)2,3直到滿(mǎn)足退出條件。產(chǎn)生新路徑的方法有如下幾種：1).隨機(jī)選擇2個(gè)節(jié)點(diǎn)，叫喚路徑中的這2點(diǎn)的順序。2).隨機(jī)選擇2個(gè)節(jié)點(diǎn)，將路徑中2個(gè)節(jié)點(diǎn)間的節(jié)點(diǎn)順序逆轉(zhuǎn)；3).隨機(jī)選擇3個(gè)節(jié)點(diǎn)m,n,k,然后將節(jié)點(diǎn)m與n間的節(jié)點(diǎn)移位到節(jié)點(diǎn)k后面。算法運(yùn)行結(jié)果（20個(gè)地點(diǎn)）初始旅行商路線(xiàn)初始旅行商路線(xiàn)最終求得旅行商路線(xiàn)最終求得旅行商路線(xiàn)每次迭代求得的旅行距離其它應(yīng)用工業(yè)方面：再制造車(chē)間布局優(yōu)化問(wèn)題1;系統(tǒng)可靠性4;交通方面：運(yùn)輸網(wǎng)絡(luò)的優(yōu)化2；供應(yīng)鏈

6、優(yōu)化3;材料科學(xué)：自旋玻璃模型優(yōu)化5；圖像帶寬系統(tǒng)最優(yōu)化問(wèn)題6;地球物理：物體重力研究7；大氣輻射方程求解問(wèn)題9;醫(yī)學(xué)方面：放射治療中放束角優(yōu)化問(wèn)題8;其他方面：最優(yōu)解的求解；電解過(guò)程優(yōu)化10；家具下料問(wèn)題；貸款問(wèn)題優(yōu)化方案11.外文文獻(xiàn)講解2 文獻(xiàn)題目：Simulated annealing approach for transportation problem of cross-docking network design 譯名：使用模擬退火方法解決運(yùn)輸問(wèn)題中的直接轉(zhuǎn)運(yùn)網(wǎng)的設(shè)計(jì) 2014年，Uludag 大學(xué)，第二屆世界商業(yè)經(jīng)濟(jì)管理大會(huì) 研究背景：在產(chǎn)品供應(yīng)鏈管理中，運(yùn)輸效率是一個(gè)重要因素

7、，高效的運(yùn)輸既滿(mǎn)足了顧客的需求，也降低了成本。直接轉(zhuǎn)運(yùn)策略降低了儲(chǔ)存成本加速了產(chǎn)品流通，而直接轉(zhuǎn)運(yùn)網(wǎng)的設(shè)計(jì)與優(yōu)化是一個(gè)研究熱點(diǎn)。 研究目的：設(shè)計(jì)二維的直接轉(zhuǎn)運(yùn)網(wǎng)絡(luò)，設(shè)計(jì)卡車(chē)載運(yùn)計(jì)劃與貨物的流通路徑來(lái)實(shí)現(xiàn)最低的運(yùn)輸費(fèi)用。文獻(xiàn)講解問(wèn)題描述 如圖，為一個(gè)二維運(yùn)輸網(wǎng)，由供應(yīng)商，直接轉(zhuǎn)運(yùn)設(shè)施與用戶(hù)組成，本文做出以下相關(guān)假設(shè)，約束條件方便建模。文獻(xiàn)講解算法應(yīng)用 退火算法流程所示如圖 求新解的方法1.改變貨物的順序2.改變進(jìn)入車(chē)的順序3.改變出去車(chē)的順序文獻(xiàn)講解計(jì)算與結(jié)論 通過(guò)設(shè)置不同的參數(shù)（S/C/D/Fmax） 文中設(shè)置了兩個(gè)例子分析：?jiǎn)萎a(chǎn)品，單卡車(chē)模型與多產(chǎn)品多卡車(chē)模型。 SA算法可以在短時(shí)間內(nèi)高效的

8、獲得有效解或最優(yōu)解，優(yōu)化結(jié)果是有效的。參考文獻(xiàn)1 李聰波等, 面向不確定性的再制造車(chē)間設(shè)施動(dòng)態(tài)布局方法. 計(jì)算機(jī)集成制造系統(tǒng), 2015(11): 第2901-2911頁(yè).2 Kkolu, ?. and N. ztrk, Simulated Annealing Approach for Transportation Problem of Cross-docking Network Design. Procedia - Social and Behavioral Sciences, 2014. 109: p. 1180-1184.3 Zaretalab, A., et al., A knowle

9、dge-based archive multi-objective simulated annealing algorithm to optimize seriesparallel system with choice of redundancy strategies. Computers & Industrial Engineering, 2015. 80: p. 33-44.4 Zaretalab, A., et al., A knowledge-based archive multi-objective simulated annealing algorithm to optim

10、ize seriesparallel system with choice of redundancy strategies. Computers & Industrial Engineering, 2015. 80: p. 33-44.5 Yamaguchi, C., Proposal of a checking parameter in the simulated annealing method applied to the spin glass model. Computer Physics Communications, 2016. 199: p. 47-52.6 Torre

11、s-Jimenez, J., et al., A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs. Information Sciences, 2015. 303: p. 33-49.7 Biswas, A., Interpretation of residual gravity anomaly caused by simple shaped bodies using very fast simulated annealing global op

12、timization. Geoscience Frontiers, 2015. 6(6): p. 875-893.8 Dias, J., et al., Simulated annealing applied to IMRT beam angle optimization: A computational study. Physica Medica, 2015. 31(7): p. 747-756.9 Buras-Schnell, R., F. Schnell and A. Buras, GORRAM: Introducing accurate operational-speed radiat