基于差分和状态空间遗传混合算法的信号配时优化

陈小静　李茂军　张辉

摘 要：为了最大限度地挖掘现有道路的承载能力，提出了一种基于差分进化算法和状态空间模型遗传算法的两阶段混合优化算法，建立以车辆平均等待时间最小为目标的数学模型进行优化。为了解决差分进化算法在后期收敛速度变慢，容易陷入局部最优的缺点，引入改进后的状态空間模型遗传算法形成一种混合算法。然后，用所提出的混合算法对5个经典测试函数进行寻优测试，并与定时控制、差分进化算法以及状态空间模型遗传算法进行对比，实验结果表明该混合算法不仅提高了收敛速度，并且在保证了算法收敛精度的前提下缩短了迭代次数。最后，以单交叉路口为例，验证该混合算法在求解信号灯配时问题时的优化效果。

关键词：差分进化算法;状态空间模型遗传算法;信号配时;混合算法;平均等待时间

中图分类号：TP13      文献标识码：A

Signal Timing Optimization Based on Differential

and State-space Genetic Hybrid Algorithm

CHEN Xiao-jing1， LI  Mao-jun1， ZHANG  Hui2

（1.College of Electrical and Information Engineering， Changsha University of Science and Technology， Changsha，

Hunan 410114， China; 2. College of Robotics， Hunan University， Changsha， Hunan 410114， China）

Abstract：In order to maximize the capacity of existing roads， a two-stage hybrid optimization algorithm based on differential evolution algorithm and state-space model genetic algorithm is proposed， and a mathematical model with the goal of minimizing the average waiting time of vehicles is established for optimization.In order to overcome the slower convergence speed in the later stage of the differential evolution algorithm and easy to fall into local optimum， the improved state-space model genetic algorithm is introduced to form a hybrid algorithm.Then， 5 classical test functions are used to test the performance of the algorithm. The algorithm was compared with timing control， differential evolution algorithm， and state-space model genetic algorithm based on state-space model. Experimental results show that the algorithm not only improves the convergence speed， but also shortens the number of iterations while ensuring the accuracy of the algorithm's convergence. Finally， taking a single intersection as an example， verify the optimization effect of this algorithm in solving the signal timing problem.

Key words：differential evolution algorithm; genetic algorithm based on state-space model; signal timing;hybrid algorithm; average waiting time

单交叉路口交通信号控制系统大多采用多时段定时控制的方式，根据路口历史通行数据把一天划分为多个时间段，人为的设置不同的信号灯时间[1]。由于传统的信号灯配时方法无法适应复杂的交通环境和实时多变的车流量要求，不少学者开始利用神经网络、模糊控制、自适应控制、智能优化算法等研究信号灯的配时优化方案[2-5]，增强交叉路口的通行效率，使车辆拥堵情况得到改善 [6]。

Wu等提出了一种以十字路口的交通流量和周围十字路口的交通流量为参数的雾计算交通灯控制系统[7]，它的主要原理是采用雾计算平台计算和共享某一路口及相邻路口的实时车流量情况，来协调多个路口之间的信号灯周期。陈丹利用混沌优化的遍历性改进遗传算法[8]，来提高初始种群的随机性和多样性，然后在变异操作后对部分种群进行混沌搜索，并用该算法对城市微观交通仿真系统模型进行优化。Qu等以路口的通行承载力最大化为目标构造了绿灯利用率的数学模型[9]，而且并提出了一种能够实时调整绿灯时间的自适应控制方案。张文泉将模糊控制和按照误差逆向传播的BP神经网络融合，得到一种拥有自学习结构的多交叉口信号协调系统[10]。张小雨等综合考虑车辆起步延误、道路的通行能力和车辆尾气排放等因素，构造多目标信号配时优化模型[11]并采用遗传算法求最优解。

针对基本群体智能算法在解决信号灯配时优化问题上所出现的收敛速度缓慢、收敛精度不高以及易陷入局部最优的问题。建立了车辆平均等待时间的数学模型，并提出一种差分进化算法（Differential Evolution， DE）和改进的状态空间模型遗传算法（Modified Genetic Algorithm Based on State-space Model， MGABS）的混合算法。该混合算法在迭代前期采用DE算法来快速缩小搜索空间，在后期用MGABS算法加快收敛速度。仿真实验结果证明，该混合算法可以快速精准的找到车辆平均等待时间的数学模型的最优解。

1 控制策略

