基于改进克隆选择算法的区域交通灯配时优化

陈海洋，金晓磊，牛龙辉，刘喜庆

西安工程大学 电子信息学院，西安710600

1 引言

交通作为城市经济活动的命脉，对促进社会发展、提高人民生活水平具有十分重要的意义，但随着城市居民汽车拥有量的不断攀升，交通拥堵现象在我国很多城市都日益严重。在基础设施建设周期漫长且耗资巨大的情况下，充分利用现有的路网资源、优化交通信号控制对解决城市交通拥堵问题的重要性不可低估。

交通灯是城市交通信号控制的最重要组成部分，目前国内外已有许多关于智能交通灯的研究工作，而依据实时交通流动态设置交通灯状态正是最常用的方法之一[1-4]。Wu 等[5]提出了基于雾计算的交通灯智能控制系统，它的主要思想是通过雾计算平台来计算和分享当前路口及周围路口的实时车流量信息，并以实时车流量作为参数，设计交通灯智能控制算法，使相邻路口的交通灯周期实现相互协调、共同优化。Shaghaghi等[6]提出了一种基于车载自组网的自适应交通控制系统，该控制系统以交叉口处的车辆排队长度为交通评估依据，并采用车对车通信技术与车对基础设备通信技术进行车辆密度计算、信息传递。Muntaser 等[7]提出一种基于模糊系统与车辆通信技术的交通信号控制策略，将信号控制问题转化为逻辑问题而不是优化问题，并证明提出的控制策略性能是优越的。Sun 等[8]提出了一种基于车联网（IOV）的动态交通控制与诱导协同优化模型，该模型包含三层，其中上层模型通过遗传算法求解，中层模型和下层模型通过连续平均法求解。Zhao 等[9]提出一种基于遗传算法和机器学习的交通灯实时调度算法，该算法根据交叉口的实时交通流来调度每个交通灯的时间相位，同时考虑每个交叉口下一个时间段的车流量，此车流量数据采用线性回归算法预测，仿真结果表明该调度算法通过减少路网中所有行驶车辆的总等待延误提高了路网的交通流畅性。

区域交通灯配时控制优化属于全局优化问题，遗传算法等智能优化算法对解决多变量全局寻优问题具有明显优势，因此，近年来许多学者将遗传算法及其改进算法应用于交通优化研究领域[10-13]。而与遗传算法同为进化类智能优化算法的免疫克隆选择算法同样具有很强的全局搜索能力，但在交通控制方面的应用则较少。相比于遗传算法只考虑到个体的适应度，免疫克隆选择算法既考虑抗体与抗原间的亲和度，也考虑抗体浓度；遗传算法只有变异和交叉操作，而免疫克隆选择算法具有独特的克隆操作算子、种群更新算子。因此本文考虑将免疫克隆选择算法应用于区域交通灯配时优化，并以西安市某区域路网为研究参考对象，提出一种基于改进免疫克隆选择算法的交通灯实时配时方法。本文提出的配时方法以区域路网中所有路口总滞留车辆数最小为优化目标，将交通灯状态设置问题转换成免疫克隆选择算法搜索最优解问题，并将克隆选择算法编码和解码过程融入到交通灯配时控制场景中，提升了路网的交通效率，对减轻城市道路通行压力、保障市民出行畅通具有重要的意义。

2 改进的免疫克隆选择算法

免疫算法是受生物免疫学启发，模拟免疫系统工作原理来解决现实生活中复杂问题的智能算法[14]。克隆选择算法是其中的一个重要研究方向，主要思想是将现实问题和问题的解分别抽象为克隆选择学说中的抗原和抗体，通过选择、克隆、变异等一系列操作来进行最优解的搜索。

免疫克隆选择算法以激励度来衡量抗体质量的优劣。激励度的计算需综合考虑抗体亲和度与抗体浓度，计算公式通常如式（1）所示：

式中，sim(abi)为抗体abi的激励度；aff(abi)为抗体abi的亲和度；den(abi)为抗体abi的浓度；a、b为计算参数，根据实际情况确定。从式（1）中可以看出，抗体的亲和度值越高、浓度值越低，其激励度值就越高。抗体浓度值高，意味着当前种群中相似个体较多，对其进行一定抑制可以更好地保证种群的多样性，使最优解的搜索不会只局限于一小片区域。

