基于模擬退火算法的TSP研究.pdf

《基于模擬退火算法的TSP研究.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、l學(xué)術(shù)探討算藩儕究f2012率第4嬲基于模擬退火算法的TSP研究黃麗韶(湖南科技學(xué)院計(jì)算機(jī)與通信工程系，湖南永州425100)[摘要]多項(xiàng)式復(fù)雜程度的非確定性(NP)問題是一種紐合優(yōu)化問題，模擬退火算法(sA)是其中的一種搜索方法。同其它通用的有效近似算法相比，SA應(yīng)用的范圍較廣，運(yùn)行的效率也較高，還具有描述較簡單、能夠?qū)崿F(xiàn)靈活使用的優(yōu)點(diǎn)。本文首先分析了sA的基本原理，針對TSP問題，我們將sA應(yīng)用到TSP上，并建立了TSP的數(shù)學(xué)模型，闡述了利用模擬退火算法解TSP的方法。最后通過實(shí)驗(yàn)實(shí)現(xiàn)了求解TSP的模擬退火算法。[關(guān)鍵詞]模擬退火；TSP；組合優(yōu)化決此問題的

2、。到了2003年，HisaoTamaki發(fā)現(xiàn)了TSPHB中1．意義和目標(biāo)pla33810的一個(gè)次優(yōu)解，當(dāng)時(shí)使用了Lin—Kemigh~an啟發(fā)和1．1意義路徑融合的變種相結(jié)合的方法。之后，由KeldHelsgaun在TSP(TravelingSalesmanProblem)是優(yōu)化技術(shù)領(lǐng)域中一2004年獲得了plas5900問題的次優(yōu)解。同年12月又獲得了個(gè)具有代表性的問題，它經(jīng)常被用來測試很多新型算法的目前為止已知的求解規(guī)最大的7，516，353，779個(gè)節(jié)點(diǎn)的世性能，是優(yōu)化技術(shù)一種成功的體現(xiàn)。在優(yōu)化算法及其啟發(fā)式界TSP問題中一條比較好的解。搜索中，TSP已經(jīng)

3、成為了一種標(biāo)準(zhǔn)。研究TSP，加深對TSPTSP可能的路徑總數(shù)與城市數(shù)目n是成階乘數(shù)增長算法的理解，對我們繼續(xù)學(xué)習(xí)優(yōu)化理論知識(shí)有很大幫助。的，故一般很難精確地求出其最優(yōu)解。對于這個(gè)問題，不論模擬退火算法是一種高效的全局優(yōu)化方法，其基本思是傳統(tǒng)的動(dòng)態(tài)規(guī)劃、分枝定界法、貪婪法等方法，還是在近想來源于固體的退火過程。目前該算法已經(jīng)在自然科學(xué)、工些年的研究過程中采用的各種智能優(yōu)化算法如：模擬退火、程技術(shù)和管理等諸多領(lǐng)域得到廣泛應(yīng)用。研究模擬退火算遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、蟻群算法等都存在解的質(zhì)量不高法，有助于我們解決更多的應(yīng)用于組合優(yōu)化的問題?；蛘咝枰臅r(shí)空開銷太大等問題圓

4、。1．2目標(biāo)2．2模擬退火算法的研究現(xiàn)狀本文是基于模擬退火算法的TSP的研究，使用模擬退在理論上，受到廣大學(xué)者與專家青睞的模擬退火算法火算法解決TSP。了解TSP和模擬退火算法的國內(nèi)外研究能夠達(dá)到全局極小值，這是已經(jīng)得到證明的。近些年，有兩現(xiàn)狀，實(shí)現(xiàn)模擬退火算法，并使該算法應(yīng)用于TSP中，最終類關(guān)于模擬退火算法的研究。其一，是基于有限狀態(tài)奇異馬求出TSP問題的結(jié)果。爾可夫鏈的有關(guān)理論，給出模擬退火算法的某些關(guān)于理想2．國內(nèi)外研究現(xiàn)狀收斂模型的充分條件或充要條件，這些條件在理論上證明2．1TSP的研究現(xiàn)狀了當(dāng)退火三個(gè)原則f初始溫度足夠高、降溫速度足夠慢、終止求解T

5、SP問題是具有一定難度的，但是，隨著優(yōu)化理論溫度足夠低)滿足時(shí)，模擬退火算法以概率1達(dá)到全局最優(yōu)和技術(shù)的不斷發(fā)展，及其計(jì)算機(jī)技術(shù)的飛速進(jìn)步，人們在解；其二，是針對某些具體問題，給出了模擬退火算法的很TSP問題上面取得了一個(gè)又一個(gè)的突破『l1。多成功應(yīng)用。事實(shí)上，正是由于專家和學(xué)者對該算法的鉆1980年，對于318座城市的TSP問題是～個(gè)難題，但研，才使該算法從經(jīng)典的模擬退火算法走到了今天的多樣是由Padberg、Crowder成功地求解出了最優(yōu)解。1987年，性的模擬退火算法：快速模擬退火算法，使得該算法的速度2392座城市的TSP問題由Rinaldi、Padb

6、erg求解。1992年，和收斂性都得到較大提高；適應(yīng)性的模擬退火算法，使得該城市數(shù)達(dá)到3038座的TSP問題也由美國萊斯大學(xué)的算法具有一定的智能性：現(xiàn)在有學(xué)者提到的遺傳一模擬退CRPC小組成功得到解決，這是用50臺(tái)工作站和一種基于火算法，就是將遺傳算法和模擬退火算法二者的優(yōu)越性結(jié)“切平面”的算法來求解的，當(dāng)年此次成績還被《發(fā)現(xiàn)雜志》合起來；帶有單調(diào)升溫的模擬退火算法[31，使得搜索跳出局評為50大科學(xué)新聞之一。1994年，由Applegate、Chvatal和部最優(yōu)變得相對會(huì)容易。其實(shí)，每種算法都是在應(yīng)用中被提Bixby等人解決了TSP中7397座城市的問題，他

7、們花了出的，它是同應(yīng)用進(jìn)行結(jié)合的，不能分開，這樣，算法才能更3．4年的CPU時(shí)間，利用的是若干臺(tái)SPARC作站組成的機(jī)好地適應(yīng)于應(yīng)用的領(lǐng)域，才能為應(yīng)用服務(wù)。正是因?yàn)槟M退群。1995年，TSP中的13509座城市問題由CRPC研究小組火算法能夠達(dá)到全局極小值，而且是在理論上的，所以，在成功解決，他們當(dāng)時(shí)是拿三臺(tái)DigitalAlphaServer4100s(12實(shí)際意義上，對該算法進(jìn)行研究才更加具有意義，許多的專個(gè)處理器)組成的集群和32臺(tái)Pentinrn．I1個(gè)人計(jì)算機(jī)來解家和學(xué)者都在非常努力地將這個(gè)問題進(jìn)行普遍化一般化，作者簡介：黃麗韶，女，湖南永州人，碩士

8、研究生，助教，研究方向：