基于黄金分割点遗传算法的交通信号多目标优化

杨文臣,张 轮,饶 倩,张 孟

(同济大学道路与交通工程教育部重点实验室,上海201804)

基于黄金分割点遗传算法的交通信号多目标优化

杨文臣,张 轮,饶 倩,张 孟

(同济大学道路与交通工程教育部重点实验室,上海201804)

针对遗传算法求解交通信号配时模型容易陷入局部最优的问题,提出一种基于黄金分割点遗传算法的城市交通信号建模与优化方法.该方法采用数值模拟分析各交通信号常用性能指标间的相关性及其与配时参数间的关联程度,选取延误、停车率和通过量构建相对评价指标体系;并采用加权系数法建立交通信号多目标配时模型;同时,设计一种基于黄金分割点的自适应遗传算法对交通信号配时模型进行求解.该算法采用实数编码,引入黄金分割点算子增强遗传算法的局部搜索能力.以典型城市单交叉口进行试验,设计多种交通场景,在三种控制策略下采用数值计算和VISSIM仿真对提出的模型及算法进行效用评价.结果表明,所设计的算法求解质量好和计算效率高,提出的配时模型具有良好的控制效果.

智能交通;交通信号;相关性分析;配时模型;遗传算法;黄金分割

1 引 言

Akcelik在Webster的交通信号配时F.B方法的基础上引入停车补偿系数,建立考虑延误和停车系数的双目标配时模型,用以评价信号配时方案优劣,使基于多目标优化的交通信号自适应控制得到国内外学者的长期关注[1].从TRANSYT和SCOOT的综合性能指标的采用,到利用智能优化算法实现延误、排队长度、通行能力等多目标优化,以Hong[2]、杨晓光[3]等为代表的众多学者均在综合考虑交通损失和交通效益的基础上,建立模拟各交叉口交通控制状况的多目标数学模型,并用遗传算法和蚁群等智能算法求解配时模型,进而对路口进行最优控制,以解决信号配时实时优化问题.

遗传算法模拟生物进化过程,从问题解的种群开始全局搜索,已被广泛应用于交通控制的多目标函数优化领域[4].但是,交通信号多目标控制模型存在各类约束条件,传统的遗传算法在求解时优化速度慢,易陷入局部最优,致使控制方案质量低,特别在路口交通流量较高时更为明显.为此,众多学者设计模型中的约束条件和惩罚转换规则,并引入模拟退火、蚁群觅食和粒子群捕食等仿生机理[5,6],改进遗传算子计算规则或是组合两类算法,以提高遗传算法的局部搜索能力.但是,改进的混合遗传算法结构复杂、计算量大,导致算法效率低且可移植性差,难以满足交通信号控制在线实时优化的需求.

本文以典型城市单交叉口为研究对象,从配时建模优化和遗传算法改进两方面,提出一种基于黄金分割点遗传算法的城市交通信号优化控制方法.采用数值分析的方法,分析传统交通信号控制性能指标间的相关性,建立基于相对评价指标的动态配时模型.为克服混合遗传算法求解带约束优化问题时效率低的不足,引入黄金分割点算子,设计了基于黄金分割点的改进自适应实数编码遗传算法求解配时模型.最后,以典型城市单交叉口进行实验,基于实测的交通流数据采用三种控制策略进行大量的数值计算,并采用VISSIM微观交通仿真软件对三种交通信号控制策略的控制效果进行仿真,对模型及算法进行效用评价.

2 交通信号多目标配时优化建模

2.1 性能指标相关性分析

交通信号常用的评价指标包括交叉口饱和度、延误、排队车辆数、停车次数和通行能力.对典型双向六车道、采用标准四相位控制的城市单路口,采用数值模拟的方法,在不同的车流量到达水平下,估算不同配时方案下路口修正的webster平均延误(avgDelay)、webster平均停车率(avgStopRate)和通过量(Capacity)的数值,计算结果如图1示.

从图1可以看出,平均延误与通行量及平均停车率与通过量之间呈抛物线关系,平均停车率和延误之间呈指数趋势,这说明停车次数与通过量、延误与通过量,以及停车率和延误之间没有显著的正负相位性.这是因为信号周期小,车辆到达路口经常停车排队,延误和停车次数增大,路口通行能力得不到充分利用,而在合理的周期范围内,通过量增大,延误和停车率也随之增大.因而,相关性分析结果表明:在路口交通条件确定的前提下,存在一个合理的周期范围,其使延误和停车次数尽可能小,并保障路口一定的通过量.