针对免疫克隆选择算法在寻优过程中收敛速度较慢的问题，本文提出了两个改进点：一是利用双层动态变异算子对种群中抗体进行变异；二是对克隆抑制算子和种群刷新算子进行了改进。

（1）双层动态变异算子

在标准免疫克隆选择算法中，抗体的变异概率一般取一较大的确定值，高频率的变异是抗体种群多样性和亲和度成熟的重要保证。但在寻优迭代过程的后期，较大的变异概率会使得算法缺乏局部搜索，并且有一定可能对当前种群中已经寻得的优秀抗体造成破坏。因此，在许多学者的研究中，都采用了动态变异算子，即变异概率会随着迭代次数增加而动态调整。

本文提出的双层动态变异算子是指变异概率会随着种群迭代次数的增加而线性递减。且在同一代中，被选择出来进行克隆的父代抗体在当代种群中激励度排名越靠前，对它的所有克隆副本以更小的概率进行变异，反之，父代抗体在当代种群中激励度排名越靠后，对它的所有克隆副本以更大的概率进行变异。变异概率值的第一层动态调整是基于迭代次数，使得算法既能在前中期快速、大范围寻优，也能在后期进行更多局部搜索且有更大概率稳定收敛于全局最优解；变异概率值的第二层动态调整是基于每一代中父代抗体的激励度排名，既能对不够优秀抗体的克隆副本进行较大的变异以搜索更优秀的抗体，又能尽可能地保护优秀抗体的克隆副本不受太大的破坏得以传到下一代。

（2）改进的克隆抑制算子与种群刷新算子

标准免疫克隆选择算法的运算过程大致如下：种群个体数为NP，先进行选择操作，即挑选出种群中激励度排序靠前的k 个抗体，再对这k 个抗体进行克隆、变异操作。之后对变异结果进行再选择，即克隆抑制，剔除亲和度较低的抗体，仅保留亲和度最高的k 个抗体。最后进行种群刷新，即随机生成NP-k个新抗体，与经过克隆抑制保留下来的k个抗体组合，形成新一代种群。

用随机生成的新抗体，来替代选择操作中被淘汰的次优抗体，可以大幅提高种群的多样性。但随机生成的新抗体亲和度好坏程度不定，不利于加速种群收敛。对此，本文提出了改进的克隆抑制算子与种群刷新算子：种群个体数为NP，先选择种群中激励度排序靠前的NP/2个抗体，再进行克隆、变异操作，之后进行克隆抑制，每个父代抗体的所有克隆副本仅保留亲和度最高的两个，这样被保留下来的抗体共有NP 个，这NP 个抗体就是新一代的种群。如此的克隆抑制与种群刷新机制，可以大幅提高算法收敛速度，但需配合较大的克隆倍数值并应用动态变异算子，否则种群的多样性得不到保障，容易陷入局部最优。

综上所述，本文提出的改进免疫克隆选择算法的完整运算过程可描述如下：

（1）随机生成初始抗体种群。

（2）判断是否满足迭代终止条件：若满足，则终止算法运算，输出末代种群中的最优解；若不满足，则执行步骤（3）。

（3）计算当前种群中所有抗体的激励度值，并按降序排序。

（4）选择排序靠前的一半抗体，对它们以相同的倍数进行克隆复制。

（5）利用双层动态变异算子对克隆得到的副本进行变异操作。

（6）利用上文提出的改进的克隆抑制算子与种群刷新算子进行克隆抑制、种群刷新，再转入步骤（2）。

3 基于改进克隆选择算法的区域交通灯配时方法

传统的固定配时交通灯只是机械地变换信号，不能根据当前交通路网中的车流状况进行灵活调整，导致时常出现一个路口绿灯长亮方向无车通过，而红灯长亮方向则排起长长车队的现象。而目前随着检测传感器[15]、车载卫星定位[16]、射频模块[17]和视频图像检测[18]等技术的发展，实时车流信息的获得不再是问题。因此，本文的研究工作就是将智能优化算法应用到区域交通灯配时方案中，根据实时获取的车流量信息，灵活地对区域交通灯配时，使得区域交通状况能得到显著优化。

本文以西安市某区域一个包含36 个十字路口的路网为研究参考对象。为方便具体研究，对这36 个路口进行标识，标识名为C1～C36。

