基于约束粒子群算法的交叉口定周期信号配时

段鹏飞

(蚌埠汽车士官学校 装备保障系，安徽 蚌埠233011)

道路交叉口的信号控制涉及包括机动车、人和环境在内的多种影响因素，如何更全面地协调控制多个目标，使其综合效益最优成为广大学者研究的重点。文献［1—5］分别采用蚁群算法、遗传算法、强化学习法、免疫遗传算法等优化方法对交叉口的周期信号进行了优化，都反映了各自算法的优越性。然而这些研究虽然满足了基本控制需求，却无法获得最优的多相位配时方案。因此，针对定周期时长条件下的相位配时优化进行研究非常必要。文献［6—7］分别利用相容优化算法和模式搜索算法研究了定周期时长情况下不同相位绿灯时间的优化，取得了良好的效果，并与经典的Webster 算法进行了比较，然而这些算法的收敛速度不高，仍有待做进一步改善。本文在此基础上，将粒子群算法引入到定周期信号控制优化中，并结合实际应用中存在的约束条件限制和算法易陷入局部最优解问题，对算法进行了改进，以单交叉口机动车延误、行人延误和停车率综合最小为优化目标进行了优化，达到了很好的收敛效果。

1 系统模型

以机动车流为控制对象，从机动车效益、人的效益和环境效益3 个方面考虑，选取机动车车均延误、行人人均延误以及机动车平均停车率三者综合最小为优化目标，建立单交叉口信号控制多目标优化模型如下:

式中:ge=［ge1，ge2，…，gen］，gei为第i相位的有效绿灯时间;C为周期总时长;l为周期损失时间;fp(ge)，p=1，2，3 为第p个优化目标函数，这里分别代表机动车平均延误函数、行人平均延误函数和平均停车率函数;λi为第i相位的绿信比;xij为第i相位第j进口道的车流饱和度;β为规定的交叉口最大车流饱和度。

机动车平均延误采用Webster 经典延误模型，延误时间由机动车流在非饱和状态下的稳态均匀到达延误和随机延误2 部分组成，其计算公式为

式中:第1 部分为交通流均匀到达的一致延误，s/pcu;第2 部分为车辆随机到达并引起超饱和周期所产生的附加延误，s/pcu;qij为第i相位第j进口道的车流量，pcu/h。

则其机动车平均延误时间优化目标函数为

在假定交叉口行人均匀到达，且每个信号周期绿灯信号均能保证所有等待的行人通过，不存在跨周期滞留现象的前提下，建立行人延误模型:

式中Ri为第i行人相位的红灯等待时间。

不考虑不完全停车的情形，在均匀到达情况下，一个周期内交叉口进口道机动车流的平均停车率可以按照Webster 的计算方法建立模型［8］。模型表达式为

式中Sij为第i相位第j进口道的设计饱和流量，pcu/h。

则平均停车率优化目标函数可表示为

本文重点针对固定周期时长的信号配时进行研究，因此在优化过程中，一个周期内各相位总的有效绿灯时间应该满足:

即该优化问题事实上是带有约束条件的多目标优化问题，与一般的无约束条件优化相比，该类问题在模型求解过程中需要考虑约束条件的限制。

2 模型求解

2.1 约束优化问题求解

本文所研究的是一种带有约束条件的多目标优化问题，一个约束优化问题通常可以表示为

式中:X={x1，x2，…，xn}∈F⊆S⊆Rn为优化控制变量，集合S⊆Rn为问题的搜索空间;F为搜索空间中的可行域，即满足约束条件的解所构成的空间;X的每维向量取值于区间［ai，bi］，i=1，2，…，n;F(X)为目标函数;gk(X)≤0 和hk(X)=0 分别为约束优化问题的不等式约束和等式约束。

目前，针对约束优化问题的求解算法主要分为精确算法和现代启发式算法2 种，前者通常需要目标函数具有良好的性质，如连续、可微等。而现代启发式算法在求解一般约束问题时，不需要借助目标函数的这些性质条件限制。粒子群算法(particle swarm optimization，PSO)作为一种基于群体的进化算法，与其他启发式算法相比，被证明是一种极具竞争力的求解算法。为了利用该算法收敛速度快的特点，将其引入以解决交叉口相位配时优化问题。

2.2 带杂交算子的粒子群算法

在标准的PSO 中，问题的每个解均可以看作是搜索空间中的一个粒子，所有粒子都有一个由优化目标函数决定的适应度值，此外每个粒子还有一个速度决定他们下一步所要移动的方向和距离。所有粒子根据个体和全体的飞行经验综合分析动态调整自身速度，以完成在解空间的迭代搜索，直到找到最优解。每一次迭代过程中粒子的更新方程［9］为

