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

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