实地调查分析典型路口的周期时长及其相关因素的关联程度,国内外研究发现,通过量与周期时长的关联度最大、排队长度次之、延误与停车率接近,且饱和度与通过量、停车率与排队长度直接正相关[7,8].在确保交通安全的前提下,信号控制目标在于最大限度提高道路通过量,并使交叉口延误和停车次数尽可能小.因此,可以选取延误、停车次数和通过量作为交通信号控制方案的性能评价指标.

图1 停车次数、延误、通过量之间的相关性分析Fig.1 Correlation analysis among stop times, delay and traffic capacity

2.2 基于相对指标的交通信号配时建模

目前配时优化研究中多采用延误、停车率和通过量的绝对值,但各性能指标的量级、量纲不同,导致各指标权重模型的物理意义不明确,或因某个指标的量级过大,多目标优化实质上为单目标优化.为使目标函数无量纲化和克服性能指标的量级差异,以经典F-B配时法的控制方案(TRRL)对应的各性能指标值为标准数,基于相对指标的动态配时模型为

式中 PI是综合性能指标值;gi、xi、li分别为相位i的绿灯时间、饱和度和损失时间;n为相位总数; gmin和gmax为相位i的最小、最大绿灯时间;Cmin、Cmax为最小、最大周期;avgD、avgH和Q分别是交叉口修正的Webster平均延误、Webster平均停车率和HCM2000通过量,并按式(2)计算;avgDTRRL、avgHTRRL和QTRRL分别是TRRL控制方案下对应计算得到的交叉口修正Webster平均延误、Webster平均停车率和HCM2000通过量.

式中 avgDi、avgHi和Qi分别是相位i修正的Webster延误、Webster停车率和HCM2000通过量; Si、qi、yi、ui分别为相位i的饱和流量、到达车辆数、到达流率和绿信比.

k1、k2、k3分别是延误、停车率和通过量的权值系数,其随交通需求的变化而自适应调整,并按式(3)计算.

式中 Ui为指标i的临时权重;Y为交叉口总流率;权值修正系数X为交叉口总饱和度.k1、k2随着交叉口流率比的增加而减小,k3随交叉口流率比的增加而增加,从而使得控制目标在路口闲散状态下侧重降低延误;在顺畅状态下侧重减少延误和停车;而在繁忙和拥堵状态下则着重提高通过量,实现不同交通状态下交通控制策略的优化,使路口管理效能最大.采用交叉口“流率—占有率”组合描述路口交通流不同强度状态的论述详见文献[9].

3 基于黄金分割点的遗传算法

3.1 黄金分割点的局部优化

经典黄金分割比例已经被广泛应用于建筑、美学、音乐、工业设计等领域,近几年,黄金比例也被应用于复杂系统优化问题并取得了良好的效果[10].当遗传算法进化到一定阶段,两个局部最优个体将趋同于解空间的同一个“凹处”.可以假设,在两个局部最优个体的基因之间,存在潜在的更优的基因位置.为此,引入黄金分割比例确定局部最优点的搜索位置.如图2所示,A和B为两个相邻的最优个体,C为通过黄金比例得到的潜在最优点的位置,AC和AB的关系满足黄金分割点定义.

图2 基于黄金分割比例计算局部最优点示意Fig.2 The diagram of local minima calculation based on the golden ratio

为了拓展遗传算法解集的局部搜索空间,如图3所示,运用反向原理(将C的位置旋转180°)生成反向黄金分割的局部最优点C',其中C'C和C'B的关系满足黄金分割定义.

图3 基于反向原理计算反向黄金分割局部最优点示意Fig.3 The diagram of reverse golden ratio-based local minima calculation

3.2 基于黄金分割点的混合遗传算法

基于黄金分割点的混合遗传算法(GRGA)以改进实数编码遗传算法(SRGA)每一代的m个优秀个体作为初始向量,引入黄金分割点产生新个体向量集,拓展遗传算法解空间的搜索范围,逼近更好的解集.算法流程如图4所示,GRGA采用实数编码生成初始种群,该种群满足信控约束条件和个体间互不相同准则;在算法控制参数中:种群规模取100,进化代数Gen取100,局部寻优规模m取10;个体适应度值取PI值,且每个方案的PI值采用式(1)计算;交叉和变异的概率及操作算子随当前代数G及个体PI值的优劣自适应动态调整[9,11].

图4 基于黄金分割点的混合遗传算法流程Fig.4 The golden ratio-based hybrid genetic algorithm

为保持种群的多样性,在SRGA算法的每一新生代中,挑选最好的30个个体构成算法的子种群,并从子种群中随机选取2 m个优秀个体作为初始向量,调用黄金分割算子强化遗传算法的局部寻优搜索,具体步骤如下:

(1)由3.1节的黄金分割函数产生m个新个体向量;

(2)采用式(1)评估新个体向量集;

