基于遺傳算法城市交叉路口交通流量優化控制

王雪梅，李曉峰

?

基于遺傳算法城市交叉路口交通流量優化控制

王雪梅，李曉峰

摘要：為了控制十字路口的交通流量，以確保交通網的交通流順暢。針對車輛隊列長、綠燈時間、信號燈周期以及黃燈的影響問題進行了模擬實驗研究。提出遺傳算法使交通流控制最優化，從而在自我調整過程中找到最優解。首先遺傳算法視當前隊列長度為輸入，然后，輸出十字路口最優化后的綠燈時間。最后，通過引入各相態紅燈期間涌入的交通流，使結果得到進一步改進。實驗表明在十字路口應用遺傳算法能夠快速應對變化的車輛隊列長，綠燈時間、信號燈周期等問題，并且實現交通流控制。

關鍵詞：交通控制系統；交通流；遺傳算法；十字路口

0　引言

如今的交通流狀況與幾年前相比變得越加飽和，這是由于中國路上的車輛明顯增多[1-2]。新建路段設立更多車道，目的是為了增大當前交通網絡的車容量，但鑒于中國多數的主要城市像北京、上海發展快速[3]，新道路建設的用地有限。由于新道路建設不再是城市規劃師的一個可選手段，交通網絡順暢的優化問題因而成了一大難題[4-5]。

各種交通控制應用在目前的交通網絡，從簡單的交通控制器（例如道路信號）到電子交通控制器（如交通燈）。在北京、上海常見的交通控制器有道路標識、交通燈、道路設施（如環形路、天橋）。不過，由于北京，上海等城市交通流量的加大超出了目前交通網的最大承受力，交通擁堵如今是司空見慣。在可用地有限及重建道路設施困難重重的情況下，較為妥善的解決方法之一就是研究并設計出交通燈控制器來對交通流進行優化[6]。如今，大多數交通燈控制系統仍采用預設模式，這已不再滿足超飽和的交通流情況。

目前交通燈系統的不足是因為對實時交通特征缺乏了解所致，比如隊列長度、交通信號持續時間。紅燈過程中涌入的交通流也是交通控制模擬實驗的一個考慮方面。本文采用遺傳算法是因為它具有自然遺傳機制的特點，能夠快速找到次優解。

1　交通特征

（1）十字路口

本文研究的是某個十字路口的交通控制系統。在每個十字路口，都會存在交流流量的方式，即所謂的“相態”來表現交通流。這個十字路口，有3個（A，B，C）這樣的交通流相態，如圖1中的箭頭所示：

三個交通流相態連接

（2）交通燈

交通燈的設計是為了控制和優化十字路口的交通流，只允許某個相態內的交通流在某個時間點通過十字路口。反過來這些相態又取得許可，交叉路口的交通流順暢得以保障和控制。

用來控制交通流的交通燈通常是3種信號燈，即綠燈、紅燈和黃燈。綠燈是交通流獲得通過十字路口；紅燈即暫停，指的是交通流嚴禁在紅燈時段通過十字路口；黃燈是介于紅燈和綠燈之間，提醒交通流綠燈很快過去要減速緩行。

近年來，傳統的交通燈系統已無法滿足日益增加的交通需求，于是，就有很多關于改善交通流量控制的研究。那些系統應用傳感器來感知隊列車輛并利用模糊邏輯來判斷是否延長綠燈周期以讓更多車輛通過。也有人提出用無線通信方式來進行交通控制。基于這個理念，車輛發出信息給附近的交通控制系統，然后系統基于信息對交通燈進行優化。也有人提出用遺傳算法來進行交通流控制。這方面的研究里，車輛在道路網絡的通行時間是研究的焦點，它們都提到利用遺傳算法來對網絡的流量進行優化。

本文也利用到遺傳算法來對交通燈系統的周期和相態的優化進行分析：首先對交通燈系統的交通流進行分析，再應用遺傳算法來判斷十字路口所有交通燈的相態、綠燈總時間以及交通流的分割。

（3）十字路口

交通流量控制包括幾個重要特點和參數，比如隊列長度、浪費時間、涌入交通流和周期時間。

隊列長度是指在十字路口隊列等候通行的車輛總數。隊列長度是衡量交通控制系統性能的指標之一。交通流量控制不到位會引發長長的隊列，說明交通流控制無法滿足較大車流量的需求；相比而言，短的隊列長度反映了交通流控制有能力允許更多車輛通過十字路口。隊列的長度將對其他參數產生影響，如延遲等待時間和行程時間[7]。

