基于改进NSGA-Ⅱ的区域交通信号优化控制

牟 亮，赵 红，李 燕，仇俊政，崔翔宇，袁焕涛

(青岛大学机电工程学院，山东 青岛 266071)

0 引言

随着中国经济的日益发展，城市规模以及汽车保有量迅速增加，各类交通需求也随之增长[1]。交通拥堵问题亟需解决，道路渠化、增加车道等解决方案成本巨大并且周期较长，难以实施，因此交通信号控制成为一种可以有效解决交通拥堵问题的方法。目前城市内的交通路口错综复杂，不同的路口之间具有一定的联系，当采用单交叉口优化控制时易发生溢流现象，严重的话会导致区域路网交通瘫痪，因此单交叉口的研究已经不能从根本上解决问题，区域交通优化控制已经是最快速以及最经济的方法。

以上文章在研究区域交通信号配时优化时，未将车辆延误与尾气排放综合考虑。本文旨在达到路网性能的综合最优，故选用多目标优化NSGA-Ⅱ算法，建立关于车辆延误与排放的数学模型进行优化。并且本文将在快速非支配排序遗传算法的基础上提出改进，根据该算法的迭代特性，建立更加符合的交叉算子。

1 选取交通信号配时优化模型

为保证区域路网的交通能够高效、安全通行，交通信号控制的目标模型也需要由单目标优化向多目标优化发展。本文为提高区域路网的性能，将车辆延误与尾气排放作为优化控制目标来建立模型。

1.1 车辆延误模型

可以选用Webster延误模型和美国道路通行能力手册(Highway Capacity Manual，HCM)延误模型。Webster延误模型经广泛的使用和验证，得出仅适应于饱和度0～0.67范围内。而HCM延误模型适用于饱和度较高的干道协调控制的延误计算。本文是在这两种模型的基础上来建立模型进行计算的，公式[16]为

其中，dijk为区域路网中第i个路口第j相位第k车道的车辆平均延误;ci为第i交叉口周期长度;λij为第i交叉路口第j相位绿信比;qijk为第i交叉口第j相位第k车道的车流量;sij为第i交叉口第j相位的饱和流量;yijk为qijk与sij之比。

区域路网中的车均延误为

1.2 尾气排放模型

本文也将该效益作为目标进行优化。根据现有的研究[17]，区域交通的碳排放有很多因素影响，并且车辆在行驶过交叉口的过程中大都经历了4种工况，每种工况的汽车排放量不同，因此需要分情况进行考虑。

本文将以车辆的CO尾气排放量作为优化目标，周申培[18]将车辆行驶过交叉口的尾气排放量分为行驶排放和因车辆延误引起的怠速排放，排放模型为

其中，eijk为区域路网第i交叉口第j相位第k车道的排放量;e1为标准小汽车单位排放因子;Lijk为第i交叉口第j相位第k车道的路段长度;e2为标准小汽车单位怠速排放因子;dijk为区域路网中第i个路口第j相位第k车道的车辆平均延误。

区域路网中的车均尾气排放量为

1.3 建立优化目标模型

将两个优化目标放到同一量级上进行比较，实地对区域路网的原始配时进行采集，运用上述模型求得初始的延误d0以及初始排放e0，最终构建交叉口的优化模型为

2 NSGA-Ⅱ基本概念

NSGA-Ⅱ(带精英策略的非支配排序的遗传算法)，是基于遗传算法的多目标优化算法[19]。快速非支配排序会根据个体的优劣程度对种群进行分层，分到多个不同的前沿面中。拥挤距离描述了种群中个体的分散程度，拥挤度可以保证种群的多样性，计算公式为

为了维持种群的多样性，需要对拥挤度进行比较。拥挤距离比较算子定义为

i>j⟺irankCj

对于处于同一前沿面的个体，优先选取拥挤度小的，以保证个体的多样性。

精英策略：将父代种群Pt和子代种群Qt组合成大小为2N的新种群，对Qt进行快速非支配排序和拥挤度计算，选择前N个个体进入种群Pt+1。如果某个相同前沿面的所有个体加入会导致超过种群上限。

3 改进的快速非支配遗传算法

3.1 自适应交叉算子