(3)采用Metropolis准则概率选择新个体,并用接收的优秀个体依次替换SRGA新生代中最差的个体,个体接收概率P(X)按式(4)计算,为逼近最优空间及加速收敛,P(X)随进化代数的增加而增大,即在进化后期对局部寻优的依懒度加大.式中 α为比例系数,控制算法对进化代数的依懒程度,研究取α=0.6.

4 模型验证

4.1 实例描述

以佛山市三水区某典型十字路口作为模型和算法的验证实例.路口道路交通组织和VISSIM仿真模型如图5所示,该路口为主干道与次干道相交,平峰和高峰期间的流量差异明显,采用三相位的两时段定周期控制(平峰/高峰),且相位1和相位2之间无黄灯过渡.在平峰期间,南北主路左转车流及东西支路的车流量小,而在高峰期间,路口周期达98 s,绿灯时间的浪费现象严重.

采用实地调查的平峰期(Non-peak)和高峰期(Peak-hour)的车流量(5min统计间隔)均值作为模拟交通场景的驶入流量,平峰和高峰路口流量的流向图如图6所示.

4.2 仿真场景

(1)数值计算.

为验证GRGA的效用,采用GRGA与基于模拟退火的混合实数编码遗传算法(HRGA)[9]分别求解平峰期和高峰期下的配时模型,计算机数值计算采用Visual C#编程.两种优化算法在两种状态下各进行100次仿真计算.选取最优、最差和平均适应度、平均迭代次数、收敛次数、可行解/不可行解、优化时间为遗传算法性能评价指标,并对比分析GRGA、HRGA两种算法的最佳配时方案及路口现行信号控制方案(ExpT)的控制性能.

(2)VISSIM仿真.

微观交通仿真是评价信号控制策略的有效方法,采用微观交通仿真软件VISSIM4.30对实验交叉口的基础路网和交通控制设施进行可视化建模,并设置仿真路网OD和统计分析参数,对GRGA、HRGA和ExpT的方案进行仿真.仿真场景设计如下:

①平峰/高峰的仿真时长均为1h,且为模拟路口短时车流到达的波动特性,在VISSIM Inputs的Time intervals文件中根据实地调查的结果设置1 h内5 min间隔的车辆发车比例.

②根据国内城市道路通行能力的设计规范,车头时距、驾驶员反应时间校准为1.8 s和1.5 s.

③由于仿真效果受随机种子影响,对每个控制方案批量仿真20次.选取平均延误(Delay)、平均速度(Speed)、平均排队长度(Queue)和平均停车时间(Stop Time)为VISSIM仿真的性能评价指标.

图6 平峰(左)和高峰(右)的路口流量的流向图Fig.6 The flow diagrams in the non-peak(Left)and peak period(Right)

4.3 结果分析

(1)GRGA的算法性能分析.

GRGA算法性能指标的统计结果如表1所示:在100次独立运行中,GRGA均可得到可行解,而且在最好解、平均迭代次数和优化时间等指标方面均优于HRGA,说明对本文的单路口控制实例,设计的黄金分割局部搜索具有好的应用效果.尤其优化时间得到大幅缩短,更好满足控制系统实时性需求,这是因为相比模拟退火算子,采用黄金分割局部搜索算子的计算量小.

表1 GRGA和HRGA两种算法100次数值计算的统计结果Table 1 Statistical results for 100 calculations with GRGA and HRGA

(2)控制方法的控制效能分析.

GRGA、HRGA的最佳配时方案及ExpT方案的数值计算和VISSIM仿真的统计结果分别如表2和图7所示:在平峰和高峰期间,GRGA算法与各状态下制定的控制目标一致,在平峰状态下能大幅减小延误和减小停车次数,而在高峰状态下在减小延误和停车次数同时,大幅度增加路口通过车辆数,仍能获得稳定的控制性能.以GRGA和ExpT的仿真结果对比为例,在平峰和高峰交通状态下, GRGA在车辆延误、路口行车速度等指标上均得到了明显改善,约有15%-33%的改进,大大提升了路口的运营效能.

表2 GRGA、HRGA和ExpT的性能指标计算结果Table 2 The calculation result of the GRGA,HRGA and ExpT

图7 GRGA、HRGA和ExpT方案性能指标的VISSIM仿真统计结果Fig.7 VISSIM simulation results of the GRGA,HRGA and ExpT

5 研究结论

