基于改進蟻群算法的最優(yōu)路徑選擇研究*

王　珂

(徐州能源工業(yè)學(xué)?！⌒熘荨?21004)

?

基于改進蟻群算法的最優(yōu)路徑選擇研究*

王珂

(徐州能源工業(yè)學(xué)校徐州221004)

最優(yōu)路徑問題一直是城市應(yīng)急救援的研究核心,其研究目標也從單純的搜索“最短路徑”發(fā)展到尋求面向各類實際需要的“最優(yōu)路徑”,相關(guān)算法也因?qū)嶋H情況不同而千差萬別。在實際的復(fù)雜條件下,最優(yōu)路徑的選取除了考慮距離問題外,還應(yīng)考慮多種實際因素的影響。在基本蟻群算法的模型上,針對基本蟻群算法收斂速度慢和易陷入局部等缺點,提出一種改進的蟻群算法。該改進算法借鑒最大最小蟻群算法中利用限制信息素范圍的思想,這樣可以抑制由于最短路徑和最長路徑信息量差距加劇而引起的停滯現(xiàn)象,引入局部信息素更新及局部搜索策略,有效抑制早熟現(xiàn)象,加快了算法的求解速度,在此基礎(chǔ)上通過改進信息素的全局更新機制,使算法能夠更快地收斂到全局最優(yōu)解。同時考慮到影響交通最佳路徑選擇的各種不確定因素,如天氣、路質(zhì)、路況、車速等,并對該算法的數(shù)學(xué)模型以及參數(shù)組合選擇方法進行了改進研究,得到實際情況下更合適的交通行車路徑。

改進蟻群算法; 城市救援; 最優(yōu)路徑

Class NumberTP391

1　引言

隨著城市規(guī)模不斷擴大,城市應(yīng)急救援系統(tǒng)在人們的生命財產(chǎn)和社會安全問題等方面扮演著越來越重要的角色。在有突發(fā)事件時,通過智能化的計算機輔助決策系統(tǒng),可以在最短的時間內(nèi)計算出最佳路線,以便幫助政府領(lǐng)導(dǎo)迅速拿出最佳的指揮調(diào)度方案。最佳路徑是指從車輛的當前位置出發(fā),到出行目的地之間的一條路段阻抗和最小的道路[1～2]。路段阻抗是指車輛在該條路段上行駛的時間以及其他一些用戶感興趣的因素,如安全性、成本和舒適程度等[3～4],但主要是指路徑消耗時間最短等,考慮到天氣、路況車速等因素的算法不多。由意大利學(xué)者Dorigo等提出的蟻群算法是近幾年問世并逐步引起重視的一種新的后啟發(fā)式仿生類最優(yōu)路徑算法。

蟻群算法是受自然界中螞蟻尋路行為啟發(fā)產(chǎn)生的一種具有自適應(yīng)特性的分布式算法,它不需要進行大量的概率計算和建立復(fù)雜的數(shù)學(xué)模型,容易實現(xiàn)。螞蟻算法自問世以來表現(xiàn)出了強大的生命力,較之以往的啟發(fā)式不論在搜索效率上,還是在算法的時間復(fù)雜度方面都取得了令人滿意的效果,它具有并行性、正反饋性、健壯性等特點,且搜索過程不需要人工干預(yù),已經(jīng)越來越多地被人們用于解決組合優(yōu)化和交通通信網(wǎng)絡(luò)方面的問題[5～7]。在基本蟻群算法的模型上,針對基本蟻群算法收斂速度慢和易陷入局部等缺點,同時考慮到影響交通最佳路徑選擇的各種不確定因素,如天氣、路質(zhì)、路況、車速等,提出一種改進的蟻群算法,得到實際情況下更合適的交通行車路徑。

2　基本蟻群算法原理

蟻群算法是20世紀90年代由意大利學(xué)者Dorigo等[5]通過模擬自然界螞蟻覓食行為提出的一種仿生進化算法。自然界中的螞蟻,在尋找食物或遇到障礙物時,總能找到一條從食物到蟻巢或繞過障礙物的最優(yōu)路徑[8]。原因在于,螞蟻運動中會在所經(jīng)過的路徑上釋放出信息素(pheromone),后續(xù)螞蟻可根據(jù)前面螞蟻遺留下來的信息素選擇下一條要走的路徑。一條路徑上的信息素越高,說明這條路徑被選中的次數(shù)越多,即路徑的性能更優(yōu),后續(xù)螞蟻選擇這條路徑的概率就更大,由此構(gòu)成一個學(xué)習信息的正反饋,從而逐漸逼近最優(yōu)解[9]。

