基于黄金分割双种群遗传算法的区域交通信号控制

张诗煜，嵇启春，孟月波

(西安建筑科技大学 信息与控制工程学院，西安 710000)

0 引言

据统计，在交通出行的高峰时段，处于拥堵或缓行状态的城市占全国城市的61%，并且全国主要城市道路信控路口的服务水平较低[1]。城市交通信号控制是减少交叉口延误、提高交通效率、缓解交通拥堵的重要手段[2-4]，而区域交通信号控制是城市交通控制中一种行之有效的信号配时方法[5-7]。信号控制技术的关键在于信号配时模型中控制参数的确定。文献[8]同时考虑车辆自身延误和下游延误，构建交叉口之间的预测模型和互动模型，并采用滚动时间窗进行优化，降低区域整体延误时间；文献[9]构建以平均延误时间为目标的交通优化模型，同时引入马尔科夫链改进固定相序信号控制模型，并采用遗传算法优化求解，提高了路网通行效率。但以上研究只考虑车辆延误指标，实际上对交通信号控制参数进行优化时，需要综合考虑延误时间、通行能力、排队长度等多个目标。而权衡多个优化目标的关键在于怎样将各个目标结合起来达到综合最优控制。文献[10]构建以区域总通行量和总延误为目标的区域协调控制双层规划模型，并结合遗传模拟退火算法求解模型，但优化目标分解分层控制，得到的不一定是全局最优解；文献[11]提出基于饱和度、延误时间、通过量的多目标区域协调控制算法，采用遍历的方法求解模型的最佳方案，但计算量过大求解速度较低；文献[12]以停车次数、延误时间和排队长度的加权和为综合目标，并结合Q学习和粒子群算法对模型进行求解，能够有效提高城区的通行效率，但模型中权重的大小由设计者的重视程度选取；文献[13]构建以区域机动车排放最小和路网通行能力最大为目标的交通调控模型，并用改进蚁群算法求解模型，能够有效控制交通污染同时合理引导交通流的分布，但模型通过设置不同加权系数来平衡权重，求解过程繁琐；文献[14]构建以车均延时、平均排队长度和通行能力为目标的交通控制模型，结合快速非支配排序遗传算法求解，能均衡车辆分布、提升路网效率，但计算复杂且耗时。

本文对信号配时优化模型和遗传算法两方面进行改进，提出一种基于黄金分割双种群遗传算法的城市区域交通信号协调控制策略。在非均匀交通流的区域交通信号优化控制研究中，以区域内交叉口周期时间、相位时间和相位差为控制变量，以路网总通行能力和总延误为优化目标，为获取多目标模型的综合最优解，引入目标相对占优策略处理多目标优化问题。由于遗传算法在求解高维多变量的区域交通协调优化问题时存在易早熟效率低的问题，故本文采用双种群遗传算法(dual population genetic algorithm,DPGA)，主种群采用动态交叉变异算子进行全局寻优，次种群引入黄金分割法(golden ratio,GR)进行局部寻优，同时在两种群间进行个体交换。

1 城市区域交通信号多目标优化建模

1.1 交通信号控制目标的选取

区域协调控制策略实际应用必须具备高实时性、模型适应多变的离散、非均匀交通流等条件，才能实现对区域交通的有效协调控制。通常在交叉口车流量较小且不会对上游交叉口有影响时，以延误时间作为评价指标构建区域交通协调控制模型；当交叉口的车流量接近甚至大于路网通行能力时，在交叉口必定会产生拥堵现象，此时在构建区域交通协调控制模型时需要保证通行能力最大，能够对交叉口的车流量进行疏导分流从而减小车辆排队。因此本文综合考虑通行能力和延误时间2个决策目标，建立城市区域交通信号协调控制模型。

1.2 基于目标相对占优策略的区域交通信号协调控制模型

本文所建的区域交通信号协调控制模型是一个高维多变量的多目标优化问题，它的解实际上是由多个Pareto最优解组成的最优解集。因此，为从Pareto最优解集中选择一个满足目标的“最好”解，使各子目标函数之间达到某种平衡，让各目标函数都最接近满意值，本文引入目标相对占优策略[15]对多目标优化问题进行处理，其基本思想是：对种群中的所有个体分别计算各子目标函数值，将每一个子目标函数的最优值记为该子目标函数的基点，然后分别计算各个个体相对各基点的目标值之和，目标值之和最优的个体即为该种群的最优个体，也就是多目标优化模型的最优解。

模型中对交叉口每条车道组的绿灯时间约束、公共周期时长约束和相位差约束均可在算法的种群初始化时进行调整。假设随机个体k代表一种信号配时方案，则个体k基于目标相对占优策略的区域交通信号控制模型的目标函数计算公式为：

(1)

