基于遗传算法城市交叉路口交通流量优化控制

王雪梅，李晓峰



基于遗传算法城市交叉路口交通流量优化控制

王雪梅，李晓峰

摘要：为了控制十字路口的交通流量，以确保交通网的交通流顺畅。针对车辆队列长、绿灯时间、信号灯周期以及黄灯的影响问题进行了模拟实验研究。提出遗传算法使交通流控制最优化，从而在自我调整过程中找到最优解。首先遗传算法视当前队列长度为输入，然后，输出十字路口最优化后的绿灯时间。最后，通过引入各相态红灯期间涌入的交通流，使结果得到进一步改进。实验表明在十字路口应用遗传算法能够快速应对变化的车辆队列长，绿灯时间、信号灯周期等问题，并且实现交通流控制。

关键词：交通控制系统；交通流；遗传算法；十字路口

0　引言

如今的交通流状况与几年前相比变得越加饱和，这是由于中国路上的车辆明显增多[1-2]。新建路段设立更多车道，目的是为了增大当前交通网络的车容量，但鉴于中国多数的主要城市像北京、上海发展快速[3]，新道路建设的用地有限。由于新道路建设不再是城市规划师的一个可选手段，交通网络顺畅的优化问题因而成了一大难题[4-5]。

各种交通控制应用在目前的交通网络，从简单的交通控制器（例如道路信号）到电子交通控制器（如交通灯）。在北京、上海常见的交通控制器有道路标识、交通灯、道路设施（如环形路、天桥）。不过，由于北京，上海等城市交通流量的加大超出了目前交通网的最大承受力，交通拥堵如今是司空见惯。在可用地有限及重建道路设施困难重重的情况下，较为妥善的解决方法之一就是研究并设计出交通灯控制器来对交通流进行优化[6]。如今，大多数交通灯控制系统仍采用预设模式，这已不再满足超饱和的交通流情况。

目前交通灯系统的不足是因为对实时交通特征缺乏了解所致，比如队列长度、交通信号持续时间。红灯过程中涌入的交通流也是交通控制模拟实验的一个考虑方面。本文采用遗传算法是因为它具有自然遗传机制的特点，能够快速找到次优解。

1　交通特征

（1）十字路口

本文研究的是某个十字路口的交通控制系统。在每个十字路口，都会存在交流流量的方式，即所谓的“相态”来表现交通流。这个十字路口，有3个（A，B，C）这样的交通流相态，如图1中的箭头所示：

三个交通流相态连接

（2）交通灯

交通灯的设计是为了控制和优化十字路口的交通流，只允许某个相态内的交通流在某个时间点通过十字路口。反过来这些相态又取得许可，交叉路口的交通流顺畅得以保障和控制。

用来控制交通流的交通灯通常是3种信号灯，即绿灯、红灯和黄灯。绿灯是交通流获得通过十字路口；红灯即暂停，指的是交通流严禁在红灯时段通过十字路口；黄灯是介于红灯和绿灯之间，提醒交通流绿灯很快过去要减速缓行。

近年来，传统的交通灯系统已无法满足日益增加的交通需求，于是，就有很多关于改善交通流量控制的研究。那些系统应用传感器来感知队列车辆并利用模糊逻辑来判断是否延长绿灯周期以让更多车辆通过。也有人提出用无线通信方式来进行交通控制。基于这个理念，车辆发出信息给附近的交通控制系统，然后系统基于信息对交通灯进行优化。也有人提出用遗传算法来进行交通流控制。这方面的研究里，车辆在道路网络的通行时间是研究的焦点，它们都提到利用遗传算法来对网络的流量进行优化。

本文也利用到遗传算法来对交通灯系统的周期和相态的优化进行分析：首先对交通灯系统的交通流进行分析，再应用遗传算法来判断十字路口所有交通灯的相态、绿灯总时间以及交通流的分割。

（3）十字路口

交通流量控制包括几个重要特点和参数，比如队列长度、浪费时间、涌入交通流和周期时间。

队列长度是指在十字路口队列等候通行的车辆总数。队列长度是衡量交通控制系统性能的指标之一。交通流量控制不到位会引发长长的队列，说明交通流控制无法满足较大车流量的需求；相比而言，短的队列长度反映了交通流控制有能力允许更多车辆通过十字路口。队列的长度将对其他参数产生影响，如延迟等待时间和行程时间[7]。

