基于免疫遺傳算法的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)

董勇剛,譚 燕

(1.湖北省交通規(guī)劃設(shè)計院股份有限公司，湖北 武漢 430064；2.湖北工業(yè)大學(xué) 土木建筑與環(huán)境學(xué)院 ，湖北 武漢 430072)

0 引 言

區(qū)域內(nèi)汽車的保有量逐漸增長，使得區(qū)域道路交通狀態(tài)日益惡化。交通運行狀態(tài)如果較差，將會對社會發(fā)展和人們的工作、生活造成較大的影響，甚至造成巨大的經(jīng)濟(jì)損失[1-2]。因此，為了滿足人民群眾對美好生活的需求，設(shè)計有效的道路網(wǎng)規(guī)劃和車輛誘導(dǎo)措施具有重要的現(xiàn)實意義。

為提升區(qū)域交通運輸水平、緩解交通擁堵狀態(tài)，文獻(xiàn)[3]在道路運行監(jiān)管系統(tǒng)中設(shè)置通信數(shù)據(jù)采集設(shè)備，應(yīng)用ITS技術(shù)實現(xiàn)對區(qū)域交通中汽車數(shù)據(jù)的無縫采集與實時傳輸，建立24 h獲取數(shù)據(jù)信息的區(qū)域交通路徑規(guī)劃網(wǎng)絡(luò)。在這種系統(tǒng)的支持下，區(qū)域道路網(wǎng)規(guī)劃系統(tǒng)主要研究道路的空間變化與交通流量的神經(jīng)網(wǎng)絡(luò)測試，能夠有效協(xié)調(diào)區(qū)域道路中汽車流量，但是不能對汽車行駛方向和最優(yōu)路徑進(jìn)行引導(dǎo)。文獻(xiàn)[4]采用動態(tài)路徑誘導(dǎo)系統(tǒng)技術(shù)，實現(xiàn)區(qū)域道路網(wǎng)紅外信標(biāo)通信，從而對擁堵路況展開調(diào)度。這種方式需要在汽車上安裝與動態(tài)路徑誘導(dǎo)系統(tǒng)技術(shù)相匹配的語音導(dǎo)航系統(tǒng)，并需要安裝交通數(shù)據(jù)頻道的廣播設(shè)備，從而保障汽車導(dǎo)航數(shù)據(jù)的實時精準(zhǔn)性。但這種系統(tǒng)對車輛最優(yōu)路徑的規(guī)劃能力較差。

免疫遺傳算法是基于生物免疫機制提出的一種改進(jìn)遺傳算法，可對應(yīng)傳統(tǒng)遺傳算法中個體的多樣性，有利于提高遺傳算法的全局搜索能力，避免其陷入局部最優(yōu)。因此，為進(jìn)一步優(yōu)化區(qū)域道路網(wǎng)路徑誘導(dǎo)能力，本文基于免疫遺傳算法設(shè)計了新的區(qū)域道路網(wǎng)智能路徑規(guī)劃系統(tǒng)，其創(chuàng)新之處在于運用該算法對最優(yōu)路徑不斷的進(jìn)行迭代，得出最優(yōu)解，再通過層次搜索法和限制區(qū)域搜索法對得出的最優(yōu)解，進(jìn)行區(qū)域性的固定與限制，以增強智能路徑誘導(dǎo)系統(tǒng)的穩(wěn)定性。

1 系統(tǒng)設(shè)計

為了使區(qū)域道路網(wǎng)中智能路徑誘導(dǎo)系統(tǒng)隨時掌握區(qū)域道路交通狀態(tài)，本文在免疫遺傳算法的基礎(chǔ)上進(jìn)行硬件設(shè)備的開發(fā)與設(shè)計，從而完成對路徑誘導(dǎo)系統(tǒng)中的交通數(shù)據(jù)收集、處理等功能的設(shè)計?；诿庖哌z傳算法的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)硬件結(jié)構(gòu)如圖1所示。

圖 1 區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)硬件結(jié)構(gòu)Fig.1 Hardware architecture of intelligent path guidance system in regional road network

