模擬退火719課件

1/16/202411導(dǎo)入為了找出地球上最高的山，一群有志氣的兔子們開始想方法。方案一：兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機(jī)落到了地球上的某些地方。他們不知道自己的使命是什么。但是，如果你過幾年就殺死一局部海拔低的兔子，多產(chǎn)的兔子們自己就會找到珠穆朗瑪峰。遺傳算法方案二：兔子們知道一個兔子的力量是渺小的。于是，它們互相轉(zhuǎn)告著，哪里的山已經(jīng)找過，并且找過的每一座山他們都留下一只兔子做記號。這樣，它們制定了下一步去哪里尋找的策略。禁忌搜索法

組合優(yōu)化問題解空間中的每一點都代表一個具有不同目標(biāo)函數(shù)值的解。所謂優(yōu)化，就是在解空間中尋找目標(biāo)函數(shù)最小〔大〕解的過程。假設(shè)把目標(biāo)函數(shù)看成能量函數(shù)，某一控制參數(shù)視為溫度T，解空間當(dāng)作形態(tài)空間，那么尋找基態(tài)的過程也就是求目標(biāo)函數(shù)極小值的優(yōu)化過程。數(shù)學(xué)描述：在某一個特定溫度T下，進(jìn)行了充分的轉(zhuǎn)換之后，材料將到達(dá)熱平衡。這時材料處于狀態(tài)i的概率滿足波爾茲曼分布：其中，x表示材料當(dāng)前狀態(tài)的隨機(jī)變量，S表示狀態(tài)空間集合數(shù)學(xué)描述：其中，|S|表示狀態(tài)空間集合中狀態(tài)的數(shù)量。這就說明，所有狀態(tài)在高溫下具有相同的概率。數(shù)學(xué)描述：而當(dāng)溫度下降時：上式說明當(dāng)溫度降至很低時，材料會以很大概率進(jìn)入最小能量狀態(tài)。數(shù)學(xué)描述：從另外一個角度來看：在同一個溫度T，選定兩個能量E1<E2，有：在同一個溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。>0<1數(shù)學(xué)描述：針對上述現(xiàn)象，Metropolis提出了著名的Metropolis準(zhǔn)那么〔1953〕——以概率接受新狀態(tài)——來模擬這一過程：固體在恒定溫度下到達(dá)熱平衡的過程可以用MonteCarlo方法〔計算機(jī)隨機(jī)模擬方法〕加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，計算量很大。Metropolis準(zhǔn)那么(1953)—以概率接受新狀態(tài)：假設(shè)在溫度T，當(dāng)前狀態(tài)i→新狀態(tài)j假設(shè)Ej<Ei，那么接受j為當(dāng)前狀態(tài)；否那么，假設(shè)概率p=exp[-(Ej-Ei)/KT]大于[0,1)區(qū)間的隨機(jī)數(shù)，那么仍接受狀態(tài)j為當(dāng)前狀態(tài)；假設(shè)不成立，那么保存狀態(tài)i為當(dāng)前狀態(tài)。p=exp[-(Ej-Ei)/KT]：在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。組合優(yōu)化問題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過程Metropolis抽樣過程等溫過程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量狀態(tài)產(chǎn)生函數(shù)：原那么：設(shè)計狀態(tài)產(chǎn)生函數(shù)〔鄰域函數(shù)〕的出發(fā)點應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間。通常，狀態(tài)產(chǎn)生函數(shù)由兩局部組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布方法：在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式〔均勻分布、正態(tài)分布、指數(shù)分布等〕產(chǎn)生溫度更新函數(shù)：溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。常用的算法溫度下降函數(shù)：1)：α越接近1溫度下降越慢，且其大小可以不斷變化；2〕：其中t0為起始溫度，K為算法溫度下降的總次數(shù)。內(nèi)循環(huán)終止準(zhǔn)那么：常用的Metropolis抽樣穩(wěn)定準(zhǔn)那么：〔1〕檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；〔2〕連續(xù)假設(shè)干步的目標(biāo)值變化較?。弧?〕按一定的步數(shù)抽樣。外循環(huán)終止準(zhǔn)那么〔1〕設(shè)置終止溫度的閾值；〔2〕設(shè)置外循環(huán)迭代次數(shù)；〔3〕算法搜索到的最優(yōu)值連續(xù)假設(shè)干步保持不變；〔4〕概率分析方法。巡航問題：敵方100個目標(biāo)的經(jīng)度、緯度如表所示：巡航問題：敵方100個目標(biāo)的經(jīng)度、緯度如表所示：我方有一個基地，經(jīng)度和緯度為〔70,40〕。假設(shè)我方飛機(jī)的速度為1000公里/小時。我方派一架飛機(jī)從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來的