用模擬退火方法解決tsp問題

1、用模擬退火方法解決用模擬退火方法解決TSP問題問題一、退火原理退火是一種物理過程，金屬物體在加熱到一定溫度后，他的分子狀態(tài)在狀態(tài)空間D中自由運(yùn)動(dòng)。隨著溫度的降低，這些分子停留在低能量狀態(tài)的概率逐漸增大，當(dāng)溫度趨進(jìn)于0時(shí)，分子停留在低能量狀態(tài)的概率趨向于1。二、退火原理運(yùn)用于組合優(yōu)化問題組合優(yōu)化問題金屬物體解狀態(tài)最優(yōu)解能量最低狀態(tài)目標(biāo)函數(shù)能量三、模擬退火算法步驟1任選一個(gè)初始解，初始溫度，給定降溫比例系數(shù)，以及一個(gè)紀(jì)it?錄最優(yōu)解的變量和

2、其函數(shù)值best=；bi??步驟2若，則停止計(jì)算，輸出最優(yōu)解best；否則執(zhí)行3；1t?步驟3從的鄰域中隨機(jī)選擇一個(gè)j，；若，則令i()()ijffjfi???0ijf??，執(zhí)行4；否則若時(shí)，，執(zhí)行4；否則執(zhí)行ij?exp()(01)ijftr???ij?3；步驟4若，則，，，執(zhí)行2；否則，()fibest?bii?()bestfi?tt??tt??執(zhí)行2；四、實(shí)驗(yàn)結(jié)果和分析通過五個(gè)城市節(jié)點(diǎn)的TSP問題的求解，其城市間的距離矩陣為：01

3、015621008139158020156132005291550????????????????模擬退火找到的最優(yōu)路徑為，總路程為43；ACBDE????由實(shí)驗(yàn)結(jié)果我們發(fā)現(xiàn)，對(duì)于小規(guī)模的TSP問題，用模擬退火方法找到的解和用禁忌搜索方法找到的解不謀而合，都能夠找到很好的解。用模擬退火方法解決用模擬退火方法解決TSP問題問題一、退火原理退火是一種物理過程，金屬物體在加熱到一定溫度后，他的分子狀態(tài)在狀態(tài)空間D中自由運(yùn)動(dòng)。隨著溫度的降低，這

4、些分子停留在低能量狀態(tài)的概率逐漸增大，當(dāng)溫度趨進(jìn)于0時(shí)，分子停留在低能量狀態(tài)的概率趨向于1。二、退火原理運(yùn)用于組合優(yōu)化問題組合優(yōu)化問題金屬物體解狀態(tài)最優(yōu)解能量最低狀態(tài)目標(biāo)函數(shù)能量三、模擬退火算法步驟1任選一個(gè)初始解，初始溫度，給定降溫比例系數(shù)，以及一個(gè)紀(jì)it?錄最優(yōu)解的變量和其函數(shù)值best=；bi??步驟2若，則停止計(jì)算，輸出最優(yōu)解best；否則執(zhí)行3；1t?步驟3從的鄰域中隨機(jī)選擇一個(gè)j，；若，則令i()()ijffjfi???0i

5、jf??，執(zhí)行4；否則若時(shí)，，執(zhí)行4；否則執(zhí)行ij?exp()(01)ijftr???ij?3；步驟4若，則，，，執(zhí)行2；否則，()fibest?bii?()bestfi?tt??tt??執(zhí)行2；四、實(shí)驗(yàn)結(jié)果和分析通過五個(gè)城市節(jié)點(diǎn)的TSP問題的求解，其城市間的距離矩陣為：01015621008139158020156132005291550????????????????模擬退火找到的最優(yōu)路徑為，總路程為43；ACBDE????由實(shí)驗(yàn)結(jié)