圖1中的VICS、Euro-Scout型號路徑誘導(dǎo)設(shè)備作為紅外信標(biāo)的標(biāo)識設(shè)備，需要安裝在區(qū)域道路網(wǎng)中，方便工作人員的及時管理，同時也能夠精準(zhǔn)地識別道路中的車輛信息。這2種類型的紅外信標(biāo)設(shè)備可以通過自身發(fā)射的紅外信號與車輛接收設(shè)備之間的通信時長、數(shù)據(jù)類型等信息確定系統(tǒng)數(shù)據(jù)中心對車輛運行情況的計算[5-7]。系統(tǒng)硬件部分通過區(qū)域道路網(wǎng)誘導(dǎo)控制中心數(shù)據(jù)庫的命令，向車載路徑誘導(dǎo)系統(tǒng)發(fā)送實時交通狀態(tài)，并結(jié)合區(qū)域道路的突發(fā)事件進(jìn)行信息更改與處理，向硬件設(shè)備提供穩(wěn)定、有效的基礎(chǔ)信息。在區(qū)域交通路徑中，比較重要的交通路口需要裝配具有信息發(fā)送與信息采集功能的數(shù)據(jù)信息收集板，同時，還能夠為車載單元提供相應(yīng)的道路信息文本，最終呈現(xiàn)于車載屏幕上，并按照一定類型的模糊聚類原理劃分不同道路的交通擁擠狀態(tài)，能夠提供給系統(tǒng)用戶穩(wěn)定且實時的道路擁擠狀態(tài)[8-9]。

此外，本文應(yīng)用北斗衛(wèi)星雷達(dá)和民用交通型號衛(wèi)星雷達(dá)作為全球道路網(wǎng)絡(luò)的信息覆蓋硬件設(shè)備，為用戶提供精準(zhǔn)三維數(shù)據(jù)模型與速度信息，通過差分方式將汽車的位置信息定位至1～2 m，滿足大多數(shù)普通雷達(dá)的位置精準(zhǔn)度。在衛(wèi)星雷達(dá)中裝置偽隨機噪聲碼設(shè)備，能夠為衛(wèi)星雷達(dá)提供抗干擾信號與信息傳播通道，保證在區(qū)域道路網(wǎng)絡(luò)智能路徑規(guī)劃過程中不出現(xiàn)較大數(shù)據(jù)誤差與干擾因子[10-11]。相對于軍用雷達(dá)來講，民用交通型號衛(wèi)星雷達(dá)偏差較大，但應(yīng)用于區(qū)域交通網(wǎng)智能路徑規(guī)劃完全能夠滿足汽車的路徑行駛規(guī)范[12]。

本研究還在衛(wèi)星雷達(dá)中安裝了基點信息接收器，能夠反饋區(qū)域道路智能路徑誘導(dǎo)過程中的測量距離與現(xiàn)實距離之間的誤差，接收器中的終端接口再向系統(tǒng)用戶傳達(dá)經(jīng)過接收器修正過的定位系統(tǒng)動態(tài)值。衛(wèi)星雷達(dá)的接收機作為信息誤差的修正設(shè)備，結(jié)合衛(wèi)星雷達(dá)中的數(shù)據(jù)慣性以及定位觀測量完成數(shù)據(jù)的實時修正，提升原始雷達(dá)數(shù)據(jù)的穩(wěn)定性與精準(zhǔn)性[13-15]。為對車輛的導(dǎo)航信息確定方式進(jìn)行優(yōu)化與改善，本文采用ADVANCE型號設(shè)備，通過自主通信的方式誘導(dǎo)數(shù)據(jù)定位算法與車輛流量的關(guān)聯(lián)。

2 免疫遺傳算法

路徑誘導(dǎo)的作用是指應(yīng)用連接法確定出發(fā)點和終點之間的距離、道路狀態(tài)等信息，然后在區(qū)域道路網(wǎng)中確定兩點之間的最優(yōu)行駛路線[16-17]。

本文應(yīng)用免疫遺傳算法設(shè)計智能路徑誘導(dǎo)系統(tǒng)，確定區(qū)域道路網(wǎng)中智能路徑與遺傳算法中染色體等串位結(jié)構(gòu)之間的關(guān)聯(lián)，應(yīng)用編碼對排列運算路徑誘導(dǎo)信息，同時，需要結(jié)合實時的道路運行狀態(tài)信息與免疫遺傳算法中染色體等因素的算法功能，設(shè)定免疫遺傳算法中染色體的長度代表路徑規(guī)劃的初始點與結(jié)束點。染色體內(nèi)包含的子染色體是未知因素，其具有一定的延展性。因此，在設(shè)計編碼的過程中，需要將區(qū)域道路網(wǎng)中所有的路徑信息全部涵蓋。

遺傳免疫算法中的染色體具有不可重復(fù)的特點[18-19]。因此，當(dāng)區(qū)域道路中具有環(huán)路、立交橋等路狀時，不考慮將其道路信息添加至免疫遺傳算法中，從而減少編碼儲存空間。在區(qū)域道路網(wǎng)中設(shè)置n個節(jié)點。則道路網(wǎng)中共有n個道路的初始點或終點，計算不同點之間的最佳路徑時，可以對點與點之間進(jìn)行路徑個體編碼，編碼中的終點為基因結(jié)束位置，路徑經(jīng)過點位為基因串。免疫遺傳算法在系統(tǒng)中的路徑規(guī)劃步驟如下：

