【正文】 ( Traveling Salesman Problem) 是一個(gè) NP 完全問題 ,目前求解 TSP 問題的主要方法有模擬退火算法、遺傳算法、啟發(fā)式搜索法、 Hopfield 神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等，還包括許多算法。它是一種典型的組合優(yōu)化問題 ,其最優(yōu)解的求解代價(jià)是指數(shù)級的?；?于智能優(yōu)化算法求解 TSP問題 ,是近年來剛剛興起的熱門課題。對于旅行商問題 (Traveling salesman Problem ,TSP),實(shí)際中經(jīng)常要同時(shí)考慮多個(gè)目標(biāo) ,如路程最短、時(shí)間最短、費(fèi)用最省、風(fēng)險(xiǎn)最小等多方面的因素。如何在多個(gè)目標(biāo)中尋找一個(gè)公平、合理的解是比較復(fù)雜的問題。根據(jù)Metropolis 準(zhǔn)則，粒子在溫度 T 時(shí)趨于平衡的概率為 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ù)雜問題的集中概括和簡化形式。 對于用模擬退火算法對求解旅行商組合優(yōu)化問題做來了在滿足模擬退火算法全局收斂性的情況下，子排列反序并移位抽樣方式對求解 NP 完全問題是非常有效的。人們在努力尋找大維數(shù)最優(yōu)化算法的同時(shí)，構(gòu)造出了許多近似求解法，如遺傳法、局部搜索算法、蟻群算法等，特別是提出了如模擬退火等用統(tǒng)計(jì)方法近似求解 TSP 的隨機(jī)算法，為人們求解 TSP 問題開辟了新的途徑 。 模擬退火算法的原理 模擬退火算法是近年來在國內(nèi)外都比較受關(guān)注的算法。由于它具有很強(qiáng)的實(shí)用性和極佳的性能表現(xiàn)，迅速引起了很多專家學(xué)者的興趣，不斷對其進(jìn)行研究。 NP 問題是一個(gè)比較麻煩的問題，其解的規(guī)模隨問題規(guī)模的增大而成指數(shù)級增長，對于一般的方法而言，當(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) 對 k=1， …… ， L 做第 (3)至第 6 步： (3) 產(chǎn)生新解 S′ (4) 計(jì)算增量 Δ t′=C(S′)C(S)，其中 C(S)為評價(jià)函數(shù) 。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。 算法對應(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)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進(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 問題簡述 旅行商 問題，即 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ì)劃、工作指派、貨物裝箱方案等。現(xiàn)在應(yīng)用的主要方面仍是網(wǎng)絡(luò)上的最優(yōu)化問題，如最短路問題、最大（?。┲螛鋯栴}、最優(yōu)邊無關(guān)集問題、最小截集問題、推銷員問題等 [2]。組合優(yōu)化往往涉及排序、分類、篩選等問題，它是運(yùn)籌學(xué)的一個(gè)重要分支 [3]。這些問題描述非常簡單，模擬退火算法在 TSP問題中的應(yīng)用研究 第二章 相關(guān)知識介紹 6 并且有很強(qiáng)的工程代表性，但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法需要極長的運(yùn)行時(shí)間與極大的存儲空間，以致根本不可能在現(xiàn)有計(jì)算機(jī)上實(shí)現(xiàn)，即所謂的 “組合爆炸 ”。 組合優(yōu)化問題在實(shí)踐中有著廣泛的應(yīng)用，同時(shí)也是計(jì)算機(jī)科學(xué)中的重要研究課題 [4]。如果有 n 個(gè)城市，需要對所有 n 個(gè)城市進(jìn)行訪問且 只訪問一次的最短距離 [5]。虛擬的 “信息素 ”也會揮發(fā)，每只螞蟻每次隨機(jī)選擇要走的路徑，它們傾向于選擇路徑比較短的、信息素比較濃的路徑。由于這個(gè)算法利用了正反饋機(jī)制，使得較短的路徑能夠有較大的機(jī)會得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優(yōu)解。 其它優(yōu)化算法 隨著 計(jì)算機(jī) 技術(shù)的飛速發(fā)展，智能計(jì)算方法的應(yīng)用領(lǐng)域也越來越廣泛 ，算法的內(nèi)容也越來越多。 1． 人工神經(jīng)網(wǎng)絡(luò)算法 “人工神經(jīng)網(wǎng)絡(luò) ”(ARTIFICIAL NEURAL NETWORK，簡稱 ANN)是在對人腦組織結(jié)構(gòu)和運(yùn)行機(jī)制的認(rèn)識理解基礎(chǔ)之上模擬其結(jié)構(gòu)和智能行為的一種工程系統(tǒng)。其后， F Rosenblatt、 Widrow 和 J. J .Hopfield 等學(xué)者又先后提出了感知模型，使得人工神經(jīng)網(wǎng)絡(luò)技術(shù)得以蓬勃發(fā)展 [7]。據(jù)神經(jīng)生物學(xué)家研究的結(jié)果表明，人的一個(gè)大腦一般有 1010～ 1011 個(gè)神經(jīng)元。軸突 的功能是將本神經(jīng)元的輸出信號 (興奮 )傳遞給別的神經(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)的變化趨勢，并可以依據(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ù)，把問題的變量對應(yīng)于網(wǎng)絡(luò)的狀態(tài)，那么 Hopfield 神經(jīng)網(wǎng)絡(luò)就能夠用于解決優(yōu)化組合問題。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息。 1975 年霍蘭教授發(fā)表了第一本比較 系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性》模擬退火算法在 TSP問題中的應(yīng)用研究 第二章 相關(guān)知識介紹 8 （《 Adaptation in Natural and Artificial Systems》）。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。在發(fā)展過程中，進(jìn)化策略、進(jìn)化規(guī)劃和遺傳算法之間差異越來越小。 4． 粒子群優(yōu)化算法 粒子群優(yōu)化算法 (PSO)是一種進(jìn)化計(jì)算技術(shù) (Evolutionary Computation)， 有Eberhart 博士和 Kennedy 博士發(fā)明。 PSO 同遺傳算法類似，是一種基于疊代的優(yōu)化工具。但是并沒有遺傳算法用的交叉 (crossover)以及變異(mutation)。 同遺傳算法比較， PSO 的優(yōu)勢在于簡單容易實(shí)現(xiàn)并且沒有許多參數(shù)需要調(diào)整。 粒子群優(yōu)化算法 (PSO) 也是起源對簡單 社會 系統(tǒng)的模擬，最初設(shè)想是模擬鳥群覓食的過程，但后來發(fā)現(xiàn) PSO 是一種很好的優(yōu)化工具。不僅僅只是功能模仿要持有信息機(jī)理一致的觀點(diǎn)。這兩者的結(jié)合將開辟一個(gè)全新的領(lǐng)域，開辟很多新的研究方向。 模擬退火算法在 TSP問題中的應(yīng)用研究 第三章 問題描述與算法分析研究 9 第三章 問題描述與算法分析研究 本章介紹了模擬退火算法解決 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)行平臺做下簡介。 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)域中著名模擬退火算法在 TSP問題中的應(yīng)用研究 第三章 問題描述與算法分析研究 10 問題之一。路 徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。 TSP問題的目的就是選擇出 路徑路程為所有路徑之中的最小值 的路徑。 模擬退火算法的分析 下面介紹并且分析模擬退火算法的模型和組合優(yōu)化 的問題。物理退火過程： （ 1） 加溫過程 （ 2） 等溫過程 （ 3） 冷卻過程 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 模擬退火算法在 TSP問題中的應(yīng)用研究 第三章 問題描述與算法分析研究 11 (2) 對 k=1， …… ， L 做第 (3)至第 6 步： (3) 產(chǎn)生新解 S′ (4) 計(jì)算增量 Δt′=C(S′)C(S)，其中 C(S)為評價(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，對于控制參數(shù) t的每一取值，算法持續(xù)進(jìn)行“產(chǎn)生新解 —— 判斷 —— 接受或舍棄”的迭代過程，對應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。然后減小控制參數(shù) t的值，重復(fù)執(zhí)行上述迭代過程。 應(yīng)用研究方案分析 根據(jù)該課題要求，研究模擬退化算法的基本原理以及 TSP組合優(yōu)化問題，用一種程序語言實(shí)現(xiàn)基于模擬退火算法的 TSP問題求解方法。 通過 C++語言編寫并且實(shí)現(xiàn)出模擬退火算法。 模 擬退火算法在 TSP問題中的應(yīng)用研究 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 12 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 前面的章節(jié)主要介紹了問題描述與算法分析研究的內(nèi)容，而本章主要是對該系統(tǒng)的具體實(shí)現(xiàn)進(jìn)行了詳細(xì)設(shè)計(jì)。具體分為基于模擬退火算法求解 TSP問題詳細(xì)設(shè)計(jì)和求解 TSP問題的算法主體模塊詳細(xì)設(shè)計(jì)。 模擬退火算法的應(yīng)用很廣泛 ， 可以求解 NP 完全問題 ， 但其參數(shù)難以控制 ，其主要問題有以下三點(diǎn)溫度 T 的初始值設(shè)置問題 ， 退火速度問題 ， 溫度管理問題 。 求解 TSP 問題的模擬退火算法及流程圖 模擬退火算法是解決 TSP問題的有效方法之一，其最初的思想由 Metropolis在 1953年提出， Kirkpatrick在 1983年成功地將其應(yīng)用在組合最優(yōu)化問題中。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E模 擬為目標(biāo)函數(shù)值 f，溫度 T演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i和控制參數(shù)初值 t開始，對當(dāng)前解重復(fù) “產(chǎn)生新解 → 計(jì)算目標(biāo)函數(shù)差 → 接受或舍棄 ”的迭代，并逐步衰減 t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。初始解