遗传算法在交叉口配时优化中的应用

遗传算法在交叉口配时优化中的应用

摘要：介绍了模糊控制、人工神经网络、遗传算法、蚁群算法、粒子群算法、多智能体等智能控制方法，详细分析了遗传算法的在交通控制领域的实际应用案例，更深入了解和掌握了交通智能算法的应用。

关键词：优化；相位；配时参数；遗传算法

1 引言

随着社会经济的发展，交通量急剧增长，交通拥堵加剧，交通事故频发，特别是在一些大城市，交通问题已成为制约城市经济发展的瓶颈[1]。为此，人们提出建立智能交通系统(ITS)。作为ITS的重要组成部分，交通管理系统（ATMS）在改善交通流秩序、提高交通安全性等方面发挥积极的作用。其中，交通信号优化控制是保证城市交通安全、有序、畅通、快速、高效运行的重要途径。当前，随着交通控制智能化的不断提高，智能控制方法在交通信号控制的重要性日益凸显。按照控制原理的不同，传统的交通信号控制分为定时控制和感应控制。定时控制按事先设定的配时方案运行，其配时的依据是交通量历史数据。感应控制是某相位绿时根据车流量的变化而改变的一种控制方式，其中车流量可由安装在平面交叉口进口道上的车辆检测器测量。这两种控制方法存在共同的局限性：以数学模型为基础。由于城市交通系统中被控对象过程的非线性、较大的随机干扰、过程机理错综复杂以及现场车辆检测的误差，建立精确的数学模型非常困难，这就造成了算法本身就有一定的缺陷。即使经过多次简化己建立的数学模型，它的求解还须简化计算才能完成。所以传统的交通控制方法并不能有效地解决目前复杂的交通问题。针对传统交通控制的固有缺陷和局限性，许多学者将模糊控制、神经网络、遗传算法、蚁群算法、多智能体技术等人工智能基础研究方法同常规交通控制方法结合应用。

2 交通优化智能算法

2.1 模糊逻辑

模糊逻辑是一种处理不确定性、非线性等问题的有力工具，与人类思维的某些特征相一致，故嵌入到推理技术中具有良好效果。模糊逻辑不需要获取模型中的复杂关系，不需要建立精确的数学模型，是一种基于规则的智能控制方式，特别适用于具有较大随机性的城市交通控制系统。

2.2 人工神经网络

人工神经网络是模拟生物的神经结构以及其处理信息的方式来进行计算的一种算法。它具有自适应、自组织和自学习能力，在认知处理、模式识别方面有很强的优势，最显著特点是具有学习功能。人工神经网络适用于非线性时变性系统的模拟与在线控制，交通控制系统正是一个非线性、时变系统。

2.3 遗传算法

遗传算法是运用仿生原理实现在解空间的快速搜索，广泛应用于解决大规模组合优化问题。它是一种比较先进的参数寻优算法，对于不易建立数学模型的场合其实用价值较为突出，是以同样适用于交通工程。1997年，Kiseok和Michael等应用遗传算法对交通网络内的交叉口信号相位进行设计[2]，在交叉口形成的冲突点，结果显示该方法给出的相位方案要优于TRANSYT给出的方案。同年，Memon等人给出了利用遗传算法进行信号配时方案设计的研究结果。陈小锋，史忠科针对典型的多车道双向交叉路口的交通流分布，建立四相位控制的动态交通控制模型，采用遗传算法同时对信号周期时长和相位绿灯持续时间进行优化[3]。承向军等对到达车辆数目进行模糊分类，将不同数量车辆的信号控制决策方案以规则集形式存储在知识库中，利用改进的遗传算法对交叉口信号模糊控制器的模糊规则进行优化，建立了新的优化算法[4]。顾榕等

将免疫遗传学思想运用到交通信号控制中，提出一种新的相位配时优化算法，实验结果充分验证了该算法处理交通配时优化问题的可行性和有效性[5]。

2.4 蚁群算法

蚁群算法是一种模拟进化算法，它是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。

2.5 粒子群算法

粒子群优化算法是由Eberhart 博士和Kennedy 博士于1995年提出，是基于对鸟群、鱼群捕食的行为模拟研究而来。同其他基于群智能(Swarm Intelligence)的随机优化算法相比，PSO 算法具有收敛速度快、设置参数少、程序实现异常简洁、具有深刻的智能背景等特点。

2.6 多智能体技术