1) 獲取區(qū)域內(nèi)的路徑數(shù)據(jù)信息并生成基因種群結(jié)構(gòu)；

2) 模擬路徑的相關(guān)參數(shù)并設(shè)定路徑規(guī)劃中所應(yīng)用的初始值；

3) 在種群數(shù)據(jù)中尋找具有代表性的路徑運算參數(shù)，將其作為抗原，并判斷最佳的適度計算條件；

4) 判斷適度計算條件在一定時間內(nèi)是否存在，并應(yīng)用2種搜索方法擴大范圍搜索備用適度計算條件，通過計算抗體確定路徑最優(yōu)解的存在；

5) 通過遍歷所有的數(shù)據(jù)節(jié)點，將數(shù)據(jù)節(jié)點的重組操作，并將新產(chǎn)生的節(jié)點基因個體不斷代入免疫遺傳算法中循環(huán)迭代計算，并將計算結(jié)果持續(xù)性地檢索與驗證，保障最佳路徑的有效性。

免疫遺傳算法具有變量數(shù)量大的特點，因此，在復(fù)雜交錯的道路網(wǎng)中可以設(shè)定大量的數(shù)據(jù)節(jié)點。然而隨著區(qū)域道路網(wǎng)規(guī)模的不斷擴大，數(shù)據(jù)節(jié)點的規(guī)模也不斷增大，當(dāng)基因中重復(fù)性地出現(xiàn)相同染色體時，將不能滿足免疫遺傳算法的基本適應(yīng)函數(shù)，導(dǎo)致免疫遺傳算法在路徑規(guī)劃的過程中出現(xiàn)基因種群庫超載現(xiàn)象，不能夠及時對種群基因庫限制[20-21]，進(jìn)而降低了系統(tǒng)對路徑規(guī)劃的搜索效率。為此，本文在免疫遺傳算法的基礎(chǔ)上建立種群的層次搜索方法與限制區(qū)域搜索方法，通過上述方法提升基因搜索效率。其中，層次搜索法用于實現(xiàn)圖像分層處理、道路等級劃分搜索以及關(guān)聯(lián)子圖搜索；限制區(qū)域搜索法用于實現(xiàn)限制距離與構(gòu)建模型以及提取道路子網(wǎng)數(shù)據(jù)。

應(yīng)用基因搜索方法選擇區(qū)域道路中的任意兩點作為種群基因的初始路徑規(guī)劃范圍，兩點之間進(jìn)行連接可以得到相應(yīng)的橢圓形搜索范圍，橢圓限制區(qū)域搜索范圍如圖2所示。

圖 2 橢圓限制區(qū)域搜索范圍Fig.2 Ellipse area to limited search range

圖2中，a為出發(fā)點，b為到達(dá)點，(A,B)為橢圓圓心坐標(biāo)，(xa,ya)為a點坐標(biāo)，(xb,yb)為b點坐標(biāo)。由于每一個區(qū)域的道路網(wǎng)都具有不同的特點，導(dǎo)致橢圓形的搜索范圍不同，應(yīng)用幾何學(xué)方法計算橢圓范圍內(nèi)的道路網(wǎng)匹配基因系數(shù)為橢圓長軸與橢圓焦距之比，進(jìn)而能夠確定橢圓的基本模型，可表示為

(1)

式中：θ為長軸與坐標(biāo)系X軸的角度。

隨著道路網(wǎng)的拓展，在橢圓形區(qū)域搜索免疫遺傳基因的算法與搜索的功能特性也隨之提升[22-23]。在應(yīng)用免疫遺傳算法規(guī)劃最佳路徑的同時，也需要考慮到用戶的實用信息，例如路徑長度、路況、道路等級、心理期待預(yù)期等，因此需要在免疫遺傳算法的基礎(chǔ)上建立函數(shù)策略，滿足算法中染色體與基因構(gòu)造過程中的環(huán)境穩(wěn)定性。

假設(shè)路徑權(quán)值為ω，通行率為g，路徑基礎(chǔ)長度為l，路徑染色體參與數(shù)為r，路況染色體比重參數(shù)為r1，道路等級為C，道路等級染色體比重為r2，可得路徑權(quán)值ω表達(dá)式為

(2)

權(quán)值ω越小，則證明通過此路徑的時間越少，時間消耗損耗越小。

綜合上述分析，設(shè)計基于免疫遺傳的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)流程如圖3所示。

圖 3 區(qū)域道路網(wǎng)智能路徑誘導(dǎo)流程Fig.3 Intelligent route guidance process of regional road network

3 實驗研究

