基于遗传算法的城市交通安全系统的设计

张 颖(重庆交通大学信息科学与工程学院,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