基于遺傳算法的城市交通安全系統的設計

張 穎(重慶交通大學信息科學與工程學院,400074)

?

基于遺傳算法的城市交通安全系統的設計

張 穎
(重慶交通大學信息科學與工程學院,400074)

摘要：城市交通安全系統是城市智能交通系統中十分重要的組成部分。本文針對目前城市特點及交通現狀，詳細介紹了遺傳算法在系統實現中的關鍵技術，圍繞系統結構、數據庫建模，對安全系統的設計與實現進行研究，最后以交通誘導的處理為例闡述了系統的實現.

關鍵詞：安全系統;數據庫;遺傳算法

0　引言

近年來，隨著經濟的發展，交通需求日益增加。城市規模與數量的迅速增長的同時，城市社會格局也發生著巨變，對城市建設提出了諸多要求。同時，生活水平的提高使市民出行的數量大大提高、出行距離的線性增長，對城市道路交通系統建設的要求在“量”上大大提高，然而在城市道路交通系統的建設與管理上，單純依靠交通設施的建設，已經遠不能解決日益突出的城市交通擁堵、交通事故頻發、交通環境惡化等世界各國所面臨的共同問題。

大力發展智能運輸系統，提高城市交通系統的管理技術，是實現交通系統暢通、安全、有序的重要途徑。建立合理高效的交通安全系統，為管理者及時提供交通信息及決策支持；幫助出行者合理選擇行車路線，避開交通擁擠，減少交通事故，從而極大增加路網系統的有效使用潛力和通行能力，使整個交通系統的運輸效率和經濟效益隨之增加。

1　系統設計

1.1 系統目標

本系統的最終目標就是要實現最大限度地利用并整合各種資源(包括信息，人員，設備，物資及工作方式等)，使城市交通管理決策者能夠實時調節、合理調度交通流，確保城市路網不出現超飽和交通流；同時，能夠快速處置突發性事件引起的交通堵塞，迅速恢復正常交通秩序，為實施救援提供信息和決策支持。

1.2 系統結構

交通安全系統的總體框架如下。在整個系統中，GIS 作為用戶輸入輸出界面，承擔著事故基本信息錄入，應急方案及交通、事故信息發布等任務；同時通過與GIS 平臺的交互，可實現相關文件的歸檔與數據庫的更新及維護。

整個系統的工作流程如下：

當交通事件（交通事故，交通流異常等）發生并通過檢測及驗證后，系統被激活。事件的基本信息如事件類型、發生地點、時間、受損車輛數、人員傷亡數，道路阻塞情況等，通過GIS 界面輸入系統。

系統下一步將生成最優決策方案，完成這一核心任務的是處理方案生成模塊，該模塊包含兩個子模塊：基于專家系統的決策支持子模塊和動態最優路徑生成子模塊。根據輸入的信息，由專家系統依據已經建立的知識庫判斷并確定事故等級，同時查詢當前資源數據庫中各部門(消防、交警、醫療、路政、牽引、排障等)的資源情況，擇優選擇參與調度的有關部門，并生成動態最優路徑，對交通流進行疏導，快速處置交通堵塞，避免二次事故。事件信息控制模型結構如圖1.1。

圖1.1　事件信息控制模型結構

1.3 數據庫的建模

通過關系數據庫的二維表來表達概念，把多維結構劃分為兩類表，一類是事實表，用來存儲事實的度量(measure)值以及各個維的碼值；另一類是維表，對于每一個維來說，至少有一個表用來保存該維的元數據，即維的描述信息，包括維的層次及成員類別等。在最簡單的情況下，維表有一行，內容是該維的每一個合法值。在相關事實表中，這些值會衍生出該維的列。在這種結構中，事實表通過每一維的值與維表聯系在一起。圖1.2 表示了道路連接關系數據表的結構。

圖1.2　道路連接關系數據結構表

2　遺傳算法

遺傳算法（Genetic Algorithms）是基于生物進化理論的原理發展起來的一種廣為應用的、高效的隨機搜索與優化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息。近幾年來，進化策略、進化規劃和遺傳算法之間差異越來越小，遺傳算法成功的應用到作業調度與排序、可靠性設計、車輛路徑選擇與調度、設備布置與分配、交通問題等優化問題中去。