Agent 由Minsky 在1986年首次提出，一般认为Agent 指驻留在某一环境下，能持续自主地发挥作用，具备驻留性、反应性、社会性、主动性等特征的计算实体。随着车辆数和城市路网规模的增大，信号控制系统的复杂性增大，同时由于交通流在信息、控制方面固有的分布性，采用多Agent 系统构建城市交通控制系统的计算环境已成为交通系统协调控制的热点。

3 遗传算法应用案例

3.1进出口道综合效率最优的交叉口配时参数优化

3.1.1优化问题概述

进出口道综合效率最优的交叉口配时参数优化问题 [6]如下, 配时参数优化目标为T 时间段内，交叉口中所有进口路段及出口路段的周期平均车辆数之和最小。

{}11

111,,,,,,,,,1min ()min ()(1)()()()()1()()()2()min ();/()min ();()min ()()max I K i i k i i i i i f f f i i i f f f i j i j i i j i j f i j j j f f f f i j i j j j j i j i j OF k n k K n k n k u k y k n k f n k u k y k f F S k n k Q t t L v y k S k N n k n k S k t β==---=+=+-=???+-=??=-=-++?∑∑满足：{}41,,,1,,0,,()min ,()();()()/()min ()()max ,0,out f j in out f i f f f f f f i i i i i in i i j in

j I f W h i

i i f f f f i i h i i o f h h i Q t i I j I u k q t N n k y k i I y k y k i I t L v y k n k S k Q t i I t =∈=????????????∈∈??????????????????

=-+∈=∈????-????=+?∈????????????∑∑∑{},,111,()min min (),,()(),()();()()

ut in W f f f f f i h h i h i i i i out in h F F f f i i i i f f h I u k n k Q t N n k y k i I h I u k u k y k y k ===????????????

??∈?????=-+∈∈??????==??∑∑∑ 考虑行人过街的安全性及驾驶员容忍极限等因素的限制，交叉口的相位绿灯时长应满足如下约束：

min max f f f t t t ≤≤

其中，min f t 和max f t 分别为相位f 的最小绿灯时长和最大绿灯时长(S )。

所有相位的绿灯时长及绿灯间隔时间之和即为交叉口的周期时长，表达式为：

1

11F F f f f f C t I -===+∑∑

其中，C — 交叉口周期时长(S )；I f — 相位f 与下一相位的绿灯间隔时间(S )。

3.1.2 道路交通条件概述

在每一个时间间隔KC 内，检测器应能准确检测到输入路段的流量数据。式(17)所示的数学规划问题即是寻求在特定的约束条件下使得目标函数值最小的T f 值，且优化得到的周期时长及相位绿灯时长可作为下一时间间隔内配时参数的重要理论参考。本数学规划问题可用智能算法——遗传算法进行求解。

以如图1所示的十字交叉口为例进行过饱和和低饱和情况下的实例分析，假设四个进口道均为直行单车道，交叉口采用两相位控制，且在过饱和情况下，四个进口道的车辆到达率分别为0.3、0.2、0.2、0.25 PCu /S ，低饱和情况下进口道的车辆到达率分别为0.15、0.1、0.1、0.125 PCu /S 。四个出口道通行能力分别为0.3、0.25、0.25、0.20 PCu /S ，低饱和状态下路段初始容纳车辆数均为10 PCu ，过饱和状态下路段初始容纳车辆数为50 PCu 。8条进口路段及出口路段的最大容纳能力及路段长度如表1所示。

表1 进出口路段最大容纳能力及路段长度

进出口编号i

1 2 3 4 5 6 7 8 N i

100 100 120 80 90 80 50 120 L i 700 700 840 560 630 560 350 840

本文以10个信号周期为优化时间间隔，假设所有路段的自由流速度均为14M /S ，结合上述输入参量，通过遗传算法可以求得节点的配时参数值。

3.1.3算例求解

遗传算法是依据适者生存、优胜劣汰的进化原则对包含可能解的群体反复进行遗传操作, 寻求最优或近似最优解的随机搜索算法，已被广泛应用于数学优化、自动控制、图像处理与模式识别等方面，主要内容包括编码、初始种群产生、适应度计算及遗传操作4个部分。

(1) 编码。由于行人过街时间及排队容忍时间等条件的制约，相位应有最大绿和最小绿的限制，其取值一般分别为60S [12]和15S [13]。设定本文的求解精度为整数，由于区间长度为60-15=45，区间[15,60] 必须分成45等份。32=25<45<26=64，因此编码的二进制串长至少需要6位。

