【導(dǎo)讀】師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。盡我所知，除文中特別加。而使用過的材料。對(duì)本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。究所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文。不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。全意識(shí)到本聲明的法律后果由本人承擔(dān)。同意學(xué)校保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)大學(xué)可以將本學(xué)位。印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。涉密論文按學(xué)校規(guī)定處理。

　　

【正文】 的路徑，路經(jīng)的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。選擇出現(xiàn)的頻率最高的 路徑 最短路徑，并且，顯示出最短路徑的值。其中，中間涉及到了一些函數(shù)調(diào)用，一個(gè) C++語(yǔ)言的程序有一個(gè)主函數(shù)和多個(gè)函數(shù)組成。主函數(shù)調(diào)用其他函數(shù)，其他函數(shù) 也可以互相調(diào)用。 C語(yǔ)言的函數(shù)調(diào)用遵循先定義，后調(diào)用的原則。 主體 main函數(shù)程序代碼實(shí)現(xiàn)： int main(int argc, char* argv[]) { char filename[81]。 float firsttemp, secondtemp。 int i。 FILE *pfile。 printf(請(qǐng)輸入旅行城市文件全名： )。 scanf(%s, amp。filename)。 // strcpy(filename, )。 if( (pfile = fopen( filename, r )) == NULL ) { 模 擬退火算法在 TSP問題中的應(yīng)用研究 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 20 printf( 打不開旅行城市文件（ %s） !\n, filename)。 printf(請(qǐng)按任意鍵結(jié)束 !)。 getch()。 return false。 } fscanf(pfile, %d, amp。city_number)。 amount = city_number。 printf(\n)。 for(i=0。 icity_number。 i++) { fscanf(pfile, %s\t%f\t%f, amp。citylist[i], amp。firsttemp, amp。secondtemp)。 citycoordinate[i][0] = firsttemp。 citycoordinate[i][1] = secondtemp。 } fclose(pfile)。 srand( (unsigned)time( NULL ) )。 //設(shè)置種子 int *sequence。 //初始序列 sequence = random()。 for(i=0。i4。i++) { Recperc[i].nvalue=1000。 } printf(序列 \t距離 \n)。 for(i=0。 i10*amount。 i++) { out(stimulation(sequence))。 } 以上代碼是系統(tǒng)程序的主要 main函數(shù)代碼，通過調(diào)用其它編寫的代碼函數(shù)還實(shí)行模擬整個(gè)模擬退火算法的主要內(nèi)容。最后，在 DOS界面中輸出每一次新的鄰域解產(chǎn)生的形式和其在計(jì)算函數(shù)部分算出來的某一個(gè)序列中城市之間的距離總和。 算法的具體編碼實(shí)現(xiàn) 在前面已經(jīng)介紹了大部分關(guān)鍵函數(shù)代碼，以 及得到最優(yōu)解排序，并且統(tǒng)計(jì)最優(yōu)解出現(xiàn)次數(shù)和計(jì)算出最優(yōu)解的出現(xiàn)頻率。所以，接下來將要把程序正確運(yùn)行界面進(jìn)行詳細(xì)的講解。 模 擬退火算法在 TSP問題中的應(yīng)用研究 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 21 建立城市坐標(biāo)文本文件 通過 ，將表中的數(shù)據(jù)記錄在其中并且命名為 。 圖 建立的 同時(shí)，也可以自己編寫具體的城市坐標(biāo)，用來自己分析模擬退火算法求解TSP問題的優(yōu)缺點(diǎn)。 DOS 下界面數(shù)據(jù)輸出以及概率統(tǒng)計(jì)與分析 這節(jié)主要介紹了輸出界面的輸出格式和數(shù)據(jù)的形式。在這里界面的輸出輸入形式主要應(yīng)用的 printf語(yǔ)句和 scanf語(yǔ)句進(jìn)行完成的。 Printf是 C語(yǔ)言和 C++語(yǔ)言提供的按指定格式進(jìn)行標(biāo)準(zhǔn)輸出的函數(shù)。而 scanf是 C語(yǔ)言和 C++語(yǔ)言中提供的按指定格式進(jìn)行標(biāo)準(zhǔn)輸入的函數(shù)。 首先是 printf(請(qǐng)輸入旅行城市文件全名： )。 scanf(%s, amp。filename)。語(yǔ)句的輸入使 DOS界面顯示的圖 , 圖 輸入顯示圖 模 擬退火算法在 TSP問題中的應(yīng)用研究 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 22 DOS界面下顯示出“清輸入旅行城市文件全名” ,這個(gè)也就是要求輸入我們所編寫文本文件 .。然后繼續(xù)輸入命令語(yǔ)句： printf( 打不開旅行城市文件（ %s） !\n, filename)。 printf(請(qǐng)按任意鍵結(jié)束 !)。 printf(序列 \t距離 \n)。 printf(最優(yōu)解排序 \t序列 \t\t\t出現(xiàn)次數(shù) \t出現(xiàn)的概率 \n)。 printf(請(qǐng)按任意鍵結(jié)束 !)。 這些將在 。 在輸入完需要處理的信息數(shù)據(jù)之后， 通過對(duì)新產(chǎn)生的鄰域解進(jìn)行統(tǒng)計(jì)列出序列和距離的數(shù)據(jù)在最后分別計(jì)算出所以有排序的路徑的前 4位數(shù)據(jù)，并且分別統(tǒng)計(jì)對(duì)應(yīng)的序列解得出現(xiàn)次數(shù)和出現(xiàn)概率。 例如圖 圖 統(tǒng)計(jì)概率和最優(yōu)解 程序代碼如下： printf(最優(yōu)解排序 \t序列 \t\t\t出現(xiàn)次數(shù) \t出現(xiàn)的概率 \n)。 for(i=0。i4。i++) { printf(%f\t, Recperc[i].nvalue)。 for(int j=0。 jamount。 j++) { printf(%c, Recperc[i].list[j])。 } float statlist = (float)(10*(float)Recperc[i].nflag/(float)amount)。 printf(\t\t%d\t%\n, Recperc[i].nflag, statlist)。 } printf(請(qǐng)按任意鍵結(jié)束 !)。 getch()。 return true。 } 這段程序代碼是多最優(yōu)解排序，并且統(tǒng)計(jì)最優(yōu)解出現(xiàn)次數(shù)和計(jì)算出最優(yōu)解的出現(xiàn)頻率。 下面這段代碼是用來判斷 從 Xi的鄰域中隨即選擇 Xj，計(jì)算 Xi與 Xi的路徑差，模 擬退火算法在 TSP問題中的應(yīng)用研究 第四章 算法具體設(shè)計(jì)與編碼實(shí)現(xiàn) 23 比較差值。按一定方式將 T降溫，即令 T(t+1)＝ kT(t)， i=i+1，然后檢查退火過程是否結(jié)束，如果不是繼續(xù)交換，如果是的話輸出 Si作為最優(yōu)輸出。 代碼段程序如下： double P(int *i,int *j,double t) //t代表當(dāng)前溫度 ,i,j分別代 表不同的兩個(gè)序列 ,返回對(duì)應(yīng)的轉(zhuǎn)移發(fā)生概率 { double fi = 0,fj = 0。 double result = 0。 fi = evaluate(i)。 fj = evaluate(j)。 if(fj fi) result = 。 else result = exp( (fi fj)/t )。 return result。 } 模擬退火算法在 TSP問題中的應(yīng)用研究 第五章 算法運(yùn)行分析 24 第 五章 算法運(yùn)行分析 第 4 章給出了應(yīng)用開發(fā)的組織結(jié)構(gòu)和各個(gè)功能模塊的具體實(shí)現(xiàn)，這章介紹程序 編碼實(shí)現(xiàn)后的運(yùn)行界面圖示以及結(jié)果分析情況。 運(yùn)行界面圖示 1．成功運(yùn)行程序到 DOS界面下的截圖 運(yùn)行 Visual C++，調(diào)試成功后運(yùn)行程序。然后，跳出 DOS界面顯示如圖 ， 圖 成功在 DOS下運(yùn)行程序界面 成功運(yùn)行了程序代碼， DOS環(huán)境下顯示出所要達(dá)到的目的。 2．輸入要打的文件名 輸入要打開的文件名 。界面如圖 ， 模擬退火算法在 TSP問題中的應(yīng)用研究 第五章 算法運(yùn)行分析 25 圖 輸入文本文件的文件名 3．輸入錯(cuò)誤的文件 在顯示要輸入文件名的地方輸入一個(gè)錯(cuò)誤的文件觀看 系統(tǒng)反應(yīng)，輸入，程序反應(yīng)如圖 ， 圖 輸入一個(gè)錯(cuò)誤的文件名 DOS環(huán)境下界面顯示情況與預(yù)先預(yù)想的一樣沒有出現(xiàn)異常情況。 模擬退火算法在 TSP問題中的應(yīng)用研究 第五章 算法運(yùn)行分析 26 4．輸入正確的文件 與上面相反，輸入正確的文件名觀看系統(tǒng)的反應(yīng)，程序反應(yīng)如圖 ， 圖 輸入 程序運(yùn)行正確的文件后，程序已經(jīng)開始運(yùn)行模擬退火算法進(jìn)行分析解決 TSP問題。圖 。用來判斷并且尋找最優(yōu)解。 經(jīng)過上面的一系列操作后，我 可以繼續(xù)觀察程序運(yùn)行情況，一會(huì)后，程序得出最終結(jié)果，如圖 和平均出現(xiàn)的概率。 模擬退火算法在 TSP問題中的應(yīng)用研究 第五章 算法運(yùn)行分析 27 圖 成功得出最優(yōu)解排序以及概率 運(yùn)行結(jié)果 通過上面的運(yùn)行圖示截圖展示了程序的總體流程，在圖 中可以看出最終程序運(yùn)行得到的最優(yōu)解序列為 ACBJIHGFED，這個(gè)最優(yōu)解一共在程序運(yùn)行中出項(xiàng)了 42 次，通過它計(jì)算出文件 中給出的 10 個(gè)坐標(biāo)點(diǎn)的最短路徑問題，計(jì)算的結(jié)果為 。 畢業(yè)設(shè)計(jì)課題研究到此完成了模擬退火算法求解 TSP 問題基 本系統(tǒng)及其編碼部分和實(shí)現(xiàn)均已演示完畢。因?yàn)橛捎趥€(gè)人知識(shí)水平的有限等原因，程序運(yùn)行界面做的十分粗糙并且簡(jiǎn)陋，整體不太美觀。并且實(shí)現(xiàn)不了解題目，導(dǎo)致花費(fèi)時(shí)間從而未在只做城市節(jié)點(diǎn)圖分布的功能模塊。但是基本功能已經(jīng)實(shí)現(xiàn)，符合實(shí)驗(yàn)要求。但在以后我將繼續(xù)學(xué)習(xí)相關(guān)知識(shí)去豐富自己。 模擬退火算法在 TSP問題中的應(yīng)用研究 第六章 結(jié)束語(yǔ) 28 第六章 結(jié)束語(yǔ) 模擬退火算法是將物理退火過程與組合優(yōu)化相結(jié)合的一種隨機(jī)迭代尋優(yōu)算法， TSP問題 即 旅行商問題是一個(gè)組合優(yōu)化問題 ， 該問題被證明具有 NPC計(jì)算復(fù)雜性 ，因此研究模擬退化算法的基本原理及其在 TSP問題求解中的應(yīng)用 受到高度的關(guān)注 。 本文給出了用模擬退火算法求解旅行商問題的流程，給出了各參數(shù)的如何取值。程序是在 Visual C ++ 的環(huán)境中編寫。該程序基本實(shí)現(xiàn)了該課題的任務(wù)目標(biāo)，研究模擬退化算法的基本原理以及 TSP組合優(yōu)化問題，用一種程序語(yǔ)言實(shí)現(xiàn)基于模擬退火算法的 TSP問題求解方法。并且本文說明了用模擬退火算法能夠較好地求解旅行商問題。因而理論上能夠找到最優(yōu)解，但實(shí)際使用過程中諸多的參數(shù)如起始溫度，溫度下降速率，迭代次數(shù)等都需要人為的測(cè)試和調(diào)整，而這些參數(shù)將直接影響能否搜索到最優(yōu)解，所以模擬退火算法仍然存在一些缺點(diǎn)。 本次 畢業(yè)設(shè)計(jì)也存在一些缺點(diǎn)，如程序運(yùn)行太簡(jiǎn)陋沒有細(xì)致的優(yōu)化運(yùn)行界面，但不夠完善缺少一些輔助圖。但總體上還是達(dá)到了課題的要求。 29 致 謝 參考文獻(xiàn) [1] 王大志，汪定 偉 ， 閆楊 . 一 類 多旅行商 問題 的 計(jì) 算及仿 真 分析 [J]，系 統(tǒng)仿 真學(xué)報(bào) ， 2020 年 20 期 [2] 汪定 偉 等 編 著 . 智能 優(yōu) 化方法 [M]，北京：高等 教 育出版社， 2020 [3] 田景文 ， 高美娟 . 人工神 經(jīng)網(wǎng)絡(luò) 算法 研 究及 應(yīng) 用 [M], 北京：北京理工大 30 學(xué) 出版社， 2020 [4] 雷德明， 嚴(yán) 新平 編 著 . 多目 標(biāo) 智能 優(yōu) 化算法及其 應(yīng) 用 [M]，北京：科 學(xué) 出版社， 2020 [5] 劉 升，王行愚，游 曉 明 .求解 TSP 問題 的文化 蟻 群 優(yōu) 化算法 [J]， 華東 理工大 學(xué)學(xué)報(bào) ， 2020 年 02 期 [6] 張曉 如 。 高 尚 . 求解旅行商 問題 的 蟻 群 遺傳 混合算法 [J]，微 電 子 學(xué)與計(jì)算機(jī)， 2020 年 04 期 [7] 邢文 訓(xùn) 著 . 現(xiàn) 代 優(yōu) 化 計(jì) 算方法 [M],第 2 版，北京： 清華 大 學(xué) 出版社， 2020 [8] 王萬森著 . 人工智能原理及其 應(yīng) 用 [M],第 2 版 ，北京： 電 子工 業(yè) 出版社，2020 [9] 梁 艷 春等著 . 群智能 優(yōu) 化算法理 論與應(yīng) 用 [M]，北京：科 學(xué) 出版社， 2020 [10] Ingber L,Rosen algorithms and fast simulated annealing:A Computer ,16(Ⅱ ):87100 [11] 康立山， 謝 云， 羅 祖 華 ，非 數(shù)值并 行算法 —— 模 擬 退火算法 [M],北京 :科 學(xué) 出版社 ,1997