模擬退火算法解決TSP問題.doc

《模擬退火算法解決TSP問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、智能優(yōu)化方法課題報(bào)告專業(yè)班級(jí)：電子信息科學(xué)與技術(shù)12-3班課題名稱：模擬退火算法解決TSP問題指導(dǎo)教師：姚睿學(xué)生姓名：蔣文斌學(xué)號(hào)：08123453（課題設(shè)計(jì)時(shí)間：2015年3月28日——2015年4月13日）中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)學(xué)院一、問題描述旅行商問題（TravelingmonituihuolesmanProblem，簡(jiǎn)稱TSP）又名貨郎擔(dān)問題，是威廉·哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼(T.P.Kirkman)于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問題，也是著名的組合優(yōu)化問題。問題是這樣描述的：一名商人要到若干城市

2、去推銷商品，已知城市個(gè)數(shù)和各城市間的路程（或旅費(fèi)），要求找到一條從城市1出發(fā)，經(jīng)過所有城市且每個(gè)城市只能訪問一次，最后回到城市1的路線，使總的路程（或旅費(fèi)）最小。TSP剛提出時(shí)，不少人認(rèn)為這個(gè)問題很簡(jiǎn)單。后來人們才逐步意識(shí)到這個(gè)問題只是表述簡(jiǎn)單，易于為人們所理解，而其計(jì)算復(fù)雜性卻是問題的輸入規(guī)模的指數(shù)函數(shù)，屬于相當(dāng)難解的問題。這個(gè)問題數(shù)學(xué)描述為：假設(shè)有n個(gè)城市，并分別編號(hào)，給定一個(gè)完全無向圖G=（V，E），V={1，2，…，n}，n>1。其每一邊(i,j)E有一非負(fù)整數(shù)耗費(fèi)Ci,j(即上的權(quán)記為Ci,

3、j，i，jV)。并設(shè)G的一條巡回路線是經(jīng)過V中的每個(gè)頂點(diǎn)恰好一次的回路。一條巡回路線的耗費(fèi)是這條路線上所有邊的權(quán)值之和。TSP問題就是要找出G的最小耗費(fèi)回路。人們?cè)诳紤]解決這個(gè)問題時(shí)，一般首先想到的最原始的一種方法就是:列出每一條可供選擇的路線(即對(duì)給定的城市進(jìn)行排列組合)，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個(gè)城市分別為A、B、C和D，各城市之間的耗費(fèi)為己知數(shù)，如圖1-1所示。我們可以通過一個(gè)組合的狀態(tài)空間圖來表示所有的組合，如圖1-2所示。圖1-1頂點(diǎn)帶權(quán)圖圖1-2

4、TSP問題的解空間樹1.模擬退火是什么?首先,讓我們看看模擬退火是如何工作的,以及為什么它是善于解決旅行商問題。模擬退火（SimulatedAnnealing，簡(jiǎn)稱monituihuo）是一種通用概率算法，用來在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解。該算法是源于對(duì)熱力學(xué)中退火過程的模擬，在某一給定初溫下，通過緩慢下降溫度參數(shù)，使算法能夠在多項(xiàng)式時(shí)間內(nèi)給出一個(gè)近似最優(yōu)解。退火與冶金學(xué)上的“退火”相似，而與冶金學(xué)的淬火有很大區(qū)別，前者是溫度緩慢下降，后者是溫度迅速下降。我們將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜

5、尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動(dòng)能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對(duì)命題的合適程度。算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。2.模擬退火的優(yōu)點(diǎn)先來說下爬山算法：爬山算法是一種簡(jiǎn)單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。爬山算法實(shí)現(xiàn)很簡(jiǎn)單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1-3所示：假設(shè)C點(diǎn)為當(dāng)前

6、解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵贏點(diǎn)無論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。圖1-3爬山算法模擬退火其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1-3為例，模擬退火算法在搜索到局部最優(yōu)解A后，會(huì)以一定的概率接受到E的移動(dòng)。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D點(diǎn)

7、，于是就跳出了局部最大值A(chǔ)。3.模擬退火算法描述：若J(Y(i+1))>=J(Y(i))(即移動(dòng)后得到更優(yōu)解)，則總是接受該移動(dòng)。若J(Y(i+1))

8、然指數(shù)，且dE<0。這條公式說白了就是：溫度越高，出現(xiàn)一次能量差為dE的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。又由于dE總是小于0（否則就不叫退火了），因此dE/kT<0，所以P(dE)的函數(shù)取值范圍是(0,1)。隨著溫度T的降低，P(dE)會(huì)逐漸降低。我們將一次向較差解的移動(dòng)看做一次溫度跳變過程，我們以概率P(dE)來接受這樣的移動(dòng)。關(guān)于爬山算法與模擬退火，有一個(gè)有趣的比喻：爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠(yuǎn)處的最高山峰。