道路交通安全法规定，驾驶机动车在路口右转弯不受信号灯限制，所以这里不考虑右转车道，单交叉路口的车流一共分为8个方向，如图1所示。因为n2和n5、n3和n7、n1和n6、n4和n8的车流互不干扰，所以只需要设置4个方向的绿灯时间。每个方向上有两个车道是互不干扰的，取其中车流量较大的车道作为该方向上的实际车流量。

黄灯一般位于绿末红初之间，时间一般为3 s，可以在此时从视频检测系统获取各个方向的车流量和下一个分配点之前每辆车已经等待的时间[12]。例如在方向4的黄灯开始时获取视频检测系统中的数据，那么接下来第一个信号周期的绿灯时长分别为t1、t2、t3、t4，第二个信号周期的绿灯时长分别为t′1、t′2、t′3、t′3，在分配点之前的4个方向的绿灯时间分别为t″1、t″2、t″3、t″4。

3.3 差分进化和状态空间模型遗传混合算法

信号灯定时控制的方式无法合理的分配红绿灯时间，使得车辆通行效率低，容易造成交通拥堵，所以越来越多的研究人员尝试用智能算法来解决信号灯配时问题。DE算法在初始阶段能够快速收敛，并且善于求解复杂的多变量函数优化问题[17]。但是，DE算法也有缺点，引起其后期收敛速度变慢的主要原因就是变异操作。而MGABS算法参数少、容易实现、收敛速度快、跳出局部最优点的能力强。因此，将DE算法与MGABS算法融合在一起，形成一种两阶段混合优化算法。

首先，用DE算法对初始种群进行优化，当种群迭代Q次后，寻优搜索空间被缩小，则进入下一阶段;用MGABS算法在已被缩小的搜索空间中进一步寻优迭代，找出目标函数的最优解。关于两阶段混合算法迭代次数的分配问题，经过多次试验总结，当Q=0.8M时，实验结果相比其他迭代方式更接近最优值，而且标准差明显小于其他分配方式。

DE和MGABS混合算法的基本步骤如下所示，该算法分为两个阶段。

第一阶段采用DE算法：

Step1 初始化种群确定基本参数：迭代次数Q、种群规模N、总迭代次数M、粒子维度D、放缩因子F、交叉概率CR，在可行域内随机产生且满足约束条件的初始种群中选择三个不同的个体;

Step2 变异和交叉操作：根据（8）式在种群中随机选择两个个体进行向量差分后经过放缩，再加上第三个个体，得到变异后的新个体。将其按（9）式进行交叉操作来产生试验个体;

Step3 选择操作：比较试验个体和上一代个体，选择其中更优秀的粒子成为新的种群。

Step4 判断是否满足进入下一阶段的条件，若kSymbolcB@Q次则转至Step2，否则转至Step5;

第二阶段采用MGABS算法：

Step5按照（12）式构造状态进化矩阵G，将DE算法迭代Q次后的种群作为初始种群X（k），按（11）式进行迭代，产生子代群体X（k+1）;

Step6计算子代群体X（k+1）的个体适应度值。从X（k）和X（k+1）中选择N个优秀的个体设为下一代群体，然后置X（k+1）为X（k）;

Step7从X（k）中选出适应度较差的P个个体，若QSymbolcB@kSymbolcB@（M+Q）/2，则采用变异策略（1）;否则，采用变异策略（2）;

Step8判断是否完成M次迭代，若满足则终止进化;否则转至Step5。

4 仿真结果

4.1 测试函数

为了验证提出的差分进化和状态空间模型混合算法在处理复杂优化问题上的寻优精度和收敛速度，选取了5个经典标准测试函数进行寻优能力测试。测试函数的表达式、取值范围、全局最小值以及函数特性如下面表1所示。这5个函数分为单峰函数和多峰函数，单峰函数的作用是测试混合算法的收敛精度和收敛速度，而多峰函数具有多个的局部极大值，能够很好的测试算法的全局搜索能力和跳出局部极值的能力。

该算法的测试环境为：采用MATLAB R2018a编程语言，在Intel（R）Celeron（R） CPU 1007@ 1.50 GHz、内存4 GB的电脑上运行程序。

4.2 测试结果分析

为了检验混合算法的优化能力，在仿真实验中将种群规模均设为50，粒子维度设为20，总迭代次数设为200，比较5个测试函数独立运行30次的平均值、最小值、标准差。DE算法、MGABS算法和该混合算法的性能对比结果如表2所示。

4.3 信号灯配时优化

