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

?

基于遺傳算法的城市交通安全系統(tǒng)的設(shè)計

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

摘要：城市交通安全系統(tǒng)是城市智能交通系統(tǒng)中十分重要的組成部分。本文針對目前城市特點及交通現(xiàn)狀，詳細(xì)介紹了遺傳算法在系統(tǒng)實現(xiàn)中的關(guān)鍵技術(shù)，圍繞系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)庫建模，對安全系統(tǒng)的設(shè)計與實現(xiàn)進行研究，最后以交通誘導(dǎo)的處理為例闡述了系統(tǒng)的實現(xiàn).

關(guān)鍵詞：安全系統(tǒng);數(shù)據(jù)庫;遺傳算法

0　引言

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

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

1　系統(tǒng)設(shè)計

1.1 系統(tǒng)目標(biāo)

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

1.2 系統(tǒng)結(jié)構(gòu)

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

整個系統(tǒng)的工作流程如下：

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

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

圖1.1　事件信息控制模型結(jié)構(gòu)

1.3 數(shù)據(jù)庫的建模

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

圖1.2　道路連接關(guān)系數(shù)據(jù)結(jié)構(gòu)表

2　遺傳算法

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

2.1 編碼

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

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

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

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

我們?yōu)閳D中的每一條邊e設(shè)定一個優(yōu)先權(quán)值R(e)，每條邊的優(yōu)先權(quán)各不相同，然后根據(jù)邊的優(yōu)先權(quán)，使用如下的路徑生長算法來獲取路徑，具體如下：

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

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

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

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

根據(jù)路徑生長算法，我們可以由邊優(yōu)先權(quán)值確定任意兩個節(jié)點之間唯一的一條路徑，同時還可以發(fā)現(xiàn)，對于兩個節(jié)點間的任何一條路徑，我們都可以找到與其相對應(yīng)的邊權(quán)值。這樣我們就可以通過對邊權(quán)值的優(yōu)化來獲取對路徑的優(yōu)化。下面給出一個編碼的例子，如圖2.1。

圖2.1　路網(wǎng)結(jié)構(gòu)示意圖

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

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

按照以上編碼方式， 對應(yīng)B―>A路徑優(yōu)先權(quán)編碼為232。

根據(jù)路徑生長算法，我們可以由邊優(yōu)先權(quán)值確定任意兩個節(jié)點間唯一的一條路徑，同時還可以發(fā)現(xiàn)，對于兩個節(jié)點間的任何一條路徑，我們都可以找到與其相對應(yīng)的一種邊權(quán)值。這樣我們就可以通過對邊權(quán)值的優(yōu)化來獲取對路徑的優(yōu)化。

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

2.2 適度函數(shù)

遺傳算法中群體的進化過程是以群體中個體的適應(yīng)度為依據(jù)，通過反復(fù)的迭代，不斷尋求適應(yīng)度較大的個體，最終就可得到問題的最優(yōu)解或較優(yōu)解。這里，適應(yīng)度函數(shù)對應(yīng)于問題的目標(biāo)函數(shù)。

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

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

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

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

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

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

3　系統(tǒng)實現(xiàn)

本系統(tǒng)選用Oracle 9i 構(gòu)建關(guān)系數(shù)據(jù)庫，Oracle Express存儲和管理事故多維數(shù)據(jù)模型；利用MapX控件進行二次開發(fā)，選用VC++6.0 進行系統(tǒng)核心模塊和人機界面的開發(fā)，系統(tǒng)具有較高的運行速度。

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

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

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

圖4.1　交通安全系統(tǒng)部分界面圖

圖4.2　交通誘導(dǎo)方案輸出界面

4　結(jié)語

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

參考文獻

[1]唐恩輝.智能交通系統(tǒng)——現(xiàn)代交通的發(fā)展方向. 2014,12

[2]陶剛等.道路交通安全綜合決策支持系統(tǒng)的設(shè)計與實現(xiàn) 警察技術(shù).2014, 03

[3]張志兵.空間數(shù)據(jù)挖掘及其相關(guān)問題研究 [M]. 武漢: 華中科技大學(xué)出版社, 2011.

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

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

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

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

文獻標(biāo)識碼:A