基于廣義離散事件動態系統的多路口智能交通流量控制

摘要:在傳統意義上的離散事件動態系統中事件定義的基礎上，提出了廣義離散事件動態系統的思想。通過對事件屬性劃分的動態調節，使事件的辨識條理化。文中對公路交通中的多路口流量建模進行了分析。基于廣義離散事件動態系統的調度思想，利用人工代謝算法對交通流量進行了控制分析。分析結果表明:廣義離散事件動態系統能對系統的狀態進行進一步的細化。人工代謝算法與該系統相配合，通過代謝算子的調節能較快地實現整個系統負荷均衡，能對流量的變化進行自適應調節。

關鍵詞:新陳代謝;廣義離散事件動態系統;事件辨識;人工代謝算法;自適應調度

中圖分類號:TP182 文獻標識碼:A

Intelligent Transportation Traffic Flows Control for Multi-crossover Road Based on Generalized Discrete Event Dynamic System

HU Yang#8224; ， GUI Wei-hua

(School of Information Science and Engineering， Central South University， Changsha， Hunan，410083， China)

Abstract:The idea of Generalized Discrete Event Dynamic System(GDEDS) is proposed based on the definition of traditional discrete event dynamic system. The events can be identified according to their dynamic features. The model of multi-crossover road is analyzed in the paper. The traffic flows are controlled by artificial metabolic algorithm based the scheduling plan of generalized discrete event dynamic system. The results state that the system status can be evaluated by generalized discrete event dynamic system better. The load balancing in system can be realized by the regulating of metabolic operators under the integrating artificial metabolic algorithm with generalized discrete event dynamic system. The level of adaptive scheduling for traffic flows can be reached also.

Key words:metabolism; generalized discrete event dynamic system; event identification; artificial metabolic algorithm; adaptive scheduling

離散事件動態系統(DEDS)的概念自從20世紀80年代提出后，得到了很大的發展[1-2]，成為解決計算機集成制造系統(CIMS)、智能交通系統(ITS)、車間調度等領域內流水排序、優化控制問題的重要工具[3]。在經典意義上的DEDS理論中，事件的狀態分為3種:已處理事件、處理中事件、未處理事件。其中“處理”的概念依所應用的領域不同而定。但在實際應用時，上述劃分則顯粗略。如:同樣為“未處理事件”，有些事件的狀態已接近“處理中事件”，而另一些事件的狀態則遠未達到“待處理”的程度。以交通系統為例，當信號是紅燈時，同樣是處于等候狀態的車輛，因其在等候隊列中的前后位置不同而導致其發動機狀態有顯著區別。排在等候隊伍前列的車輛，已做好出發準備。而對于排在等候隊伍后部分的車輛，可能發動機已經熄火。從另一個角度看，由于在交叉路口原先行駛方向一致的車輛將出現流量分支，故交通信號周期也應隨流量的變化而動態改變。上述事例說明傳統意義上的離散事件狀態劃分已較難適應日益更新的社會需要，因此需要對離散事件的狀態進行進一步的細化辨識[4]。

本文提出的廣義離散事件動態系統在一定程度上克服了DEDS中事件定義模糊的缺點。通過對事件的狀態及等級按實時控制的要求進行動態劃分，提高系統對離散事件狀態的辨識能力，從而節余了調度時間，優化了調度性能。

1多路口交通流量建模

在多路口交通系統中，交通流量存在分支、匯合的問題。多路口交通流量圖如圖1所示。多路口模型中的流量可劃分為四類優先級。按優先級從高到低排列順序如下:等級1:V1，V2，V3，V4，V5，V6，V8，V9;等級2:V11，V12，V14，V15;等級3:V7，V10;等級4:V13，V16。在這四類等級中，等級3中的V7與V10，等級4中的V13與V16均為起始端點不同的車流，狀態容易被辨識。等級2中的V11與V15，等級4中的V12與V14的狀態符合廣義離散事件特征。開始車流量方向相同，都向Ni點運行，快到Ni點后再逐漸進行分流。對于等級1的情況，優先級的劃分較為復雜。不但需考慮車輛直行時的狀態，也需考慮直行后未來可能的轉向狀態。在等級1的8類車流量的優先級又可分為4類，分別用等級11，等級12，等級13和等級14表示。其中等級11的優先級最高，等級14的優先級最低。具體的劃分是:等級11:V3，V6;等級12:V2，V5;等級13:V8，V9;等級14:V1，V4。

