基于改进NSGA-Ⅱ的交叉口信号配时多目标优化

陈秀锋,王瑞聪,陈咨羽,高梦圆,郭玉彤

(青岛理工大学 土木工程学院, 青岛 266525)

随着城市化进程的进一步的加快和车辆占有率的增加,居民出行的需求也日益增加,平面交叉口堵塞问题已成为世界众多城市交通面临的主要问题之一。交通信号配时是改善城市道路拥堵、优化道路通行效率的重要策略[1]。目前,利用多目标优化措施解决信号交叉口配时优化问题逐渐成为热点。刘畅等[2]以交叉口延误、一氧化碳排放为优化指标,建立多目标信号配时优化模型,通过优化的粒子群算法求解模型;牟亮等[3]提出了车辆延误-尾气排放联合优化目标模型,将车辆延误和尾气排放放到同一量级进行比较,通过Vissim仿真证实了模型的优越性;CHEN等[4]以延误、停车和通行能力作为性能指标,约束条件为饱和度,根据交叉口特点赋予权重,通过遗传算法进行信号配时。牟海维等[5]以车辆延误、行人延误、停车率、通行能力、尾气排放作为性能指标,采用粒子群优化算法求解,仿真结果表明:相对于经典方法,极大地减少了交叉口的总延误时间以及停车率,增加了路段通行效率;张小雨等[6]以延误、通行能力、停车次数、汽油车排放及柴油车排放等5个目标建立多目标规划模型,运用遗传算法求解,通过实际交叉口验证获得了较好的控制效果;JIA等[7]提出了一个新颖的多目标配时模型,以人均延误、汽车排放和交叉口饱和流量为目标,经过一种启发式算法证实了模型的优越性;ZHANG等[8]以交通流为基本数据,结合交通流描述理论和尾气排放估算规则,建立了一个信号配时问题的多目标模型,通过混合约束策略和NSGA-ⅡI框架相结合的方法,有效增加了多目标模型的求解质量和效率。但是,现有研究成果普遍将多个优化目标加权组合成一个综合目标[9-11],或者通过转约束法将其他控制目标包含在约束条件中,从优化理论的角度看,这仍属于单目标优化模型[12],不能够让多个目标一起获得最优解;另外,一些进化算法,如非支配排序的遗传算法(NSGA-Ⅱ),存在多目标求解耗时、收敛精度差和难以获得最优解的问题[13-14]。为此,本文设计了车辆延误、停车次数、通行能力为评价指标的信号配时多目标优化模型,并提出了改进的NSGA-Ⅱ算法(NSGA-Ⅱ-DE)对模型进行求解,有效提升信号配时多目标优化算法的收敛速度和求解精度。

1 信号配时多目标优化模型

1.1 多目标函数

利用车辆平均延误、平均停车次数和通行能力3个评价目标,来设计信号配时多目标优化模型。为了更好地比较指标的优化程度,采用比值法进行无量纲化处理,多目标函数表达式为

(1)

1.1.1 车辆平均延误

通过Webster公式中的延误计算[15],车辆平均延误的组成可以分为2部分,分别为正常相位延误、随机延误,相位车辆平均延误模型为

(2)

式中:di为第i相位的车辆平均延误;C为信号周期;λi为相位绿信比;xi为饱和度,即到达交通量与通行能力的比值;qi为进口道车流量。

随机延误相对较小,在实际计算中常忽略不计,本文采用式(2)前2项,得出相位车辆平均延误为

(3)

相位车辆平均延误加权得出周期车辆平均延误:

(4)

1.1.2 平均停车次数

根据Webster相关理论,车辆在交叉口的停车次数为

(5)

式中:hi为相位平均停车次数;yi为进口道车辆到达率和饱和流量之比的比值。

得到加权相位平均停车次数周期平均停车次数为

(6)

1.1.3 通行能力

依据停车线原理[16],周期内通行能力计算公式为

(7)

式中:Si为某一相位的饱和流量。

1.2 约束条件

考虑到信号配时控制的实际情况,多目标优化模型对于目标的约束主要包含以下3个方面:①信号周期时长C介于最大周期和最小周期之间。②有效绿灯时间g处于最短绿灯时间和最长绿灯时间之间,并且周期长等于各相位有效绿灯长加上信号总损失时间L。③根据饱和度的定义,如果饱和度过小,可以采用传统的信号配时方案解决需求,没有必要应用多目标优化策略;如果饱和度过高,车辆的运行状态会因为干扰而不稳定,从而进入过饱和状态[17],通过以上分析,xi一般在0.75～0.90之间。

综上,约束条件如下:

(8)

2 改进NSGA-Ⅱ算法

NSGA-Ⅱ算法是依靠遗传算法并且利用快速非支配排序及精英策略的多目标优化算法,NSGA-Ⅱ中存在模拟二进制交叉算子,这种计算会导致收敛速度较慢、移动空间不足,存在陷入局部的最优解[18]的问题。本文采用DE算法的交叉变异策略改进NSGA-Ⅱ算法的子代生成,并且动态更新种群避免DE算法种群多样性的不断降低,在提高算法收敛速度的同时得到全局最优解。

