【正文】 但總體上還是達(dá)到了課題的要求。但在以后我將繼續(xù)學(xué)習(xí)相關(guān)知識去豐富自己。4．輸入正確的文件與上面相反，輸入正確的文件名觀看系統(tǒng)的反應(yīng)， 程序運(yùn)行正確的文件后，程序已經(jīng)開始運(yùn)行模擬退火算法進(jìn)行分析解決TSP問題。 if(fj fi) result = 。 return true。i++) { printf(%f\t, Recperc[i].nvalue)。printf(序列\(zhòng)t距離\n)。Printf是C語言和C++語言提供的按指定格式進(jìn)行標(biāo)準(zhǔn)輸出的函數(shù)。 }以上代碼是系統(tǒng)程序的主要main函數(shù)代碼，通過調(diào)用其它編寫的代碼函數(shù)還實(shí)行模擬整個(gè)模擬退火算法的主要內(nèi)容。 //初始序列 sequence = random()。citylist[i], amp。 return false。 FILE *pfile。之后，通過函數(shù)的得出的多個(gè)選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。city_number)。 save[i] = save[0]。i++) { if(save[i] == temp) { signal = 0。 save = new int[amount]。 }while(n == m)。程序代碼實(shí)現(xiàn)該部分功能：double random0_1(void){ //產(chǎn)生隨機(jī)數(shù),范圍在01之間 return (double)rand() / (double)RAND_MAX。語句將不同城市間的距離相加得到總路徑。 for(int counter=0。分別給出這個(gè)10個(gè)點(diǎn)所在坐標(biāo)軸上的坐標(biāo)。 result = i。 i = j。 //降溫次數(shù) int L = 100*amount。 int *j = new int[amount]。1．初始溫度的選取由于模擬退火算法的求解不依賴于初始值，所有可從中隨機(jī)選取一個(gè)初始狀態(tài)。 根據(jù)上述描述。模擬退火算法是解決TSP問題的有效方法之一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地將其應(yīng)用在組合最優(yōu)化問題中。通過C++語言編寫并且實(shí)現(xiàn)出模擬退火算法。模擬退火算法用于優(yōu)化問題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性。下面介紹并且分析模擬退火算法的模型和組合優(yōu)化的問題。因此采用c++語言進(jìn)行編寫程序。并且確定了模擬退火算法在TSP問題中的應(yīng)用研究的主要設(shè)計(jì)思想。也是起源對簡單社會系統(tǒng)的模擬，最初設(shè)想是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。源于對鳥群捕食的行為研究。遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門解決最優(yōu)化問題而設(shè)計(jì)的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時(shí)人工智能的發(fā)展服務(wù)的。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息。反饋型網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)就是它具有穩(wěn)定狀態(tài)。神經(jīng)元的樹突與另外的神經(jīng)元的神經(jīng)末梢相連的部分稱為突觸[8]。.Hopfield等學(xué)者又先后提出了感知模型，使得人工神經(jīng)網(wǎng)絡(luò)技術(shù)得以蓬勃發(fā)展[7]。1．人工神經(jīng)網(wǎng)絡(luò)算法根據(jù)“信息素較濃的路線更近的原則，即可選擇出最佳路線。組合優(yōu)化問題在實(shí)踐中有著廣泛的應(yīng)用，同時(shí)也是計(jì)算機(jī)科學(xué)中的重要研究課題[4]。 組合最優(yōu)化發(fā)展的初期，研究一些比較實(shí)用的基本上屬于網(wǎng)絡(luò)極值方面的問題 ，如廣播網(wǎng)的設(shè)計(jì) 、開關(guān)電路設(shè)計(jì)、航船運(yùn)輸路線的計(jì)劃、工作指派、貨物裝箱方案等。模擬退火算法是局部搜索算法的擴(kuò)展,理論上來說,它是一個(gè)全局最優(yōu)算法。 TSP問題簡述旅行商問題，即TSP問題（Travelling Salesman Problem）是數(shù)學(xué)領(lǐng)域中著名問題之一。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一部先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。由于它具有很強(qiáng)的實(shí)用性和極佳的性能表現(xiàn)，迅速引起了很多專家學(xué)者的興趣，不斷對其進(jìn)行研究。TSP問題是一個(gè)典型的、容易描述但是難以處理的NP完全問題，同時(shí)TSP問題也是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡化形式。如何在多個(gè)目標(biāo)中尋找一個(gè)公平、合理的解是比較復(fù)雜的問題。 TSP問題的基本概念旅行商問題( Traveling Salesman Problem) 是一個(gè)NP 完全問題,目前求解 TSP 問題的主要方法有模擬退火算法、遺傳算法、啟發(fā)式搜索法、Hopfield 神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等，還包括許多算法。作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日目 錄摘 要 IIIABSTRACT IV第一章 前言 1 TSP問題的基本概念 1 模擬退火算法的背景 1 發(fā)展趨勢 1第二章 相關(guān)知識介紹 1 1 模擬退火的基本思想 1 算法對應(yīng)動態(tài)演示步驟 1 TSP問題簡述 1 1 蟻群算法及其它算法原理 1 1 1第三章 問題描述與算法分析研究 1 1 1 1 1 TSP問題的描述和分析 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é)束語 1致 謝 1參考文獻(xiàn) 1摘 要TSP問題是一個(gè)典型的NP 完全問題,模擬退火算法是求解此問題的一種理想方法。作 者 簽 名：　　 　 　　日　 期：　　 　 　　 指導(dǎo)教師簽名：　　 　 　　 日　　期：　　 　 　　 使用授權(quán)說明本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。作者簽名：　　 　 　　 日　 期：　　 　 　　 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。模擬退火算法是將物理退火過程與組合優(yōu)化相結(jié)合在一起的一種隨機(jī)迭代尋優(yōu)算法，TSP問題即旅行商問題是一個(gè)組合優(yōu)化問題，該問題被證明具有NPC計(jì)算復(fù)雜性。TSP(Traveling salesman Problem,旅行商問題)是指給定n個(gè)城市和各城市間的距離,要求確定一條經(jīng)過各個(gè)城市當(dāng)且僅當(dāng)一次的最短路線。 模擬退火算法的背景模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。目前求解TSP問題的主要方法有啟發(fā)式搜索法、模擬退火算法、遺傳算法、Hopfield神經(jīng)網(wǎng)絡(luò)算法、二叉樹描述算法。模擬退火算法主要應(yīng)用在各種優(yōu)化問題上，函數(shù)優(yōu)化是其中非常重要的一個(gè)方面。模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。事實(shí)表明，對大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。如何在初始解附近找出一個(gè)“好的解”是一項(xiàng)關(guān)鍵技術(shù),它直接影響算法的收斂速度。自從擬陣概念進(jìn)入圖論領(lǐng)域之后，對擬陣中的一些理論問題的研究成為組合規(guī)劃研究的新課題，并得到應(yīng)用。 蟻群算法及其它算法原理由于這個(gè)算法利用了正反饋機(jī)制，使得較短的路徑能夠有較大的機(jī)會得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優(yōu)解。 “人工神經(jīng)網(wǎng)絡(luò)”(ARTIFICIAL神經(jīng)系統(tǒng)的基本構(gòu)造是神經(jīng)元(神經(jīng)細(xì)胞)，它是處理人體內(nèi)各部分之間相互信息傳遞的基本單元。2．Hopfield神經(jīng)網(wǎng)絡(luò)，提出了Hopfiel神經(jīng)網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)的時(shí)候，也就是它的能量函數(shù)達(dá)到最小的時(shí)候。它是在70年代初期由美國密執(zhí)根（Michigan）大學(xué)的霍蘭（Holland）教授發(fā)展起來的。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。目前的智能計(jì)算研究水平暫時(shí)還很難使“智能機(jī)器”真正具備人類的常識，但智能計(jì)算將在21世紀(jì)蓬勃發(fā)展。通過對程序的理解和分析，這個(gè)課題項(xiàng)目應(yīng)該分為2個(gè)階段進(jìn)行。本課題開發(fā)語言選用c++語言，可以選用的開發(fā)平臺可以從c++語言平臺中選擇一種出來，本課題選用visual C++。模擬退火算法起源于物理退火。算法的基本思想是從一給定解開始的，從鄰域中隨機(jī)產(chǎn)生另一個(gè)解，接受準(zhǔn)則允許目標(biāo)函數(shù)在有限范圍內(nèi)變壞。在利用編寫出的模擬退火算法模型去解決之前所建立的TSP問題模型。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 YYYYNNNN選擇初始路徑X0確定初始溫度T0當(dāng)前路徑Xi=X0當(dāng)前溫度Ti=T0當(dāng)前路徑Xi=Xj△f=0Exp(△f/Ti)random(0,1)跳出內(nèi)循環(huán)跳出外循環(huán)結(jié) 束當(dāng)前溫度Ti下降從Xi的鄰域中隨機(jī)選擇Xi，計(jì)算Xi與Xj的路程差△f=f(Xj)f(Xi)。2．溫度的下降函數(shù)溫度管理問題也是模擬退火算法難以處理的問題之一。 int *i = new int[amount]。 //每個(gè)溫度的迭代次數(shù),也就是每一個(gè)溫度上的平衡條件 int time = 0。 j = te