蟻群算法最初用于TSP問題,以此建立算法的模型。TSP問題組合優(yōu)化問題中的標準問題,可以用有向圖G=(V,E)表示,其中V=(1,2,…,n)表示節(jié)點的集合,E={(ij)}表示邊的集合,D=(dij)表示i,j間的歐氏距離。在應(yīng)用蟻群算法求解TSP問題之前需要限定每個人工螞蟻在一個路徑上每個節(jié)點只能選擇一次。所有的螞蟻都搜索到一個完整合法的路徑之后,根據(jù)螞蟻走過的線路更新各個邊對應(yīng)的信息素,在搜索過程中,螞蟻根據(jù)各個路徑上的信息素以及路徑的啟發(fā)信息計算概率,根據(jù)此概率選擇下一個節(jié)點。人工螞蟻在t時刻由節(jié)點i轉(zhuǎn)移到節(jié)點j的概率為

(1)

式中Dk={0,1,…,n-1}-tabuk表示人工螞蟻遞k個節(jié)點時,下一步允許選擇的節(jié)點集合。人工螞蟻具有記憶功能,用tabuk(k=1,2,…,m)記錄該螞蟻當前已走過的節(jié)點,隨著進化過程作動態(tài)調(diào)整。隨時間推移,以前留下的信息逐漸消失。ηij(t)為邊ij的能見度,取ηij=1/dij;τij(t)表示ij在t時刻的信息素;d表示信息素的相對重要程度。1-ρ表示信息素揮發(fā)程度。經(jīng)過一定時刻螞蟻完成一次循環(huán),對各個路徑上的信息素根據(jù)式(2)、(3)進行調(diào)整[10～11]。

τij(t+1)=ρτij(t)+Δτij(t)

(2)

(3)

(4)

3　蟻群算法的改進研究

為適合應(yīng)急救援實際狀況的應(yīng)用,需要對算法進行改進。另外,基本蟻群算法在實際應(yīng)用中收斂性不高,算法的搜索空間太小,易過早地陷入局部最優(yōu),并且計算時間太長,尋找路徑的效率不高,甚至出現(xiàn)停滯,也急需改進以適應(yīng)應(yīng)急救援的實際需求。

3.1對算法設(shè)計的改進

1) 子路徑構(gòu)造過程的改進:在基本蟻群算法中,每只螞蟻均要經(jīng)過所有節(jié)點;而在改進蟻群算法中,每只螞蟻并不需要遍歷所有節(jié)點。因此,在改進后的蟻群算法的每次迭代中,每只螞蟻移動次數(shù)是不確定的,只能將是否回到原點作為路徑構(gòu)造完成的標志。

2) 信息素更新策略是蟻群算法的關(guān)鍵步驟之一,信息更新過快將導(dǎo)致算法陷入局部最優(yōu)甚至停滯,信息更新過慢則收斂速度緩慢,無法搜索到最優(yōu)路線。因此文章對信息濃度更新規(guī)則的改進:為了提高計算效率,只考慮前nk個本代最優(yōu)解進行信息更新,改造更新規(guī)則為:

(5)

(6)

C={(vi,vj)(vi,vj)∈A且取得的值Lk的解路徑使用了弧(vi,vj)},其中,ρ為信息素揮發(fā)后所剩的比例系數(shù),Lk為第k優(yōu)的目標值,λ為更新系數(shù),靈活控制信息素的增加幅度。

3) 改進后的蟻群算法螞蟻轉(zhuǎn)移時不僅要考慮路徑距離和信息量,還要考慮到影響交通最佳路徑選擇的各種不確定因素,如天氣、路質(zhì)、路況、車速和車輛容量等的限制,并對該算法的數(shù)學(xué)模型以及參數(shù)組合選擇方法進行了改進研究,得到實際情況下更合適的交通行車路徑。

3.2對參數(shù)組合選擇方法的改進