(2) 种群产生。种群规模设定为50，初始种群的染色体随机选取。

(3) 适用度计算。考虑本文目标函数在定义域内的取值均大于0，而且是寻找函数最小值，所以可直接引用目标函数作为适用度函数来评价染色体的优劣。即：

11

1()min ()I K i i k f s n k K ===∑∑ (4) 遗传操作。采用跨代精英选择机制，设定交叉概率P C =0.25，变异概率P M =0.01，交叉变异后形成的中间种群与父代种群合并后按照适应度进行排序，且50%个体形成下一代种群。

按照上述基本遗传算法，设定南北直行为第一相位，东西直行为第二相位，则满足3.1节所设定的两种交通状况下，式(17)的最优解分别为：过饱和状态下，T 1=59S 、T 2=60S ，优化目标函数值为581PCu ；低饱和状态下，'1t =48S ，'2t =18S ，优化目标函数值为89PCu 。进口道及出口道周期平均车辆数之和与相位有

效绿灯时长的关系分别如图3、4所示。

假设所有相位的绿灯间隔时间均为3S ，两种状态下的交叉口的周期时长为：

1212125o C t t I I s =+++=

''121272u C t t I I s =+++=

通过上述算例分析可得，本文模型可同时适用于低饱和及过饱和状态的孤立交叉口信号配时参数优化，且在过饱和状态下，交叉口各相位的绿灯时长均接近最大绿。低饱和状态下，由于相位2关键车流的车辆到达率与相位1的关键车流车辆到达率接近，且进口道4属于瓶颈路段，因此，为避免路段排队长度的可能上溯，配时参数优化结果中的'1t 远大于'2t 。

图1 低饱和状况下优化指标与相位绿灯时长关系图图2 过饱和状况下优化指标与相位绿灯时长关系图3.2交通网络多交叉口配时优化

以某城市某区主要交叉路口的交通信号控制问题为背景，构造交通网络中以多交叉口滞留的车辆数最少为目标的优化模型，求解仿真数据，得到实时控制的配时方案。

3.2.1道路交通条件

采用的城市道路网如图3所示。

A C F

G

D

B

E H

I

图3 城市道路网结构简图

选取A、C、I三个主要交叉口，将该三交叉口视为一个网络主要节点，三个交叉口的交通流向和相位设置如图4所示。

A C I

图4 主要交叉口交通流向和相位结构设置

其中，路口A的相位显示顺序如图5（相位1→相位2→相位3→相位4）。

图5 交叉口A的相位显示顺序

路口C、I的相位显示顺序如图（相位1→相位2→相位3）。

图6 交叉口C和I的相位显示顺序

3.2.2模型参数的标定与建模分析

l为节点编号，取值1,2,3分别表示路口A、B、C三个交叉口。i为相位编号，取值1,2,3,4分别表示相位1，相位2，相位3，相位4；j为各相位的方向编号，取值1,2,3,4分别表示东，南，西，北（上北下南左西右东）；k为车道编号，取值1,2,3分别表示左转，直行，右转。

A xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道的小车到达率；A xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道的小车到达率；

A xljk(i)’：表示第x个周期，第l个交叉口，相位i中j方向k车道的大车到达率；

M xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道的小车驶离率；

M xljk(i)’：表示第x个周期，第l个交叉口，相位i中j方向k车道的小车驶离率；

T xljk(i)：表示第x个周期，第l个交叉口，相位i的绿灯显示时间；

T xl：表示第x个周期，第l个交叉口的周期；

SA xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道到达路口的车辆数；

SM xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道驶离路口的车辆数；

T：表示各交叉口周期的最小公倍数；

P l：表示交叉口l的放行矩阵，其元素为P ljk(i)；

P ljk(i)：表示同一个周期内，各交叉口的放行矩阵元素，其值为0或1，即取值为1时表示第l个交叉口，相位i，方向j中车道k车辆放行；取值为0时表示禁止放行；

u xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道单位时间内混合车辆总流入车辆数；

v xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道单位时间内混合车辆总驶离车辆数；

S xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道总滞留车辆数；

y xljk(i)：表示第x个周期，第l个交叉口，相位i中j方向k车道的黄灯时间；

n l：表示交叉口l的相位数。

