遺傳算法在路徑規(guī)劃上的應(yīng)用①

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

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

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

3(廣東工貿(mào)職業(yè)技術(shù)學院,廣州 510510)

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

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

1 交通路網(wǎng)模型

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

圖1 道路路網(wǎng)數(shù)據(jù)地圖

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

2.1 遺傳算法基本概念

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

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

2.2 種群的初始化

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

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

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

2.3 適應(yīng)度函數(shù)設(shè)計

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

其中,F—適應(yīng)度函數(shù)值;

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

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

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

T1—交叉口所有直行方向的次數(shù);

T2—交叉口所有右轉(zhuǎn)方向的次數(shù);

T3—交叉口所有左轉(zhuǎn)及掉頭方向的次數(shù);

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

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

2.4 選擇-復制

選擇操作是用來確定交叉?zhèn)€體,以及產(chǎn)生多少個子代個體.在選擇過程時應(yīng)保持種群的整體數(shù)量不變.計算種群中各個染色體的適應(yīng)值,并按照適應(yīng)度由小到大排序?qū)⑷旧w中適應(yīng)度最小的個體直接保留到下一代,然而個體適應(yīng)度值越小,則被選擇的概率就越高,相同染色體只保留一條染色體.

2.5 交叉

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

圖3 交叉前的染色體路徑

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

2.6 校正

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

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

2.7 變異

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

2.8 算法流程

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

OptV:起點集合,針對多入口路網(wǎng);

Gen:迭代的次數(shù);

K:起點的個數(shù);

F:各種群中染色體的適應(yīng)度值;

L:行駛路徑的長度;

T:交叉口的個數(shù);

Fcpti:第i次進化時的最優(yōu)的適應(yīng)度值.

圖6 變異前的染色體路徑

圖7 變異后的染色體路徑

圖8 算法流程圖

3 實例應(yīng)用

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

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

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

圖10 廣州大學城道路距離權(quán)值圖

圖11 總的最優(yōu)路徑規(guī)劃圖

表1 各入口到中山大學最優(yōu)路徑下的相關(guān)指標及適應(yīng)度值

4 結(jié)語

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