肖自乾，陳經(jīng)優(yōu)

(海南軟件職業(yè)技術(shù)學(xué)院 軟件工程系，海南 瓊海 571400)

基于改進(jìn)遺傳算法的動(dòng)態(tài)路徑優(yōu)化研究

肖自乾，陳經(jīng)優(yōu)

(海南軟件職業(yè)技術(shù)學(xué)院 軟件工程系，海南 瓊海 571400)

日常出行中，由于道路養(yǎng)護(hù)、天氣變化等原因，導(dǎo)致部分路段交通受阻甚至禁止通行，這種情況下需要避開此路段。在基于改進(jìn)遺傳算法查找最優(yōu)路徑的基礎(chǔ)上，對(duì)如何根據(jù)路況變化動(dòng)態(tài)尋找更為合適的最優(yōu)路徑進(jìn)行了探討。

遺傳算法；動(dòng)態(tài)優(yōu)化；路權(quán)

1 最優(yōu)路徑主要影響因素

本文探討的最優(yōu)路徑主要影響因素包括道路是否暢通和道路通行緩慢兩方面[1]。最優(yōu)路徑定義不同意義也不同，路權(quán)的標(biāo)定方法有5種：①將車輛行駛距離作為優(yōu)化目標(biāo)；②將行駛時(shí)間作為優(yōu)化目標(biāo)；③將行駛費(fèi)用作為優(yōu)化目標(biāo)；④將是否選擇高速路、減少費(fèi)用等作為優(yōu)化目標(biāo)；⑤將實(shí)際交通情況如擁擠程度作為優(yōu)化目標(biāo)。本文主要將行駛路徑作為優(yōu)化目標(biāo)，在此基礎(chǔ)上考慮實(shí)際交通狀況，將這些因素轉(zhuǎn)換后納入路權(quán)進(jìn)行路徑分析。

(1)道路是否暢通。在靜態(tài)路網(wǎng)模型中，可以直觀地將路段長(zhǎng)度作為最優(yōu)路徑的判斷依據(jù),只需將其轉(zhuǎn)換為經(jīng)典的TSP問題即可求解。而實(shí)際情況中，往往一些道路因?yàn)榫S修或天氣原因?qū)е聼o法通行，在最優(yōu)路徑的搜索中應(yīng)避開這樣的路段，尋找其它最優(yōu)路徑。

(2)通行時(shí)間。如果通行時(shí)間非常緩慢，則考慮搜索其它更優(yōu)路徑。

2 改進(jìn)遺傳算法基本思想

改進(jìn)遺傳算法相比傳統(tǒng)遺傳算法具有收斂快、較好的全局最優(yōu)搜索能力等特點(diǎn)。最優(yōu)路徑搜索以經(jīng)典TSP問題作為研究模型，其主要實(shí)現(xiàn)思想是：①將遺傳過程分階段進(jìn)行，設(shè)定相應(yīng)的交叉、變異參數(shù)，后階段進(jìn)行自適應(yīng)參數(shù)設(shè)定；②在后期先將種群中所有個(gè)體進(jìn)行適應(yīng)度排序，計(jì)算適應(yīng)度平均值；再根據(jù)個(gè)體適應(yīng)度與平均值的關(guān)系執(zhí)行自適應(yīng)參數(shù)的交叉和變異操作，即在交叉操作中，比較適應(yīng)度值fc：當(dāng)fc|favg時(shí)，執(zhí)行固定的交叉概率k1；當(dāng)fc>favg時(shí)，執(zhí)行自適應(yīng)的交叉概率。在變異操作中，選取兩個(gè)個(gè)體，找出較大適應(yīng)度值fm，當(dāng)fm|favg時(shí)，執(zhí)行固定的變異概率k4；當(dāng)fm>favg時(shí)，執(zhí)行自適應(yīng)變異概率，同時(shí)引入精英保留策略來保留優(yōu)良個(gè)體[2-3]。

對(duì)普通遺傳算法(Rank)和改進(jìn)的自適應(yīng)遺傳算法進(jìn)行仿真比較，發(fā)現(xiàn)傳統(tǒng)的遺傳算法存在求解速度較慢問題，子代適應(yīng)度低于父代適應(yīng)度的情況也時(shí)有出現(xiàn)，而改進(jìn)的自適應(yīng)遺傳算法尋優(yōu)速度較快，能得到較為理想的結(jié)果，具有較好的收斂性[2]，如圖1所示。

圖1 兩種算法路徑尋優(yōu)過程曲線

3 路徑動(dòng)態(tài)優(yōu)化探討

首先隨機(jī)模擬出20個(gè)坐標(biāo)點(diǎn)(模擬地點(diǎn))，其坐標(biāo)如圖2所示。

圖2 初始化模擬地點(diǎn)

基于改進(jìn)遺傳算法的最優(yōu)路徑優(yōu)化搜索結(jié)果如圖3所示。

圖3 最優(yōu)路徑搜索結(jié)果(長(zhǎng)度3537.2014)

路徑搜索結(jié)果為：

1→7→6→4→11→14→18→8→12→17→16→5→20→13→9→3→10→19→15→2→1

3.1 路徑連通情況