2.1 編碼

雖然遺傳算法在組合優化的問題中有著廣泛的應用，但是直接對路徑進行編碼，把遺傳算法應用到路徑規劃中確有兩點困難：

1)首先路徑中的節點個數并不固定，需要使用可變長編碼的方式，這為后面的變異操作帶來了麻煩。

2)并不是任何一個對接點的編碼都可以對應一條有效的路徑，因為很多節點在圖中并不是相鄰的。這使得在交叉和變異過程中可能產生大量的無效路徑。

編碼是應用遺傳算法時的一個首要問題，也是設計算法的一個關鍵步驟。編碼方法除了決定個體的染色體排列之外，還決定了個體從搜索空間的基因型轉換到解空間的表現型時的解碼方法。編碼方法也影響到選擇算子、變異算子等遺傳算子的運算方法。因此編碼方法在很大程度上決定了如何進行群體的遺傳進化計算以及遺傳進化計算的效率。為此這里使用一種間接編碼的方法，不是直接對每個節點進行編碼，而是通過對邊的優先權進行編碼，并建立邊的優先權值和路徑間的映射關系。

我們為圖中的每一條邊e設定一個優先權值R(e)，每條邊的優先權各不相同，然后根據邊的優先權，使用如下的路徑生長算法來獲取路徑，具體如下：

1)初始化當前節點v=vi，路徑p={vi}，把所有的邊放入可用邊集合C中，也既是C=V。

2)在與v相聯接的所有邊中，尋找邊em=v-vm,使得em在可用邊集合C中，且邊優先權值R(em)最大。如果找到，把節點vm加入到路徑p中，把em從集合C中刪除。否則,不能找到邊em和節點vm，到(4)。

3)如果vm=vj，vi到vj路徑找到返回p。否則，設定v=vm，到（2）。

4)把em從集合C中刪除，再回溯到路徑p當前節點v的前一個節點vk,把v和em從p中刪除，并取v=vk,返回到2)。

根據路徑生長算法，我們可以由邊優先權值確定任意兩個節點之間唯一的一條路徑，同時還可以發現，對于兩個節點間的任何一條路徑，我們都可以找到與其相對應的邊權值。這樣我們就可以通過對邊權值的優化來獲取對路徑的優化。下面給出一個編碼的例子，如圖2.1。

圖2.1　路網結構示意圖

有順序表C = (1,2,3,4,5,6)

B―>C路徑為1-3-6

按照以上編碼方式， 對應B―>A路徑優先權編碼為232。

根據路徑生長算法，我們可以由邊優先權值確定任意兩個節點間唯一的一條路徑，同時還可以發現，對于兩個節點間的任何一條路徑，我們都可以找到與其相對應的一種邊權值。這樣我們就可以通過對邊權值的優化來獲取對路徑的優化。

由于在一個圖中，所有邊的邊優先權編碼是定長的，而且邊優先權值與邊有一一對應關系，適合用遺傳算法進行優化。考慮邊優先權僅僅有排序的意義，假設圖中有n條邊，其邊優先權R1，R2，…，Rn是整數1，2，…，n的一個排列。R1，R2，…，Rn可以看作是遺傳算法中基本的染色體。

2.2 適度函數

遺傳算法中群體的進化過程是以群體中個體的適應度為依據，通過反復的迭代，不斷尋求適應度較大的個體，最終就可得到問題的最優解或較優解。這里，適應度函數對應于問題的目標函數。

2.3 算子的選擇、變異和交叉

選擇算子模擬生物進化過程中的優勝劣汰，即適應度高的個體被遺傳到下一代群體的概率較大，而適應度小的個體遺傳到下一群體的可能性小。這里使用的是最優保存策略，既在每一輪計算完畢后，按照一定比率選取適應度的最大的樣本進入下一輪。