为提高该算法的收敛性以及寻优能力，在原方法的基础上提出一种自适应交叉算子的改进方法。

基本的NSGA-Ⅱ算法中是采用的二进制交叉，该交叉算子实现起来非常简单，但是移动空间不足，算法搜索空间小，易陷入局部最优解。因二进制交叉算子的不足，引入一种新的交叉算子，正态分布交叉算子(Normal Distribution Crossover)。正态分布交叉算子搜索范围大，适合前期的要求[20]，因此在算法迭代的前期将大比例采用正态分布交叉算子。当进行到算法迭代后期，种群中个体大都接近最优解，不需要再进行大范围的搜索，此时要求算法可以迅速收敛，因此将交叉算子大比例分配给二进制交叉算子，以加快算法的收敛。

引入一个可以根据算法迭代次数自适应调整算法交叉度的因子，前期加大个体的交叉，后期适当减小交叉度，自适应交叉算子的更新公式为

其中，M=P1+P2,N=P1-P2,P1,P2为选中进行交叉的父代个体；g为算法当前的迭代次数，G为算法的总迭代次数；beta为正态分布随机变量。

3.2 自适应调节种群规模

在算法前期，当采用更大规模的种群时，可以提高算法的寻优范围，在后期经迭代的个体基本都已趋向最优值，要求快速收敛，所以不再需要大规模的种群，此时将种群规模适当缩小，可以加快算法的收敛。

需要添加一个条件来判断何为算法前期何为算法后期，这里采用每迭代m次产生的m个最优值，采用线性拟合的方法求得这m个点的斜率，当该斜率的绝对值小于某个数值时，说明寻优过程已经逐渐平稳，基本得到最优解，此时不再需要大规模的种群。判断公式为

其中，左侧为所取g个点的斜率的绝对值，ε表示判断算法前后期的标准。

3.3 算法流程

改进后NSGA-Ⅱ的算法流程如下：

1)随机产生2N个个体的初始种群P0；

2)进行自适应交叉和变异操作生成数量为N的新种群Qt;

3)将种群Pt与Qt合并得到Rt，并对合并种群进行快速非支配排序；

4)计算拥挤度距离，利用精英策略选择N个个体作为新的父代种群Pt+1；

5)判断当前迭代次数g是否不小于最大迭代次数G，是，则算法的迭代结束，否则g=g+1，并进行下一步判断；

6)当前迭代次数g达到了m次后，每迭代一次就选取m代的m个最优值，进行以下判断：

若成立则返回第2)步，否则进行下一步。

7)随机产生N个种群，与父代种群Pt+1合并产生个数为2N的种群Pr；

8)对种群Pr进行快速非支配排序、精英策略，找出最优的N个个体，返回第2)步。

本文算法的流程图如图1所示。

图1 改进NSGA-Ⅱ的算法流程图

4 算法案例分析

为验证本文方法应用于区域交通方面的有效性，使用matlab R2015b对该方法进行编程，在CPU型号Core i7-8565U，内存为8G的电脑中运行。选取青岛市青岛理工大学附近路网，如图2所示，该路网为典型区域路网，并对该路口的数据进行实地采集。

图2 本文案例的路网结构

4.1 交叉口数据信息

该区域路网由4个交叉路口组成，每个路口每个相位由两条对向车道组成。并设置相位最小绿灯时间为20s，令行人有充足的时间穿过马路，最大相位绿灯时间为50s，防止某相位绿灯时间过长对其他相位造成积压车流的现象；最小周期时长为80s，最大周期时长为150s。

机动车相位饱和设置为1 500 pcu/h，选取CO作为本文尾气排放的目标，标准小汽车CO的排放因子为45g/(pcu.km)，标准小汽车怠速排放因子为53g/(pcu.h)。

对该路网高峰时期(16：00～17：00)的小时车流量进行采集，采集结果如表1所示。

表1 路网小时车流量(16：00～17：00)

4.2 优化结果对比

为验证本文的改进方法相对于未改进方法的优势，将上述案例分别用标准NSGA-Ⅱ以及改进的NSGA-Ⅱ进行优化，并利用迭代图的形式形象展示改进后的优点。在迭代图中会展示每代中的最优值以及平均值，这里每代最优值是在经快速非支配排序中第一前沿面中选取，并通过拥挤度距离的计算选取拥挤度最佳的一个，因为两个优化目标均放在同一标准下，故在迭代图中将表示两个目标的平均值。迭代图如图3和图4所示。