在圖1中，設交通主干道為X—N1—N2—…—Ni—…—Nn—Y，設其方向為南北向。X和Y分別表示多路口的兩個終端。Ni(i=1-n)表示第i個十字路口，Ai(i=1-n)表示第i個十字路口的西側端點，Bi(i=1-n)表示第i個十字路口的東側端點。對應的車道Ai-Bi(i=1-n)表示第i個十字路口的非主干直行車道。

對第Ni個十字路口而言，主干道直行車流量可表示為: ， ，

，

， ，

。

主干道轉向車流量包括: ， ， ， 。

非主干道直行車流量包括: ， 。

非主干道轉向車流量包括: ， ， ， 。

2人工代謝算法

2.1代謝優化模型

在生物體內部，時時有大量的生物化學反應發生。這些反應促進生物體進行新陳代謝，實現細胞的更新換代。生物就是通過這樣的“吐故納新”機制而維持生命的正常運行。這些新陳代謝反應均受到生物酶的控制。生物酶決定反應的方向、代謝率的高低和代謝過程的停止和啟動。針對不同類型的代謝物，在生物體內部形成一條條代謝通路。代謝網絡通過對各條代謝路徑的協調，實現整個生物體功能的正常運轉[5-6]。

代謝平衡方程如式(1)所示。其中A和B表示反應物(生物化學中稱為“底物”)，C和D表示生成物，x是催化酶。雙向箭頭表示反應的可逆性。反應進行的方向由底物、生成物和催化酶的濃度共同決定。

.(1)

圖2 代謝優化算法流程圖

Fig.2 Metabolic optimization algorithm flowchart

與其他智能學習算法不同，代謝優化算法的核心是代謝濃度平衡，濾除過時的信息。其基本思想是:將被優化系統看成一個代謝體系，當各條代謝路徑均實現了代謝物的濃度平衡時，整個系統的代謝反應速率將達到穩態。此時系統代謝處于最旺盛階段，對應的代謝路徑即為相應代謝物的最優代謝路徑。因為如果代謝路徑不是最優路徑，就必然會出現代謝停滯的狀態，此時代謝濃度將產生濃度差，代謝反應速率也將出現波動。系統將繼續尋找更好的代謝路徑調整代謝濃度，以實現最終的濃度穩態平衡。此時對應的代謝濃度即為被優化函數的最優解。

代謝優化算法引入了平衡算子和抑制算子2種代謝算子，分別對應代謝路徑上流量濃度的正向和反向的催化強度。代謝算子的初始值由起始反應時底物和生成物的濃度決定。人工代謝優化算法通過調整代謝算子來對底物和生成物的濃度進行調節。當底物和生成物的濃度差為零時實現代謝平衡，代謝反應速率達到最大值，尋優結束。代謝優化算法的流程圖如圖2所示。A，B，C和D代表不同的底物或生成物，是隨時間變化的量。

在圖2中，由于濃度差和速率差而很難實現在數學意義上的嚴格等于零，故采用等價無窮小ε表示濃度差和速率差接近于零。完成算法流程后，輸出的生成物濃度為目標函數穩態最大值。若將其轉化為生成物的量，則可得到系統的最大輸出值。

2.2代謝算法編碼

