【正文】 序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。目標(biāo)之間往往存在沖突性。 然而在科學(xué)管理與經(jīng)濟(jì)決策的許多應(yīng)用領(lǐng)域中 ,現(xiàn)實(shí)世界存在著大量的多目標(biāo)優(yōu)化問題。已經(jīng)證明 TSP問題是一個 NPhard問題。 TSP(Traveling salesman Problem,旅行商問題 )是指給定 n個城市和各城市間的距離 ,要求確定一條經(jīng)過各個城市當(dāng)且僅當(dāng)一次的最短路線。 因此采用模擬退火算法來解決 TSP 旅行問題是一種比較理想的方法。幫助理解模擬退化算法的基本原理及其在 TSP 問題求解中的應(yīng)用。 本文主要闡述了模擬退火算法的原理和一些與其相關(guān)聯(lián)的知識結(jié)構(gòu)點(diǎn)。 模擬退火算法是將物理退火過程與組合優(yōu)化相結(jié)合在一起的一種隨機(jī)迭代尋優(yōu)算法， TSP 問題 即 旅行商問題是一個組合優(yōu)化問題 ， 該問題被證明具有 NPC計算復(fù)雜性 。 涉密論文按學(xué)校規(guī)定處理。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國 家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。 作者簽名： 日 期： II 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。對本研究提供過幫助和做出過貢獻(xiàn)的個人或集體，均已在文中作了明確的說明并表示了謝意。 畢業(yè)論文（設(shè)計） 題 目 模擬退火算法在 TSP 問題中的應(yīng)用研究 I 畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人完全意識到本聲明的法律后果由本人承擔(dān)。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 作者簽名： 日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 III 目 錄 摘 要 ............................................................... V ABSTRACT........................................................... VI 第一章 前言 ....................................................... 1 TSP 問題的基本概念 ........................................... 1 模擬退火算法的背景 .......................................... 1 發(fā)展趨勢 .................................................... 2 第二章 相關(guān)知識介紹 ............................................... 3 模擬 退火算法的原理 ........................................... 3 模擬退火的基本思想 .................................... 3 算法對應(yīng)動態(tài)演示步驟 .................................. 4 TSP 問題簡述 ................................................. 4 組合優(yōu)化問題簡述 ............................................. 5 蟻群算法及其它算法原理 ...................................... 6 蟻群優(yōu)化算法 ........................................... 6 其它優(yōu)化算法 ........................................... 6 第三章 問題描述與算法分析研究 ...................................... 9 應(yīng)用研究整體規(guī)劃 ............................................. 9 應(yīng)用開發(fā)環(huán)境 ................................................. 9 開發(fā)語言 ............................................... 9 開發(fā)平臺 ............................................... 9 TSP 問題的描述和分析 ......................................... 9 模擬退火算法的分析 .......................................... 10 模擬退火算法模型 ...................................... 10 模擬退火算法與優(yōu)化問題分析 ............................ 11 應(yīng)用研究方案分析 ............................................ 11 第四章 算法具體設(shè)計與編碼實(shí)現(xiàn) ..................................... 12 基于模擬退火算法求解 TSP 問題詳細(xì)設(shè)計 ........................ 12 求解 TSP 問題的模擬退火算法及流程圖 .................... 12 算法溫度的選擇和變化 .................................. 14 定義坐標(biāo)表的具體參數(shù)與具體實(shí)現(xiàn) ........................ 15 新解的產(chǎn)生方法 ........................................ 17 求解 TSP 問題的算法主體模塊詳細(xì)設(shè)計 .......................... 19 算法的具體編碼實(shí)現(xiàn) .......................................... 20 IV 建立城市坐標(biāo)文本文件 .................................. 21 DOS 下界面數(shù)據(jù)輸出以及概率統(tǒng)計與分析 .................. 21 第五章 算法運(yùn)行分析 ............................................... 24 運(yùn) 行界面圖示 ............................................... 24 運(yùn)行結(jié)果 ................................................... 27 第六章 結(jié)束語 ..................................................... 28 致 謝 .............................................................. 29 參考文獻(xiàn) ........................................................... 29 V 摘 要 TSP 問題是一個典型的 NP 完全問題 ,模擬退火算法是求解此問題的一種理想方法。因此，研究模擬退化算法的基本原理及其在 TSP 問題求解中的應(yīng)用 受到高度的關(guān)注 。通過對其算法的原理，以及退火 算法在函數(shù)優(yōu)化 問題 上的應(yīng)用 ，與優(yōu)化組合問題的研究來了解 TSP 問題以及模擬退火算法 上解決 實(shí)際 問題上的 應(yīng)用 與研究。 關(guān)鍵詞 模擬退火算法， TSP，組合優(yōu)化， C/C++，遺傳算法 VI ABSTRACT TSP problem is a typical NPplete problem, using simulated annealing algorithm to solve this problem is an ideal way. Simulated Annealing Algorithm bines the process of physical annealing and binatorial optimization together ,it is a stochastic iterative optimization algorithm, TSP problem that the traveling salesman problem is a binatorial optimization problem that is shown to have NPC putational plexity. Therefore, studying the basic principles of simulated annealing algorithm and its application in problem solving TSP should have a high degree of attention. This article focuses on the principle of simulated annealing algorithm and some of the knowledge structure what associated with the first point. By studying the principle of their algorithm, simulated annealing algorithm to optimize the application function, and optimization of research to understand the problem and the simulated annealing algorithm for TSP The practical application and research. Help to understand the basic principles of simulated annealing algorithm and its application in solving TSP problems. KEY WORDS: SAA， Geic Algorithm， Combinatorial Optimization， TSP， C/C++ 模擬退火算法在 TSP問題中的應(yīng)用研究 第一章 前言 1 第一章 前言 模擬退火算法是將物理退火過程與組合優(yōu)化相結(jié)合的一種隨機(jī)迭代尋優(yōu)算法， TSP 問題 即 旅行商問題是一個組合優(yōu)化問題 ， 該問題被證明具有 NPC計算復(fù)雜性 ，因此 研究模擬退化算法的基本原理及其在 TSP 問題求解中的應(yīng)用受到高度的關(guān)注 。 TSP 問題的基本概念 旅行商問題