本文在免疫遺傳算法的基礎(chǔ)上，應(yīng)用2種數(shù)據(jù)搜索方法在限制區(qū)域內(nèi)尋找路徑的最優(yōu)解，使遺傳算法與2種搜索方法形成數(shù)據(jù)平衡狀態(tài)，更有利于免疫遺傳算法信息的深度積累與最優(yōu)路徑空間的解鎖。

將免疫遺傳算法應(yīng)用到實際系統(tǒng)中，通過節(jié)點與節(jié)點之間的路徑規(guī)劃驗證本文系統(tǒng)的有效性。設(shè)定在實驗道路區(qū)域內(nèi)具有11個路徑出發(fā)點與終點(a—b點，將a設(shè)為起點，將b設(shè)為終點)。在考慮用戶心理變化的情況下要保障權(quán)重值不能大于高峰值，根據(jù)生活常識需要在早晚高峰時期進(jìn)行目標(biāo)的最快路徑搜索，此時的路徑規(guī)劃過程需要具有更短的路徑規(guī)劃時間，為用戶行駛方向的改變爭取時間。

為突出說明本文系統(tǒng)在最優(yōu)路徑誘導(dǎo)方面的作用，實驗環(huán)境不便的前提下，進(jìn)行對比實驗，設(shè)置對照組，對比系統(tǒng)分別為文獻(xiàn)[3]和文獻(xiàn)[4]，實驗結(jié)果的評價以路徑作為評價指標(biāo)，路徑越短，說明系統(tǒng)的路徑規(guī)劃性能越好。實驗結(jié)果如圖4所示。

(a) 本文系統(tǒng)

(b) 文獻(xiàn)[3]系統(tǒng)

(c) 文獻(xiàn)[4]系統(tǒng)圖 4 最佳路徑對比實驗結(jié)果Fig.4 Experiment results of the best path comparison

從圖4可以看出，本研究通過免疫遺傳算法對區(qū)域道路節(jié)點的不斷操作與數(shù)據(jù)適應(yīng)搜索，最終規(guī)劃的路徑為a—c—b，文獻(xiàn)[3]系統(tǒng)規(guī)劃的路徑為a—g—d—e—b，文獻(xiàn)[4]系統(tǒng)規(guī)劃的路徑為a—h—i—k—b，其中本文系統(tǒng)規(guī)劃的路徑除起點和終點外，只經(jīng)過1個節(jié)點c，文獻(xiàn)的系統(tǒng)除起點和終點外，均經(jīng)過3個節(jié)點，與本文系統(tǒng)相比，路徑的節(jié)點數(shù)量超出本文2個，路徑的長度超過本文系統(tǒng)規(guī)劃的路徑。因此，本文系統(tǒng)規(guī)劃的路徑更合理，有效提高了路徑的規(guī)劃能力，實現(xiàn)車輛路徑最優(yōu)誘導(dǎo)。測試不同系統(tǒng)進(jìn)行網(wǎng)智能路徑誘導(dǎo)系統(tǒng)的穩(wěn)定性，得到對比結(jié)果見表1。

表 1 路徑誘導(dǎo)系統(tǒng)穩(wěn)定性測試Tab.1 Stability test of path induction system

從表1可以看出，當(dāng)?shù)螖?shù)達(dá)到400次時，本文系統(tǒng)的穩(wěn)定性達(dá)到0.997，近乎為1，文獻(xiàn)[3]系統(tǒng)的穩(wěn)定性為0.913，文獻(xiàn)[4]系統(tǒng)的穩(wěn)定性為0.901，分別低于本文0.084和0.096，其他迭代次數(shù)時的穩(wěn)定性也均低于本文系統(tǒng)。由此可見，本文系統(tǒng)的路徑誘導(dǎo)系統(tǒng)的穩(wěn)定性效果得到了提升。

4 結(jié) 語

本文根據(jù)區(qū)域交通的特點對基于免疫遺傳算法的區(qū)域道路網(wǎng)智能路徑誘導(dǎo)系統(tǒng)展開研究與設(shè)計，采用經(jīng)典的免疫遺傳算法獲取區(qū)域道路網(wǎng)中可能存在的路徑最優(yōu)解，再應(yīng)用層次搜索法和限制區(qū)域搜索法對免疫遺傳算法的最優(yōu)解進(jìn)行區(qū)域性的限制與穩(wěn)固，從而增強了路徑誘導(dǎo)的智能程度與高效性。

然而由于研究時間的限制，本文系統(tǒng)還存在一定的不足，如路徑規(guī)劃過程耗時偏多。因此，在接下來的研究中，將考慮從提高誘導(dǎo)路徑規(guī)劃時效性的角度進(jìn)一步提高本文系統(tǒng)的應(yīng)用優(yōu)勢。