資源描述:
《改進(jìn)的混合型蟻群算法及其應(yīng)用碩士學(xué)位論文》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、分類(lèi)號(hào):O157單位代碼:10110學(xué)號(hào):s20110075中北大學(xué)碩士學(xué)位論文改進(jìn)的混合型蟻群算法及其應(yīng)用xxx華北改進(jìn)的混合型蟻群算法及其應(yīng)用碩士研究生孫晶指導(dǎo)教師xxx教授學(xué)科專(zhuān)業(yè)應(yīng)用數(shù)學(xué)年月日?qǐng)D書(shū)分類(lèi)號(hào)O157密級(jí)非密UDC510碩士學(xué)位論文改進(jìn)的混合型蟻群算法及其應(yīng)用孫晶指導(dǎo)教師(姓名、職稱(chēng))xxx教授申請(qǐng)學(xué)位級(jí)別理學(xué)碩士專(zhuān)業(yè)名稱(chēng)應(yīng)用數(shù)學(xué)論文提交日期年月日論文答辯日期年月日學(xué)位授予日期年月日論文評(píng)閱人答辯委員會(huì)主席年月日xxx學(xué)位論文摘要旅行商問(wèn)題(TSP)與車(chē)輛路徑問(wèn)題(VRP)自提出以來(lái),許多學(xué)者進(jìn)行了大量的理論研究和實(shí)驗(yàn)分析,取得了非常顯著的進(jìn)展
2、,已經(jīng)成為了運(yùn)籌學(xué)和組合優(yōu)化問(wèn)題領(lǐng)域的熱點(diǎn)研究問(wèn)題。求解他們的算法主要有精確型算法、近似算法和啟發(fā)式算法。在眾多求解TSP算法中,蟻群算法具有較好的性能,該仿生智能算法和傳統(tǒng)的算法截然不同,具有魯棒性、正反饋、并行性和易與其他方法相結(jié)合等特點(diǎn)。自創(chuàng)立以來(lái),無(wú)論理論研究還是在應(yīng)用方面都取得了突破性的進(jìn)展,不但在求解以上兩種問(wèn)題上得到了最優(yōu)解,而且在工件的排序問(wèn)題、圖著色問(wèn)題、多目標(biāo)函數(shù)等許多領(lǐng)域也取得了相當(dāng)不錯(cuò)的效果,具有相當(dāng)廣闊的發(fā)展前景。本文首先介紹了一種求解TSP問(wèn)題的算法—改進(jìn)的混合型蟻群算法,該算法在近鄰法構(gòu)造初始解的基礎(chǔ)上,使用2-opt局部搜索法對(duì)當(dāng)
3、前解進(jìn)行改進(jìn),在更新全局信息素時(shí)采用基于排序的螞蟻系統(tǒng)對(duì)排在前2名的螞蟻更新全局信息素,且為全局信息素設(shè)置最大值和最小值,并使用MATLAB仿真求解了kroa200等13個(gè)經(jīng)典TSP問(wèn)題。通過(guò)仿真實(shí)驗(yàn)可以看出本文改進(jìn)的算法在求解TSP問(wèn)題時(shí)具有很好的效果,在求解很多問(wèn)題時(shí)已經(jīng)非常接近最優(yōu)解或者優(yōu)于最優(yōu)解,和最優(yōu)解相差的百分比基本都在1%以下,并和兩種最新改進(jìn)的蟻群算法以及兩種自組織算法進(jìn)行比較,比較結(jié)果充分證明了該改進(jìn)算法的有效性。其次,本文利用文獻(xiàn)提出的統(tǒng)計(jì)邊數(shù)的方法對(duì)TSP問(wèn)題的種群多樣性進(jìn)行了分析,通過(guò)實(shí)驗(yàn)仿真與基本蟻群算法從平均的邊數(shù)和、最大的邊數(shù)以及最
4、小邊數(shù)和進(jìn)行了比較分析,從數(shù)據(jù)上說(shuō)明了改進(jìn)的算法具有種群多樣性。最后又把改進(jìn)的混合型蟻群算法應(yīng)用到VRP問(wèn)題,使用MATLAB仿真工具對(duì)N44K6等10個(gè)經(jīng)典VRP問(wèn)題進(jìn)行了求解,得到的結(jié)果和已知最優(yōu)解的誤差很小,都在6%以下,并且N33K6問(wèn)題得到了和已知最優(yōu)解相同的解。并且與基本蟻群算法做了比較,比較結(jié)果充分證明了該改進(jìn)算法的有效性。關(guān)鍵詞:混合型蟻群算法,TSP問(wèn)題,種群多樣性,VRP問(wèn)題xxx學(xué)位論文AbstractManyscholarshavebeenalotoftheoreticalresearchandexperimentalanalysissi
5、nceTravelingSalesmanProblem(TSP)andVehicleRoutingProblem(VRP)areproposedandnotableprogressismade.TSPandVRPhavebecomethecentralissueinoperationalresearchandcombinatorialoptimization.Precisealgorithm,approximatealgorithmandheuristicalgorithmareusedtosolvetheproblems.Amongallthealgorith
6、ms,antcolonyalgorithmhasbetterperformance.Thisbionicintelligencealgorithmisquitedifferentfromthetraditionalones,it’smorerobust,positivefeedback,concurrencyandeasytocombinewithotheralgorithms.Sinceantcolonyalgorithmisproposed,breakthroughprogresshasbeenmadebothintheoreticalresearchand
7、realisticapplication.Notonlyoptimalresultsareachievedbutalsoproventobeeffectiveinschedulingjobs,graphcoloring,multi-objectivefunctionandotherscopes.Ithasaverybroadprospect.Inthispaper,amixedantcolonyalgorithmisintroducedfirstly.Thealgorithmisbasedonthetraditionalantcolonysystemalgori
8、thm,construc