在蟻群算法中,信息素揮發(fā)系數(shù)ρ、信息啟發(fā)因子α、期望式啟發(fā)因子β、信息素強度Q、螞蟻的數(shù)目m等都是非常重要的參數(shù),其選取方法和選取原則直接影響到蟻群算法的全局收斂性和求解效率。同時,蟻群算法中各參數(shù)的作用是緊密聯(lián)系的,其中對算法性能起著最關(guān)鍵作用的是信息素揮發(fā)因子ρ、信息啟發(fā)因子α、期望式啟發(fā)因子β三個參數(shù)。如果ρ、α、β的組合參數(shù)配置不當,會導(dǎo)致求解的速度很慢且所得解的質(zhì)量特別差,因此,研究關(guān)鍵參數(shù)的最佳組合和配置策略有著非常重要的意義。在蟻群算法中,α、β、ρ為常量參數(shù),其最佳組合往往要根據(jù)具體的問題,通過大量的實驗來確定。實際上α、β、ρ的取值影響著算法的搜索空間及收斂性,參數(shù)ρ對算法具有雙重影響,當ρ較小時算法的收斂性降低;當ρ較大時雖然算法收斂性提高,但是搜索空間減小,容易陷入局部最優(yōu)。這一問題可以通過式(6)進行改進:

(7)

式中,0<μ<1<1;ρo是預(yù)先給定的最小值以確保取得最優(yōu)解[5]。

4　城市交通最佳路徑選擇問題的模擬

4.1問題描述

時間算法需要屬性如下:Vmax為城市中A、B兩點之間路段允許車輛行駛最大速度(單位:公里/小時;超出此值為非法);V為當前車輛行駛速度(單位:公里/小時);φ為當前路段車輛所占用車道的交通流量(車輛數(shù)/小時);φmax為當前路段允許的交通最大流量(車輛數(shù)/小時);φ某路段當前理想流量(動態(tài):車輛數(shù)/小時);dij為i、j之間路段長度(公里)。

由城市中i點轉(zhuǎn)移到城市j點的期望程度ηij定義為i與j之間的路徑長度的倒數(shù),在用式(1)～(4)進行算法循環(huán)迭代過程中,分別引入wij、hij、rij等“狀態(tài)參數(shù)”表示天氣、路質(zhì)、路況等不確定因素對公路交通的影響程度?？紤]到這些影響后,將式(6)表示的實際路徑長度dij用“虛擬路徑”長度式(8)替換:

(8)

可近似算出的當前i、j之間路段dij上的平均行車速度vij為

Vij=(V×φ/φ≤φmax,Vij≤V≤Vmax)

(9)

4.2實驗?zāi)M數(shù)據(jù)和結(jié)果

在Matlab中通過分析實驗確定改進蟻群算法中不確定因素“狀態(tài)參數(shù)”的最佳取值,采用改變一個參數(shù)、其他不變的策略來討論參數(shù)的設(shè)置對蟻群算法性能的影響。見表1,表2。

表1　不確定因素的“狀態(tài)參數(shù)”取值范圍

表2　初始化參數(shù)值

將實驗算出的參數(shù)帶入改進的蟻群算法,確定了從徐州消防支隊到市區(qū)某一事故現(xiàn)場之間車輛行駛時間最短的路徑。因此考慮到天氣、路況和限速等實際因素,兩點間的最佳路徑即可確定,路徑的選擇更具有理論和實踐意義。

5　結(jié)語

改進后的蟻群算法不僅繼承了原有算法群體合作、正反饋選擇、并行計算等特點,而且算法的收斂性和對最優(yōu)解的搜索空間都有較好的提高。根據(jù)實際情況,不僅是選擇距離最短的路徑,而是將各種天氣、路質(zhì)、路況等不確定因素對交通行車的影響考慮在內(nèi),重新選擇合適的行車最佳路徑,即行車所用時間最短的路徑。該模型把不同狀態(tài)條件稍加改變,還可以應(yīng)用于其他優(yōu)化問題,適用范圍較廣。在本算法中,因為簡化問題的緣故,狀態(tài)參數(shù)都設(shè)定為固定值,而實際情況卻是動態(tài)變化的,另外還有一些諸如改進蟻群算法的參數(shù)設(shè)計的問題還有待在以后的研究中進一步改進。

[1] 谷遠利,李善梅,邵春福.基于蟻群算法的交通控制與誘導(dǎo)協(xié)同研究[J].系統(tǒng)仿真學(xué)報,2008,20(10):2754-2756.

GU Yuanli, LI Shanmei, SHAO Chunfu. Study on Cooperation of Traffic Control and Route Guidance Based on Ant Algorithm[J]. Journal of System Simulation,2008,20(10):2754-2756.

[2] 劉海燕.智能交通系統(tǒng)的車輛行駛最佳路徑算法[J].北京工商大學(xué)學(xué)報(自然科學(xué)版),2006,24(1):53-55.