由于在算法中，每個有效的染色體必須是整數1，2，…，n的一個排列。因此，在交叉和變異的時候必須使用特殊的算子，下面詳細討論：

變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力。設定變異的時候每次隨機的產生兩個位置A，B，再把這兩個位置的對應元素RA,和RB相互交換。

例如：變異前：1245789，A=2，B=1；變異后：2145789

交叉算子是遺傳算法區別于其它進化算法的重要特征，它在遺傳算法中起著重要的作用，是產生新個體的主要方法，決定了遺傳算法的全局搜索能力。在這里選用基于位置的基因重組方案，既先從第一個父代染色體中隨機挑出幾個樣本按照原有位置放入子個體中，同時對于子個體其它空位置的元素則按照另一個父代個體的前后順序排列。

3　系統實現

本系統選用Oracle 9i 構建關系數據庫，Oracle Express存儲和管理事故多維數據模型；利用MapX控件進行二次開發，選用VC++6.0 進行系統核心模塊和人機界面的開發，系統具有較高的運行速度。

在Oracle 數據倉庫解決方案實施過程中，通常把匯總數據存儲在Oracle Express(多維數據庫OLAP 服務器)中，而將詳細數據存儲在Oracle 關系數據庫中，當需要詳細數據時，Express Server通過構在SQL 語句訪問關系數據庫，由于Oracle 9i 在Oracle 8i 的基礎上強化了OLAP 和數據挖掘的功能，與Express 的集成度也更高了。

MapX 是MapInfo 公司推出的功能較完備的ActiveX 組件，能夠和標準的編程語言Visual Basic、Visual C++等結合進行開發。MapX 提供了一系列的對象模型，大量的屬性、方法和事件，易于使用。交通安全系統的部分主界面如圖4.1。

應用舉例：在不發生交通阻塞的情況下：路徑尋優結果為“石橋鋪”→“陳家坪”→“氣象局”→“石坪橋”→“楊家坪”→“楊家坪中學”→“毛線溝”。圖4.2顯示了“楊家坪”→“楊家坪中學”這段道路發生交通阻塞后，系統通過算法擇優避開擁堵節點，選擇從“石橋鋪”→“陳家坪”→“氣象局”→“高新區九龍園區”→“水碾”→“毛線溝”路線的應急決策方案。顯然，改決策系統在發生交通異常時可通過生成方案疏導交通流，降低交通堵塞，避免二次事故的發生。

圖4.1　交通安全系統部分界面圖

圖4.2　交通誘導方案輸出界面

4　結語

本文針對城市的道路特點及交通現狀，介紹了交通安全系統的設計思路與實現的關鍵技術及算法。該系統可以移植到目前已經成熟的智能交通綜合管理服務系統平臺上，與其他的子系統集成，對于減少交通阻塞、降低再生事故所帶來的災害、改善交通環境、提高交通營運收入都有著重大的社會意義和經濟價值。

參考文獻

[1]唐恩輝.智能交通系統——現代交通的發展方向. 2014,12

[2]陶剛等.道路交通安全綜合決策支持系統的設計與實現 警察技術.2014, 03

[3]張志兵.空間數據挖掘及其相關問題研究 [M]. 武漢: 華中科技大學出版社, 2011.

[4]陳國良等.遺傳算法及其應用[M].北京:人民郵電出版社,2008.

[5]楊福濤.基于MapX &oracle9i空間分析的研究, 科技創新與應用, 2014,08

張穎（1977－）， 女(漢族), 實驗師, 重慶交通大學, 信息科學與工程學院, 重慶，主要研究方向：智能交通、無線傳感器網絡；

Design of City Traffic Safety System Based On Genetic Algorithms

Zhang Ying
(Department of Information and Engineering,Chongqing Jiao Tong University,400074)

Abstract：City traffic safety system is the important part of ITS. This paper presented system structure and database model of safety system design, then paper introduced pivotal technology of genetic algorithm of system design based on the city character and traffic actuality,then the experimental results of traffic abduction as an example of traffic safety system.

Keywords：safety system;database;genetic algorithms

作者簡介

中圖法分類號:U121

文獻標識碼:A