遺傳算法在路徑規劃上的應用①

李 敏,黃 敏,程智鋒,周 靜

1(招商局重慶交通科研設計院有限公司,重慶 400067)

2(中山大學 智能工程學院,廣州 510006)

3(廣東工貿職業技術學院,廣州 510510)

隨著城市化建設的不斷發展,路網日趨復雜,出行者的路徑選擇更趨于多樣化,為此,出行者如何選擇最優路徑并高效快捷地到達目的地成為其關心的問題[1].目前尋找最優路徑的算法主要采用啟發式算法和最佳式算法,啟發式算法能夠在一定的時間內找出近似最優解,常見的啟發式算法有遺傳算法、神經網絡、蟻群算法等.最佳式算法能夠找出最優解,但一般時間復雜度較高,具有代表性的算法有Dijkstra、BFS 算法等[2].

對比其他路徑尋優算法,遺傳算法是一種全局優化算法,能夠有效地進行概率意義的全局搜素,具有較強的魯棒性,應用較為廣泛,適合于求解復雜的優化問題[2].為此,本文旨在運用遺傳算法,為出行者找到一條綜合權值最優的路徑.針對出行者路徑選擇的多樣性,結合前人研究[2,3],影響出行者路徑選擇因素諸多,主要表現在行程時間、行程路程、交叉口的個數、沿途風景等[3,4].本文初步選用以行駛路程和交叉口的個數作為綜合指標,定義綜合指標最小的路徑作為最優路徑,并以廣州大學城中山大學為例,采用遺傳算法的方法,找到從廣州大學城入口到中山大學的最優路徑,從而驗證遺傳算法在路徑規劃應用上的有效性.

1 交通路網模型

城市道路路網是由若干路段(弧段)和交叉口(結點)組成的網狀結構,描述了道路和交叉口之間的關系.在基于拓撲路網的情況下,交通路網數據可包含道路幾何中心線、路網弧段、路網結點3 個部分[5,6].其中三者之間的關系如圖1所示.本文采用弧段-結點模型來描述路網,定義以下路網模型,G=(V,E)表示路網;其中V={vi|i=1,2,···,n}是G的結點集,表示路段的端點,如道路交叉口或斷頭路口等,E={ei=(vk,vl)|i=1,···,m;vk,vl∈V}是G的弧段集.ei為從vk到vl的有向弧,vk為起點vl為終點.為了更好地描述道路交叉路口處的交通限制以及轉向信息,在路網模型中引入結點-弧段夾角及結點的邏輯連通關系[2].

圖1 道路路網數據地圖

2 遺傳算法基本概念及算法模型

2.1 遺傳算法基本概念

遺傳算法是一種借鑒達爾文提出的生物進化論的思想,利用計算機科學與自然遺傳學相互結合去解決一些復雜的優化問題[7,8].在遺傳算法中存在一些遺傳學與進化的概念,如染色體、種群、適應度等概念,為此闡述其各自的定義.染色體:英文全稱為chromosome,染色體又可以稱作為個體,一條染色體代表著一個可行解.種群:英文全稱為population,表示每代染色體的總數,一個種群表示解決該問題的部分解的集合.基因:英文全稱為gene,基因是染色體的組成元素,用來表達個體的基本特性.適應度:英文全稱為fitness,適應度表示衡量對環境的適應程度,每條染色體都有對應一個適應度值.

遺傳算法的過程主要分成以下幾個過程即種群的初始化、適應度值計算、選擇、交叉、變異、產生新種群.接下來分別介紹種群中染色體在指路標志誘導系統中的編碼、適應度函數的設計、選擇、交叉、變異等操作.

2.2 種群的初始化

在種群初始化之前,需要進行染色體編碼,本文遺傳算法采用的編碼方式不同于傳統的遺傳算法中的0-1 編碼,本文中遺傳算法的染色體是由一系列路網的結點組成,形成一條完整的路徑,為此將這種編碼方式稱為路徑編碼方法.這種方法規定每條染色體中的基因不允許有重復編碼的基因,但對于染色體的長度并沒有強行規定即染色體的長度是變化的,但其長度需要滿足小于路網的結點總數.染色體編碼即為從源節點到目的節點的隊列組成,以圖2的路網為例.

圖2 路由路徑與其編碼表示

圖2中一條從節點S 到節點D的一個染色體,其編碼可為:S-4-9-10-11-16-D,其中染色體編碼的第一位置基因(節點)是源節點,第二位置基因是從與源節點連接的其他節點中隨機選擇或啟發式選擇.選擇的節點從結構信息庫中刪除,避免重復,再重復過程直到目的地節點D.種群可以根據路網的大小來設定初始的染色體數量.

2.3 適應度函數設計

本文主要考慮行駛路程和交叉口的個數作為綜合指標,以綜合指標最小的路徑作為最優路徑.由于兩大指標存在量綱差異,為此需要對其進行歸一化處理,本文借鑒前人研究成果,將兩大指標轉換成時間消耗成本[7,8].出行者從始發地到目的地的時間總消耗由路段時間消耗與節點時間消耗組成,其中路段時間消耗取決于路程的長度、行駛的速度等因素,本文假定車輛在道路上勻速行駛,為此單位長度下的時間消耗是固定的,從而路段總消耗時間可用路徑總長度乘以單位長度下的時間消耗得到[8].節點時間消耗取決于交叉口的類型、轉向方向等因素[8],為此節點總消耗時間即通過每個交叉口時間消耗的累加.根據交叉口信號配時經驗,綠燈配置時間從長到短依次為直行方向、右轉方向、左轉及掉頭方向,然而在時間消耗上則成反向,假定左轉及掉頭方向的時間消耗是直行方向的2 倍,右轉方向的時間消耗是直行方向的1.5 倍[8,9].基于上述分析,適應度函數可以表達如式(1)所示.