人工代謝算法的編碼規則如下:底物A和生成物C的濃度區間在[0，1]之間，底物A和生成物C的量各占整個反應平衡方程中全部物理量的比例可計算得出，即為其濃度。將其濃度用二進制編碼表示。設采用n位二進制代碼的編碼方式，即將實際濃度映射成[0，2n-1]上的0和1組成的編碼串。酶的濃度也用n位二進制代碼的編碼方式表達，即為[0，2n-1]上的0和1組成的編碼串。酶的濃度的初始值為隨機給出。根據酶與底物的匹配情況，通過代謝算子對酶的編碼進行邏輯關系的調節，使酶與當前底物更好地匹配。匹配的原則是A的編碼和X的編碼相“同或”的結果對應的二進制數應盡可能逼近1。其中平衡算子ke的作用是隨機選擇酶中的二進制數位，使數位上的值與底物對應數位上的值相等;抑制算子ki的作用是隨機選擇酶中的二進制數位，使數位上的值與底物對應數位上的值不相等;平衡算子ke和抑制算子ki的值在[0，1]之間，統稱為代謝算子。在得到平衡算子ke和抑制算子ki的值后，按其值對應的百分數，決定所隨機選擇酶中的二進制數位的位數。平衡算子ke在一個計算周期中的值為當前全部底物的濃度;抑制算子ki在一個計算周期中的值為全部生成物的濃度。當代謝速率達到穩態，即d(A(t))/dt<ε時(ε為某一較小值)時，代謝終止。

在交通流量調度中，將一個十字路口的信號調度看成是一個生化反應過程。進入該路口的車輛看成底物;駛出該路口的車輛看成生成物。信號燈的調節看成是酶的催化調節。通過酶的催化調節實現流量均衡，減少擁塞[7-10]。

3代謝算法在多路口流量調度中的應用

在廣義離散事件動態系統中，系統可看作一個多級自動機，用五元組G=(Q，E，δ，q0， Qm)來定義。Q為狀態集，E為事件集，δ:Q×E→Q為一個狀態轉移映射，當某個事件ek∈E發生時，現狀態qk轉移到下一狀態qk+1=δ(qk，ek)。q0∈Q為初始狀態，Qm為系統到達的目標集。其中的狀態轉移映射為分階段進行。事件的分類不是確定的。隸屬于某個事件集的類型[11]。

本文以三路口為例，采用人工代謝算法對信號進行調度。三路口交通圖如圖3所示。設車輛的到達服從泊松分布。16支車流的分布密度為: ，其中λ為隨機數，表示流量的不確定性[12-14]。

圖3三路口交通流量圖

Fig.3 Three crossover roads traffic flowchart

對于圖3所示的三路口系統，代謝算法編碼采用16位二進制編碼。即底物A，生成物C和酶的濃度均采用16位二進制編碼。對第Ni(i=1-3)個十字路口，V1～V16的流量各用16位二進制編碼來隨機產生。酶(信號燈)的調節作用由2.2節算法規則產生。通過調節規律，使交通調度有序化。設三路口的初始流量如表1所示。通過代謝算法調節后，三路口的信號燈周期見表2。通過流量反饋表明，該信號周期的調節方式能有效地跟隨流量的實時變更，實現長期、穩定的調節。

4結論與展望

本文通過對離散事件動態系統中類似屬性事件的分析，提出了廣義離散事件動態系統的思想。通過對事件“粒度”的動態劃分來對事件進行動態調度。通過對生化反應機理的分析提出了人工代謝系統的思想。將調度過程看成是一個酶催化反應過程，利用代謝平衡的原理實現催化反應的濃度平衡，進而實現調度的優化。將這一原理應用于交通調度過程，有機地實現了各調度過程的參數協調。經上述分析，有如下結論:

1)通過廣義離散事件動態系統，對事件屬性進行動態劃分和逐級分解，避免了傳統事件調度過程的繁雜性，簡化了系統模型。

2)利用人工代謝系統，用基于酶的催化代謝模擬事件的處理過程。通過代謝算子調節和代謝速率的評估確定調度的進程。該算法和廣義離散事件動態系統相互配合，有機地實現了調度的優化。