行程时间延迟是车辆从某一点行驶至另一点所需的时间。它与交通流控制里的车辆等待时间密切相关。长的队列会使车辆的等待时间拉长，且将直接导致行程时间延迟更多。本文对交通流控制的重点在于减少十字路口交通流的队列长度[8]。

其他一些相关参数有周期时间和浪费时间。周期时间是指所有相态在绿灯开始工作后,交通灯信号轮流一番后所需的时间。浪费时间是在等信号切换过程中以及因为驾驶员的驾驶行为而导致失去的时间。浪费时间可能对交通流控制有重要影响，因为它会随信号灯切换次数的增多而增加。导致交通流控制方面时间浪费的一个重要因素就是黄灯时间。黄灯时间设立是为了区分绿灯和红灯时间：考虑一定时间内可能有车辆在注意红灯并停止往前。但这样就降低了绿灯的效率，因为它已经占用了一个周期信号灯内的时间。因此，通过延长周期时间来降低信号灯的周期也是本文应用遗传算法实现交通流控制的目的之一。

本文采用的一个参数是驶入交通流，它会增加车辆队列长度并提高对绿灯的需求，尤其是在等红灯时，由于车辆不允许在此时间段通过，因此随着后续驶入的车辆，队列长度会不断拉长。

2　遗传算法

遗传算法是经过选择、复制和变异过程后发现最优解的一种方法，由生物领域的遗传演化衍生而来[9-10]。遗传算法模拟自然进化论这一特点使其能够一代接一代进行复制而同时去除不合适解。在遗传算法里，最适合解或最优解会在整个过程结束后保存下来。

（1）染色体种群

需要对范围内的染色体或解构成的种群进行判断。在交通流控制方面，染色体是指交通灯系统里的绿灯时间。种群范围设为大于0，因为绿灯时间不可能小于0。种群里的染色体个数也需要确定，因为解的数量决定了优化速度以及所求解的准确度。如果种群里生成的解过多，那么找到最适合的最优解所需时间就更长。但如果解的个数过少或偏小，遗传算法可能会无法找到最适合的优化解。所以，必须仔细选出适当数目的染色体，因为交通流控制既要求速度也要求准确性。在交通流控制方面，染色体的个数设为50，指的是遗传算法会在种群里生成50个解，且从中找到最适合的解。

需要对种群的初始范围进行仔细筛选。如果得当，遗传算法就能够选出最佳兴趣点。种群的初始范围也就是遗传算法开始时首批生成的种群的染色体范围。范围恰当的话将会为遗传算法找到所需或最佳染色体节约大量时间。如果范围太小，将影响染色体的多样性，以致遗传算法在操作过程中会遗漏掉的最佳点而陷入局部最佳。所以找到合适的初始范围对交通流控制很重要，本文选用范围为0-80。

（2）染色体生成与复制

另一个重要方面是遗传算法需要进行的迭代次数。这是遗传算法的停止规则之一，当遗传算法运算所需的迭代次数确定好遗传算法就会停止操作。对于交通流控制，遗传算法的迭代次数是100次。这个次数是在认真考虑了迭代次数对遗传算法有关的影响之后得出的。如果迭代次数太多，遗传算法可能要执行较长的计算时间后才能停止下来。另一方面，如果迭代次数太少，遗传算法的效率可能不如预期的好，因为遗传算法无法从种群中找到最佳染色体。

交叉部分是指复制所需的选择过程完成后来自父代或染色体的信息部分。在复制过程中，染色体都是成对选出来构成下一代染色体的父代。交叉部分决定了会有多少个父辈转移到其子代来生成新的染色体。在交通流控制方面，交叉部分设为0.8。这说明一对父代A和B将会生成2个后代。后代的产生是根据父代的价值或信息而来的。所以一个后代将遗传父代A的0.8和B的0.2部分；另一个后代将遗传父代A的0.2及B的0.8部分，结果如公式（1）：

其中，X和Y是继承的新生代。

（3）适应度函数

适应度函数是指让遗传算法从种群里筛选合适染色体所用到的规则或公式。种群里的每条染色体均将接受适应度函数测试，然后对应地都生成一个适应度值。本文适应度函数其实是一组简单的规则或法则。交通的适应度函数将从某个具体时刻的所有3个相态里取出队列长度方面的数据，然后与所有染色体进行测试，通过直接核实各相态排队的车辆来达到对绿灯时间的优化。

