基于蟻群算法的TSP問題研究-畢業(yè)論文開題報告

南京航空航天大學金城學院南京航空航天大學金城學院 畢業(yè)設計（論文）開題報告畢業(yè)設計（論文）開題報告 題題目目基于蟻群算法的 TSP 問題研究 系系部部XXXX 系 專專業(yè)業(yè)XXXX 學生姓名學生姓名XXXX學號學號XXXX 指導教師指導教師XXXX職稱職稱講師 畢設地點畢設地點XXXX 年月日 填寫要求 1開題報告只需填寫“文獻綜述”、 “研究或解決的問題和擬 采用的方法”兩部分內(nèi)容，其他信息由系統(tǒng)自動生成，不需要手 工填寫。 2為了與網(wǎng)上任務書兼容及最終打印格式一致，開題報告采 用固定格式，如有不適請調(diào)整內(nèi)容以適應表格大小并保持整體美 觀，切勿輕易改變格式。 3任務書須用 A4 紙，小 4 號字，黑色宋體，行距 1.5 倍。 4使用此開題報告模板填寫完畢，可直接粘接復制相應的內(nèi) 容到畢業(yè)設計網(wǎng)絡系統(tǒng)。 1.結合畢業(yè)設計結合畢業(yè)設計（論文論文）課題任務情況課題任務情況，根據(jù)所查閱的文獻資料根據(jù)所查閱的文獻資料，撰寫撰寫15002000 字左右的文獻綜述字左右的文獻綜述： 1.11.1蟻群算法的發(fā)展和應用蟻群算法的發(fā)展和應用 在計算機自動控制領域中, 控制和優(yōu)化始終是兩個重要問題。使用計算機進行 控制和優(yōu)化本質(zhì)上都表現(xiàn)為對信息的某種處理。隨著問題規(guī)模的日益龐大, 特性上 的非線性及不確定性等使得難以建立精確的“數(shù)學模型” 。人們從生命科學和仿生學 中受到啟發(fā), 提出了許多智能優(yōu)化方法, 為解決復雜優(yōu)化問題(NP- hard 問題) 提 供了新途徑。 蟻群算法(Ant Colony Algorithm, ACA) 是 Dorigo M 等人于 1991 年提出的。 經(jīng)觀察發(fā)現(xiàn), 螞蟻個體之間是通過一種稱之為信息素的物質(zhì)進行信息傳遞的。在運 動過程中, 螞蟻能夠在它所經(jīng)過的路徑上留下該種信息素, 而且能夠感知信息素的 濃度, 并以此指導自己的運動方向 。蟻群的集體行為表現(xiàn)出一種信息正反饋現(xiàn)象: 某一路徑上走過的螞蟻越多, 則后來者選擇該路徑的概率就越大。螞蟻個體之間就 是通過這種信息的交流達到搜索食物的目的。它充分利用了生物蟻群通過個體間簡 單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優(yōu)特征，以及該過程與旅行 商問題求解之間的相似性。同時，該算法還被用于求解二次指派問題以及多維背包 問題等，顯示了其適用于組合優(yōu)化問題求解的優(yōu)越特征。 蟻群算法應用于靜態(tài)組合優(yōu)化問題, 其典型代表有旅行商問題( TSP) 、二次分 配問題(QAP) 、車間調(diào)度問題、車輛路徑問題等。在動態(tài)優(yōu)化問題中的應用主要集 中在通訊網(wǎng)絡方面。這主要是由于網(wǎng)絡優(yōu)化問題的特殊性, 如分布計算, 隨機動態(tài) 性, 以及異步的網(wǎng)絡狀態(tài)更新等。例如將蟻群算法應用于 QOS 組播路由問題上, 就 得到了優(yōu)于模擬退火(SA)和遺傳算法(GA)的效果。蟻群優(yōu)化算法最初用于解決 TSP 問題，經(jīng)過多年的發(fā)展，已經(jīng)陸續(xù)滲透到其他領域中，如圖著色問題、大規(guī)模集成 電路設計、通訊網(wǎng)絡中的路由問題以及負載平衡問題、車輛調(diào)度問題等。蟻群算法 在若干領域獲得成功的應用，其中最成功的是在組合優(yōu)化問題中的應用。 1.21.2蟻群算法求解蟻群算法求解 TSPTSP 問題問題 （1） TSP 問題的描述 TSP 問題的簡單形象描述是:給定 n 個城市,有一個旅行商從某一城市出發(fā),訪問 各城市一次且僅有一次后再回到原出發(fā)城市,要求找出一條最短的巡回路徑。 （2） TSP 問題的理論意義 該問題是作為所有組合優(yōu)化問題的范例而存在的。它已經(jīng)成為并將繼續(xù)成為測 試新算法的標準問題。這是因為，TSP 問題展示了組合優(yōu)化的所有方面。它從概念上 來講非常簡單，但是其求解的難度是很大的。如果針對 TSP 問題提出的某種算法能 夠取得比較好的實算效果，那么對其進行修改，就可以應用于其他類型的組合優(yōu)化 問題并取得良好的效果。 （3） 蟻群算法求解 TSP 的算法流程 步驟 1: nc=0(nc 為迭代步數(shù)或搜索次數(shù)); 每條邊上的 Tj(0)=c(常數(shù)), 并且 Tj=0; 放置 m 個螞蟻到 n 個城市上。 步驟 2: 將各螞蟻的初始出發(fā)點置于當前解集 TABUk(s)中; 對每個螞蟻 k(k=1, ,m), 按概率 Pij(t)移至下一城市 j; 將城市 j 置于 TABUk(s)中。 步驟 3: 經(jīng)過 n 個時刻, 螞蟻 k 可走完所有的城市, 完成一次循環(huán)。計算每個 螞蟻走過的總路徑長度 Lk, 更新找到的最短路徑。 步驟 4: 更新每條邊上的信息量 Tij(t+n) 步驟 5: 對每一條邊置Tij=0; nc=nc+1 步驟 6: 若 nc預定的迭代次數(shù) Ncmax, 則轉(zhuǎn)步驟 2; 否則, 打印出最短路徑, 終止整個程序。 1.31.3蟻群算法優(yōu)缺點蟻群算法優(yōu)缺點 蟻群算法是一種分布式的本質(zhì)并行算法，蟻群算法是一種正反饋算法，蟻群算 法具有較強的魯棒性，易于與其它方法結合。但蟻群算法收斂速度慢、計算時間長， 易于過早陷入局部最優(yōu)，不利于解決連續(xù)問題。 1.41.4蟻群算法的展望蟻群算法的展望 （1） 目前大部分改進的蟻群算法都是針對于特定問題, 普適性不強, 同時蟻 群算法模型也不能直接應用于實際優(yōu)化問題。雖然正反饋機制就是一個很好的普適 性模型, 但還遠遠不夠。因此, 急需設計一種通用的蟻群算法普適性模型。 （2） 現(xiàn)階段的蟻群算法只是模擬了自然螞蟻很少一部分社會性, 例如信息素 機制。仍然有很大的空間去提出更加智能化的蟻群行為。 （3） 蟻群算法目前還帶有明顯的經(jīng)驗性, 很多結果只是建立在實驗的基礎之 上, 需要逐步奠定其理論基礎。 因此，根據(jù) TSP 問題的特點，建立蟻群算法的模型，可以較好的解決此類組合 優(yōu)化問題（NP 問題） 。 參考文獻參考文獻 1 Dorigo MAnt algorithms and atigmergyJFuture Generation Computer System.2000,16（8） ：851-871 2 Dorigo MGambardella LMAnt colony system：a cooperative learning approach to the traveling salesman problemJ IEEE Trans on Evolutionary Computation，1997，1（1） ：5366 3 Dorigo MLuca MThe ant colony algorithm applied to the nuclear reload problemAnnals ofNuclear Energy2009，29（12） ：14551470 4 Dorigo MAnt colony system：optimizationby a colony of cooperating agentsIEEE Trans on Systems, Man，and Cybernetics， Part B，1996， 26（1） ：2941 5 楊海，王洪國，徐衛(wèi)志蟻群算法的應用研究與發(fā)展J科學和技術信息學報， 2007， （28） ：13-14 6 張宗永， 孫靜， 譚家華 蟻群算法的改進及其應用J 上海交通大學學報， 2002， 36（11） ：1564-1567 7 尹曉峰，劉春煌基于 MATLAB 的混合型蟻群算法求解旅行商問題J鐵路計 算機應用，2005，14（9） ：4-7 8 劉志碩，申金升，柴躍廷一種求解車輛路徑問題的混合多蟻群算法J系統(tǒng) 仿真學報，2007，19（15） ：3513-3520 9 董萍基于蟻群算法求解 TSPJ無錫職業(yè)技術學院學報，2008，7（5） ：34-36 10 王果，戴冬基于蟻群算法的 TSP 問題求解J河南機電高等?？茖W校學報， 2008，16（5） ：42-43 2.畢業(yè)設計任務要研究或解決的問題和擬采用的方法：畢業(yè)設計任務要研究或解決的問題和擬采用的方法： （1）畢業(yè)設計任務要研究或解決的問題 研究基于蟻群算法的 TSP 問題，要求 閱讀蟻群算法相關的論文和書籍， 系統(tǒng)地了解蟻群算法相關知識和原理的目的。 掌握旅行商問題的基本原理和常用解決方面。 掌握 MATLAB 軟件平臺的應用和操作，學習蟻群算法模型在不同的 NP 問題中的 模型建立。 通過蟻群算法的仿真和分析，實現(xiàn)蟻群算法解決 TSP。 （2）預期成果： 通過研究和分析各種蟻群算法模型，掌握蟻群算法的基本原理和實現(xiàn)步驟，并在 MATLAB 環(huán)境中進行仿真，分析蟻群算法中各關鍵參數(shù)對算法性能的影響。 針對旅行商問題，掌握經(jīng)典算法的基本思想和解決方法，并應用性能優(yōu)異的蟻群 算法得出旅行商問題的最佳解。 （3）擬采用的研究方法 在蟻群算法解決 TSP 問題中，采用以下研究方法： （1）研究蟻群算法的基本原理，通過仿真結果分析蟻群算法關鍵參數(shù)對算法的 影響。 （2）通過理論分析和仿真實驗，討論蟻群算法的收斂性。 （3）分析旅行商問題的經(jīng)典解決方法，并和蟻群算法解決旅行商問題的結果進 行比較分析。 指導教師意見（對課題的深度、廣度及工作量的意見和對畢業(yè)設計（論文）結