2.1 交叉变异策略的改进

利用DE算法中的DE/Rand/1全局变异策略[19],对NSGA-Ⅱ算法的变异策略进行应用改进,在解空间内快速而广泛地寻找最优解。对于第t代的每个向量xt,随机选择3个不同的目标向量x1,x2,x3,通过变异方案生成变异个体:

(9)

式中:F为变异率(差分向量的缩放因子)。

变异个体后,通过二项式分布交叉法得到实验种群:

(10)

2.2 种群动态更新

(11)

种群动态更新策略有效改善了多样性降低、局部收敛的情况,经过保留和更新,并不破坏优化过程。

NSGA-Ⅱ-DE算法的全部算法计算过程如图1所示。

图1 NSGA-Ⅱ-DE算法流程

1) 初始化种群,利用随机函数生成多个初始个体种群Pt,根据多目标优化问题的维数,选择种群数目,一般为n=10d,其中d为问题维数。设置最大迭代次数tmax,初始化迭代次数t=0;

2) 是否达到目标条件(t>tmax),如果达到目标条件则终止计算过程,得到帕累托(Pareto)最优解[20],不满足会进行下一步;

3) 将快速非支配排序策略应用到种群中,指定每一层的适应度;

4) DE算法交叉变异算子产生下一代,与父代种群合并种群;

5) 定量评价种群多样性,得到种群多样度;

6) 若多样性大于设定值, 执行下一步,否则根据公式(11)进行更新再执行下一步;

7) 在拥挤度距离的设计中,利用精英策略选择N个个体成为新的父代种群Pt+1;

8)t=t+1,返回第2)步。

3 实例分析

3.1 交叉口数据采集

T形交叉口作为沿海景区常见的交叉口,高峰时段容易发生堵塞,为解决景区交通拥堵,选择青岛市崂山区某T形交叉口进行实证分析,该交叉口三相位控制。交叉口现状渠化及相位相序见图2所示,表1为早高峰和晚高峰各进口道小时流量。

表1 早高峰和晚高峰时段小时流量 pcu/h

图2 交叉口渠化及信号相位现状

3.2 信号配时优化

NSGA-Ⅱ算法与NSGA-Ⅱ-DE算法Pareto最优解集如图3所示,相对于图3(a),图3(b)Pareto最优解分布较为集中,因此具备更好的分布性。收敛性在2种算法之间差异不大。这个解集说明了3个目标之间的关系,从图3可以看出,要想获得较好的通行能力,车辆延误与停车次数也需要控制在一定水平内。在多目标优化过程中存在一个最优的解集,即,使模型达到最优。

图3 NSGA-Ⅱ和NSGA-Ⅱ-DE Pareto最优解

利用NSGA-Ⅱ-DE算法,得到最优信号周期时间为106 s,东西直行相位有效绿灯时间35 s,西进口道左转相位有效绿灯时间40 s,北进口道左转相位有效绿灯时间16 s,具体配时方案如图4所示。

3.3 仿真分析

根据表1的交通数据,饱和流量设定为1650 pcu/h,通过Vissim软件仿真工具[21-22]仿真交叉口,如图5所示。为了更准确体现优化算法的优越性,对现状配时方案、NSGA-Ⅱ配时方案以及本文配时方案进行对比,以平均停车延误、停车次数和排队长度作为参数,结果如表2所示。

表2 配时方案效果对比

图5 交叉口仿真

由表2可知,相比于现状信号配时方案,NSGA-Ⅱ-DE配时方案交叉口进口道的车辆平均延误分别降低了27.47%,30.89%,23.31%,排队长度分别降低了35.39%,33.56%,31.06%,平均停车次数分别降低了25.44%,31.79%,35.10%,优化效果明显。同时,比较于NSGA-Ⅱ法优化方案,NSGA-Ⅱ-DE配时方案交叉口进口道的车辆平均延误分别降低了14.76%,16.90%,10.47%,排队长度分别降低了19.94%,21.05%,14.17%,平均停车次数分别降低了12.27%,20.83%,21.55%。结果表明,改进的NSGA-Ⅱ算法能够有效实现车辆停车延误、道路通行能力、车辆停车次数等多项性能指标的最优化控制。

4 结束语

本文将车辆延误最小、停车次数最少和通行能力最大作为评价尺度对青岛市崂山区某交叉口配时优化。鉴于传统的优化方法解决多目标问题存在缺陷,设计了一个经过改进的NSGA-Ⅱ算法,以此用来求解配时优化模型,并获得了良好的Pareto最优解,最后通过Vissim软件模拟证明了NSGA-Ⅱ-DE多目标优化模型的合理性和有效性。通过差分交叉变异来改进NSGA-Ⅱ子代,算法会增强全局寻优能力,收敛特性与鲁棒性更好,而在实际的信号控制系统上,延误和停车次数均明显下降。但是本文以T形交叉口为例,普遍性不足,未来还需要以更为常见的十字交叉口作为验证。