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

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