基于模擬退火算法的旅行商問題求解畢業(yè)論文-資料下載頁
2025-06-27 21:05本頁面
【正文】 iterations = iterations + 1。 end end clc fprintf(’\t\t\tIterations = %d\n’,iterations)。 fprintf(’\t\t\tTemperature = %\n’,temperature)。 fprintf(’\t\t\tIn current temperature for %d times\n’,... plete_temperature_iterations)。endprevious_distance輸入?yún)?shù)：inputcities的作用是將n個城市的坐標(biāo)表示兩行和n列，并且傳遞給simulatedannealing作為新的參數(shù)。initial_temperature則是開始模擬退火過程的起始溫度。cooling_rate是模擬退火過程的冷卻速率，冷卻速率應(yīng)該始終低于1。threshold是模擬退火的停止條件，并且它是n個城市的可接受的距離。numberofcitiestoswap指定用于交換城市對數(shù)量的最大值。隨著溫度的降低，用于交換的城市對也減少，最終達(dá)到一對城市。 小結(jié)本章對旅行商問題的模擬退火求解做了分析說明，首先用模擬退火的基本原理對旅行商問題做了理論描述，重點介紹了其解空間、目標(biāo)函數(shù)、新解、以及接收準(zhǔn)則，并且給出了TSP的實現(xiàn)流程圖。之后用MATLAB實現(xiàn)，分析了各個函數(shù)的用途并附有部分源代碼。通過本章，我們用MATLAB實現(xiàn)了基于模擬退火算法的旅行商問題的求解。 3 仿真實例 仿真分析與評價為了驗證用MATLAB實現(xiàn)的模擬退火算法的有效性，選擇29個點作為仿真研究對象，它們在坐標(biāo)平面的坐標(biāo)(Location)如表31所示。表 31 29個城市的坐標(biāo)城市序號12345678910X坐標(biāo)Y坐標(biāo)城市序號11121314151617181920X坐標(biāo) Y坐標(biāo)城市序號212223242526272829X坐標(biāo) Y坐標(biāo) 運行結(jié)果如圖31： 初始溫度為2000，交換城市數(shù)為2，29個城市的TSP運行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9122。 初始溫度為2000，交換城市數(shù)為2，29個城市的TSP運行結(jié)果 如上圖，該優(yōu)化路徑的總路程近似為9703。 初始溫度為2000，交換城市數(shù)為2，29個城市的TSP運行結(jié)果如上圖，該優(yōu)化路徑的總路程近似為9077。圖 31 TSP的模擬退火運行界面 上圖為用模擬退火算法解決TSP的GUI（Graphics User Interface,圖形用戶界面）。這是由29個城市構(gòu)成的一個對稱TSP實例，利用上述算法對該實例進(jìn)行模擬退火求解，設(shè)定初始溫度T0=2000，互換城市數(shù)為2。經(jīng)過20次仿真，得到的最優(yōu)解與已知最優(yōu)解非常接近，所需時間也令人滿意。 結(jié)論 本節(jié)使用MATIAB對求解TSP問題的模擬退火算法程序進(jìn)行了仿真。平均結(jié)果結(jié)果表明，首先該算法能夠找到TSP問題的最優(yōu)解，說明算法的正確性。其次算法對TSP問題的求解時間并不呈指數(shù)增長，說明了算法的有效性?？偨Y(jié)與展望 模擬退火算法是依據(jù)Metropolis準(zhǔn)則接受新解，該準(zhǔn)則除了接受優(yōu)化解外，還在一定的限定范圍內(nèi)接受劣解，這正是模擬退火算法與局部搜索法的本質(zhì)區(qū)別，在避免陷入局部極小值、提高解空間的搜索能力和擴(kuò)大搜索范圍方面具有明顯的優(yōu)越性[8]。本文給出了一種TSP的求解算法，并用MATLAB語言編程實現(xiàn)了算法。算法實驗結(jié)果表明，對大多數(shù)組合優(yōu)化問題而言，模擬退火算法在求最優(yōu)解和求解時間均達(dá)到了滿意的結(jié)果。利用MATLAB語言實現(xiàn)的模擬退火程序，能夠找到系統(tǒng)的最優(yōu)解，仿真結(jié)果證明了該方法的有效性。采用該方法既可使大家熟悉MATLAB語言，又可以加深對模擬退火算法的認(rèn)識和理解，以此來設(shè)計智能系統(tǒng)。旅行商問題一直都是業(yè)界研究的重點，其應(yīng)用范圍廣，在許多領(lǐng)域都有其重要的指導(dǎo)意義。隨著對TSP問題研究的深入，目前已經(jīng)提出了多種TSP問題的變種，如：多目標(biāo)TSP問題、局部重復(fù)路徑的TSP問題、多人TSP問題以及帶時間約束的TSP問題等等。TSP的算法研究領(lǐng)域中，除非有新的解決組合優(yōu)化問題的算法框架出現(xiàn)，各種仿自然的算法結(jié)合局部優(yōu)化的算法思想仍將是研究的重點。針對各種模擬退火算法的優(yōu)劣，如何揚長避短，提高算法的時間效率和尋優(yōu)能力，目前許多學(xué)者致力于各種求解算法的綜合集成的研究，如遺傳模擬退火算法、模擬退火蟻群算法、混合遺傳算法、混合螞蟻算法等等。結(jié)合實際問題設(shè)計適當(dāng)?shù)乃惴▍?shù)和局部優(yōu)化策略以構(gòu)造混合算法將是解決TSP的重要途徑?？陀^地說，目前并不存在一種求解TSP問題的最佳算法，各個算法都有其應(yīng)用的局限性：經(jīng)典算法追求精確解，但是忽略了算法的時空消耗，可行性不高；而現(xiàn)代流行改進(jìn)算法則是追求近似解，降低了算法的時空消耗，但是在求解結(jié)果上往往不能讓人滿意。筆者認(rèn)為今后在TSP的算法研究上應(yīng)該把握3個方面：繼續(xù)改進(jìn)已有TSP算法；采用人工智能的思想，創(chuàng)造新的TSP算法；集合各個算法的優(yōu)點，進(jìn)行混合TSP算法的研究。目前這些相關(guān)方向業(yè)界人士都有所涉及，也都取得了一定成效，相信在不久的將來，TSP問題一定會有更好的解決方案。 致謝首先感謝張明強老師，他在論文選題及研究過程中給予我悉心的指導(dǎo)和幫助，張老師平易近人，做事認(rèn)真負(fù)責(zé)。在此也要感謝這四年里教授我知識的所有老師和輔導(dǎo)員，他們不僅給我傳授了基本的學(xué)習(xí)本領(lǐng)，更重要的是幫助我樹立正確的人生觀、價值觀和優(yōu)良的品德。在我犯錯誤時，輔導(dǎo)員的批評指正。在我遇到專業(yè)問題時，老師們的悉心指導(dǎo)，尤其是在我考研的過程中所有老師給予我的不記報酬的幫助，我將銘記于心。感謝我朝夕相處的兄弟們，讓我感受到家的溫暖，畢業(yè)了我們要為各自的理想去努力開始人生新的篇章。最后，我要感謝我最親愛的父母，是他們讓我在漫長的求學(xué)道路上不感到孤單，讓我在拼搏和奮斗的歷程中不感到疲倦。感謝我的女友，陪我走過了奮斗的每一天。參考文獻(xiàn)[1]苗卉,(TSP)(管控一體化),2007,23(11):241[2]祝崇俊,劉民,[J].,7(11):16[3]陳文蘭,[J].滁州學(xué)院學(xué)報,2006,8(3):16[4]—遺傳算法和數(shù)據(jù)編碼的結(jié)合[M].科學(xué)出版社,2007,12(7):10071008[5]曲曉麗,潘 昊,柳向斌. ,2007,（18）：78[6]吳小菁. ,2008,(5):5556,57.[7]萬軍洲. ,2006,(8):88,8889.[8]曲強，,2003,26(3):197
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1