区域交叉口总通行能力以美国交通研究委员会(TRB)的《道路通行能力手册》中的通行量的计算方法为基础，模型的具体形式为：

(2)

建立区域总延误模型时，要考虑相位差对延误的影响，区域的延误分为路网边缘进口道延误和路网中间交叉口延误，计算公式为式(3)。

(3)

其中：路网边缘进口道延误由路网边缘进入车流所产生，采用HCM2000延误模型[3]进行计算，如式(4)；而区域内部交叉口延误是由车流队行驶到路网内部的下游交叉口所产生的延误，分为车队头部遇到红灯和车队尾部遇到红灯两种情况，其计算公式[6]为式(5)。

(4)

(5)

2 基于黄金分割的双种群遗传算法

为解决遗传算法寻优过程易早熟且收缩效率低的问题，同时达到区域交通协调控制的高效实时性要求，本文将黄金分割法引入双种群遗传算法中，两个种群同时且独立地进行寻优操作，并将次种群中最优的个体迁移到主种群中替换最差个体，主种群中最优个体代替次种群中的相似个体，提高算法的全局寻优性能，使算法快速且准确的寻找到最优解。

2.1 基于黄金分割率的动态交叉变异算子

针对遗传算法收敛速度较慢的问题，在主种群中采用基于动态交叉变异算子的遗传算法进行全局寻优。通过黄金分割率选择最佳自适应交叉、变异算子，每次搜索空间缩小0.382倍或0.618倍，能够快速寻找最优自适应点，提升算法搜索效率。改进的交叉和变异概率公式如下：

(6)

其中：f为进行变异操作的个体的适应度值；f′为进行交叉操作的两个个体中较大的适应度值。favg为种群的平均适应度值；fmax为种群的最大适应度值，Pcmax为最大交叉概率，Pmmax为最大变异概率。

2.2 基于黄金分割的局部寻优算法

为提高算法的寻优精度，在次种群中以黄金分割法为基础进行局部寻优操作，依次对种群中各个体的每一维进行黄金分割。在局部寻优过程中，假设个体为X=(x1,x2,…,xn)，若对个体的第i维变量进行优化，需要固定其他n-1维的值，计算第i维变量的搜索区间，并在个体第i维的搜索区间内进行多次黄金分割，用优化得到的高质量的新个体替换旧个体；然后对个体第i+1维变量进行优化，固定其他维的值，求解第i+1维变量的搜索区间并对其进行黄金分割，以此类推，直到对个体的每一维都进行黄金分割，得到局部最优解。其中，个体X第i维变量xi的搜索区间[ai,bi]的计算公式为：

ai=max(ai0,xi-ei),bi=min(bi0,xi+ei)

(7)

式中，[ai0,bi0]为个体第i维变量xi的初始搜索区间即该维变量xi的整个区间。

2.3 基于黄金分割的双种群遗传算法的流程

基于黄金分割双种群遗传算法(GRDPGA)的求解过程步骤如下，流程如图1所示。

图1 改进算法的求解流程图

步骤一：初始化。对遗传算法和黄金分割算法的控制参数进行初始化，并随机生成初始种群PA和PB，PA和PB的种群规模M，最大迭代次数Gen，最大交叉概率Pc和最大变异概率Pm。

步骤二：算法的终止判断。判断是否达到最大迭代次数，若达到则输出最优解；否则，进入下一步。

步骤三：计算适应度函数值。对种群PA和PB中的每个个体，根据本文的配时模型如式(1)，计算个体的目标函数值。

步骤四：个体迁移。局部寻优种群PB中的最优个体迁移到种群PA中替换最差的个体；种群PA中最优个体替换种群PB中与其最近似的个体，个体相似度的计算为：

(8)

步骤五：PB进行局部寻优操作。对种群PB进行2.2中的局部寻优操作，更新种群PB，并保留种群PB中一定数目的最优个体。

步骤六：PA进行遗传操作。先对种群PA进行轮盘赌选择操作；然后对种群PA进行交叉操作和变异操作，具体的交叉概率和变异概率公式如式(6)；更新种群PA，并保留种群PA中一定数目的最优个体。

3 实例验证

3.1 GRDPGA算法的实验分析

在4个标准测试函数上对GRDPGA算法和标准遗传算法进行对比分析。仿真实验环境基于Windows 7操作系统，使用MatlabR2017a进行编程仿真。具体测试函数如下：

1)Sphere Model函数：

2)Rastrigin函数：

3)Griewank函数：

4)Rosenbrock函数：

4个测试函数的具体参数设置如表1所示。

表1 测试函数参数设置

在对比实验中，设置遗传算法参数：M=100，Gen=200，Pc=0.8，Pm=0.1。对各测试函数的适应度函数的迭代过程进行比较，结果如图2所示。

