改進(jìn)的混合型蟻群算法及其應(yīng)用碩士學(xué)位論文

《改進(jìn)的混合型蟻群算法及其應(yīng)用碩士學(xué)位論文》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、分類號：O157單位代碼：10110學(xué)號：s20110075中北大學(xué)碩士學(xué)位論文改進(jìn)的混合型蟻群算法及其應(yīng)用xxx華北改進(jìn)的混合型蟻群算法及其應(yīng)用碩士研究生孫晶指導(dǎo)教師xxx教授學(xué)科專業(yè)應(yīng)用數(shù)學(xué)年月日圖書分類號O157密級非密UDC510碩士學(xué)位論文改進(jìn)的混合型蟻群算法及其應(yīng)用孫晶指導(dǎo)教師（姓名、職稱）xxx教授申請學(xué)位級別理學(xué)碩士專業(yè)名稱應(yīng)用數(shù)學(xué)論文提交日期年月日論文答辯日期年月日學(xué)位授予日期年月日論文評閱人答辯委員會主席年月日xxx學(xué)位論文摘要旅行商問題（TSP）與車輛路徑問題（VRP）自提出以來，許多學(xué)者進(jìn)行了大量的理論研究和實(shí)驗(yàn)分析，取得了非常顯著的進(jìn)展，已經(jīng)成為了運(yùn)籌

2、學(xué)和組合優(yōu)化問題領(lǐng)域的熱點(diǎn)研究問題。求解他們的算法主要有精確型算法、近似算法和啟發(fā)式算法。在眾多求解TSP算法中，蟻群算法具有較好的性能，該仿生智能算法和傳統(tǒng)的算法截然不同，具有魯棒性、正反饋、并行性和易與其他方法相結(jié)合等特點(diǎn)。自創(chuàng)立以來，無論理論研究還是在應(yīng)用方面都取得了突破性的進(jìn)展，不但在求解以上兩種問題上得到了最優(yōu)解，而且在工件的排序問題、圖著色問題、多目標(biāo)函數(shù)等許多領(lǐng)域也取得了相當(dāng)不錯的效果，具有相當(dāng)廣闊的發(fā)展前景。本文首先介紹了一種求解TSP問題的算法—改進(jìn)的混合型蟻群算法，該算法在近鄰法構(gòu)造初始解的基礎(chǔ)上，使用2-opt局部搜索法對當(dāng)前解進(jìn)行改進(jìn)，在更新全局信息素時(shí)

3、采用基于排序的螞蟻系統(tǒng)對排在前2名的螞蟻更新全局信息素，且為全局信息素設(shè)置最大值和最小值，并使用MATLAB仿真求解了kroa200等13個(gè)經(jīng)典TSP問題。通過仿真實(shí)驗(yàn)可以看出本文改進(jìn)的算法在求解TSP問題時(shí)具有很好的效果，在求解很多問題時(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ù)的方法對TSP問題的種群多樣性進(jìn)行了分析，通過實(shí)驗(yàn)仿真與基本蟻群算法從平均的邊數(shù)和、最大的邊數(shù)以及最小邊數(shù)和進(jìn)行了比較分析，從數(shù)據(jù)上說明了改進(jìn)的算法

4、具有種群多樣性。最后又把改進(jìn)的混合型蟻群算法應(yīng)用到VRP問題，使用MATLAB仿真工具對N44K6等10個(gè)經(jīng)典VRP問題進(jìn)行了求解，得到的結(jié)果和已知最優(yōu)解的誤差很小，都在6%以下，并且N33K6問題得到了和已知最優(yōu)解相同的解。并且與基本蟻群算法做了比較，比較結(jié)果充分證明了該改進(jìn)算法的有效性。關(guān)鍵詞：混合型蟻群算法，TSP問題，種群多樣性，VRP問題xxx學(xué)位論文AbstractManyscholarshavebeenalotoftheoreticalresearchandexperimentalanalysissinceTravelingSalesmanProblem(TSP)

5、andVehicleRoutingProblem(VRP)areproposedandnotableprogressismade.TSPandVRPhavebecomethecentralissueinoperationalresearchandcombinatorialoptimization.Precisealgorithm,approximatealgorithmandheuristicalgorithmareusedtosolvetheproblems.Amongallthealgorithms,antcolonyalgorithmhasbetterperformanc

6、e.Thisbionicintelligencealgorithmisquitedifferentfromthetraditionalones,it’smorerobust,positivefeedback,concurrencyandeasytocombinewithotheralgorithms.Sinceantcolonyalgorithmisproposed,breakthroughprogresshasbeenmadebothintheoreticalresearchandrealisticapplication.Notonlyoptimalresultsareach

7、ievedbutalsoproventobeeffectiveinschedulingjobs,graphcoloring,multi-objectivefunctionandotherscopes.Ithasaverybroadprospect.Inthispaper,amixedantcolonyalgorithmisintroducedfirstly.Thealgorithmisbasedonthetraditionalantcolonysystemalgorithm,construc