【正文】 mp。 return result。以備主函數(shù)調(diào)用文本文件中點(diǎn)的坐標(biāo)軸位置進(jìn)行計(jì)算兩個(gè)點(diǎn)之間的路徑距離建立個(gè)表格， 城市坐標(biāo)表A4044B2414C1722D2276E5194F8765G6852H8436I6625J6126“”。counteramount1。通過(guò)以上兩個(gè)函數(shù)代碼可以達(dá)到我們所希望達(dá)到的要求。}void Neighbour(int *i,int *result) //i代表父序列，result代表子序列。 n++。 for(int j=0。 break。 save[0] = temp。實(shí)現(xiàn)城市坐標(biāo)的數(shù)據(jù)輸入。選擇出現(xiàn)的頻率最高的路徑最短路徑，并且，顯示出最短路徑的值。 printf(請(qǐng)輸入旅行城市文件全名：)。 } fscanf(pfile, %d, amp。firsttemp, amp。 for(i=0。最后，在DOS界面中輸出每一次新的鄰域解產(chǎn)生的形式和其在計(jì)算函數(shù)部分算出來(lái)的某一個(gè)序列中城市之間的距離總和。而scanf是C語(yǔ)言和C++語(yǔ)言中提供的按指定格式進(jìn)行標(biāo)準(zhǔn)輸入的函數(shù)。printf(最優(yōu)解排序\t序列\(zhòng)t\t\t出現(xiàn)次數(shù)\t出現(xiàn)的概率\n)。 for(int j=0。}這段程序代碼是多最優(yōu)解排序，并且統(tǒng)計(jì)最優(yōu)解出現(xiàn)次數(shù)和計(jì)算出最優(yōu)解的出現(xiàn)頻率。 else result = exp( (fi fj)/t )。用來(lái)判斷并且尋找最優(yōu)解。模擬退火算法在TSP問(wèn)題中的應(yīng)用研究 第六章 結(jié)束語(yǔ)第六章 結(jié)束語(yǔ)模擬退火算法是將物理退火過(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)注。致 謝參考文獻(xiàn)[1] 王大志，汪定偉，閆楊. 一類多旅行商問(wèn)題的計(jì)算及仿真分析[J]，系統(tǒng)仿真學(xué)報(bào)，2009年20期[2] 汪定偉等編著. 智能優(yōu)化方法[M]，北京：高等教育出版社，2007[3] 田景文，高美娟. 人工神經(jīng)網(wǎng)絡(luò)算法研究及應(yīng)用[M], 北京：北京理工大學(xué)出版社，2006[4] 雷德明，嚴(yán)新平編著. 多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M]，北京：科學(xué)出版社，2009[5] 劉升，王行愚，[J]，華東理工大學(xué)學(xué)報(bào)， 2009年02期[6] 張曉如。本次畢業(yè)設(shè)計(jì)也存在一些缺點(diǎn)，如程序運(yùn)行太簡(jiǎn)陋沒(méi)有細(xì)致的優(yōu)化運(yùn)行界面，但不夠完善缺少一些輔助圖。但是基本功能已經(jīng)實(shí)現(xiàn)，符合實(shí)驗(yàn)要求。 輸入文本文件的文件名3．輸入錯(cuò)誤的文件在顯示要輸入文件名的地方輸入一個(gè)錯(cuò)誤的文件觀看系統(tǒng)反應(yīng)， 輸入一個(gè)錯(cuò)誤的文件名DOS環(huán)境下界面顯示情況與預(yù)先預(yù)想的一樣沒(méi)有出現(xiàn)異常情況。 fj = evaluate(j)。 getch()。i4。printf(請(qǐng)按任意鍵結(jié)束!)。在這里界面的輸出輸入形式主要應(yīng)用的printf語(yǔ)句和scanf語(yǔ)句進(jìn)行完成的。 i++) { out(stimulation(sequence))。 //設(shè)置種子 int *sequence。 i++) { fscanf(pfile, %s\t%f\t%f, amp。 getch()。 int i。并且一次循環(huán)知道溫度降低，達(dá)到平衡。應(yīng)用pfile = fopen( filename, r )語(yǔ)句來(lái)打開(kāi)文件，并且通過(guò)fscanf(pfile, %d, amp。i++) { if(save[i]==0) { temp = save[i]。iamount。 int *save =NULL。 m = rand() % (amount 1)。并且將交換的結(jié)果儲(chǔ)存在result中。計(jì)算某一個(gè)序列中城市之間的距離總和是通過(guò) for 函數(shù)進(jìn)行循環(huán)相加將值不斷賦給 result 并且通過(guò) result += distance(x[amount1],x[0])。}計(jì)算某一個(gè)序列中城市之間的距離總和double evaluate(int *x)/{ double result = 0。在坐標(biāo)軸上選擇恰當(dāng)?shù)?0個(gè)點(diǎn)，描繪和10個(gè)城市。 }while( fabs(f2 f1) 1e5)。 if ( (random == ) || (random random0_1()) ) { temp = i。 //初始溫度，降溫系數(shù) int k = 0。 double random = 0。因此，溫度參數(shù)的設(shè)定影響到模擬退火算法能否收斂到全局最優(yōu)解。新路徑的產(chǎn)生：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，不妨假設(shè)km，則將原路徑(w1,w2,…,wk,wk+1,…,wm,wm+1,…,wn)變?yōu)樾侣窂剑?w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述變換方法就是將k和m對(duì)應(yīng)的兩個(gè)城市在路徑序列中交換位置,稱為2opt映射。并且這部分包括一些關(guān)鍵代碼。問(wèn)題的目標(biāo)是選擇出路徑路程為所有路徑之中的最小值的路徑。模擬退火算法用于優(yōu)化問(wèn)題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般優(yōu)化問(wèn)題的相似性[11]。目前人們已經(jīng)構(gòu)造出了許多近似求解法，如遺傳法、蟻群算法、模擬退火算法等[10]。面向?qū)ο蟮脑O(shè)計(jì)思想是在原來(lái)結(jié)構(gòu)化程序設(shè)計(jì)方法基礎(chǔ)上的一個(gè)質(zhì)的飛躍，C++完美地體現(xiàn)了面向?qū)ο蟮母鞣N特性。主要對(duì)系統(tǒng)進(jìn)行了整體的分析，明確了系統(tǒng)目標(biāo)，確定了開(kāi)發(fā)環(huán)境，構(gòu)建了基本的框架結(jié)構(gòu)和功能模塊。粒子群優(yōu)化算法(PSO)Computation)，有Eberhart博士和Kennedy博士發(fā)明。Systems》）。Algorithms）是基于生物進(jìn)化理論的原理發(fā)展起來(lái)的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。其狀態(tài)變化可以用差分方程來(lái)表征。神經(jīng)元細(xì)胞體將接受到的所有信號(hào)進(jìn)行簡(jiǎn)單處理(如：加權(quán)求和，即對(duì)所有的輸入信號(hào)都加以考慮且對(duì)每個(gè)信號(hào)的重視程度——體現(xiàn)在權(quán)值上——有所不同)后由軸突輸出。J如人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、模擬退火算法、模擬退火技術(shù)和群集智能技術(shù)等。虛擬的“信息素”也會(huì)揮發(fā)，每只螞蟻每次隨機(jī)選擇要走的路徑，它們傾向于選擇路徑比較短的、信息素比較濃的路徑。正是這些問(wèn)題的代表性和復(fù)雜性激起了人們對(duì)組合優(yōu)化理論與算法的研究興趣。從最廣泛的意義上說(shuō)，組合規(guī)劃與整數(shù)規(guī)劃這兩者的領(lǐng)域是一致的，都是指在有限個(gè)可供選擇的方案的組成集合中，選擇使目標(biāo)函數(shù)達(dá)到極值的最優(yōu)子集。模擬退火算法最早思想由Met ropolis 在20世紀(jì)1953 年提出,1983 年Kirkpat rick 等成功地將退火思想引入組合優(yōu)化領(lǐng)域。 模擬退火算法與初始值無(wú)關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無(wú)關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差?！∧M退火的原理也和金屬退火的原理近似：將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動(dòng)能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對(duì)命題的合適程度。它的思想最早在1953年由Metropolis提出，在1983年被Kirkpatrick等人成功引入組合優(yōu)化領(lǐng)域。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è)解法。目標(biāo)之間往往存在沖突性。因此采用模擬退火算法來(lái)解決TSP旅行問(wèn)題是一種比較理想的方法。涉密論文按學(xué)校規(guī)定處理。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。因此，研究模擬退化算法的基本原理及其在TSP問(wèn)題求解中的應(yīng)用受到高度的關(guān)注。它是一種典型的組合優(yōu)化問(wèn)題,其最優(yōu)解的求解代價(jià)是指數(shù)級(jí)的。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為eΔE/(kT)，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為 Boltzman 常數(shù)。對(duì)于用模擬退火算法對(duì)求解旅行商組合優(yōu)化問(wèn)題做來(lái)了在滿足模擬退火算法全局收斂性的情況下，子排列反序并移位抽樣方式對(duì)求解NP完全問(wèn)題是非常有效的。NP問(wèn)題是一個(gè)比較麻煩的問(wèn)題，其解的規(guī)模隨問(wèn)題規(guī)模的增大而成指數(shù)級(jí)增長(zhǎng)，對(duì)于一般的方法而言，當(dāng)問(wèn)題規(guī)模過(guò)大時(shí)，就失去了可行性。(1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L (2) 對(duì)k=1，……，L做第(3)至第6步： (3) 產(chǎn)生新解S′ (4) 計(jì)算增量Δ t′=C(S′)C(S)，其中C(S)為評(píng)價(jià)函數(shù)。 第三步是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則: 若Δ t′0則接受S′作為新的當(dāng)前解S，否則以概率exp(Δ t′/T)接受S′作為新的當(dāng)前解S。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。TSP問(wèn)題是經(jīng)典的NP Hard組合優(yōu)化問(wèn)題之一,求解該問(wèn)題的啟發(fā)式算法一直是數(shù)學(xué)，計(jì)算機(jī)科學(xué)研究的熱點(diǎn)之一。現(xiàn)在應(yīng)用的主要方面仍是網(wǎng)絡(luò)上的最優(yōu)化問(wèn)題，如最短路問(wèn)題、最大（?。┲螛?shù)問(wèn)題、最優(yōu)邊無(wú)關(guān)集問(wèn)題、最小截集問(wèn)題、推銷員問(wèn)題等[2]。受螞蟻覓食時(shí)的通信機(jī)制的啟發(fā)，90年代Dorigo提出了蟻群優(yōu)化算法(Ant蟻群優(yōu)化算法對(duì)于解決貨郎擔(dān)問(wèn)題并不是目前最好的方法，但首先，它提出了一種解決貨郎擔(dān)問(wèn)題的新思路；其次由于這種算法特有的解決方法，它已經(jīng)被成功用于解決其他組合優(yōu)化問(wèn)題，例如圖的著色(GraphNEURAL據(jù)神經(jīng)生物學(xué)家研究的結(jié)果表明，人的一個(gè)大腦一般有1010～1011個(gè)神經(jīng)元。