行程時間延遲是車輛從某一點行駛至另一點所需的時間。它與交通流控制里的車輛等待時間密切相關。長的隊列會使車輛的等待時間拉長，且將直接導致行程時間延遲更多。本文對交通流控制的重點在于減少十字路口交通流的隊列長度[8]。

其他一些相關參數有周期時間和浪費時間。周期時間是指所有相態在綠燈開始工作后,交通燈信號輪流一番后所需的時間。浪費時間是在等信號切換過程中以及因為駕駛員的駕駛行為而導致失去的時間。浪費時間可能對交通流控制有重要影響，因為它會隨信號燈切換次數的增多而增加。導致交通流控制方面時間浪費的一個重要因素就是黃燈時間。黃燈時間設立是為了區分綠燈和紅燈時間：考慮一定時間內可能有車輛在注意紅燈并停止往前。但這樣就降低了綠燈的效率，因為它已經占用了一個周期信號燈內的時間。因此，通過延長周期時間來降低信號燈的周期也是本文應用遺傳算法實現交通流控制的目的之一。

本文采用的一個參數是駛入交通流，它會增加車輛隊列長度并提高對綠燈的需求，尤其是在等紅燈時，由于車輛不允許在此時間段通過，因此隨著后續駛入的車輛，隊列長度會不斷拉長。

2　遺傳算法

遺傳算法是經過選擇、復制和變異過程后發現最優解的一種方法，由生物領域的遺傳演化衍生而來[9-10]。遺傳算法模擬自然進化論這一特點使其能夠一代接一代進行復制而同時去除不合適解。在遺傳算法里，最適合解或最優解會在整個過程結束后保存下來。

（1）染色體種群

需要對范圍內的染色體或解構成的種群進行判斷。在交通流控制方面，染色體是指交通燈系統里的綠燈時間。種群范圍設為大于0，因為綠燈時間不可能小于0。種群里的染色體個數也需要確定，因為解的數量決定了優化速度以及所求解的準確度。如果種群里生成的解過多，那么找到最適合的最優解所需時間就更長。但如果解的個數過少或偏小，遺傳算法可能會無法找到最適合的優化解。所以，必須仔細選出適當數目的染色體，因為交通流控制既要求速度也要求準確性。在交通流控制方面，染色體的個數設為50，指的是遺傳算法會在種群里生成50個解，且從中找到最適合的解。

需要對種群的初始范圍進行仔細篩選。如果得當，遺傳算法就能夠選出最佳興趣點。種群的初始范圍也就是遺傳算法開始時首批生成的種群的染色體范圍。范圍恰當的話將會為遺傳算法找到所需或最佳染色體節約大量時間。如果范圍太小，將影響染色體的多樣性，以致遺傳算法在操作過程中會遺漏掉的最佳點而陷入局部最佳。所以找到合適的初始范圍對交通流控制很重要，本文選用范圍為0-80。

（2）染色體生成與復制

另一個重要方面是遺傳算法需要進行的迭代次數。這是遺傳算法的停止規則之一，當遺傳算法運算所需的迭代次數確定好遺傳算法就會停止操作。對于交通流控制，遺傳算法的迭代次數是100次。這個次數是在認真考慮了迭代次數對遺傳算法有關的影響之后得出的。如果迭代次數太多，遺傳算法可能要執行較長的計算時間后才能停止下來。另一方面，如果迭代次數太少，遺傳算法的效率可能不如預期的好，因為遺傳算法無法從種群中找到最佳染色體。

交叉部分是指復制所需的選擇過程完成后來自父代或染色體的信息部分。在復制過程中，染色體都是成對選出來構成下一代染色體的父代。交叉部分決定了會有多少個父輩轉移到其子代來生成新的染色體。在交通流控制方面，交叉部分設為0.8。這說明一對父代A和B將會生成2個后代。后代的產生是根據父代的價值或信息而來的。所以一個后代將遺傳父代A的0.8和B的0.2部分；另一個后代將遺傳父代A的0.2及B的0.8部分，結果如公式（1）：

其中，X和Y是繼承的新生代。

（3）適應度函數

適應度函數是指讓遺傳算法從種群里篩選合適染色體所用到的規則或公式。種群里的每條染色體均將接受適應度函數測試，然后對應地都生成一個適應度值。本文適應度函數其實是一組簡單的規則或法則。交通的適應度函數將從某個具體時刻的所有3個相態里取出隊列長度方面的數據，然后與所有染色體進行測試，通過直接核實各相態排隊的車輛來達到對綠燈時間的優化。