一片区域内所有十字路口的交通灯状态设置是一个复杂的实际问题，难以直接应用智能优化算法，需要先从复杂的实际问题中找出最关键的控制因素。通过调研本文研究的区域路网，发现这片区域中C1～C21 路口为二相位控制，C22～C36 路口为四相位控制，相位图分别如图1、2 所示（右转弯不考虑）。基于以上各路口的相位调研情况，则可将区域内所有路口的交通灯状态设置问题，转换成在不同时间确定各个路口哪一个相位获取通行权的问题。

图1 路口C1～C21相位图

图2 路口C22～C36相位图

为了实现区域交通灯的配时优化，本文提出一种基于改进免疫克隆选择算法的区域交通灯实时配时方法，采用克隆选择算法搜索最优解，最优个体解码后其表现型转换成对应各个路口交通灯状态。克隆选择算法的过程大致为：首先，初始化初代种群；随后，通过激励度评估来筛选种群个体；最后，借助免疫算子，产生下一代个体，生成代表新的潜在解集的种群直至进化到最高代种群。为了实时控制交通灯，需要利用克隆选择算法和各路口的实时交通流数据，找到使在单位时间T 内各个路口滞留车辆数总和达到最小的交通灯配时方案。配时方法具体描述如下：

（1）基因编码和初始化种群

①基因编码：表现型到基因型映射

对于二相位的路口，使用二进制编码表示基因型，用“0”代表相位a，用“1”代表相位b。所以从表现型到基因型的映射就是相位a对应“0”，相位b对应“1”。

对于四相位的路口，同样使用二进制编码表示基因型，用“00”代表相位c，“01”代表相位d，“10”代表相位e，“11”代表相位f。所以从表现型到基因型的映射就是相位c对应“00”，相位d对应“01”，相位e对应“10”，相位f对应“11”。

根据二相位、四相位的编码规则，在整个区域36 个路口全部编码后，字符串的长度为51 位。其中，字符串第1～21 位对应路口C1～C21，字符串第22～51 位对应路口C22～C36。举例说明：编码字符串的第3、4 位解码后分别对应路口C3、C4 的表现型；第24、25 位解码后对应路口C23的表现型。

②初始化种群

一个种群代表所要解决的问题的潜在解集，种群中的每个抗体都是经过基因编码的潜在解。在随机生成初始种群之后，依据进化法则逐代搜索最优近似解。

（2）亲和度评价

本文以区域路网内所有路口总的滞留车辆数为评价交通灯配时方案好坏的指标，即亲和度评价规则是基于路网总滞留车辆数生成的。为了便于描述，定义一个变量Delay 来表示在单位周期内，区域路网中所有路口总的滞留车辆数。如此，本算法的亲和度函数可以表示为：

其中，ti表示时间。种群中每个抗体解码后对应区域中各个路口的交通灯状态设置方案，根据该交通灯状态设置方案可以计算出各个抗体对应的Delay 值。对应Delay值越小的抗体，其亲和度越高，即该抗体解码后所对应的交通灯配时方案能使区域总滞留车辆数越少。本文算法的目的就是在末代种群中选出对应的Delay值达到最小的抗体，并在该单位时间内，按该抗体对应的表现进行区域交通灯配时。

（3）免疫算子操作

免疫算子的详细操作过程如本文第2章所述。

（4）解码：基因型到表现型映射

解码过程就是抗体由基因型到表现型的映射。在算法进化过程中，需要对种群中每个抗体进行解码才能计算出它的亲和度值。对最终得出的最优抗体也需要先经过解码，然后才能按该抗体对应的表现型进行交通灯状态设置。

在一段时间内，区域交通灯配时方案设计如果仅是考虑全部路口滞留车流量最少，那有一定可能性导致某些方向车流长时间得不到通行权，使等待时间超过驾驶人员的心理承受极限，从而容易发生交通事故。所以，还需要在由免疫克隆算法搜索出的最优配时方案基础上进行改善。

在本文提出的配时方法中，对于二相位的21 个路口，要求最终的配时方案必须保证每个路口a 和b 这两个相位都不会连续获得通行权超过四个单位周期T；对于四相位的15 个路口，以8 T 为一个大周期，要求最终的配时方案必须保证每个路口在一个大周期内，c、d、e、f四个相位都至少有一个单位周期T获得通行权。

