第八講模擬退火

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

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

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

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

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

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

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

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

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