王　珂

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

?

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

王珂

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

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

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

Class NumberTP391

1　引言

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

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

2　基本蟻群算法原理

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

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

(1)

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

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

(2)

(3)

(4)

3　蟻群算法的改進(jìn)研究

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

3.1對(duì)算法設(shè)計(jì)的改進(jìn)

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

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

(5)

(6)

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

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

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

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

(7)

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

4　城市交通最佳路徑選擇問(wèn)題的模擬

4.1問(wèn)題描述

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

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

(8)

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

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

(9)

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

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

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

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

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

5　結(jié)語(yǔ)

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

[1] 谷遠(yuǎn)利,李善梅,邵春福.基于蟻群算法的交通控制與誘導(dǎo)協(xié)同研究[J].系統(tǒng)仿真學(xué)報(bào),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é)報(bào)(自然科學(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].計(jì)算機(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] 黃貴玲,高西全,靳松杰.基于蟻群算法的最短路徑問(wèn)題的研究和應(yīng)用[J].計(jì)算機(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] 楊瑞臣,郝海燕.改進(jìn)的蟻群算法在物流配送路徑問(wèn)題求解中的應(yīng)用[J].承德石油高等?？茖W(xué)校學(xué)報(bào),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年度課題(編號(hào):B-a/2015/01/014);江蘇省高校自然科學(xué)研究項(xiàng)目資助(編號(hào):13KJB170003);江蘇省社科應(yīng)用研究精品工程(編號(hào):14SWC-117);徐州市哲學(xué)社會(huì)科學(xué)研究課題(編號(hào):15XSZ-096);徐州市科技情報(bào)研究計(jì)劃項(xiàng)目;江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程資助。

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

TP391

10.3969/j.issn.1672-9722.2016.10.001