基于改進(jìn)蟻群算法的最短路徑問題研究

《基于改進(jìn)蟻群算法的最短路徑問題研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、無憂文檔無憂文檔可免積分在線閱讀和下載文檔包括資格考試、應(yīng)用文書等大量word文檔免費(fèi)下載基于改進(jìn)蟻群算法的最短路徑問題研究[搜索文檔]·無憂文檔·高等教育·高中教育·初中教育·小學(xué)教育·外語考試·資格考試·工作范文·求職職場·黨團(tuán)工作·表格模板·總結(jié)匯報·經(jīng)管營銷·教學(xué)研究您的位置：無憂文檔所有分類基于改進(jìn)蟻群算法的最短路徑問題研究基于改進(jìn)蟻群算法的最短路徑問題研究《自動化技術(shù)與應(yīng)用》２００９年第２８卷第６期控制理論與應(yīng)用ControlTheoryandApplications基于改進(jìn)蟻群算法的最短路

2、徑問題研究*張學(xué)敏,張航（中南大學(xué)信息科學(xué)與工程學(xué)院,湖南長沙410075）摘要:最短路徑問題是智能交通:交通網(wǎng)絡(luò)分析中的一個重要問題。文章分析了基本蟻群算法在求解交通網(wǎng)絡(luò)兩點(diǎn)之間最短路徑時所出現(xiàn)的問題,并針對這些問題,在方向引導(dǎo)及信息素更新等方面對算法進(jìn)行了改進(jìn)。實驗證明,改進(jìn)后的方法較基本蟻群算法能準(zhǔn)確快速地找到交通路網(wǎng)中兩點(diǎn)間的最短路徑,是切實可行的。關(guān)鍵詞:智能交通;最短路徑;蟻群算法中圖分類號:TP301.6文獻(xiàn)標(biāo)識碼:A文章編號:1003-7241(2009)06-0004-04Resear

3、chAnImprovedAntColonyAlgorithmoftheOptimalRoutingProblemZHANGXue-min,ZHANGHang(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410075China)Abstract:SearchfortheshortestpathintransportationnetworkisoneofthemostimportantproblemofITS

4、.Thispaperanalyzesthebasicantcolonyalgorithmandpresentsanimprovedalgorithmontheheuristicdirectioninformationandrenewalofpheromone.Theresultsoftheexperimentationprovedthattheimprovedalgorithmcouldfindtheshortestpathmoreaccuratelyandquicklythanthebasicalgo

5、rithm,andit’sfeasible.Keywords:intelligenttransportsystem(ITS);shortestpath;antcolonyalgorithm1引言最短路徑問題是智能交通中交通網(wǎng)絡(luò)分析中的一個重要問題,也是一個研究熱點(diǎn)。它是資源分配、路線設(shè)計及分析等優(yōu)化問題的基礎(chǔ),具有重要理論意義和實際應(yīng)用價值。有許多研究者曾對最短路徑算法進(jìn)行了大量的研究,并取得了很大的進(jìn)展,提出了很多解決這類問題的方法。其中傳統(tǒng)的算法有,Dijkstra算法、A*算法及其改進(jìn)算法等等;還

6、有近幾十年來,通過模擬或揭示某些自然現(xiàn)象而產(chǎn)生了一些新穎的啟發(fā)式智能算法,如遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法等。城市道路網(wǎng)中的交叉路口,連接兩節(jié)點(diǎn)之間的邊表示道路路線,并將路線的長度、通行時間、路況等屬性表示為該邊的權(quán)值,那么就可以把道路網(wǎng)絡(luò)抽象為一個帶權(quán)有向圖。給定一個帶權(quán)有向圖G為二元組G=(V,{E}),其中V是包含n個節(jié)點(diǎn)的集合,E是包含h條邊(弧段)的集合,是E中從節(jié)點(diǎn)i至j的邊,wij是邊的非負(fù)權(quán)值。設(shè)S,T分別為V中的起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn),則最優(yōu)路徑問題就是

7、指在帶權(quán)有向圖G中,尋找從指定起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條具有最小權(quán)值總和的路徑。2交通最短路徑問題描述城市道路網(wǎng)有道路路線、交叉路口等物理屬性,同時也具有路線長度、通行時間、路況等各種其它邏輯屬性。用節(jié)點(diǎn)來表示3蟻群算法的基本原理及存在的問題蟻群算法就是受螞蟻覓食行為的啟發(fā),以人工螞蟻模擬真實螞蟻行為來求解組合優(yōu)化問題的方法。在20世紀(jì)90年代初期,由意大利學(xué)者DorigoMacro等首先提出[1]。其原理在于[5],螞＊基金項目：湖南省科學(xué)技術(shù)與科技計劃（編號２００６ＧＫ３１３０）；湖南省自然科學(xué)基金獎

8、資助項目（編號０５ＪＪ３０１２１）收稿日期：２００８－１１－１０T蟻在所經(jīng)過的路徑上留下一種稱為信息素的揮發(fā)性分泌物,在覓食過程中螞蟻能夠感知這種物質(zhì)的存在及其強(qiáng)度,并以此來指導(dǎo)第1頁下一頁Word文檔免費(fèi)下載：基于改進(jìn)蟻群算法的最短路徑問題研究（共4頁，當(dāng)前第1頁）你可能喜歡·蟻群算法matlab程序·蟻群算法求解TSP問題·數(shù)學(xué)最短路徑問題·最短路徑動態(tài)規(guī)劃·最短路徑問題·最短路徑算法改進(jìn)·物流配送路徑優(yōu)化·matlab實例教程·蟻群算