遺傳算法在交叉口配時優(yōu)化中的應(yīng)用.doc

遺傳算法在交叉口配時優(yōu)化中的應(yīng)用摘要：介紹了模糊控制、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法、粒子群算法、多智能體等智能控制方法，詳細分析了遺傳算法的在交通控制領(lǐng)域的實際應(yīng)用案例，更深入了解和掌握了交通智能算法的應(yīng)用。關(guān)鍵詞：優(yōu)化；相位； 配時參數(shù)； 遺傳算法1 引言隨著社會經(jīng)濟的發(fā)展，交通量急劇增長，交通擁堵加劇，交通事故頻發(fā)，特別是在一些大城市，交通問題已成為制約城市經(jīng)濟發(fā)展的瓶頸1。為此，人們提出建立智能交通系統(tǒng)(ITS)。作為ITS的重要組成部分，交通管理系統(tǒng)（ATMS）在改善交通流秩序、提高交通安全性等方面發(fā)揮積極的作用。其中，交通信號優(yōu)化控制是保證城市交通安全、有序、暢通、快速、高效運行的重要途徑。當(dāng)前，隨著交通控制智能化的不斷提高，智能控制方法在交通信號控制的重要性日益凸顯。按照控制原理的不同，傳統(tǒng)的交通信號控制分為定時控制和感應(yīng)控制。定時控制按事先設(shè)定的配時方案運行，其配時的依據(jù)是交通量歷史數(shù)據(jù)。感應(yīng)控制是某相位綠時根據(jù)車流量的變化而改變的一種控制方式，其中車流量可由安裝在平面交叉口進口道上的車輛檢測器測量。這兩種控制方法存在共同的局限性：以數(shù)學(xué)模型為基礎(chǔ)。由于城市交通系統(tǒng)中被控對象過程的非線性、較大的隨機干擾、過程機理錯綜復(fù)雜以及現(xiàn)場車輛檢測的誤差，建立精確的數(shù)學(xué)模型非常困難，這就造成了算法本身就有一定的缺陷。即使經(jīng)過多次簡化己建立的數(shù)學(xué)模型，它的求解還須簡化計算才能完成。所以傳統(tǒng)的交通控制方法并不能有效地解決目前復(fù)雜的交通問題。針對傳統(tǒng)交通控制的固有缺陷和局限性，許多學(xué)者將模糊控制、神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法、多智能體技術(shù)等人工智能基礎(chǔ)研究方法同常規(guī)交通控制方法結(jié)合應(yīng)用。2 交通優(yōu)化智能算法2.1 模糊邏輯 模糊邏輯是一種處理不確定性、非線性等問題的有力工具，與人類思維的某些特征相一致，故嵌入到推理技術(shù)中具有良好效果。模糊邏輯不需要獲取模型中的復(fù)雜關(guān)系，不需要建立精確的數(shù)學(xué)模型，是一種基于規(guī)則的智能控制方式，特別適用于具有較大隨機性的城市交通控制系統(tǒng)。2.2 人工神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò)是模擬生物的神經(jīng)結(jié)構(gòu)以及其處理信息的方式來進行計算的一種算法。它具有自適應(yīng)、自組織和自學(xué)習(xí)能力，在認知處理、模式識別方面有很強的優(yōu)勢，最顯著特點是具有學(xué)習(xí)功能。人工神經(jīng)網(wǎng)絡(luò)適用于非線性時變性系統(tǒng)的模擬與在線控制，交通控制系統(tǒng)正是一個非線性、時變系統(tǒng)。2.3 遺傳算法 遺傳算法是運用仿生原理實現(xiàn)在解空間的快速搜索，廣泛應(yīng)用于解決大規(guī)模組合優(yōu)化問題。它是一種比較先進的參數(shù)尋優(yōu)算法，對于不易建立數(shù)學(xué)模型的場合其實用價值較為突出，是以同樣適用于交通工程。1997年，Kiseok和Michael等應(yīng)用遺傳算法對交通網(wǎng)絡(luò)內(nèi)的交叉口信號相位進行設(shè)計2，在交叉口形成的沖突點，結(jié)果顯示該方法給出的相位方案要優(yōu)于TRANSYT給出的方案。同年，Memon等人給出了利用遺傳算法進行信號配時方案設(shè)計的研究結(jié)果。陳小鋒，史忠科針對典型的多車道雙向交叉路口的交通流分布，建立四相位控制的動態(tài)交通控制模型，采用遺傳算法同時對信號周期時長和相位綠燈持續(xù)時間進行優(yōu)化3。承向軍等對到達車輛數(shù)目進行模糊分類，將不同數(shù)量車輛的信號控制決策方案以規(guī)則集形式存儲在知識庫中，利用改進的遺傳算法對交叉口信號模糊控制器的模糊規(guī)則進行優(yōu)化，建立了新的優(yōu)化算法4。顧榕等將免疫遺傳學(xué)思想運用到交通信號控制中，提出一種新的相位配時優(yōu)化算法，實驗結(jié)果充分驗證了該算法處理交通配時優(yōu)化問題的可行性和有效性5。2.4 蟻群算法 蟻群算法是一種模擬進化算法，它是一種求解組合最優(yōu)化問題的新型通用啟發(fā)式方法，該方法具有正反饋、分布式計算和富于建設(shè)性的貪婪啟發(fā)式搜索的特點。2.5 粒子群算法 粒子群優(yōu)化算法是由Eberhart博士和Kennedy博士于1995年提出，是基于對鳥群、魚群捕食的行為模擬研究而來。同其他基于群智能(Swarm Intelligence)的隨機優(yōu)化算法相比，PSO算法具有收斂速度快、設(shè)置參數(shù)少、程序?qū)崿F(xiàn)異常簡潔、具有深刻的智能背景等特點。2.6 多智能體技術(shù) Agent由Minsky在1986年首次提出，一般認為Agent指駐留在某一環(huán)境下，能持續(xù)自主地發(fā)揮作用，具備駐留性、反應(yīng)性、社會性、主動性等特征的計算實體。隨著車輛數(shù)和城市路網(wǎng)規(guī)模的增大，信號控制系統(tǒng)的復(fù)雜性增大，同時由于交通流在信息、控制方面固有的分布性，采用多Agent系統(tǒng)構(gòu)建城市交通控制系統(tǒng)的計算環(huán)境已成為交通系統(tǒng)協(xié)調(diào)控制的熱點。3 遺傳算法應(yīng)用案例3.1進出口道綜合效率最優(yōu)的交叉口配時參數(shù)優(yōu)化3.1.1優(yōu)化問題概述進出口道綜合效率最優(yōu)的交叉口配時參數(shù)優(yōu)化問題 6如下, 配時參數(shù)優(yōu)化目標為T時間段內(nèi)，交叉口中所有進口路段及出口路段的周期平均車輛數(shù)之和最小?？紤]行人過街的安全性及駕駛員容忍極限等因素的限制，交叉口的相位綠燈時長應(yīng)滿足如下約束：其中，和分別為相位f的最小綠燈時長和最大綠燈時長(S)。所有相位的綠燈時長及綠燈間隔時間之和即為交叉口的周期時長，表達式為：其中，C 交叉口周期時長(S)；If 相位f與下一相位的綠燈間隔時間(S)。3.1.2 道路交通條件概述在每一個時間間隔KC內(nèi)，檢測器應(yīng)能準確檢測到輸入路段的流量數(shù)據(jù)。式(17)所示的數(shù)學(xué)規(guī)劃問題即是尋求在特定的約束條件下使得目標函數(shù)值最小的Tf值，且優(yōu)化得到的周期時長及相位綠燈時長可作為下一時間間隔內(nèi)配時參數(shù)的重要理論參考。本數(shù)學(xué)規(guī)劃問題可用智能算法遺傳算法進行求解。以如圖1所示的十字交叉口為例進行過飽和和低飽和情況下的實例分析，假設(shè)四個進口道均為直行單車道，交叉口采用兩相位控制，且在過飽和情況下，四個進口道的車輛到達率分別為0.3、0.2、0.2、0.25 PCu/S，低飽和情況下進口道的車輛到達率分別為0.15、0.1、0.1、0.125 PCu/S。四個出口道通行能力分別為0.3、0.25、0.25、0.20 PCu/S，低飽和狀態(tài)下路段初始容納車輛數(shù)均為10 PCu，過飽和狀態(tài)下路段初始容納車輛數(shù)為50 PCu。8條進口路段及出口路段的最大容納能力及路段長度如表1所示。表1 進出口路段最大容納能力及路段長度進出口編號i12345678Ni10010012080908050120Li700700840560630560350840本文以10個信號周期為優(yōu)化時間間隔，假設(shè)所有路段的自由流速度均為14M/S，結(jié)合上述輸入?yún)⒘?，通過遺傳算法可以求得節(jié)點的配時參數(shù)值。3.1.3算例求解遺傳算法是依據(jù)適者生存、優(yōu)勝劣汰的進化原則對包含可能解的群體反復(fù)進行遺傳操作, 尋求最優(yōu)或近似最優(yōu)解的隨機搜索算法，已被廣泛應(yīng)用于數(shù)學(xué)優(yōu)化、自動控制、圖像處理與模式識別等方面，主要內(nèi)容包括編碼、初始種群產(chǎn)生、適應(yīng)度計算及遺傳操作4個部分。(1) 編碼。由于行人過街時間及排隊容忍時間等條件的制約，相位應(yīng)有最大綠和最小綠的限制，其取值一般分別為60S12和15S13。設(shè)定本文的求解精度為整數(shù)，由于區(qū)間長度為60-15=45，區(qū)間15,60 必須分成45等份。32=254526=64，因此編碼的二進制串長至少需要6位。(2) 種群產(chǎn)生。種群規(guī)模設(shè)定為50，初始種群的染色體隨機選取。(3) 適用度計算。考慮本文目標函數(shù)在定義域內(nèi)的取值均大于0，而且是尋找函數(shù)最小值，所以可直接引用目標函數(shù)作為適用度函數(shù)來評價染色體的優(yōu)劣。即：(4) 遺傳操作。采用跨代精英選擇機制，設(shè)定交叉概率PC=0.25，變異概率PM=0.01，交叉變異后形成的中間種群與父代種群合并后按照適應(yīng)度進行排序，且50%個體形成下一代種群。按照上述基本遺傳算法，設(shè)定南北直行為第一相位，東西直行為第二相位，則滿足3.1節(jié)所設(shè)定的兩種交通狀況下，式(17)的最優(yōu)解分別為：過飽和狀態(tài)下，T1=59S、T2=60S，優(yōu)化目標函數(shù)值為581PCu；低飽和狀態(tài)下，=48S，=18S，優(yōu)化目標函數(shù)值為89PCu。進口道及出口道周期平均車輛數(shù)之和與相位有效綠燈時長的關(guān)系分別如圖3、4所示。假設(shè)所有相位的綠燈間隔時間均為3S，兩種狀態(tài)下的交叉口的周期時長為：通過上述算例分析可得，本文模型可同時適用于低飽和及過飽和狀態(tài)的孤立交叉口信號配時參數(shù)優(yōu)化，且在過飽和狀態(tài)下，交叉口各相位的綠燈時長均接近最大綠。低飽和狀態(tài)下，由于相位2關(guān)鍵車流的車輛到達率與相位1的關(guān)鍵車流車輛到達率接近，且進口道4屬于瓶頸路段，因此，為避免路段排隊長度的可能上溯，配時參數(shù)優(yōu)化結(jié)果中的遠大于。 圖1 低飽和狀況下優(yōu)化指標與相位綠燈時長關(guān)系圖 圖2 過飽和狀況下優(yōu)化指標與相位綠燈時長關(guān)系圖3.2交通網(wǎng)絡(luò)多交叉口配時優(yōu)化以某城市某區(qū)主要交叉路口的交通信號控制問題為背景，構(gòu)造交通網(wǎng)絡(luò)中以多交叉口滯留的車輛數(shù)最少為目標的優(yōu)化模型，求解仿真數(shù)據(jù)，得到實時控制的配時方案。3.2.1道路交通條件采用的城市道路網(wǎng)如圖3所示。圖3 城市道路網(wǎng)結(jié)構(gòu)簡圖選取A、C、I三個主要交叉口，將該三交叉口視為一個網(wǎng)絡(luò)主要節(jié)點，三個交叉口的交通流向和相位設(shè)置如圖4所示。圖4 主要交叉口交通流向和相位結(jié)構(gòu)設(shè)置其中，路口A的相位顯示順序如圖5（相位1相位2相位3相位4）。圖5 交叉口A的相位顯示順序路口C、I的相位顯示順序如圖（相位1相位2相位3）。圖6 交叉口C和I的相位顯示順序3.2.2模型參數(shù)的標定與建模分析l為節(jié)點編號，取值1,2,3分別表示路口A、B、C三個交叉口。i為相位編號，取值1,2,3,4分別表示相位1，相位2，相位3，相位4；j為各相位的方向編號，取值1,2,3,4分別表示東，南，西，北（上北下南左西右東）；k為車道編號，取值1,2,3分別表示左轉(zhuǎn)，直行，右轉(zhuǎn)。Axljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道的小車到達率；Axljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道的小車到達率；Axljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道的大車到達率；Mxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道的小車駛離率；Mxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道的小車駛離率；Txljk(i)：表示第x個周期，第l個交叉口，相位i的綠燈顯示時間；Txl：表示第x個周期，第l個交叉口的周期；SAxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道到達路口的車輛數(shù)；SMxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道駛離路口的車輛數(shù)；T：表示各交叉口周期的最小公倍數(shù)； Pl：表示交叉口l的放行矩陣，其元素為Pljk(i)；Pljk(i)：表示同一個周期內(nèi)，各交叉口的放行矩陣元素，其值為0或1，即取值為1時表示第l個交叉口，相位i，方向j中車道k車輛放行；取值為0時表示禁止放行；uxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道單位時間內(nèi)混合車輛總流入車輛數(shù)；vxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道單位時間內(nèi)混合車輛總駛離車輛數(shù)；Sxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道總滯留車輛數(shù)；yxljk(i)：表示第x個周期，第l個交叉口，相位i中j方向k車道的黃燈時間；nl：表示交叉口l的相位數(shù)。將大車折算成標準小汽車，折算系數(shù)取為，為調(diào)和參數(shù)，則第x個周期，第l個交叉口，相位i中j方向k車道單位時間內(nèi)混合車輛總流入車輛數(shù)uxljk(i)為：uxljk(i)= Axljk(i)+ Axljk(i)+第x個周期，第l個交叉口，相位i中j方向k車道單位時間內(nèi)混合車輛總駛離車輛數(shù)vxljk(i)為：vxljk(i)= Mxljk(i)+ Mxljk(i)+則第x周期i相位時間段內(nèi)到達的車輛數(shù)SAxljk(i)為：SAxljk(i)= uxljk(i)Txljk(i)第x周期i相位時間段內(nèi)到達的車輛數(shù)SMxljk(i)為：SMxljk(i)= vxljk(i)Txljk(i)Pljk(i)第x周期交叉口l方向j車道k滯留的車輛數(shù)Sxljk(i)為：Sxljk(i)= S（x-1）ljk(i)+ SAxljk(i)- SMxljk(i)T周期中有A1個T1 ,A2個T2 , A3個T3, ,在T個周期內(nèi)由實時預(yù)測量實時確定最佳周期Ti。由以上分析，以滯留車輛數(shù)最少為目標的實時配時數(shù)學(xué)模型為：約束條件為：,，采用遺傳算法求解，其中群體大小為M，終止代數(shù)為T，初始交叉概率為PC，初始變異概率為PM。，以仿真流量為基礎(chǔ)數(shù)據(jù)，以 MATlAB為工具，可計算得到交叉口的每個周期的配時方案。4結(jié)語智能控制具有傳統(tǒng)控制方法難以比擬的優(yōu)越性，它通過模擬人的智能的決策方法來達到控制的目的，在處理復(fù)雜性、不確定性的問題時，顯示出強大的控制效果。智能控制方法的最大特點是其控制算法是具有強逼近非線性函數(shù)的能力，不依賴于精確的數(shù)學(xué)模型。利用模糊控制、神經(jīng)網(wǎng)絡(luò)、遺傳算法等智能控制方法能取得比定時控制與感應(yīng)控制更好的效果。但是單一使用一種智能控制方法，在策略和理解上都存在一定的不足，如果把多種智能控制方法結(jié)合起來，充分利用它們特點上的互補，可以極大的改進控制的效果。因此，采用多種智能控制方法的結(jié)合對交叉口的控制是一種必然的趨勢。但是，要實現(xiàn)交通信號的智能控制，必須首先獲