图3 标准NSGA-Ⅱ迭代图

图4 改进NSGA-Ⅱ迭代图

通过图3和图4的比较，可以明显地发现改进后的NSGA-Ⅱ方法寻找最优值的速度以及精度均优于未改进的，在100代左右就找到了最优值，而未改进的到200代左右才慢慢收敛；并且改进后的每代平均值波动剧烈，说明改进方法的搜索范围扩大。

通过采集得到的原始区域路网的信号配时及上述两种方法的优化结果，进行对比分析，如表2所示。

表2 改进前后NSGA-Ⅱ的优化配时方案

将得到的优化值取平均值，标准NSGA-Ⅱ的延误平均优化值为0.901 8，排放平均优化值为0.949 3；改进NSGA-Ⅱ的延误平均优化值为0.844 0，排放平均优化值为0.924。经过对比可知，改进后的方法不管是在迭代过程还是在优化值上均优于标准的方法。

将改进NSGA-Ⅱ算法执行后，会得到Pareto最优解集，该解集说明了车辆延误与尾气排放之间的关系，如图5所示。从图5可以看出尾气排放与车辆延误呈递减关系，当需要更小的尾气排放时，这会以牺牲车辆延误为代价，同样当需要更小的车辆延误也会导致尾气排放的增加。

图5 改进NSGA-Ⅱ的Pareto最优解集

4.3 算法实时性分析

对于区域交通信号优化控制，最根本的是根据现实交通情况，实时优化并调整交通信号的配时。为对本文算法的实时性进行分析，分别将改进前后的算法应用到本文案例与ZDT1测试函数中，并记录两种算法寻到最优值的时间。其中ZDT1是一种多目标测试函数，公式为

两种算法在本文案例和ZDT1测试函数上的寻优时间如表3所示。从表3的算法寻优时间可以看出，改进后的算法比改进前找到最优值的时间更短。同时可知算法的计算时间也可以满足交通信号配时优化对实时性的要求。

表3 算法寻优时间

4.4 VISSIM仿真

VISSIM是一种微观的、基于时间间隔和驾驶行为的仿真建模工具，用于城市交通和公共交通运行的交通建模[21]。它可以分析各种交通条件下，如车道设置、交通构成、交通信号、公交站点等，城市交通和公共交通的运行状况，是评价交通工程设计和城市规划方案的有效工具。根据本文提到的案例，在VISSIM中搭建仿真模型，如图6所示。

图6 本文案例的VISSIM仿真模型

为验证本文方法的有效性，将原始配时以及利用改进NSGA-Ⅱ方法得到的优化值进行对比，利用VISSIM的输出文件对该区域路网的车辆延误以及尾气排放进行评价。仿真周期设置为1h，采样周期设置为60s，对该路网的各种数据进行采集，采集得到数据之后进行处理，如图7和图8所示。

图7 优化前后配时的车辆平均延误对比

图8 优化前后配时的平均CO排放量对比

经过VISSIM仿真后，对比仿真得到的数据，本文改进的方法对于交叉口性能的优化十分有效。在CO的排放方面，相比于原始配时降低了8.213%；在车辆平均延误方面，降低19.023%。并且改进后的全局搜索能力较之前更强，相对于标准NSGA-Ⅱ具有一定的优势。

5 结论

针对标准NSGA-Ⅱ方法易陷入局部最优以及精度不够的问题，提出的改进交叉算子的方法，根据迭代过程每个阶段的特点进行自适应调节，前期加大交叉扩大搜索的范围，后期加速收敛。建立车辆延误及尾气排放的优化模型，将各个交叉口的有效绿灯时长作为变量，并利用改进前后的NSGA-Ⅱ求解该模型，最后利用VISSIM进行仿真分析，经验证改进后的NSGA-Ⅱ能够有效应用到区域交通信号配时优化中，提高区域路网性能，减少延误以及尾气排放。这个方法综合考虑了路网的机动车效益以及环境效益，并且达到了整体上的优化，得到了车辆延误以及尾气排放之间的关系，克服了单目标优化的弊端。