适应度极限是遗传算法的另一个停止规则。其实就是适应度函数要达到的一个目标。适应度极限是适应度函数所求的结果，因此一旦最佳适应度值达到极限，遗传算法将会停止运算而输出最合适的染色体。在交通流控制方面，适应度极限设为0且一旦染色体符合适应度函数，并生成一个为0或更小的适应度值，那么遗传算法将视该染色体为最合适的优化解。

（4）遗传算法模拟实验

遗传算法在交通流控制方面的模拟实验在黄灯时间上来展开，是为了考察控制器对实际情况的反应。我们发现遗传算法在交通灯系统的优化方面取得了成功，因为控制器能够快速对队列车辆做出反应，而相应地生成较长的绿灯相态。

遗传算法模式下的输出范围，如图2所示：

图2　遗传算法模型的输出范围

图2（1）给出了600秒模拟过程中队列交叉路口的车辆总数；图2（3）显示模拟过程中通过交叉路口的车辆总数。由图2(4)可知，模拟实验的最终结果反映了队列车辆数明显下降，因为控制器成功地让本该等待下一个信号周期的7辆车顺利通过了十字路口。

遗传算法交通流控制模拟有6次信号灯系统循环，如图2（2）所示。循环次数越多，浪费时间越多，也就降低交通灯系统的效率。由图2（5）最后可知，遗传算法成功地根据队列长度优化了交通信号。

（5）驶入交通流带来的影响

驶入交通流是我们的主要关注点，它会导致交通流控制处于混乱。驶入交通流持续不断，是系统所不可控制的。即便驶入交通流很小也会引发一定的混乱。这方面的影响在红灯或暂停时刻表现的尤为明显，一旦不允许车辆通行十字路口，就会使车辆队列拉的更长。所以要将驶入交通流控制在最低点才可确保十字路口的交通流顺畅。如果只是将队列长度或在等候信号灯的车辆分散到各个相态由遗传算法来处理是不足以解决问题的，因为有驶入车辆在十字路口不会停下来。这个现象在图1中相态A有明显体现，而且相态B 和C仍然集聚了驶入的车流。只要对某个具体时刻的队列长度进行分析，就会发现驶入交通流会使车辆队伍拉长而在下一周期的交通灯系统显现出来。

要使驶入交通流的影响达到最小，交通流控制就必须有能力预测该周期内的驶入交通流。这样才可确保交通流控制对该周期信号灯做出更好的优化决策。采用遗传算法的交通流控制在一个新周期开始时就将队列长度从所有相态分割出来，使第一个相态驶入交通流的队列长度产生的影响最小化。设一个新周期开始时的时间为0，第一个（A）相态的队列长度不会增加，因为驶入交通流在这个时段还没抵达十字路口。在第二个（B）和第三个（C）相态，情况则完全不同，因为第二相态需要在前一个周期后等信号灯切换才可通过，而第三个相态是最后一个相态，这就导致该相态比前两个的等待时间都要长。随着驶入车流不断靠近十字路口，等待过程中第二和三个相态积累的车辆越来越多。

通过遗传算法可以对因驶入交通流导致第二和第三相态的队列长度拉长情况进行预测。由于第一相态不受驶入交通流的影响，它的绿灯时间（染色体）仍可以同样的方式由遗传算法计算得到。而对于第二个相态，遗传算法将第二个相态的等待时间视作计算下一个新队列长度的参数。这样绿灯等待时间就会等同于第一个相态的。然后，第三个相态会将第一和第二个相态的总绿灯时间作为预测下一个新队列长度的等待时间。遗传算法的交通流控制综合考虑第二和第三个相态的等待时间以及驶入交通流率，从而生成相应的绿灯时间（染色体）。

公式（2）给出了各个相态队列长度的关系。变量k代表相态；变量是新队列长度或待预测车辆的总数；变量是第二个相态的驶入交通流率，与各个相态的绿灯时间相乘，可以得到等待时间内累积的车辆。

3　实验结果与讨论

遗传算法的交通流控制模拟条件与前面条件的一样。时间仍是600秒，唯一不同在于驶入交通流与模拟实验中的遗传算法的优化算法密切相关结果如图3所示：

图3　相态1的仿真结果

图3是交通相态1的模拟结果。虚线表示未采用遗传算法的驶入交通流时情况；实线表示采用遗传算法的驶入交通流情况。图3可知绿灯期间车辆数分阶段性减少。