分别采用定时控制、DE算法、MGABS算法、遺传算法、蚁群算法以及混合算法对单交叉路口4个方向的绿灯时间进行优化配时。其中种群规模N=50，总迭代次数M=30，搜索空粒子间维度设为20，在[0，180]秒之间随机选择的5组车流量数据和各车的实际等待时间。设置每个方向的绿灯时间范围为[15，60]秒，绿灯周期上限Tmax =180 s，车辆驶出交叉路口的速度为t =3 s/辆，设置分配点之前的4个方向的实际绿灯时间t″1、t″2、t″3、t″4分别为30 s、22 s、35 s、26 s。为了更直观地体现该混合算法的优越性，与4种不同控制方式下车辆的平均等待时间进行比较，仿真实验结果如表3所示。

图2为表3中第1例的车辆平均等待时间优化曲线图，横坐标代表算法的迭代次数，纵坐标代表车辆平均等待时间。从图2中能够发现，随着迭代次数的增多，除定时控制外其他5种算法的车辆平均等待时间逐渐减小。虽然蚁群算法较早的收敛到最优值附近，但后期寻优效率低且优化效果不如该混合算法。在遗传算法的控制方式下，在迭代21次时找到了最优解，此时车辆平均等待时间最短，但迭代过程不够稳定。该混合算法前12次迭代时快速收敛到最优值附近，最终在第20次迭代时搜索到最小值153.4s，该混合算法与其他五种控制方式相比优化效果最好，证明DE和MGABS混合算法的有效性。

5 结 论

在合理的交通环境假设及约束条件下，综合考虑了分配点之前车辆已经等待的时间和在当前配点后2个绿灯周期内预计需要等待的时间，建立了以车辆平均等待时间最小为目标的数学模型。鉴于DE算法早期能够快速收敛、在求解复杂的多变量函数问题上优化效果明显，但迭代后期收敛速度变慢、全局搜索能力差的情况，将DE算法和MGABS算法相结合，形成一种两阶段的差分进化和状态空间模型遗传混合算法。实验结果证明，差分和状态空间遗传混合算法能够寻到最合适的绿灯时间分配方式，完成提高交叉路口通行效率的目标。

参考文献

[1] 柳长源，任宇艳，毕晓君.基于改进萤火虫算法的区域交通信号配时优化[J].控制与决策，2020，3：1-6.

[2] 罗文慧.智慧交通背景下道路交叉口交通流控制模型与算法研究[D].北京：北京交通大学，2019.

[3] HITCHCOCK O， GAYAH V. Methods to reduce dimensionality and identify candidate solutions in multi-objective signal timing problems[J].Transportation Research Part C，2018：398-414.

[4] 刘畅，魏丽英.考虑人均延误和人均排放的信号配时优化模型[J].哈尔滨工业大学学报，2018，50（9）：83-88.

[5] 赵盼明，刘钊，刘玉，等.基于模糊控制的小区域交叉口群过饱和状态信号协调优化[J].交通信息与安全，2018，36（4）：51-59.

[6] 雷洋，黄承锋.城市交通拥堵治理的研究综述和建议[J].综合运输，2018， 40（4）： 8-11.

[7] WU Qiong， HE Fan-fan， FAN Xiu-mei. The intelligent control system of traffic light based on fog computing[J].Chinese Journal of Electronics，2018，27（6）： 1265-1270.

[8] 陈丹.城市交通信号灯的仿真优化研究[D].武汉：武汉理工大学，2011.

[9] QU Xin-ming， YAO Hong-yun， WANG Yu-gang， et al. Adaptive control strategy based on effective utilization ratio of green light time [J].Transportation Research，2015（1）：54-58.

[10]张文泉.城市区域交通信号智能控制算法分析与研究[D].成都：西南交通大学，2016.

[11]张小雨，邵春福.城乡结合部道路交叉口多目标信号配时优化模型[J].系统仿真学报，2019，32（04）：709-717.

[12]王鼎湘，李茂军.基于车流量的交通灯智能控制算法[J].计算机应用与软件，2015，32（06）：241-244.

[13]王鼎湘.单交叉口智能交通灯配时优化控制策略[D].长沙：长沙理工大学，2015.

[14]张新明，涂强，康强，等.灰狼优化与差分进化的混合算法及函数优化[J].计算机科学，2017，44（9）：93-98.

[15]李茂軍，刘黄，李奇，等.基于状态空间模型的实数编码遗传算法[J].山东科技大学学报（自然科学版），2015，34（03）：1-7.

[16]齐战，李茂军，肖雨荷，等.基于改进状态空间模型遗传算法的分数阶PID控制器优化设计[J].控制与信息技术，2019，06：18-23.

[17]杜松，周健勇.一种差分进化和模拟退火粒子群混合算法[J].计算机仿真，2015，32（12）：218-221.