基于蟻群算法的TSP問(wèn)題研究-畢業(yè)論文開(kāi)題報(bào)告

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