图3中，实线较之虚线波动幅度不大。虚线反映了极低和极高值，说明优化失败，因为一个循环周期绿灯时间过长，且期间十字路口积累的车辆太多。如果某个相态的绿灯时间过长，所有相态之间就无法达到相互平衡，因为其他相态需要牺牲自己的绿灯时间来填补它。结果，其他相态积累的车辆数过多。图中的极高值也说明所有相态之间的绿灯时间分配未达到均衡状态，导致有些相态绿灯过长而其他相态积累的车辆过多。与虚线不同的是，实线表现得更平稳，比虚线更适合也便于车辆通过。这表明，将驶入交通流纳入遗传算法交通流控制来考虑，模拟结果得到改进。应用遗传算法来分析驶入交通流便于更多车辆在相同模拟时间内通过交叉路口，同时能够更均衡地分配绿灯时间。

第二个相态的有关模拟结果如图4所示：

图4　相态2的仿真结果

如图4(a)所示，其中虚线代表未采用遗传算法的驶入交通流控制情况；实线指采用了遗传算法的驶入交通流控制情况。很明显采用了算法的交通流控制情况要比未采用的效果理想。在模拟结束时通行的车辆比之前遗传算法的要多。实线也提供了模拟过程中的高峰值，试图生成更多的绿灯时间来快速放行更多车辆。如图4(b)所示：

图4　相态2的仿真结果

虚线和实线分别给出了之前遗传算法和考虑了第三个相态阶段驶入交通流的遗传算法。结果与第二个相态相比大同小异。整个模拟过程中，实线表现要优于虚线，其中实线的车辆增加情况在模拟结果结束时有所下降。

4　总结

本文对交通特征的研究将遗传算法引入交通流控制，通过自我调整得以找出最佳染色体或解。本文对各种交通特征的影响做了分析。将队列长度，即在十字路口等待通行的车辆总数作为一个性能指标进行分析。此外，队列长度可能对交通流控制带来一些影响，因为车辆队列太长的话就无法快速放行交通流，也就难以保障十字路口的交通流畅通无阻。循环周期和交通信号周期次数也对交通流控制影响巨大。这是因为循环周期是持续时间的长短，决定着交通流控制允许放行之前在十字路口的等待的车辆队列长度。交通信号周期的次数将影响浪费时间的长度，而反过来这又取决于交通流控制情况。浪费时间是指因为黄灯以及驾驶员行为的缘故在交通流控制过程中失去的时间。模拟结果表明遗传算法能成功应用实现交通流控制。

参考文献

[1] 文孟飞. 城市智能交通系统交通流协同优化与诱导关键技术研究[D].长沙:中南大学,2013.

[2] 蔡蕾. 城市平面交叉路口交通信号优化控制[D].吉林:吉林大学,2007.

[3] 钱俊明,李鑫伟. 北京市交叉路口交通流量分析研究[J].科技和产业,2013,12:113-115

[4] 周申培. 考虑排放因素的城市交叉口交通信号控制策略的研究[D].武汉:武汉理工大学,2009.

[5] 唐艳. 城市交叉路口交通流的优化控制[J]. 农业装备与车辆工程,2007,08:45-47.

[6] 曾松林. 城市单交叉路口交通信号的控制方法研究[D].成都:西南交通大学,2013.

[7] Mohammad Reza Jabbarpour Sattari, Hossein Malakooti, Ali Jalooli, Rafidah Md Noor.A Dynamic Vehicular Traffic Control Using Ant Colony and Traffic Light Optimization[J].Advances in Intelligent Systems and Computing , 2014(240): 57-66.

[8] Andr Luiz Cunha, Jos Elievam Bessa Jr.Genetic Algorithm for the Calibration of Vehicle Performance Models of Microscopic Traffic Simulators[J].Lecture Notes in Computer Science, 2009(5816):3-14.

[9] 宋曰聪,胡伟,张涛. 基于遗传算法的交通流量组合预测研究[J]. 微计算机信息,2007,29:55-56.

[10] 张婉琳. 遗传算法优化支持向量机的交通流量预测[J].激光杂志,2014,12:116-119.

收稿日期：（2015.03.11）

作者简介：王雪梅（1978-），女，哈尔滨，黑龙江工商学院，计算机科学与技术系，讲师，博士，研究方向：信息融合，数据挖掘，哈尔滨，150025李晓峰（1978-），男，哈尔滨，黑龙江外国语学院，信息科学系，副教授，博士，研究方向：数据挖掘，智能算法，哈尔滨，150025

基金项目：黑龙江省教育厅科学技术研究项目（12543076）；教育部教师科研专项基金（CTF120772）

文章编号：1007-757X(2015)12-0012-04

中图分类号：TP301.6

文献标志码：A