【正文】 的概率為eΔE/(kT)，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為 Boltzman 常數(shù)。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子Δ t、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S[1]。TSP由美國RAND公司于1948年引入，該公司的聲譽(yù)以及線形規(guī)劃這一新方法的出現(xiàn)使得TSP成為一個(gè)知名且流行的問題。TSP問題是一個(gè)典型的、容易描述但是難以處理的NP完全問題，同時(shí)TSP問題也是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡(jiǎn)化形式。對(duì)于用模擬退火算法對(duì)求解旅行商組合優(yōu)化問題做來了在滿足模擬退火算法全局收斂性的情況下，子排列反序并移位抽樣方式對(duì)求解NP完全問題是非常有效的。人們?cè)谂ふ掖缶S數(shù)最優(yōu)化算法的同時(shí)，構(gòu)造出了許多近似求解法，如遺傳法、局部搜索算法、蟻群算法等，特別是提出了如模擬退火等用統(tǒng)計(jì)方法近似求解TSP的隨機(jī)算法，為人們求解TSP問題開辟了新的途徑。模擬退火算法是近年來在國內(nèi)外都比較受關(guān)注的算法。由于它具有很強(qiáng)的實(shí)用性和極佳的性能表現(xiàn)，迅速引起了很多專家學(xué)者的興趣，不斷對(duì)其進(jìn)行研究。NP問題是一個(gè)比較麻煩的問題，其解的規(guī)模隨問題規(guī)模的增大而成指數(shù)級(jí)增長(zhǎng)，對(duì)于一般的方法而言，當(dāng)問題規(guī)模過大時(shí)，就失去了可行性。模擬退火算法在解決這類問題上有著優(yōu)異的表現(xiàn)。模擬退火來自冶金學(xué)的專有名詞淬火。算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一部先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L (2) 對(duì)k=1，……，L做第(3)至第6步： (3) 產(chǎn)生新解S′ (4) 計(jì)算增量Δ t′=C(S′)C(S)，其中C(S)為評(píng)價(jià)函數(shù)。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。 算法對(duì)應(yīng)動(dòng)態(tài)演示步驟模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟： 第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。 第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則: 若Δ t′0則接受S′作為新的當(dāng)前解S，否則以概率exp(Δ t′/T)接受S′作為新的當(dāng)前解S。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。 TSP問題簡(jiǎn)述旅行商問題，即TSP問題（Travelling Salesman Problem）是數(shù)學(xué)領(lǐng)域中著名問題之一。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。該問題可以被證明具有NPC計(jì)算復(fù)雜性。旅行商問題TSP( Traveling Salesman Problem) 問題是一個(gè)NP 完全問題,目前求解TSP 問題的主要方法有模擬退火算法、遺傳算法、啟發(fā)式搜索法、Hopfield 神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等,各種算法各有千秋。模擬退火算法是局部搜索算法的擴(kuò)展,理論上來說,它是一個(gè)全局最優(yōu)算法。TSP問題是經(jīng)典的NP Hard組合優(yōu)化問題之一,求解該問題的啟發(fā)式算法一直是數(shù)學(xué)，計(jì)算機(jī)科學(xué)研究的熱點(diǎn)之一。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值，這是一個(gè)NP難問題。又稱組合規(guī)劃。 組合最優(yōu)化發(fā)展的初期，研究一些比較實(shí)用的基本上屬于網(wǎng)絡(luò)極值方面的問題 ，如廣播網(wǎng)的設(shè)計(jì) 、開關(guān)電路設(shè)計(jì)、航船運(yùn)輸路線的計(jì)劃、工作指派、貨物裝箱方案等?，F(xiàn)在應(yīng)用的主要方面仍是網(wǎng)絡(luò)上的最優(yōu)化問題，如最短路問題、最大（?。┲螛鋯栴}、最優(yōu)邊無關(guān)集問題、最小截集問題、推銷員問題等[2]。組合優(yōu)化往往涉及排序、分類、篩選等問題，它是運(yùn)籌學(xué)的一個(gè)重要分支[3]。這些問題描述非常簡(jiǎn)單，并且有很強(qiáng)的工程代表性，但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法需要極長(zhǎng)的運(yùn)行時(shí)間與極大的存儲(chǔ)空間，以致根本不可能在現(xiàn)有計(jì)算機(jī)上實(shí)現(xiàn)，即所謂的“組合爆炸”。組合優(yōu)化問題在實(shí)踐中有著廣泛的應(yīng)用，同時(shí)也是計(jì)算機(jī)科學(xué)中的重要研究課題[4]。受螞蟻覓食時(shí)的通信機(jī)制的啟發(fā)，90年代Dorigo提出了蟻群優(yōu)化算法(AntOptimization，ACO)來解決計(jì)算機(jī)算法學(xué)中經(jīng)典的“貨郎擔(dān)問題”。在解決貨郎擔(dān)問題時(shí)，蟻群優(yōu)化算法設(shè)計(jì)虛擬的“螞蟻”將摸索不同路線，并留下會(huì)隨時(shí)間逐漸消失的虛擬“信息素”。根據(jù)“信息素較濃的路線更近的原則，即可選擇出最佳路線。蟻群優(yōu)化算法對(duì)于解決貨郎擔(dān)問題并不是目前最好的方法，但首先，它提出了一種解決貨郎擔(dān)問題的新思路；其次由于這種算法特有的解決方法，它已經(jīng)被成功用于解決其他組合優(yōu)化問題，例如圖的著色(GraphCommon隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，智能計(jì)算方法的應(yīng)用領(lǐng)域也越來越廣泛，算法的內(nèi)容也越來越多。1．人工神經(jīng)網(wǎng)絡(luò)算法NEURAL早在本世紀(jì)40年代初期，心理學(xué)家McCulloch、數(shù)學(xué)家Pitts就提出了人工神經(jīng)網(wǎng)絡(luò)的第一個(gè)數(shù)學(xué)模型，從此開創(chuàng)了神經(jīng)科學(xué)理論的研究時(shí)代。Rosenblatt、Widrow和J..Hopfield等學(xué)者又先后提出了感知模型，使得人工神經(jīng)網(wǎng)絡(luò)技術(shù)得以蓬勃發(fā)展[7]。據(jù)神經(jīng)生物學(xué)家研究的結(jié)果表明，人的一個(gè)大腦一般有1010～1011個(gè)神經(jīng)元。軸突的功能是將本神經(jīng)元的輸出信號(hào)(興奮)傳遞給別的神經(jīng)元。樹突的功能是接受來自其它神經(jīng)元的興奮。神經(jīng)元的樹突與另外的神經(jīng)元的神經(jīng)末梢相連的部分稱為突觸[8]。他利用非線性動(dòng)力學(xué)系統(tǒng)理論中的能量函數(shù)方法研究反饋人工神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性，并利用此方法建立求解優(yōu)化計(jì)算問題的系統(tǒng)方程式。網(wǎng)絡(luò)中的每一個(gè)神經(jīng)元都將自己的輸出通過連接權(quán)傳送給所有其它神經(jīng)元，同時(shí)又都接收所有其它神經(jīng)元傳遞過來的信息。所以Hopfield神經(jīng)網(wǎng)絡(luò)是一個(gè)反饋型的網(wǎng)絡(luò)。反饋型網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)就是它具有穩(wěn)定狀態(tài)。這里的能量函數(shù)不是物理意義上的能量函數(shù)，而是在表達(dá)形式上與物理意義上的能量概念一致，表征網(wǎng)絡(luò)狀態(tài)的變化趨勢(shì)，并可以依據(jù)Hopfield工作運(yùn)行規(guī)則不斷進(jìn)行狀態(tài)變化，最終能夠達(dá)到的某個(gè)極小值的目標(biāo)函數(shù)。如果把一個(gè)最優(yōu)化問題的目標(biāo)函數(shù)轉(zhuǎn)換成網(wǎng)絡(luò)的能量函數(shù)，把問題的變量對(duì)應(yīng)于網(wǎng)絡(luò)的狀態(tài)，那么Hopfield神經(jīng)網(wǎng)絡(luò)就能夠用于解決優(yōu)化組合問題。遺傳算法（Genetic其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息。1975年霍蘭教授發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性》（《AdaptationNaturalArtificial遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門解決最優(yōu)化問題而設(shè)計(jì)的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時(shí)人工智能的發(fā)展服務(wù)的。近幾年來，遺傳算法主要在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用方面，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注。遺傳算法成功的應(yīng)用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計(jì)、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問題等等。粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(Evolutionary源于對(duì)鳥群捕食的行為研究。系統(tǒng)初始化為一組隨機(jī)解，通過疊代搜尋最優(yōu)值。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初設(shè)想是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。不僅僅只是功能模仿要持有信息機(jī)理一致的觀點(diǎn)。這兩者的結(jié)合將開辟一個(gè)全新的領(lǐng)域，開辟很多新的研究方向。模擬退火算法在TSP問題中的應(yīng)用研究 第三章 問題描述與算法分析研究第三章 問題描述與算法分析研究本章介紹了模擬退火算法解決TSP問題的需求分析階段的內(nèi)容，是本次程序設(shè)計(jì)中的關(guān)鍵環(huán)節(jié)。并且確定了模擬退火算法在TSP問題中的應(yīng)用研究的主要設(shè)計(jì)思想。第一階段是模擬退火算法的描述和實(shí)現(xiàn)；第二階段是在TSP問題中應(yīng)用模擬退火算法解決問題，即模擬退火算法在TSP問題中的具體實(shí)現(xiàn)。接下來為開發(fā)語言和系統(tǒng)運(yùn)行平臺(tái)做下簡(jiǎn)介。C++語言是一種優(yōu)秀的面向?qū)ο蟪绦蛟O(shè)計(jì)語言，它在C語言的基礎(chǔ)上發(fā)展而來C++以其獨(dú)特的語言機(jī)制在計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域中得到了廣泛的應(yīng)用。因此采用c++語言進(jìn)行編寫程序。 TSP問題的描述和分析旅行商問題，即TSP問題（Travelling Salesman Problem）是數(shù)學(xué)領(lǐng)域中著名問題之一。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問題的目的就是選擇出路徑路程為所有路徑之中的最小值的路徑。下面介紹并且分析模擬退火算法的模型和組合優(yōu)化的問題。物理退火過程： （1） 加溫過程 （2） 等溫過程 （3） 冷卻過程模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 (2) 對(duì)k=1，……，L做第(3)至第6步： (3) 產(chǎn)生新解S′ (4) 計(jì)算增量Δt′=C(S′)C(S)，其中C(S)為評(píng)價(jià)函數(shù) (5) 若Δt′0則接受S′作為新的當(dāng)前解，否則以概率exp(Δt′/T)接受S′作為新 的當(dāng)前解 (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。 (7) T逐漸減少，且T0，然后轉(zhuǎn)第2步。模擬退火算法用于優(yōu)化問題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性。它由一控制參數(shù)t決定，其作用類似于物理過程中的溫度T，對(duì)于控制參數(shù)t的每一取值，算法持續(xù)進(jìn)行“產(chǎn)生新解——判斷——接受或舍棄”的迭代過程，對(duì)應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。然后減小控制參數(shù)t的值，重復(fù)執(zhí)行上述迭代過程。根據(jù)該課題要求，研究模擬退化算法的基本原理以及TSP組合優(yōu)化問題，用一種程序語言實(shí)現(xiàn)基于模擬退火算法的TSP問題求解方法。通過C++語言編寫并且實(shí)現(xiàn)出模擬退火算法。模擬退火算法在TSP問題中的應(yīng)用研究 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn)第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn)前面的章節(jié)主要介紹了問題描述與算法分析研究的內(nèi)容，而本章主要是對(duì)該系統(tǒng)的具體實(shí)現(xiàn)進(jìn)行了詳細(xì)設(shè)計(jì)。具體分為基于模擬退火算法求解TSP問題詳細(xì)設(shè)計(jì)和求解TSP問題的算法主體模塊詳細(xì)設(shè)計(jì)。模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題