【正文】 ，在1983年被Kirkpatrick等人成功引入組合優(yōu)化領(lǐng)域。模擬退火算法在TSP問(wèn)題中的應(yīng)用研究 第二章 相關(guān)知識(shí)介紹第二章 相關(guān)知識(shí)介紹本章主要介紹一些關(guān)于模擬退火算法的原理、TSP問(wèn)題簡(jiǎn)述以及相關(guān)重要算法的原理，并且對(duì)其進(jìn)行了一些細(xì)致的闡述，以便于對(duì)模擬退火算法了解。 很多實(shí)際問(wèn)題，經(jīng)過(guò)簡(jiǎn)化處理后均可轉(zhuǎn)化為TSP問(wèn)題，對(duì)TSP問(wèn)題求解方法的研究具有重要的應(yīng)用價(jià)值。目前求解TSP問(wèn)題的主要方法有啟發(fā)式搜索法、模擬退火算法、遺傳算法、Hopfield神經(jīng)網(wǎng)絡(luò)算法、二叉樹(shù)描述算法。TSP在中國(guó)的研究，同樣的問(wèn)題，在中國(guó)還有另一個(gè)描述方法：一個(gè)郵遞員從郵局出發(fā)，到所轄街道投郵件，最后返回郵局，如果他必須走遍所轄的每條街道至少一次，那么他應(yīng)該如何選擇投遞路線，使所走的路程最短？這個(gè)描述之所以稱為中國(guó)郵遞員問(wèn)題（Chinese Postman Problem CPP）因?yàn)槭俏覈?guó)學(xué)者管梅古教授于1962年提出的這個(gè)問(wèn)題并且給出了一個(gè)解法。 發(fā)展趨勢(shì)TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周游問(wèn)題，即對(duì)于國(guó)際象棋棋盤中的64個(gè)方格，走訪64個(gè)方格一次且僅一次，并且最終返回到起始點(diǎn)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。 模擬退火算法的背景模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。目標(biāo)之間往往存在沖突性。 然而在科學(xué)管理與經(jīng)濟(jì)決策的許多應(yīng)用領(lǐng)域中,現(xiàn)實(shí)世界存在著大量的多目標(biāo)優(yōu)化問(wèn)題。已經(jīng)證明TSP問(wèn)題是一個(gè)NPhard問(wèn)題。TSP(Traveling salesman Problem,旅行商問(wèn)題)是指給定n個(gè)城市和各城市間的距離,要求確定一條經(jīng)過(guò)各個(gè)城市當(dāng)且僅當(dāng)一次的最短路線。因此采用模擬退火算法來(lái)解決TSP旅行問(wèn)題是一種比較理想的方法。幫助理解模擬退化算法的基本原理及其在TSP問(wèn)題求解中的應(yīng)用。本文主要闡述了模擬退火算法的原理和一些與其相關(guān)聯(lián)的知識(shí)結(jié)構(gòu)點(diǎn)。模擬退火算法是將物理退火過(guò)程與組合優(yōu)化相結(jié)合在一起的一種隨機(jī)迭代尋優(yōu)算法，TSP問(wèn)題即旅行商問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題，該問(wèn)題被證明具有NPC計(jì)算復(fù)雜性。涉密論文按學(xué)校規(guī)定處理。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。作者簽名：　　 　 　　 日　 期：　　 　 　　 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。畢業(yè)論文（設(shè)計(jì)）題 目 模擬退火算法在TSP問(wèn)題中的應(yīng)用研究 畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說(shuō)明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過(guò)的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過(guò)的材料。作 者 簽 名：　　 　 　　日　 期：　　 　 　　 指導(dǎo)教師簽名：　　 　 　　 日　　期：　　 　 　　 使用授權(quán)說(shuō)明本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝?、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)校可以公布論文的部分或全部?jī)?nèi)容。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。本人授權(quán)　　 　 　大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日目 錄摘 要 IIIABSTRACT IV第一章 前言 1 TSP問(wèn)題的基本概念 1 模擬退火算法的背景 1 發(fā)展趨勢(shì) 1第二章 相關(guān)知識(shí)介紹 1 1 模擬退火的基本思想 1 算法對(duì)應(yīng)動(dòng)態(tài)演示步驟 1 TSP問(wèn)題簡(jiǎn)述 1 1 蟻群算法及其它算法原理 1 1 1第三章 問(wèn)題描述與算法分析研究 1 1 1 1 1 TSP問(wèn)題的描述和分析 1 1 1 1 1第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 1 1 1 1 1 1 1 1 1 DOS下界面數(shù)據(jù)輸出以及概率統(tǒng)計(jì)與分析 1第五章 算法運(yùn)行分析 1 運(yùn)行界面圖示 1 運(yùn)行結(jié)果 1第六章 結(jié)束語(yǔ) 1致 謝 1參考文獻(xiàn) 1摘 要TSP問(wèn)題是一個(gè)典型的NP 完全問(wèn)題,模擬退火算法是求解此問(wèn)題的一種理想方法。因此，研究模擬退化算法的基本原理及其在TSP問(wèn)題求解中的應(yīng)用受到高度的關(guān)注。通過(guò)對(duì)其算法的原理，以及退火算法在函數(shù)優(yōu)化問(wèn)題上的應(yīng)用，與優(yōu)化組合問(wèn)題的研究來(lái)了解TSP問(wèn)題以及模擬退火算法上解決實(shí)際問(wèn)題上的應(yīng)用與研究。關(guān)鍵詞 模擬退火算法，TSP，組合優(yōu)化，C/C++，遺傳算法ABSTRACTTSP 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，Genetic Algorithm，Combinatorial Optimization， TSP，C/C++31模擬退火算法在TSP問(wèn)題中的應(yīng)用研究 第一章 前言第一章 前言模擬退火算法是將物理退火過(guò)程與組合優(yōu)化相結(jié)合的一種隨機(jī)迭代尋優(yōu)算法，TSP問(wèn)題即旅行商問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題，該問(wèn)題被證明具有NPC計(jì)算復(fù)雜性，因此研究模擬退化算法的基本原理及其在TSP問(wèn)題求解中的應(yīng)用受到高度的關(guān)注。 TSP問(wèn)題的基本概念旅行商問(wèn)題( Traveling Salesman Problem) 是一個(gè)NP 完全問(wèn)題,目前求解 TSP 問(wèn)題的主要方法有模擬退火算法、遺傳算法、啟發(fā)式搜索法、Hopfield 神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等，還包括許多算法。它是一種典型的組合優(yōu)化問(wèn)題,其最優(yōu)解的求解代價(jià)是指數(shù)級(jí)的?；谥悄軆?yōu)化算法求解TSP問(wèn)題,是近年來(lái)剛剛興起的熱門課題。對(duì)于旅行商問(wèn)題(Traveling salesman Problem ,TSP),實(shí)際中經(jīng)常要同時(shí)考慮多個(gè)目標(biāo),如路程最短、時(shí)間最短、費(fèi)用最省、風(fēng)險(xiǎn)最小等多方面的因素。如何在多個(gè)目標(biāo)中尋找一個(gè)公平、合理的解是比較復(fù)雜的問(wèn)題。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