第八講 模擬退火

1、 ikiikikkikiPTPETECTPiTEinS )( exp , 高能量較小的狀態(tài)概率要?jiǎng)t有如下關(guān)系：的概率為：這時(shí)處于狀態(tài)平衡，下，經(jīng)一段時(shí)間達(dá)到熱在溫度的能量為，狀態(tài)有限個(gè)，離散的個(gè)狀態(tài)中有設(shè)熱力學(xué)系統(tǒng)iknikiikkikikkiinikikikiEETTPETETEiTPTTPETETETP , 1 expexp11下的平均能量：最小的那一個(gè)代表可見：kTkiTPkT0kiTEnTPki1kiTPkiTP0kTkiTEiEjEkjTPiEjEkT367. 0406. 0367. 0406. 010010010090kkkkkjkiCCueCeCTPTP200001072.310

2、194.84440kkkjkiCCTPTPkinikiTPTP1kT0kT 內(nèi)循環(huán)熱平衡的達(dá)到外循環(huán)算法的特點(diǎn)冷卻控制搜索：隨機(jī)的鄰域移動(dòng)移動(dòng)同要素：狀態(tài)表達(dá)和鄰域代表狀態(tài)是離散有限狀態(tài)空間， , , minSATSiSSiifSi0TfT0, 0TTkk 的鄰域表示iiNiNj, ifjff0T0kiTE kTnjiTfUk , exp , 1 , 0 則令若 , 0jif令kTkT1 kkfkTT kTkT111. 0.950.992. kkkkTTrrTTT較好的方法其中。優(yōu)點(diǎn)：簡(jiǎn)單易行很美麗的表達(dá)方式0,0TTkkSikTn0n ifjff iNj 1 nn1 kkkT0 f1 , 0

3、 expUTfk ji kTnn fkTT T=Th求得初始解求得初始解BS=初始解初始解n=0求得新的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否BS初始解初始解溫度溫度T2000 n=0新的解新的解T=Th求得初始

4、解求得初始解BS=初始解初始解n=0求得新的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否當(dāng)前解當(dāng)前解新的解新的解Exp(新的解當(dāng)前解新的解當(dāng)前解)/T)=exp(-2/2000)Random0,1=0.7T=Th求得初

5、始解求得初始解BS=初始解初始解n=0求得新的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否BS當(dāng)前解當(dāng)前解溫度溫度T2000 n=1T=Th求得初始解求得初始解BS=初始解初始解n=0求得新的解求得新的解新的解比新的解

6、比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否當(dāng)前解當(dāng)前解新的解新的解Exp(新的解當(dāng)前解新的解當(dāng)前解)/T)=exp(-5/2000)Random0,1=0.99，拒絕新的解，拒絕新的解T=Th求得初始解求得初始解BS=初始解初始解n=0求得新

7、的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否當(dāng)前解當(dāng)前解新的解新的解Exp(新的解當(dāng)前解新的解當(dāng)前解)/T)=exp(-1/2000)Random0,1=0.6T=Th求得初始解求得初始解BS=初始解初始解n=0求得

8、新的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否BS當(dāng)前解當(dāng)前解溫度溫度T1200 n=2T=Th求得初始解求得初始解BS=初始解初始解n=0求得新的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解

9、用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS好？好？T=rTT=t?EndStartT: 溫度溫度Th:最高溫度最高溫度t: 最低溫度最低溫度BS：已經(jīng)找到的：已經(jīng)找到的最好解最好解N:某一溫度下達(dá)某一溫度下達(dá)到平衡的搜索次到平衡的搜索次數(shù)數(shù)是是否否是是否否是是否否是是否否是是否否當(dāng)前解當(dāng)前解新的解新的解接受新的解接受新的解溫度溫度T1200 n=0T=Th求得初始解求得初始解BS=初始解初始解n=0求得新的解求得新的解新的解比新的解比當(dāng)前解好？當(dāng)前解好？接受新的解接受新的解用新的解替換用新的解替換當(dāng)前解當(dāng)前解; n=n+1exp01Trandom，nN？BS=新的解新的解新的解比新的解比BS