4 区域交通灯配时仿真实验

4.1 仿真交通场景设计

本文以西安市某区域包含36 个路口的路网为参考对象构建仿真交通场景；实验时间段从15：30 到20：30，每15 秒作为一个时间单位T，可以分为1 200 个时间单位。为了便于本文配时方法的应用，对仿真交通场景进行简化如下：

（1）不考虑车辆掉头，车辆行驶方向只有直行、左转和右转这三种情况；且只考虑红灯和绿灯，不考虑黄灯。

（2）对于四相位路口，直行、左转、右转分车道，可以得到路口每个方向的直行、左转和右转车辆数；而二相位路口，因为直行、左转、右转不分车道，只能得到整体车流数。为了简化交通场景，将车辆直行、左转、右转的概率设为固定值，直行概率设置为0.8，右转和左转概率都设为0.1。

（3）在计算每个周期Delay 值时，每个路口在单位T时间内，各个方向车流的通过率是必不可少的。通过调研，设定实验场景区域中各个路口单位时间内车辆通过率如表1所示。

表1 单位时间各路口车辆通过率表（辆·T-1）

4.2 交通流生成模型

交通流生成模型是交通控制研究领域的最基本模型，主要研究交通车辆的到达规律，从而解决交通流生成问题[19]。本文的研究重点不在于如何通过各种先进技术来获取路网中各路口的实时车流量数据，只是想验证提出的区域交通灯配时方法的有效性，因此采用交通流生成模型来模拟生成路网中各路口的实时车流量数据是合理的。

常见的交通流生成模型主要分为两类：一是基于车辆到达随机概率的离散型分布模型，二是基于车头时距、车速等交通流特性的连续型分布模型[20]。离散型分布模型中较常用的有泊松分布、二项分布、负二项分布[21]。

泊松分布适用于对车辆到达率较低、车辆间相互影响小的交通流情况进行描述：

其中，P(x)为单位时间内到达x辆车的概率；λ为泊松分布参数，为正数。泊松分布的均值E(x)与方差D(x)均为λ，即D(x)/E(x)=1。

二项分布适用于对车辆到达率较高、车辆自由行驶机会不多的交通流情况进行描述：

其中，P(x)意义同式（3）；n、p 为二项分布参数，n 为正数，0 ＜p ＜1。二项分布的均值E(x)为np，方差D(x)为np(1-p)，即D(x)/E(x)＜1。

负二项分布适用于对车辆到达率波动大的情况进行描述：

其中，P(x)意义同式（3）；m、p为负二项分布参数，m为正数，0 ＜p ＜1。负二项分布的均值E(x)为m(1-p)/p，方差D(x)为m(1-p)/p2，即D(x)/E(x)＞1。

在15：30—20：30 时段，观测仿真参考区域内路口每单位时间T 到达车辆数据的规律，发现在15：30—16：30 和19：30—20：30 这两个时间段内，区域路网中车流量较小，车辆间相互影响较小，每T 到达车辆数据组的均值和方差近似相等，适合用泊松分布模拟生成各路口的实时车流量数据；17：30—18：30 这一段时间，处于晚高峰时期的区域路网中车流量较大，道路拥挤，每T到达车辆数据组的方差与均值的比小于1，适合用二项分布模拟生成各路口的实时车流量数据；而在16：30—17：30、18：30—19：30 这两段时间，前者即将到达晚高峰，后者处于晚高峰余波中，区域路网中车流量波动较大，每T到达车辆数据组的方差与均值的比大于1，适合用负二项分布模拟生成各路口的实时车流量数据。

由概率论可知，根据数据的均值和方差可以计算出分布参数，得出具体分布模型。本文仿真中采用的具体分布模型如表2所示。

表2 各时间段交通流生成模型

4.3 仿真结果分析

为了验证本文提出的基于改进免疫克隆选择算法的区域交通配时方法的有效性，使用Matlab编写程序进行仿真。仿真验证分为两步：

（1）进行单周期性能分析，只有在单周期性能优良的前提下，多周期配时仿真实验才有可能成功。

（2）进行五小时配时仿真实验，分别运用本文配时方法与固定配时方法进行区域交通灯配时，对比区域路网的总滞留车辆数。

4.3.1 单周期性能分析