適應度極限是遺傳算法的另一個停止規則。其實就是適應度函數要達到的一個目標。適應度極限是適應度函數所求的結果，因此一旦最佳適應度值達到極限，遺傳算法將會停止運算而輸出最合適的染色體。在交通流控制方面，適應度極限設為0且一旦染色體符合適應度函數，并生成一個為0或更小的適應度值，那么遺傳算法將視該染色體為最合適的優化解。

（4）遺傳算法模擬實驗

遺傳算法在交通流控制方面的模擬實驗在黃燈時間上來展開，是為了考察控制器對實際情況的反應。我們發現遺傳算法在交通燈系統的優化方面取得了成功，因為控制器能夠快速對隊列車輛做出反應，而相應地生成較長的綠燈相態。

遺傳算法模式下的輸出范圍，如圖2所示：

圖2　遺傳算法模型的輸出范圍

圖2（1）給出了600秒模擬過程中隊列交叉路口的車輛總數；圖2（3）顯示模擬過程中通過交叉路口的車輛總數。由圖2(4)可知，模擬實驗的最終結果反映了隊列車輛數明顯下降，因為控制器成功地讓本該等待下一個信號周期的7輛車順利通過了十字路口。

遺傳算法交通流控制模擬有6次信號燈系統循環，如圖2（2）所示。循環次數越多，浪費時間越多，也就降低交通燈系統的效率。由圖2（5）最后可知，遺傳算法成功地根據隊列長度優化了交通信號。

（5）駛入交通流帶來的影響

駛入交通流是我們的主要關注點，它會導致交通流控制處于混亂。駛入交通流持續不斷，是系統所不可控制的。即便駛入交通流很小也會引發一定的混亂。這方面的影響在紅燈或暫停時刻表現的尤為明顯，一旦不允許車輛通行十字路口，就會使車輛隊列拉的更長。所以要將駛入交通流控制在最低點才可確保十字路口的交通流順暢。如果只是將隊列長度或在等候信號燈的車輛分散到各個相態由遺傳算法來處理是不足以解決問題的，因為有駛入車輛在十字路口不會停下來。這個現象在圖1中相態A有明顯體現，而且相態B 和C仍然集聚了駛入的車流。只要對某個具體時刻的隊列長度進行分析，就會發現駛入交通流會使車輛隊伍拉長而在下一周期的交通燈系統顯現出來。

要使駛入交通流的影響達到最小，交通流控制就必須有能力預測該周期內的駛入交通流。這樣才可確保交通流控制對該周期信號燈做出更好的優化決策。采用遺傳算法的交通流控制在一個新周期開始時就將隊列長度從所有相態分割出來，使第一個相態駛入交通流的隊列長度產生的影響最小化。設一個新周期開始時的時間為0，第一個（A）相態的隊列長度不會增加，因為駛入交通流在這個時段還沒抵達十字路口。在第二個（B）和第三個（C）相態，情況則完全不同，因為第二相態需要在前一個周期后等信號燈切換才可通過，而第三個相態是最后一個相態，這就導致該相態比前兩個的等待時間都要長。隨著駛入車流不斷靠近十字路口，等待過程中第二和三個相態積累的車輛越來越多。

通過遺傳算法可以對因駛入交通流導致第二和第三相態的隊列長度拉長情況進行預測。由于第一相態不受駛入交通流的影響，它的綠燈時間（染色體）仍可以同樣的方式由遺傳算法計算得到。而對于第二個相態，遺傳算法將第二個相態的等待時間視作計算下一個新隊列長度的參數。這樣綠燈等待時間就會等同于第一個相態的。然后，第三個相態會將第一和第二個相態的總綠燈時間作為預測下一個新隊列長度的等待時間。遺傳算法的交通流控制綜合考慮第二和第三個相態的等待時間以及駛入交通流率，從而生成相應的綠燈時間（染色體）。

公式（2）給出了各個相態隊列長度的關系。變量k代表相態；變量是新隊列長度或待預測車輛的總數；變量是第二個相態的駛入交通流率，與各個相態的綠燈時間相乘，可以得到等待時間內累積的車輛。

3　實驗結果與討論

遺傳算法的交通流控制模擬條件與前面條件的一樣。時間仍是600秒，唯一不同在于駛入交通流與模擬實驗中的遺傳算法的優化算法密切相關結果如圖3所示：

圖3　相態1的仿真結果

圖3是交通相態1的模擬結果。虛線表示未采用遺傳算法的駛入交通流時情況；實線表示采用遺傳算法的駛入交通流情況。圖3可知綠燈期間車輛數分階段性減少。