式中:wt为前一代速度对当前速度的影响权重和分别为第i个粒子在第t次迭代中第j维的速度和位置，二者均有一定的范围限制;c1和c2为2个加速因子，他们是粒子飞向全局和局部最好位置的速度权重;r1和r2为2 个介于［0，1］之间的随机数分别为粒子的个体极值和全体极值。

标准的PSO 收敛速度较快，但与其他进化算法一样易于陷入局部最优的缺陷。为了有效避免这种收敛早熟，借鉴遗传算法中杂交操作思想，通过在算法中引入一个杂交算子，使粒子获得新的基因，来保持粒子群多样性，从而使算法搜索到解空间中更大的范围，减少了算法陷入局部极值的可能性［9］。但是，其没有考虑当前最优解参与杂交时会使最优粒子受到破坏的情况，因此，为了保持最优解的完整性，对其做进一步改进，规定当代最优粒子不参与杂交。具体操作中，以杂交概率ps(0 ＜ps＜1)选取一定数目粒子两两参与杂交。设为T代参与杂交的2 个粒子，p0为杂交因子，则杂交操作计算公式为

2.3 约束处理机制

标准的粒子群算法针对的是无约束条件优化问题的求解，本文采用一种广泛应用于处理该类问题的基于惩罚函数的约束粒子群算法，有效解决了模型求解中的实际问题。

定义处在可行域F内的粒子为可行粒子，反之处在非可行域S-F内的粒子称为非可行粒子。为了消除非可行粒子对算法搜索最优解的干扰，对这些粒子对应的适应度值添加惩罚函数。以最小化目标函数为例，对其增加一个惩罚值，使得这些非可行粒子的适应度函数远离最优解搜索区域。

这里给出的约束优化问题的PSO 中，对于可行粒子保持其适应度函数值不变，而对于非可行粒子通过下面的目标函数f(X)来评价其适应度［10］:

式中:fk(X)为非可行粒子对第k约束的约束违背测 度φ(X，t)为在算法执行的t代对于非可行粒子的附加启发值

3 信号配时优化算法

以交叉口各相位、各进口道的机动车平均延误时间、行人平均延误时间和平均停车率的归一化加权和为目标函数，以n个相位的有效绿灯时间ge1，ge2，…，gen为优化变量(gei∈［T］，［T］为各相位有效绿灯时间的取值范围)，给出的粒子群算法优化步骤简单概括如下:

步骤1:根据约束条件确定n个参数的取值范围以及PSO 的控制参数vmax后，在参数范围内初始化一群粒子，即随机产生位置x1和速度v1。

步骤2:在第t次迭代时，根据产生的新位置xt和速度vt，确定每个粒子的适应度值Jt。

步骤3:找出所有可行粒子，求出其中最差的粒子，即适应度函数值最大的粒子。对剩余的非可行粒子按照式(11)加上对应的惩罚函数。

步骤4:对每个粒子计算其个体极值pbestt和全体极值gbestt，更新粒子当前最优解和对应位置数组:如果Jt＞pbestt，则pbestt=Jt，Pt=xt;如果Jt＞gbestt，则gbestt=Jt，Pg=xt，P为粒子的位置。

步骤5:利用式(9)更新粒子的速度与位置，这里c1，c2为［0，2.5］中的随机数。

步骤6:保持当前最优粒子位置不变，以杂交概率ps选择一定数量的粒子按式(10)进行两两杂交。

步骤7:若未达到预设的迭代终止条件，返回步骤2。

4 仿真实例

以典型的单交叉口四相位信号控制为例进行问题研究，假设有东、西、南、北4 个车流入口，每个方向有左转、直行和右转3 个车道，东西直行和右转车辆在相位1 中放行，东西左转车辆在相位2中放行，南北直行和右转车辆在相位3 中放行，南北左转车辆在相位4 中放行。假设该交叉口的车流有关数据见表1。

表1 某交叉口机动车流量统计 pcu/h

4.1 优化目标有效性仿真

针对多目标优化问题，合理的优化目标选取对于问题研究具有重要意义，如果选择的是呈线性关系的一组目标，则二者不能同时作为仅有的目标函数出现。道路交叉口的信号配时涉及到包括机动车、行人和环境在内的诸多因素，在实际优化模型建立中选择合理的多个目标是有效求解该类问题的重要前提。

图1—3 为选取的3 个优化目标在解空间中的关系曲线。从图中可以看出，在假定车辆均匀到达且交叉口处于非饱和状态条件下，机动车平均延误与行人平均延误之间呈线性关系，为非冲突目标;机动车平均延误与平均停车率、行人平均延误与平均停车率之间均为相互冲突的关系。因此，后两组之间为有效的优化控制目标。

