資源描述:
《gis路徑尋優(yōu)中的蟻群算法研究》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、南京理工大學(xué)碩士學(xué)位論文GIS路徑尋優(yōu)中的蟻群算法研究姓名:孫中華申請學(xué)位級別:碩士專業(yè):控制理論與控制工程指導(dǎo)教師:王海梅20090608碩士論文GIS路徑尋優(yōu)中的蟻群算法研究摘要最短路徑問題是交通網(wǎng)絡(luò)分析中的一個(gè)重要問題,也是資源分配、路線設(shè)計(jì)等優(yōu)化問題的基礎(chǔ)。多年來,最短路徑算法一直是運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的研究熱點(diǎn),由此出現(xiàn)了大量研究成果。縱觀這些成果,主要還是集中在以經(jīng)典Dijkstra算法為基礎(chǔ)的各類改進(jìn)算法的研究和應(yīng)用方面。蟻群算法是近年來迅速發(fā)展起來的一種全局性優(yōu)化算法,但這種基于生物進(jìn)化原理的算法還沒有形成系統(tǒng)的、成熟的算法理論體系,提高
2、搜索速度,克服過早收斂仍然是算法研究的方向。論文以提高算法效率為出發(fā)點(diǎn),對基于道路網(wǎng)絡(luò)的蟻群算法搜索策略進(jìn)行了研究。論文還對時(shí)變道路網(wǎng)絡(luò)的最短路徑問題進(jìn)行了探討。論文的研究成果主要包括:1)基于泰州市電子地圖道路信息,通過道路的提取,拓?fù)渚W(wǎng)絡(luò)的構(gòu)建,生成了適于最短路徑問題分析的道路網(wǎng)絡(luò)平臺。2)基于上述平臺,設(shè)計(jì)并實(shí)現(xiàn)了道路網(wǎng)絡(luò)尋優(yōu)中的蟻群算法,具體包括:分析螞蟻搜尋過程,設(shè)計(jì)算法流程,編寫代碼并實(shí)現(xiàn)。3)對上述蟻群算法進(jìn)行改進(jìn),研究了矩形限制搜索區(qū)域的蟻群算法,實(shí)驗(yàn)結(jié)果表明:矩形限制搜索區(qū)域的蟻群算法較傳統(tǒng)的蟻群算法在節(jié)點(diǎn)搜索數(shù)目及運(yùn)算時(shí)間方面有較大改善。4
3、)利用蟻群算法多解性,通過調(diào)整螞蟻信息素釋放標(biāo)準(zhǔn),保證螞蟻得到的次優(yōu)解質(zhì)量,結(jié)果表明,在最短路徑不可行的情況下,螞蟻能夠迅速地收斂到最理想的替代路徑上來。5)在對時(shí)變網(wǎng)絡(luò)分析的基礎(chǔ)上,建立了一個(gè)時(shí)變道路網(wǎng)模型。對道路交通網(wǎng)絡(luò)的道路通行時(shí)間進(jìn)行區(qū)域簡化,并基于該簡化網(wǎng)絡(luò)實(shí)現(xiàn)了時(shí)變的最短時(shí)間路徑算法。關(guān)鍵詞:最短路徑,蟻群算法,限制搜索區(qū)域,時(shí)變網(wǎng)絡(luò)碩士論文AbstractTheshortestpathoptimizationisoneofthecriticalproblemsintransportationnetworks.It’Salsothebasisofm
4、anyareas,suchasresourceallocationandroutedesigning.Overtheyears,development,application,andefficiencyanalysisoftheshortestpathalgorithmhavebeenahotspotinoperationalresearch,geographicinformationscienceandsoon.Asaresult,largenumbersofalgorithmscameout.Andthesealgorithmsaremainlyfocus
5、edontheresearchesandapplicationsofimprovementbasedonclassicalalgorithm—Dijkstraalgorithm.Antcolonyalgorithmdevelopedrapidlyinrecentyears,itisaglobaloptimizationalgorithmandbasedontheprinciplesofbiologicalevolution.However,thisalgorithmhasnotyetformedasystemicandmaturetheoreticalsyst
6、em.Toimprovesearchingspeedandovercometheprematureconvergenceisstillthedirectionofthealgorithm.ThepurposeofpaperisimprovingefficiencyofthealgorithmandstudyingsearchingstrategyofACObasedonroadnetworks.Andpaperalsodiscussedtheshortestpathproblemintime-dependentnetworks.Themaintasksaref
7、ollowingaspects:1.ThroughtheextractionofroadsfromelectronicmapofTaizhouCity,andconstructionoftopologynetwork,toconstructtheroadnetworkplatformfortheshortestpathanalysis.2.Basedontheplatformabove,designandimplementACOinoptimizationofgeographicalroads,including:analysingprocessofantse
8、arching,designingst