本文提出了一种基于黄金分割点遗传算法的城市交通信号优化控制方法,其采用数值方法模拟交通信号常用性能指标,分析了指标间的相关性及其与配时参数的关联程度,并综合考虑控制效率和效益,构建了基于相对性能指标的交通信号多目标动态配时模型,提出一种基于黄金分割点的自适应遗传算法,为单交叉口交通信号实时优化控制提供了一种解决方案.以典型的实证路口进行试验,在实地的平峰和高峰交通场景下,采用三种控制策略对路口进行大量的数值计算和VISSIM仿真.与HRGA等控制方法相比,分析结果表明:在算法性能方面,通过引进黄金分割局部搜索机制,改进的遗传算法求解质量好、计算效率高;在控制效果方面,能有效降低路口延误和停车次数,并提高行车速度,与实际的交通管理目标吻合.

[1] Schmocker J D,Ahuja S,Bell M G H.Multi-objective signal control of urban junctions-Framework and a London case study[J].Transportation Research Part C:Emerging Technologies,2008,16(4):454-470.

[2] Hong L.Traffic adaptive control for oversaturated isolated intersections:Modeldevelopmentandsimulation testing[J].Journal of Transportation Engineering, 2004,130(5):594-601.

[3] 马莹莹,杨晓光,曾滢.信号控制交叉口周期时长多目标优化模型及求解[J].同济大学学报:自然科学版,2009,37(6):761-765.[MA Y Y,YANG X G, ZENG Y.Multi-objective cycle length optimization model and solution[J].Journal of Tongji University (Natural Science),2009,37(6):761-765.]

[4] Michalewicz Z.A survey of constraint handling techniques in evolutionary computation methods[C].Proceeding ofthe4thAnnualConferenceonEvolutionary Programming,1995:135-155.

[5] Teklu F,Sumalee A,Watling D.A genetic algorithm approachforoptimizingtrafficcontrolsignals considering routing[J].Computer-Aided Civil and Infrastructure Engineering,2007,22(1):31-43.

[6] Ceylan H,Bell M G H.Traffic signal timing optimization basedongeneticalgorithmapproach,including drivers'routing[J].Transportation Research Part B: Methodological,2004,38(4):329-342.

[7] 杨锦冬,杨东援.城市信号控制交叉口信号周期时长优化模型[J].同济大学学报,2001,29(7): 789-794.[YANG J D,YANG D Y.Optimized signal time model in signaled intersection[J].Journal of Tongji University,2001,29(7):789-794.]

[8] Anderson J,Sayers T,Bell M.The objectives of traffic signal control[J].Traffic Engineering&Control, 1998,39(3):167-170.

[9] 何兆成,杨文臣,梁诗,等城市单交叉路口交通信号实时优化控制与仿真[J].计算机工程与应用, 2010,46(33):239-243.[HE Z C,YANG W C, LIANG S,et al.Study of real-time traffic signal optimized control and simulation for urban isolated intersection[J].ComputerEngineeringand Applications,2010,46(33):239-243.]

[10] Sun Y X,Van B J,Wang Z H.A new golden ratio local search based particle swarm optimization[C].2012 International Conference on Systems and Informatics (ICSAI),2012:754-757.

[11] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on System,Man and Cybernetics,1994, 24(4): 656-667.

Multi-objective Optimization for Traffic Signals
with Golden Ratio Based Genetic Algorithm

YANG Wen-chen,ZHANG Lun,RAO Qian,ZHANG Meng
(Key Laboratory of Road and Traffic Engineering,Ministry of Education,Tongji University,Shanghai 201804,China)

Aiming at the problems of the local optimum of the genetic algorithm in solving traffic signal timing models,this paper presents an optimized traffic signal controller with a golden ratio-based genetic algorithm(TSCGRGA)for urban signalized intersections.This controller employs numerical simulation to analyze the correlation between the traditional performance indicators of traffic signal benefit and their correlation degree with timing parameters,select time delays,stop rate and throughput to establish relative evaluation indices of traffic signals,and a multi-objective timing model of traffic signals is developed by weighted coefficient method.Then,an adaptive golden ratio-based genetic algorithm is presented to solve the optimized models,which uses real number encoding,and introduces golden ratio calculator to enhance the local optimal capability of genetic algorithm.Experiments are conducted on a typical urban isolated intersection and the performance of the developed model and algorithm is validated by comparison with those of fixed-time,actuated,and simple real-coded genetic algorithm-based controllers for different trafficconditions.Extensive numerical circulation and VISSIM simulation results have demonstrated the potential of the developed algorithm in the quality of solutions and time efficiency,and indicated that the signal strategies derived from TSCGRGA have better performance.

intelligent transportation;traffic signal;correlation analysis;timing model;genetic algorithm;golden ratio

U491.51,TP391.9

: A

U491.51;TP391.9

A

1009-6744(2013)05-0048-08

2013-04-02

2013-05-14录用日期:2013-06-13

国家自然科学基金资助(No.50408034).

杨文臣(1985-),男,云南昌宁人,博士生.

*通讯作者:Lun_zhang@tongji.edu.cn