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