4.2 配时算法性能仿真

图1 机动车平均延误与行人平均延误的关系

图2 机动车平均延误与平均停车率的关系

图3 行人平均延误与平均停车率的关系

假设交叉口信号周期C为130 s，总的损失时间l为10 s，各进口道车流量见表1，各相位最小绿灯时间为10 s，各相位各进口道的最大车流饱和度β为0.9。同时，设定最大粒子种群规模Ν=80，加速因子c1=c2=2，采用文中给出的粒子群优化算法，计算得到交叉口4 个相位有效绿灯时间分别为ge1=45.63 s;ge2=22 s;ge3=36.36 s;ge4=17 s。

文中算法与经典Webster 算法以及模式搜索算法的优化结果比较见表2。可以看出，在等周期时长条件下，文中给出的算法优化得到的机动车平均延误和平均停车率均明显优于Webster 算法，同时与模式搜索算法差别不大。而在行人平均延误方面，文中算法较其他2 种算法差别均小于1 s。

表2 3 种算法优化结果比较

优化粒子群算法与传统的标准粒子群算法以及模式搜索算法的性能比较如图4 所示。

图4 优化粒子群算法性能比较

从图中可以看出，粒子群算法收敛速度明显优于模式搜索算法，这主要得益于该算法是一种基于群体的进化算法，具备优秀的寻优能力。同时，带改进杂交算子的粒子群算法较标准的粒子群算法性能有所提升，这主要是因为引入改进杂交算子后，在保持当前最优解完整性的同时，提高了算法对全局最优解的搜索能力。因此，优化粒子群算法在优化结果与传统算法差别不大的情况下，收敛速度得到了明显提升。

不同的周期时长情况下，机动车平均延误和行人平均延误优化结果的变化趋势如图5 所示。

图5 不同周期时长条件下优化结果

从图中可以看出，随着周期时长的增加，机动车和行人通过交叉口的平均延误都相应线性增加，且机动车延误对周期时长的灵敏性要大于行人延误对周期时长的灵敏性。这主要是因为，随着周期总时长的增加，各相位绿灯时间也相应增加，导致机动车和行人的排队时间相应增加。因此，在实际的道路交叉口信号控制中，应综合考虑各种因素，使综合效益达到最优。

5 结 语

本文在传统粒子群算法的基础上，针对交叉口定周期信号相位配时中存在的传统算法收敛速度较慢以及约束条件限制等问题，通过引入杂交算子，采用基于惩罚函数的约束粒子群算法，使得旨在处理无约束优化问题的高效粒子群进化算法有效解决了交叉口定周期信号多相位配时问题，仿真结果证明了给出算法的有效性。由于道路交叉口的交通控制涉及到机动车延误、燃油消耗率、停车率、排队长度、行人延误以及汽车尾气排放、噪音污染等诸多效益指标，本文仅以其中部分因素为优化目标，还不能全面反应优化控制需求，下一步可对于更全面的优化目标进行分析研究。

［1］ 马莹莹，杨晓光，曾滢. 信号控制交叉口周期时长多目标优化模型及求解［J］. 同济大学学报:自然科学版，2009，37(6):761-765.

［2］ Schmocker J D，Ahuja S，Bell M G H. Multi-objective signal control of urban junctions-framework and a london case study［J］. Transportation Research Part C，2008，16(4):454-470.

［3］ 万伟，陈峰.基于遗传算法的单交叉口信号优化控制［J］.计算机工程，2007，33(16):217-219.

［4］ 温凯歌，杨照辉. 基于CMAC 强化学习的交叉口信号控制［J］.计算机工程，2011，37(17):152-154.

［5］ 顾榕，曹立明，王小平. 免疫遗传算法在在交叉口信号配时中的应用［J］. 同济大学学报:自然科学版，2007，35(2):208-212.

［6］ 高云峰，徐立鸿，胡华，等.交叉口定周期信号控制多目标优化方法［J］.中国公路学报，2011，24(5):82-87.

［7］ 刘爽，岳芳，郭彦东，等.基于模式搜索算法的交叉口信号配时优化研究［J］.交通运输系统工程与信息，2011，11(1):29-35.

［8］ 全永燊.城市交通控制［M］.北京:人民交通出版社，1989.

［9］ 黄友锐.智能优化算法及其应用［M］. 北京:国防工业出版社，2008.

［10］ 李相勇，田澎，孔民.解约束优化问题的新粒子群算法［J］.系统管理学报，2007，16(2):120-129.