其中,F—適應度函數值;

a、b—權重系數,本文認為兩個指標影響程度一致,為此將二者權重比設為1:1;

L—行駛路徑總長度(km);

C1—單位路段長度所需消耗的時間;

T1—交叉口所有直行方向的次數;

T2—交叉口所有右轉方向的次數;

T3—交叉口所有左轉及掉頭方向的次數;

C2—單個節點上直行方向上所需消耗的時間.

根據式(1)可知,適應度F值越小,則時間消耗越少,即路徑選擇越優.

2.4 選擇-復制

選擇操作是用來確定交叉個體,以及產生多少個子代個體.在選擇過程時應保持種群的整體數量不變.計算種群中各個染色體的適應值,并按照適應度由小到大排序將染色體中適應度最小的個體直接保留到下一代,然而個體適應度值越小,則被選擇的概率就越高,相同染色體只保留一條染色體.

2.5 交叉

通過選擇得到的兩個個體,將其部分結構相互交換,生成新個體.不同于傳統的單點交叉,兩個染色體選擇一個公共的基因(節點)作為交叉點;一般選擇第一個公共節點,若交叉后代與父代染色體一樣則改選其他公共節點.以圖3為例.父代染色體:Chromosome1:S-4-9-10-11-16-D與Chromosome2:S-4-5-10-15-16-D;其兩條染色體的公共基因結點為4、10、16;因此按照公共基因的選擇規則,首先選擇結點4,發現并無新的染色產生,則選擇另一個公共結點10,通過交叉后得到新的兩條子代染色體Chromosome1*:S-4-9-10-15-16-D與Chromosome2*:S-4-5-10-11-16-D;其中交叉后染色體如圖4所示.

圖3 交叉前的染色體路徑

圖4 交叉后新的染色體路徑

2.6 校正

交叉后產生的新個體中不能產生環路,即滿足同一節點只能選擇一次原則,為此需要對染色體進行校正操作.以圖5為例,父代染色體為Chromosome1:S-4-5-10-11-16-D與Chromosome2:S-4-9-14-15-10-5-6-11-16-D;其中假設選擇公共結點10 作為交叉點,則交叉后的子代染色體為:Chromosome1*:S-4-5-10-5-6-11- 16-D與Chromosome2*:S-4-9-14-15-10-11-16-D;很明顯子代染色體1 需要校正,經過校正處理后,得到校正后的染色體為Chromosome1**:S-4-5-6-11-16-D.

圖5 校正前后的染色體路徑

2.7 變異

變異以很小的隨即概率改變染色體上的某些基因,找回較好的基因,與種群大小無關.同時變異操作是一種局部隨機搜索,選取適應度最差的或者滿足突變概率的染色體.假設需突變染色體Chromosome1:S-4-5-10-9-14-15-16-D,如圖6所示.從染色體中隨機選擇一個基因作為突變基因(假設10),則從源節點到變異點的基因保持不變,變異點之后的基因則從連接的基因隨機選擇,直到目的節點.突變后染色體Chromosome1*:S-4-5-10-11-16-D,如圖7所示.

2.8 算法流程

章節2.2～2.7 分別闡述了在交通拓撲路網下,利用遺傳算法尋找最優路徑的具體運算步驟.算法的主要思路為:根據給定的起點生成相應的初始種群,接著計算各種群中染色體的適應度值,并將最優染色體直接保存于下一代,再在種群中進行選擇、交叉-校正、變異操作產生新的種群,重復上述過程直至到達指定的進化代數后停止進化.其中算法流程如圖8所示.算法中用到的符號如下:

OptV:起點集合,針對多入口路網;

Gen:迭代的次數;

K:起點的個數;

F:各種群中染色體的適應度值;

L:行駛路徑的長度;

T:交叉口的個數;

Fcpti:第i次進化時的最優的適應度值.

圖6 變異前的染色體路徑

圖7 變異后的染色體路徑

圖8 算法流程圖

3 實例應用

本研究基于C#與ArcGIS的開發下,采取廣州大學城作為實例,將上述算法應用于該路網中,路網的入口O1、O2、O3、O4、O5如圖9所示,目的地(D)為中山大學,路網中各個路段的權值如圖10所示.

圖9 廣州大學城出入口示意圖

對于適應度函數參數的設定,參照《城市道路路線設計規范》CJJ193-2012和《城市道路交叉口設計規程》CJJ152-2010,并結合廣州大學城車輛運行的實際情況,本文采用50 km/h的速度作為車輛的平均行駛速度,從而單位長度上的時間消耗為1.2 min.根據前人研究成果[7,9–11],直行方向消耗的時間為0.5 min,從而適應度函數可以表示為F=1.2L+0.5(T1+1.5T2+2T3).對于算法中的參數:根據相關資料[7–9]及多次試驗,設定種 群中染色體數為40、最大進化代數為40、交叉概率為0.9、變異概率為0.1.最終總的最優路線如圖11所示,其中各入口到中山大學的最優適應度值及相關指標如表1所示.

圖10 廣州大學城道路距離權值圖

圖11 總的最優路徑規劃圖

表1 各入口到中山大學最優路徑下的相關指標及適應度值

4 結語

本文采用遺傳算法對路徑尋優問題進行了探討,在明確起終點條件下,以行駛路程和交叉口個數作為綜合指標,找到了一定路網范圍內的最優路徑,驗證了遺傳算法在路徑規劃上的有效性.但本文只考慮了行駛路程和交叉口個數作為出行者的考慮因素,在后續的研究中將對出行者的路徑選擇進行綜合分析,從綜合影響因素出發,系統地對路徑規劃進行研究,進一步提高算法的科學性與合理性.