圖3中，實線較之虛線波動幅度不大。虛線反映了極低和極高值，說明優化失敗，因為一個循環周期綠燈時間過長，且期間十字路口積累的車輛太多。如果某個相態的綠燈時間過長，所有相態之間就無法達到相互平衡，因為其他相態需要犧牲自己的綠燈時間來填補它。結果，其他相態積累的車輛數過多。圖中的極高值也說明所有相態之間的綠燈時間分配未達到均衡狀態，導致有些相態綠燈過長而其他相態積累的車輛過多。與虛線不同的是，實線表現得更平穩，比虛線更適合也便于車輛通過。這表明，將駛入交通流納入遺傳算法交通流控制來考慮，模擬結果得到改進。應用遺傳算法來分析駛入交通流便于更多車輛在相同模擬時間內通過交叉路口，同時能夠更均衡地分配綠燈時間。

第二個相態的有關模擬結果如圖4所示：

圖4　相態2的仿真結果

如圖4(a)所示，其中虛線代表未采用遺傳算法的駛入交通流控制情況；實線指采用了遺傳算法的駛入交通流控制情況。很明顯采用了算法的交通流控制情況要比未采用的效果理想。在模擬結束時通行的車輛比之前遺傳算法的要多。實線也提供了模擬過程中的高峰值，試圖生成更多的綠燈時間來快速放行更多車輛。如圖4(b)所示：

圖4　相態2的仿真結果

虛線和實線分別給出了之前遺傳算法和考慮了第三個相態階段駛入交通流的遺傳算法。結果與第二個相態相比大同小異。整個模擬過程中，實線表現要優于虛線，其中實線的車輛增加情況在模擬結果結束時有所下降。

4　總結

本文對交通特征的研究將遺傳算法引入交通流控制，通過自我調整得以找出最佳染色體或解。本文對各種交通特征的影響做了分析。將隊列長度，即在十字路口等待通行的車輛總數作為一個性能指標進行分析。此外，隊列長度可能對交通流控制帶來一些影響，因為車輛隊列太長的話就無法快速放行交通流，也就難以保障十字路口的交通流暢通無阻。循環周期和交通信號周期次數也對交通流控制影響巨大。這是因為循環周期是持續時間的長短，決定著交通流控制允許放行之前在十字路口的等待的車輛隊列長度。交通信號周期的次數將影響浪費時間的長度，而反過來這又取決于交通流控制情況。浪費時間是指因為黃燈以及駕駛員行為的緣故在交通流控制過程中失去的時間。模擬結果表明遺傳算法能成功應用實現交通流控制。

參考文獻

[1] 文孟飛. 城市智能交通系統交通流協同優化與誘導關鍵技術研究[D].長沙:中南大學,2013.

[2] 蔡蕾. 城市平面交叉路口交通信號優化控制[D].吉林:吉林大學,2007.

[3] 錢俊明,李鑫偉. 北京市交叉路口交通流量分析研究[J].科技和產業,2013,12:113-115

[4] 周申培. 考慮排放因素的城市交叉口交通信號控制策略的研究[D].武漢:武漢理工大學,2009.

[5] 唐艷. 城市交叉路口交通流的優化控制[J]. 農業裝備與車輛工程,2007,08:45-47.

[6] 曾松林. 城市單交叉路口交通信號的控制方法研究[D].成都:西南交通大學,2013.

[7] Mohammad Reza Jabbarpour Sattari, Hossein Malakooti, Ali Jalooli, Rafidah Md Noor.A Dynamic Vehicular Traffic Control Using Ant Colony and Traffic Light Optimization[J].Advances in Intelligent Systems and Computing , 2014(240): 57-66.

[8] Andr Luiz Cunha, Jos Elievam Bessa Jr.Genetic Algorithm for the Calibration of Vehicle Performance Models of Microscopic Traffic Simulators[J].Lecture Notes in Computer Science, 2009(5816):3-14.

[9] 宋曰聰,胡偉,張濤. 基于遺傳算法的交通流量組合預測研究[J]. 微計算機信息,2007,29:55-56.

[10] 張婉琳. 遺傳算法優化支持向量機的交通流量預測[J].激光雜志,2014,12:116-119.

收稿日期：（2015.03.11）

作者簡介：王雪梅（1978-），女，哈爾濱，黑龍江工商學院，計算機科學與技術系，講師，博士，研究方向：信息融合，數據挖掘，哈爾濱，150025李曉峰（1978-），男，哈爾濱，黑龍江外國語學院，信息科學系，副教授，博士，研究方向：數據挖掘，智能算法，哈爾濱，150025

基金項目：黑龍江省教育廳科學技術研究項目（12543076）；教育部教師科研專項基金（CTF120772）

文章編號：1007-757X(2015)12-0012-04

中圖分類號：TP301.6

文獻標志碼：A