實(shí)際交通環(huán)境中，一些路段往往因?yàn)榈缆佛B(yǎng)護(hù)、天氣等原因暫時(shí)不能通行，此時(shí)要另外尋找合適路徑。為驗(yàn)證算法，根據(jù)設(shè)定條件進(jìn)行動(dòng)態(tài)路徑優(yōu)化。首先假設(shè)任意點(diǎn)之間都是連通的，且不考慮方向因素，據(jù)此構(gòu)造各點(diǎn)相互連接情況如圖4所示。

其中，數(shù)字1表示兩點(diǎn)可通行，數(shù)字0表示不能通行。由圖4可以看出，坐標(biāo)點(diǎn)13和20之間不能通行，在當(dāng)前情況下最優(yōu)搜索結(jié)果如圖5所示。

路徑動(dòng)態(tài)搜索結(jié)果為：

1→7→6→4→11→14→18→8→12→17→16→5→20→10→13→9→3→19→15→2→1

3.2 交通流參數(shù)

3.2.1 參數(shù)介紹

實(shí)際交通中需要考慮交通流量、行駛速度、排隊(duì)長(zhǎng)度、占有率、交通流密度以及車頭間距、時(shí)距等交通參數(shù)。這些參數(shù)在一定程度上反映了實(shí)際的交通運(yùn)行狀態(tài)。下面將交通流量和行駛速度參數(shù)作為路徑動(dòng)態(tài)優(yōu)化條件進(jìn)行介紹[1]。

圖4 各點(diǎn)相互連接情況

圖5 道路狀況發(fā)生變化后最優(yōu)路徑(長(zhǎng)度3681.1895)

(1)交通流量：機(jī)動(dòng)車交通流量指在單位時(shí)間內(nèi)通過道路上某節(jié)點(diǎn)、路段或某條車道的車輛數(shù)。

(1)

其中，q為交通流量(輛/小時(shí))，N為車輛數(shù)，T為單位時(shí)間。由于單從交通流量上很難準(zhǔn)確反應(yīng)整個(gè)交通運(yùn)行狀態(tài)，所以，在實(shí)際應(yīng)用中不作為單獨(dú)指標(biāo)，需要結(jié)合其它參數(shù)綜合考慮。

(2)行駛速度：道路上行駛的車輛速度有幾種描述，如即時(shí)速度、平均行駛速度以及平均行程速度。其中平均行駛速度指路程與行駛時(shí)間之比，這個(gè)時(shí)間包含行駛時(shí)間和行駛過程中的等待時(shí)間，這個(gè)指標(biāo)并不能很好地反映實(shí)際交通情況；平均行程速度指行駛路程與行駛時(shí)間(不含等待時(shí)間)之比，能更好地體現(xiàn)車輛在道路上的運(yùn)行狀態(tài)。

3.2.2 優(yōu)化策略

當(dāng)兩個(gè)點(diǎn)之間發(fā)生擁堵，通行特別緩慢時(shí)，以平均行駛速度、交通流量作為判定標(biāo)準(zhǔn)。

(1)間斷交通流情況：在間斷交通流情況下，設(shè)定平均行駛速度小于每小時(shí)5公里為“慢”，大于每小時(shí)10公里小于每小時(shí)15公里為“較慢”，大于每小時(shí)20公里小于每小時(shí)25公里為“中”，可將平均行駛速度小于每小時(shí)15公里作為變換路徑的判定條件，以搜索其它更為快捷的路徑。

(2)連續(xù)交通流：在連續(xù)交通流情況下，設(shè)定平均行駛速度小于每小時(shí)10公里為“慢”，大于每小時(shí)30公里小于每小時(shí)40公里為“較慢”，可將平均行駛速度小于每小時(shí)30公里作為變換路徑的判定條件，以搜索其它更為快捷的路徑。

4 結(jié)語(yǔ)

本文在改進(jìn)遺傳算法的基礎(chǔ)上，探討了如何結(jié)合實(shí)際交通因素進(jìn)行動(dòng)態(tài)路徑優(yōu)化問題，并以兩點(diǎn)之間道路不可通行以及在可通行情況下考慮其它交通因素為例，闡述了具體的動(dòng)態(tài)路徑優(yōu)化策略。

[1] 李云.基于遺傳算法的動(dòng)態(tài)路徑優(yōu)化[D].太原：太原理工大學(xué),2013.

[2] 肖自乾,陳經(jīng)優(yōu).基于改進(jìn)的自適應(yīng)遺傳算法路徑優(yōu)化研究[J].蘇州職業(yè)大學(xué)學(xué)報(bào),2016(3):123-125.

[3] 梁旭，黃明.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2011.

(責(zé)任編輯：杜能鋼)

海南省自然科學(xué)基金項(xiàng)目(20156248)

肖自乾(1982-)，男，四川自貢人，海南軟件職業(yè)技術(shù)學(xué)院軟件工程系副教授，研究方向?yàn)檐浖_發(fā)、算法研究；陳經(jīng)優(yōu)(1983-)，女，海南東方人，海南軟件職業(yè)技術(shù)學(xué)院軟件工程系副教授，研究方向?yàn)檐浖_發(fā)。

10.11907/rjdk.162864

TP319

A

1672-7800(2017)003-0108-02