将大车折算成标准小汽车，折算系数取为α，β为调和参数，则第x个周期，第l个交叉口，相位i中j方向k车道单位时间内混合车辆总流入车辆数u xljk(i)为：

u xljk(i)= A xljk(i)+ αA xljk(i)’+β

第x个周期，第l个交叉口，相位i中j方向k车道单位时间内混合车辆总驶离车辆数v xljk(i)为：

v xljk(i)= M xljk(i)+ αM xljk(i)’+β

则第x周期i相位时间段内到达的车辆数SA xljk(i)为：

SA xljk(i)= u xljk(i)T xljk(i)

第x 周期i 相位时间段内到达的车辆数SM xljk (i )为：

SM xljk (i )= v xljk (i )T xljk (i )P ljk (i )

第x 周期交叉口l 方向j 车道k 滞留的车辆数S xljk (i )为：

S xljk (i )= S （x -1）ljk (i )+ SA xljk (i )- SM xljk (i )

T 周期中有A 1个T 1 ,A 2个T 2 , A 3个T 3, ∑==3

1

i i i T a T ,在T 个周期内由实时预测量实时确定最佳周期T i 。 由以上分析，以滞留车辆数最少为目标的实时配时数学模型为：

∑∑∑∑∑∑∑∑∑∑∑∑============-++-++-+=321141414

1

3331414141

222141414

1

111))

()()(())()()(())

()()((min a x j k i jk x jk x jk x a x j k i jk x jk x jk x a x j k i jk x jk x jk x i SM i SA i S i SM i SA i S i SM i SA i S S

约束条件为：

4,3,2,1;4,3,2,1),()(===k j i t i t xlj xljk ,3,3,4,602032111===≤≤n n n n T n xl

jk x x x x x x y t t t t T 11413121113++++=,jk x x x x x y t t t T 223222122+++=,jk x x x x x y t t t T 333323132+++= ∑==3

1l xl l T a T ，))()()((i y i t i T xljk xljk xljk xl +=λ

采用遗传算法求解，其中群体大小为M ，终止代数为T ，初始交叉概率为P C ，初始变异概率为P M 。 321334a a a M ++=，100=T ，62.0=c P ，001.0=m P ，2,5.2==βα

以仿真流量为基础数据，以 MATlAB 为工具，可计算得到交叉口的每个周期的配时方案。

4结语

智能控制具有传统控制方法难以比拟的优越性，它通过模拟人的智能的决策方法来达到控制的目的，在处理复杂性、不确定性的问题时，显示出强大的控制效果。智能控制方法的最大特点是其控制算法是具有强逼近非线性函数的能力，不依赖于精确的数学模型。利用模糊控制、神经网络、遗传算法等智能控制方法能取得比定时控制与感应控制更好的效果。但是单一使用一种智能控制方法，在策略和理解上都存在一定的不足，如果把多种智能控制方法结合起来，充分利用它们特点上的互补，可以极大的改进控制的效果。因此，采用多种智能控制方法的结合对交叉口的控制是一种必然的趋势。但是，要实现交通信号的智能控制，必须首先获取各个相位上实时的交通流信息，这就需要依赖交通流量检测技术，检测技术的准确性和可靠性仍需要进一步提高。另外，将智能控制理论推广到实际的应用中，还需要通过硬件来实现，如何利用硬件来实现智能控制也是今后需要研究的内容。总之，智能控制方法在交通信号控制的应用还处于起步阶段，需要不断地探索和研究。

参考文献

[1].刘智勇.智能交通控制理论及其应用(第一版)[M].北京：科学技术出版社,2003.

[2].Kiseok .S and M. G.H. Bell.An optimisation method for signal timing in area traffic control of the eastern Asia society for

Traps[J].Studies. 1997,Vo1. 2,No 4:993-1001.

[3].陈小锋,史忠科.基于遗传算法的交通信号动态优化方法[J].系统仿真学报,2004,16(6):1 155-1 l57;1161.

[4].承向军,贺振欢,杨肇夏.基于遗传算法的交通信号及其学习控制方法[J].系统工程理论与实践,2004(8):130-135.

[5].顾榕,曹立明,王小平.免疫遗传算法在交叉口信号配时优化中的应用[J].同济大学学报:自然科学版,2007,35(2): 208-212.

[6].马东方. 进出口道综合效率最优的交叉口配时参数优化方法[J]. 中南大学学报, 2010-2570.