图2 4种标准函数进化适应度曲线

从图2中可以看出，GRDPGA算法和GA算法最终都会收敛，得到一个最优解，但本文的GRDPGA算法具有更高的寻优精度，且算法收敛速度较快。为了进一步证明GRDPGA算法的有效性，对5个标准函数进行20次独立测试，测试结果如表2所示。

表2 测试实验结果对比

GRDPGA算法综合性能较高，其标准差均小于GA算法，说明GRDPGA算法具有较稳定的寻优过程。总体来说，本文提出的GRDPGA算法是可行有效的，能够快速稳定的的获得全局最优解。

3.2 区域配时实例分析

3.2.1 实例描述

选定文献[16]中大连市内的一块交通区域为研究对象，此区域有9个路口，区域内并没有单独的左转相位，因此设东西直行相位和南北直行相位为协调相位，所有交叉口全部采用两相位进行控制，且每个信号相位的绿灯间隔时间均为5 s，其中黄灯时间3 s，全红2 s，路段上的平均行驶车速为40 km·h-1，各交叉口的车流信息如表3所示，各交叉口之间的距离如图3所示。

表3 各交叉口的车流信息

图3 测试路网

3.2.2 基于目标相对占优策略的控制模型结果分析

为验证本文所构建的基于目标相对占优策略的区域交通信号协调控制模型的效用，采用GA算法分别对本文所建模型(模型1)、总延误时间和总通行能力固定加权的优化模型(模型2)进行50次仿真计算。设分析时间长度取T=240 s，反映上游交叉口影响的校正系数K=0.5，种群规模M=100，最大迭代次数Imax=100，交叉概率Pc=0.8，变异概率Pm=0.2，最大信号周期为Cmax=180 s，最小信号周期为Cmin=80 s，直行最小绿灯相位时间15 s，每车道饱和流率1 650 veh·h-1，2种情况的仿真结果统计如表4所示。

表4 两种情况的仿真结果统计

从表4中可以看出，两种情况下总通行能力和总延误的最优值和平均值的相对误差比较小分别为4.02%，4.73%和3.48%，7.07%，也就是说，相比以延误为主通行能力为辅的优化模型，本文所建模型与对交叉口通行能力和总延误的寻优结果改善不明显，但综合目标优化模型的寻优时间大大缩短了17.81%，并且符合最大限度提高道路通行量，并使交叉口延误尽可能小的城市交通控制目标，因此文中所构建的信号配时控制模型是有效的。

3.2.3 GRDPGA算法对信号配时模型的效用分析

为验证GRDPGA算法在求解信号配时模型时的效用性，分别采用GRDPGA和GA算法求解本文构建的信号配时优化模型，计算机数值计算采用Matlab编程。在采用两种算法进行优化求解时，取种群规模M=100，最大迭代次数Imax=50。并对两种优化算法进行50次独立仿真计算，对比分析两种算法的最佳配时方案的控制性能。

1)GRDPGA的算法性能分析：

GRDPGA和GA两种算法性能指标的统计结果如表5所示，其中，最大总通行能力maxQ为50次运行结果中总通行能力的最大值，平均总通行能力avgQ为50次运行结果中总通行能力的平均值，最小总延误minD为50次运行结果中总延误的最小值，平均总延误avgD为50次运行结果中总延误的平均值，优化时间为50次运行的平均时间。从表5中可以看处，GRDPGA与GA算法均可得到可行解，但在最大总通行能力maxQ、平均总通行能力avgQ、最小总延误minD、平均总延误avgD和优化时间等指标GRDPGA均优于GA，说明对本文区域交叉口控制实例设计的基于黄金分割的双种群遗传算法具有较好的应用效果。

表5 GRDPGA和GA两种算法50次数值计算的统计结果

2)控制方法的控制效能分析：

进行50次独立仿真运算，分别采用GRDPGA和GA两种算法求解区域信号配时模型，得到50组信号配时方案及其对应的区域交叉口性能指标，从中选择一组配时方案及性能指标统计结果如表6所示。采用GRDPGA算法优化

表6 两种算法的一组配时方案及性能指标

模型相比GA算法在区域总通行能力性能和整体延误性能上均得到了明显改善，分别约有15.71%,25.11%的改进，大大提升了城市交通区域协调控制的综合能力。

4 结束语

本文通过引入目标相对占优策略构建区域交通信号协调优化模型，并将黄金分割法与双种群遗传算法相结合，改善了遗传算法易早熟、搜索速度慢的问题。通过利用4个测试函数和实际路网数据仿真实验，结果表明：所提的区域信号配时方法能够最大限度提高道路通行量，并使交叉口延误尽可能小，符合城市区域交通控制的优化目标；改进的GRDPGA算法能够有效地实现区域信号配时，是一种高效稳健的全局优化算法。