LIU Haiyan. Best Running Path Arithmetic of Vehicles in Intelligent Transport System[J]. Journal of Beijing Technology and Business University(Natural Science Edition),2006,24(1):53-55.

[3] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005:91-117.

DUAN Haibin. The Principle and Application of Ant colony Algorithm[M]. Beijing: Science Press,2005:91-117.

[4] 賴智銘,郭躬德.基于自適應(yīng)閾值蟻群算法的路徑規(guī)劃算法[J].計算機系統(tǒng)應(yīng)用,2014,23(2):113-114.

LAN Zhiming, GUO Gongde. Ant Colony Optimization Based on Self-Adoption Threshold for Path Planning[J]. Computer System & Applications,2014,23(2):113-114.

[5] Dorigo M, Stützle T. Ant Colony Optimization[M]. Cambridge, MA: MIT Press,2004.

[6] Bonabeau E, Dorigo M, Theraulaz G. Inspiration for Optimization From Social Insect Behavior[J]. Nature,2000,406(6):39-42.

[7] 吳啟迪,汪鐳.智能蟻群算法及應(yīng)用[M].上海:上?？萍冀逃霭嫔?2004:16-38.

WU Qidi, WANG Lei. The Application of Intelligent Ant Colony Algorithm[M]. Shanghai: Shanghai Science and Technology Education Publishing House,2004:16-38.

[8] SHI Hongtao, DONG Yucai, YI Lianghai. Study on the Route Optimization of Military Logistics Distribution in Wartime Based on the Ant Colony Algorithm[J]. Computer and Information Science,2010,3(1):87-92.

[9] 黃貴玲,高西全,靳松杰.基于蟻群算法的最短路徑問題的研究和應(yīng)用[J].計算機工程與應(yīng)用,2007,43(13):233-235.

HUANG Guiling, GAO Xiquan, JIN Songjie. Research and Application of the Shortest Path Problem Based on Ant Colony Algorithm[J]. Computer Engineering and Applications,2007,43(13):233-235.

[10] TANG Ruixue, QIN Yongbin, LI Zhang. Research on Heuristics Logistics Distributi on Algorithm Based on Parallel Multi-ant Colonies[J]. Journal of Software,2011,6(4):612-619.

[11] 楊瑞臣,郝海燕.改進的蟻群算法在物流配送路徑問題求解中的應(yīng)用[J].承德石油高等專科學(xué)校學(xué)報,2009,6(11):53-56.

YANG Ruichen, HAO Haiyan. Application of Improved Ant colony Algorithm in The Solution of Logistics Distribution Routing Problem[J]. Journal of Chengde Petroleum College,2009,6(11):53-56.

Selection of Optimal Route Based on Improved Ant Colony Algorithm

WANG Ke

(Xuzhou Energy Technical School, Xuzhou221004)

The optimal path problem has always been the research core of city emergency rescue. Its research goal has developed from looking for “the shortest path” to searching “the optimal path”. The related algorithms differ in different circumstances. In addition to distance problem, the influence of various practical factors should also be considered under the complicated actual conditions. An improved algorithm is proposed based on the basic ant colony algorithm model, directing at its weakness of slow convergence and stagnation behavior etc. The improved algorithm used the idea of limiting pheromone range of max-min ant colony algorithm for reference to inhibit the stagnation behavior caused by aggregative gap between the shortest path information and the longest. The introduction of partial pheromone update and search strategy has effectively controlled the premature phenomenon and speeded up the solution. Meanwhile, the algorithm’s mathematical model and the methods of parameters combination were improved considering the various sorts of uncertain factors that influence the choice of the optimal path, such as weather, road quality, road condition, vehicle speed etc. in order to obtain a more appropriate driving path in practical condition.

improved ant colony algorithm, emergency rescue, optimal route

2016年4月17日,

2016年5月20日

江蘇省教育科學(xué)“十二五”規(guī)劃2015年度課題(編號:B-a/2015/01/014);江蘇省高校自然科學(xué)研究項目資助(編號:13KJB170003);江蘇省社科應(yīng)用研究精品工程(編號:14SWC-117);徐州市哲學(xué)社會科學(xué)研究課題(編號:15XSZ-096);徐州市科技情報研究計劃項目;江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助。

王珂,女,講師,研究方向:計算機教學(xué)與模擬仿真。

TP391

10.3969/j.issn.1672-9722.2016.10.001