基于改進蟻群算法的最優路徑選擇研究*

王　珂

(徐州能源工業學校　徐州　221004)

?

基于改進蟻群算法的最優路徑選擇研究*

王珂

(徐州能源工業學校徐州221004)

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

改進蟻群算法; 城市救援; 最優路徑

Class NumberTP391

1　引言

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

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

2　基本蟻群算法原理

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

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

(1)

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

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

(2)

(3)

(4)

3　蟻群算法的改進研究

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

3.1對算法設計的改進

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

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

(5)

(6)

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

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

3.2對參數組合選擇方法的改進

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

(7)

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

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

4.1問題描述

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

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

(8)

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

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

(9)

4.2實驗模擬數據和結果

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

表1　不確定因素的“狀態參數”取值范圍

表2　初始化參數值

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

5　結語

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

[1] 谷遠利,李善梅,邵春福.基于蟻群算法的交通控制與誘導協同研究[J].系統仿真學報,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] 劉海燕.智能交通系統的車輛行駛最佳路徑算法[J].北京工商大學學報(自然科學版),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] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2005:91-117.

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

[4] 賴智銘,郭躬德.基于自適應閾值蟻群算法的路徑規劃算法[J].計算機系統應用,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] 吳啟迪,汪鐳.智能蟻群算法及應用[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] 黃貴玲,高西全,靳松杰.基于蟻群算法的最短路徑問題的研究和應用[J].計算機工程與應用,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].承德石油高等專科學校學報,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日

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

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

TP391

10.3969/j.issn.1672-9722.2016.10.001