南京郵電大學(xué)通達學(xué)院畢業(yè)設(shè)計（論文）開題報告題目基于模擬退火算法的TSP問題研究與仿真學(xué)生姓名班級學(xué)號專業(yè)對指導(dǎo)教師下達的課題任務(wù)的學(xué)習(xí)與理解本次畢業(yè)設(shè)計主要任務(wù)是以TSP問題為背景，在掌握模擬退火算法的基礎(chǔ)上，完成基于模擬退火算法的TSP問題研究，同時利用matlab軟件對設(shè)計方案進行仿真驗證。對其中相關(guān)細節(jié)要求如下：1.為TSP問題建立數(shù)學(xué)模型；2.學(xué)習(xí)并掌握模擬退火算法，并對改算法進行研究，找出其優(yōu)點及存在問題；3.對該算法進行改進并仿真；4.在Windows 2000/XP平臺上，用Visual C+ 6.0或者matlab仿真。閱讀文獻資料進行調(diào)研的綜述目的：本文的主要研究目標(biāo)就是用改進的模擬退火算法更好地解決TSP這個有意義的NP難問題，在分析了TSP問題的求解現(xiàn)狀及基本模擬退火算法對TSP的求解理論、思路及成果的基礎(chǔ)上，再提出一種改進的模擬退火算法進行求解，并且多組數(shù)據(jù)進行分析與測試，將結(jié)果與傳統(tǒng)的求解方法加以比較，證實其可能性。 旅行商問題 ( TSP , Traveling Salesman Problem ) ：有N個城市，要求從其中某個問題出發(fā)，唯一遍歷所有城市，再回到出發(fā)的城市，求最短的路線。旅行商問題屬于所謂的NP完全問題，精確的解決TSP只能通過窮舉所有的路徑組合，其時間復(fù)雜度是O(N!) 。使用模擬退火算法可以比較快的求出TSP的一條近似最優(yōu)路徑。模擬退火解決TSP的思路：1. 產(chǎn)生一條新的遍歷路徑P(i+1)，計算路徑P(i+1)的長度L( P(i+1) )2. 若L(P(i+1) m，則將(w1,w2,，wk,wk+1,，wm,，wn)變?yōu)椋?wm,wm-1,，w1,wm+1,，wk-1,wn,wn-1,，wk).二模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)， 每個T值的迭代次數(shù)L (2) 對k=1，L做第(3)至第6步： (3) 產(chǎn)生新解S (4) 計算增量t=C(S)-C(S)，其中C(S)為評價函數(shù) (5) 若t0，然后轉(zhuǎn)第2步。三算法對應(yīng)動態(tài)演示：模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。因為目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則:若t0則接受S作為新的當(dāng)前解S，否則以概率exp(-t/T)接受S作為新的當(dāng)前解S。第四步是當(dāng)新解被確定接受時，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。此時，當(dāng)前解實現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗。而當(dāng)新解被判定為舍棄時，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。四模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 解空間：對所有可能解均為可行解的問題定義為可能解的集合，對存在不可行解的問題，或限定解空間為所有可行解的集合，或允許包含不可行解但在目標(biāo)函數(shù)中用罰函數(shù)懲罰以至完全排除不可行解； 目標(biāo)函數(shù)：對優(yōu)化目標(biāo)的量化描述，是解空間到某個數(shù)集的映射。通常表為優(yōu)化目標(biāo)的一個和式，應(yīng)正確體現(xiàn)問題的整體優(yōu)化要求切易計算，當(dāng)解空間包含不可行解時還應(yīng)包含罰函數(shù)項；初始解：是算法迭代的起點，試驗表明，模擬退火算法是健壯的，即最終解的求得不十分依賴初始解的選取，從而可任意選取一個初始解。五模擬退火算法的要素：1.狀態(tài)空間和狀態(tài)產(chǎn)生函數(shù)（鄰域函數(shù)）2.狀態(tài)轉(zhuǎn)移概率（接受概率）3.冷卻進度表T（t）4.初始溫度T（0）5.內(nèi)循環(huán)終止原則6.外循環(huán)終止原則六算法評價 模擬退火算法是一種隨機算法，并不一定能找到全局的最優(yōu)解，可以比較快的找到問題的近似最優(yōu)解。如果參數(shù)設(shè)置得當(dāng)，模擬退火算法搜索效率比窮舉法要高。課題的主要內(nèi)容主要內(nèi)容：TSP 問題是一個NP問題難題，采用傳統(tǒng)的方法很難求出問題的最優(yōu)解。TSP搜索隨著城市數(shù)n的增加而增加，所以的旅程路線組合數(shù)為（n-1）！/2。在如此龐大的搜索空間中尋求最優(yōu)解，對于常規(guī)方法和現(xiàn)有的計算工具而言，存在著諸多困難。借助于模擬退火算法的搜索能力解決TSP問題，是一個很好的想法。根據(jù)問題的規(guī)模，制定用戶的需求計劃，再根據(jù)需要進行源代碼開發(fā)，具體內(nèi)容包括：1.學(xué)習(xí)模擬退火算法原理及其使用，并對改算法進行研究，找出其優(yōu)點及存在問題。2.學(xué)習(xí)C/C+語言。3.接受各自的設(shè)計任務(wù)，開發(fā)相關(guān)源代碼程序。4.總結(jié)畢業(yè)設(shè)計成果，編寫有關(guān)材料。5.準(zhǔn)備畢業(yè)答辯。應(yīng)用模擬退火算法解決TSP問題，通過編程來驗證。在研究過程中了解浮點數(shù)編碼、適應(yīng)度函數(shù)、交叉算子和變異算子及模擬退火算法的三個基本運算（選擇、交叉、變異）等問題。根據(jù)任務(wù)書的任務(wù)及文獻調(diào)研結(jié)果，初步擬定的執(zhí)行（實施）方案（含具體進度計劃）1認(rèn)真學(xué)習(xí)和理解畢業(yè)設(shè)計任務(wù)書的要求，完成開題報告。 第七學(xué)期第14-15周2查閱關(guān)于模擬退火算法的相關(guān)書，掌握其原理及其使用。 第七學(xué)期第16-20周 3. 查找相關(guān)外文資料，完成外文資料翻譯，完成中期報告。 第八學(xué)期第1-3周4熟悉Visual C+ 6.0或matlab仿真軟件，編寫相關(guān)程序，測試。第八學(xué)期第4-9周5按要求認(rèn)真撰寫畢業(yè)報告。 第八學(xué)期第10-12周 6整理資料、準(zhǔn)備答辯。 第八學(xué)期第13-17周主要參考文獻及資料：1 王凌著.智能優(yōu)化算法及其應(yīng)用.北京:清華大學(xué)出版社,20012 黃友銳.智能優(yōu)化算法及其應(yīng)用.北京:國防工業(yè)出版社,20083 汪定偉.智能優(yōu)化方法.北京:高等教育出版社,20074 刁成嘉.面向?qū)ο驝+程序設(shè)計.北京:機械工業(yè)出版社，20045 劉瑞新,曹建春，沈淑娟. Visual C+面向?qū)ο蟪绦蛟O(shè)計程.張連堂機械工業(yè)出版社，20046 陳文宇,張松梅. C+語言教程.電子科技大學(xué)出版社，20047 LIHUA WU and YUYUN WANG.An Introduction to SimulatedAnnealing Algorithms for the Computation of Economic Equilibrium.Institute of Sysyem Science, Academia Sinica, Beijing 100080,P.R china, 19978D S Johnson, C R Aragon, L A McGeoch.C Schevon.Optimizationby simulated annealing:an experimental evaluation, Part1,AT&T bell Laborator