本文提出的区域交通灯配时方法是基于改进的免疫克隆选择算法，而对免疫克隆选择算法、遗传算法等优化算法而言，从它们的进化曲线可以得出算法的收敛性能、寻优速度和优化结果等众多信息。为验证本文配时方法的优越性能，仿真中将本文配时方法与基于标准遗传算法（SGA）、标准克隆选择算法（SCS）、动态变异算子克隆选择算法（DCS）的配时方法进行比较（动态变异算子克隆选择算法是指算法运行中变异概率值随迭代次数增加线性递减）。作为对比项的三种配时方法都采用与本文第3 章中相同的编码策略与评价指标。本文仿真实验中的车流量数据是基于三种离散型分布模型模拟生成的，所以为了性能分析的准确性，做了三组实验，每组实验的车流量数据都是基于不同的分布模型，且每组实验中包含四个对比项。

经仿真，三组单周期性能分析实验的结果是一致的，但由于篇幅所限，仅给出由泊松分布模型生成车流量数据的仿真结果，如图3所示。

在图3中，（a）为基于SGA的配时方法进化曲线，（b）为基于SCS 的配时方法进化曲线，（c）为基于DCS 的配时方法进化曲线，（d）为基于本文提出的改进克隆选择算法的配时方法进化曲线；横坐标为迭代次数，纵坐标为每一代的最优个体对应的Delay 值。下面叙述中，四种配时方法都以基于的算法代称。

4.3.2 五小时配时仿真分析

根据4.1 和4.2 节所述，利用交通流生成模型产生15：30—20：30这五个小时的车流量数据，再对固定配时方法、基于SGA 的配时方法、本文配时方法分别进行仿真。固定配时方法中，参考实际路网情况，将二相位路口的信号周期设置为4 T，相位序列为a 相位、b 相位，绿灯时间各为2 T；四相位路口的信号周期设置为8 T，相位序列为c相位、d 相位、e相位、f相位，绿灯时间依次为3 T、1 T、3 T、1 T。因标准遗传算法在本文配时策略应用中运行500 代后也只能看出优化趋势，不能收敛，所以将每个周期遗传算法的迭代次数设定为150 来进行5 h 仿真实验。而本文提出的改进克隆选择算法收敛速度快且寻优效果好，5 h 仿真实验中迭代次数设定为25即可。实验中分别记录固定配时方法、基于SGA 的配时方法、本文配时方法的每小时路网的总Delay值，如表3所示。

从表3 中可以看出，在五个时间段里，本文配时方法的每小时路网总Delay 值与固定配时方法相比都有了显著减少，且减少比例都接近于40%；与基于SGA的配时方法相比，减少比例也都高于17%。从整个仿真周期看，本文配时方法的5 h 路网总Delay 值比固定配时方法减少了38.93%，比基于SGA 的配时方法减少了20.33%。

根据表3 数据，绘制了仿真结果对比图如图4，其中，在15：30 到20：30 这一时间段，由于晚高峰的原因，路网的每小时总滞留车辆数经历了上升再下降的过程。但不论区域路网是处于晚高峰的拥挤状况还是下午4时左右的流畅状况，本文配时方法的路网总滞留车辆数相较于固定配时方法和基于SGA 的配时方法都有明显减少。这表明本文的配时方法能显著提高路口的通行能力，增加了区域路网的交通流畅性，验证了本文配时方法的有效性。

图3 四种配时方法的进化曲线

表3 三种配时方法仿真结果对比表

图4 三种配时方法仿真结果对比图

5 结论

（1）针对免疫克隆选择算法收敛速度慢、易陷入局部最优等问题，本文提出了一种双层动态变异算子，并对克隆抑制算子和种群刷新算子进行了改进。从单周期性能分析中可以看出本文的改进对克隆选择算法性能有了较大提高。

（2）本文提出一种以区域为单位的交通灯配时方法，首先将区域内所有路口的交通灯状态设置问题转换成在单位时间内确定各个路口哪一个相位获取通行权的问题，再利用免疫克隆选择算法的全局寻优能力在每个单位时间搜索出使路网总滞留车辆数最小的交通灯配时方案。仿真结果表明本文提出的配时方法达到了优化目的，显著减少了路网的总滞留车辆数，提升了路网的通行效率，对城市交通的缓堵保畅具有重要的现实意义。