3)通過代謝物的濃度變化及時地調整催化酶的濃度，催化酶的濃度又影響代謝物濃度的變化，形成了反饋調節，使代謝算法具有自適應性。根據算法的收斂規則，代謝物的濃度將在一定時間后達到平衡，實現了調度過程的負荷隨機變化和平衡之間的協調。

本文待完成的工作包括:廣義離散事件動態系統理論的進一步完善，代謝催化鏈中遞階調節規律的整理以及代謝算法和其他智能算法的配合等。

參考文獻

[1] 郭雷，程代展，馮徳興.控制理論導論——從基本概念到研究前沿[M].北京:科學出版社，2005.

GUO Lei， CHENG Dai-zhan， FENG De- xing. Introduction to control theory: from basic concept to the forefront of research [M]. Beijing: Science Press， 2005.(In Chinese)

[2] 鄭大鐘，趙千川.離散事件動態系統[M].北京:清華大學出版社，2001.

ZHENG Da-zhong， ZHAO Qian-chuan. Discrete event dynamic system[M]. Beijing: Tsinghua University Press， 2001. (In Chinese)

[3] 劉智勇.智能交通控制理論及其應用[M].北京:科學出版社，2003.

LIU Zhi-yong. Intelligent transportation control theory application[M]. Beijing: Science Press， 2003.(In Chinese)

[4] CHUNG S L， WU J C， LI C L. System identification of discrete event systems[J]. Journal of the Chinese Institute of Engineers， 2004， 27(2):203-210.

[5] 張蓓.代謝工程[M].天津:天津大學出版社，2003.

ZHANG Bei. Metabolic engineering [M]. Tianjin: Tianjin University Press， 2003. (In Chinese)

[6] A.G.馬蘭戈尼著.酶催化反應動力學——方法與應用[M]. 趙裕蓉，張鵬，譯.北京:化學工業出版社，2007.

MARANGONI A G. Enzyme kinetics-a modern approach[M]. Beijing: Chemical Industry Press， 2007.(In Chinese)

[7] PINEDO M. Scheduling: Theory， Algorithms， and Systems [M]. 2rd. Beijing: Tsinghua University Press， 2005.

[8] LEE C Y， LEUNG J， YU G. Two machine scheduling under disruptions with transportation considerations[J].Journal of Scheduling， 2006， 9(1):35—48.

[9] ERIC H D. The regulatory genome—gene regulatory networks in development and evolution[M]. Science Press，2007.

[10] DAN H S， THOMAS A R， WILLIAM A H. Development of the nervous system [M]. Beijing: Science Press， 2007.

[11] 楊冬梅，張慶，姚波，等.廣義系統[M].北京:科學出版社，2004.

YANG Dong-mei， ZHANG Qing，YAO Bo， et al. Generalized system[M]. Beijing: Science Press， 2004.(In Chinese)

[12] 鄧愛民，王曉明，陳興，等.城市中轉型配送中心布局優化研究[J].湖南大學學報:自然科學版，2009，36(1):89-92.

DENG Ai-min， WANG Xiao-ming， CHEN Xing， et al. Research on layout optimization of city transshipment distribution center [J]. Journal of Hunan University: Natural Sciences， 2009，36(1): 89-92.(In Chinese)

[13] 潘登，鄭應平.車輛追蹤運行的離散模型與最優控制[J].動力學與控制學報，2008，6(1):92—96.

PAN Deng， ZHENG Ying-ping. Discrete model and optimal control of car following [J]. Journal of Dynamics and Control， 2008， 6(1):92-96. (In Chinese)

[14] 胡揚，桂衛華.基于人工代謝系統的物流管理[J].計算機工程與科學，2008，30(10):51—54.

HU Yang，GUI Wei-hua. Logistics management based on artificial metabolism system [J]. Computer Engineering and Science， 2008，30(10): 51-54.(In Chinese)