蜂群激发抑制算法及其在交通信号配时中的应用

胡 亮，肖人彬，王英聪

(1.华中科技大学人工智能与自动化学院，武汉 430074；2.郑州轻工业大学电气信息工程学院，郑州 450002)

0 引言

现实生活中的许多问题都可以抽象为分配问题(比如时间分配、空间分配和资源分配等)，这些问题往往具有动态复杂性。以十字路口交通信号灯的绿灯时间分配为例，来自不同方向的车流量始终是动态变化的。对这种具有复杂性的动态分配问题，要求处理算法具有很强的智能性与适应性。目前，群智能算法在此领域已经取得了不错的成效。

群智能算法以蚁群优化和粒子群优化为典型代表[1]，相关研究主要集中在组合优化和函数优化等领域。这些优化算法在求解动态分配问题时，往往只在一些固定场景中有效。当环境变量与输入变量的变化范围很大时，难以保证每次输出结果的效能，即柔性较差。此外，这些优化算法本身还存在着收敛速度慢、容易陷入局部最优等问题。

上述研究主要集中在蚁群的刺激-响应劳动分工机制上，而对蜂群的激发-抑制劳动分工机制的研究相对较少。在已有群智能劳动分工的研究基础上，针对动态分配问题，本文提出一种基于蜂群的激发-抑制劳动分工模型(AILD)。为了验证AILD模型的有效性，选取了一个典型的时间分配问题——交通信号配时，设计了相应的激发-抑制劳动分工信号配时算法AILD-ST。采用AILD-ST算法对实际交通流数据进行了交通信号配时求解，并与Webster算法、蚁群算法和蜂群算法进行了对比，结果显示AILD-ST算法的实用性和有效性。

本文安排如下，第1节讨论蜂群激发-抑制原理并设计出激发-抑制劳动分工模型，第2节将激发-抑制劳动分工模型应用到交通信号配时问题中并提出激发-抑制劳动分工信号配时算法，第3节是将激发-抑制劳动分工信号配时算法应用于交通配时问题的仿真实验，第4节是算法的机理和性能分析，第5节是对全文工作的总结。

1 激发-抑制劳动分工模型

1.1 蜂群劳动分工现象

在社会性昆虫中，族群需要完成各种各样的任务，如哺育幼虫、寻找食物、维护巢穴、抵御外敌等。在任何时刻，族群都能并行地执行这些任务，这种现象叫做劳动分工。群智能劳动分工主要有两种模式[13]：一种是以蚁群为代表的形态行为多型，其中个体执行的任务与其大小和体型等有关；另一种是以蜂群为代表的时间行为多型，其中个体执行的任务与其生理年龄等有关。本文主要关注蜂群的劳动分工，下面对其进行简要介绍。

图1 蜜蜂的行为发育过程Fig.1 Behavioral development of bees

1.2 激发-抑制原理

Huang等[16]在研究蜂群的劳动分工时，提出了一种激发-抑制原理，该原理认为蜂群的劳动分工体现在它们的行为发育上，而蜂群的行为发育是由激发剂和抑制剂共同决定的，且二者具有耦合关系，即年长的蜜蜂体内激发剂和抑制剂的含量比年幼蜜蜂多。其原理可以简要描述如下：激发剂和抑制剂共同维持着蜜蜂在不同任务上的动态分配平衡。其中保幼激素被认为是蜜蜂的一种激发剂，促进个体行为发育，使其工作从巢内向巢穴外转移。个体之间进行交互时会传递抑制剂，对其保幼激素和行为发育起阻碍作用。比如，当觅食者减少时，抑制剂会减弱，促进激发剂增加，巢穴内的个体会加速发育成觅食者；当觅食者较多时，抑制剂会变强，抑制激发剂的产生，巢穴内个体的发育会被延迟，甚至一些觅食者会返回巢穴内工作。

图2 激发-抑制原理中个体间的交互方式Fig.2 The interaction between individuals in the principle of activating and inhibition

基于上述激发-抑制原理，Naug等人[17]建立了一个计算仿真模型，该模型进一步描述了激发-抑制原理中个体间的交互方式，如图2所示。蜂群中每个个体都包含一个激发剂A(Activator)和两个抑制剂I1和I2(Inhibitor)。A是个体内在的激发剂，对个体自身的行为发育起促进作用。I1是个体内在的抑制剂，不会阻碍自身的行为发育，但在个体交互过程中会对其他个体的行为发育产生抑制作用。I2是个体在交互作用中得到的外在抑制剂，会阻碍自身的行为发育。最终，蜜蜂体内的激发剂A和抑制剂I2的相对水平(A/I2)决定个体的行为发育过程是正常速度还是被加速、延迟或逆转。

1.3 激发-抑制模型

根据蜂群的群体性特点，参考Gierer等人的工作[18]，以及激发剂对细胞生长的促进作用，抑制剂对细胞生长的抑制作用，激发剂与抑制剂之间的相互作用反馈，同时考虑到激发-抑制本身是一个具有时变不确定性、自学习性和对外部系统具有高适应性的互动过程，下面提出基于蜂群劳动分工激发-抑制原理的激发-抑制劳动分工模型(AILD)。

每个蜜蜂要和群体进行交互，蜜蜂和蜂群之间的交互是通过激发剂和抑制剂实现的。具体的，激发剂(用a表示)促进个体发育成长，抑制剂(用h表示)阻碍个体发育成长，甚至产生逆生长的作用。激发剂的激发特性通过二次函数a2表现出来，同时考虑到抑制剂对激发剂有抑制作用(抑制剂越大，激发剂的增量越少；抑制剂越小，激发剂的增量越大)，通过反函数a2/h来表现抑制剂对激发剂增长的抑制作用。除了蜂群本身激发剂和抑制剂的相互作用，还需要考虑环境因素(食物变化，天气变化，天敌等)[19,20]对蜂群的影响以及激发剂和抑制剂自身对时间变化的消散作用。

结合以上特点，给出AILD模型的描述如下：

个体i的激发剂ai随时间变化，其表达式如下：

(1)

(2)

式中，hj(t)表示t时刻个体j体内的抑制剂含量，c表示激发系数，ρ表示群体密度，uaai表示激发剂的一阶衰减项，ρaρ表示环境产生的激发剂对个体的影响，i≠j说明同一个个体内的激发剂与抑制剂不存在直接作用关系，个体只能与群体进行交互。

个体i的抑制剂hi随时间变化，其表达式如下：

(3)

(4)

从上述公式可以看出，若t时刻蜂群的觅食蜂数量突然减少，会导致蜂群整体的激发剂以及抑制剂总含量降低，同时个体i的激发剂与抑制剂含量未改变。根据式(3)、(4)可知，t+1时刻个体i的抑制剂含量减少。根据式(1)、(2)可知，t+1时刻个体i的激发剂含量增加。综上，个体i的激发抑制比上升，会加速向觅食蜂的转化。同理，若t时刻觅食蜂数量过多，蜂群整体的激发剂以及抑制剂总含量增加。由上述公式可知，t+1时刻个体i的抑制剂含量增加，激发剂含量降低，激发抑制比降低。个体i的发育被抑制，由巢内到巢外的转化速度减慢，甚至会使得觅食蜂重新回到巢内。通过上述分析可知，蜂群在激发-抑制劳动分工作用下处于一种动态平衡状态。

2 交通信号配时问题应用

群智能劳动分工提供了一种柔性任务分配方式，对动态环境下的分配问题求解具有重要启发意义。交通信号配时旨在为来自不同方向的交通流分配绿灯时间，使其分时通过交叉口。交通信号配时是一种典型的时间分配问题，并且城市交通流具有较高的时空复杂性。据此，以交通信号配时问题为例来验证AILD模型的有效性。

2.1 交通信号配时问题简介

在确保交通安全的前提下，交通信号配时的主要目的在于最大限度地提高交叉口的使用效率。一方面要合理利用道路交通设施的资源，提高道路的使用效率，使得道路通行能力最大化；另一方面要以人为本，根据人的需求，让延误时间和停车次数尽可能的小。因此，本文选取延误时间、停车次数和通行能力作为衡量指标，其中延误时间和停车次数体现了道路使用者的利益，越小越好；通行能力体现了道路的使用效率，越大越好。

第i相位的车辆延误时间(s)[26]为

(5)

第i相位的车辆停车次数(次)[26]为

(6)

第i相位的通行能力(pcu/h)[26]为

Qi=si×xi/c

(7)

其中，c为信号周期时长(s)，si、yi、li、qi、(i、xi分别为第i相位的饱和流量(pcu/h)、流量比、损失时间(s)、车流量(pcu/h)、绿信比和绿灯时间(s)。

据此得到一个周期内交叉口的车辆平均延误时间(s)为

(8)

一个周期内交叉口的车辆平均停车次数(次)为

(9)

一个周期内交叉口的通行能力(pcu/h)为

(10)

其中，n为相位总数。

2.2 激发-抑制劳动分工信号配时算法

2.2.1 算法原理

在蜂群劳动分工中，不同的蜜蜂执行不同的任务完成任务分配。在交通信号配时中，不同的信号相位占据不同的绿灯时间完成时间分配。图3给出了蜂群劳动分工与交通信号配时之间的映射关系，在此基础上交通信号配时问题的求解准则为：某一信号相位的延误时间越长，则其激发剂越大，在激发-抑制原理作用下，该相位的绿灯时间将会增加；其它信号相位的停车次数越大，则该相位感知到的抑制剂越大，在激发-抑制原理作用下，该相位的绿灯时间将会减小。

通过激发剂和抑制剂的变化，AILD-ST自适应地调整各信号相位的绿灯时间，从而完成时间分配。AILD-ST采用进化的方式进行求解，不需要建立优化模型，具有原理简明、易于实现等特点。

2.2.2 算法步骤

激发-抑制劳动分工信号配时算法AILD-ST的实现步骤如图4所示，具体说明如下：

图3 蜂群劳动分工与交通信号配时之间的映射关系Fig.3 The mapping relationship between the labor division of bee colony and the timing of traffic signals

图4 AILD-ST算法计算过程Fig.4 AILD-ST algorithm calculation process

步骤1：初始化激发剂、抑制剂等参数；

步骤2：根据车流量信息和Webster算法得到初始的各信号相位绿灯时间x1、x2、x3、x4，各信号相位平均延误时间D1、D2、D3、D4，以及各信号相位停车次数H1、H2、H3、H4；

步骤3：迭代次数初始值设定为1；

步骤5：种群进化，根据公式(1)-(4)更新激发剂和抑制剂；

步骤7：判断r=Zi-Z(t)*，若|r|

步骤8：迭代次数加1；

步骤9：若迭代次数小于N，则转至步骤4继续进化。

步骤10：输出最终进化解。

3 仿真实验

3.1 实验概述与参数设置

本实验使用的交通数据来自于2014中国“云上贵州”大数据商业模式大赛——智能交通算法大挑战。中国“云上贵州”大数据商业模式大赛利用贵州省贵阳市南明区交通流量数据(包括公交车GPS信息、出租车GPS信息、高德公司普通市民导航数据等)，在充分脱敏与保护用户隐私的前提下，模拟贵阳市整体的十字路口交通情况。图5是贵阳市南明区部分区域的简化道路与红绿灯位置图，其中红绿灯用tli来表示。选取交通数据文件“flow0901”中红绿灯ID为“tl18”的6:00～20:00时间段的交通数据进行处理，如图6所示。这一时间段内车流量变化较明显，对于评估信号配时方法的效果具有较强的说服力。

图5 贵阳市南明区部分区域路口简化示意图Fig.5 Simplified schematic diagram of intersections in some areas of Nanming District, Guiyang City

图6 红绿灯“tl18”车流量Fig.6 Traffic light "tl18" traffic

本节采用两种典型的算法进行对比分析，一种是传统的Webster算法，另一种是群智能优化算法——蚁群算法和蜂群算法，它们求解的优化模型按照文献[26]给出：

(11)

实验中所涉及的参数设置如下：假设车辆在交叉口处直行、左转和右转的比例分别为60%、20%和20%，相应的直行车道、左转车道和右转车道的饱和流量分别为1 500pcu/h、1 200pcu/h和1 200pcu/h。交叉口绿灯间隔时间为4s，黄灯时间为3s，启动损失时间为3s，最短绿灯时间为15s，最长绿灯时间为90s。激发系数c为0.2，激发剂产生速率为3，抑制剂产生速率为5，源密度为1，激发剂的衰减系数为0.26，激发剂的衰减系数为15，步长k为4，最大迭代次数N为100。实验环境说明如下：本文采用Matlab语言编程实现AILD-ST算法，并在CPU主频为3.6GHz、内存为4 GB的PC机上进行实验。

3.2 实验结果

为了检验AILD-ST算法的性能，选取蜂群算法、蚁群算法和Webster算法进行对比实验。求解时，先用Webster方法估计初始周期，然后利用等饱和比的方法计算各相位的大致信号配时，再用AILD-ST进行分配求解。计算统计一天的结果见表1，表1中D为车辆一天平均延误时间；H为车辆一天平均停车次数；Q为道路平均每小时通行能力。本实验的仿真结果如图7所示。

图7 实际交通场景连续一天各项指标的比较Fig.7 Comparison of evaluation indicators in actual traffic scenes one day in a row

3.3 实验结果分析

由表1的计算结果可知，AILD-ST算法在延误时间、平均停车次数以及通行能力这三组测试实验中都优于Webster算法、蜂群算法和蚁群算法。其中在延误时间方面，本文算法相对其它算法能减少平均延误时间7.1%、9.3%和11.3%；在停车次数方面，本文算法相对其它算法能减少平均停车次数2.7%、3.5%和3.3%；在通行能力方面，本文算法相对其它算法能增大通行能力21.5%、15.3%和5.7%。

通过观察图6可以看出，交通路口的流率比从早上六点开始不断上升，一直到早上九点的时候到达峰值，然后开始一直下降。通过观察图7可以看出，随着交通路口流率比的增加，平均停车次数不断增加，通行能力先增加后下降，延误时间先增加后下降。从而使得控制信号目标在路口闲散状态下更加侧重减少延误时间和停车次数，而在拥堵状态下则更加侧重减少延误时间和提高通行能力。这种方式可以实现不同交通状态下交通路口管理效能最大化。

表1 AILD-ST算法与Webster算法、蚁群算法、蜂群算法的信号配时性能比较Tab.1 Comparison of signal timing performance (AILD-ST algorithm, webster colony algorithm, ant colony algorithm and bee algorithm)

AILD-ST算法继承了蜂群劳动分工的特点，以任务动态分配的方式完成时间动态分配，根据实时变化的车流量动态调节各个相位的绿灯时间，使其增加、不变或者减少，从而到达全局最优。相比Webster算法、蜂群算法和蚁群算法，AILD-ST算法优化性能更佳，说明对单路口控制实例，本文设计的AILD-ST算法具有好的应用效果，可以根据车流量动态调节绿灯时间，能够在一定程度上缓解交通压力，提升道路的流畅度。

综合来看，AILD-ST算法能够在高峰流量期间提高道路的通行能力，进而满足高峰流量期间的需求；而平峰流量期间，在保证车辆平均延误时间和平均停车次数较低的情况下，能提高道路通行能力。因此，AILD-ST算法优能够在一定程度上缓解道路交叉口的交通压力，提高道路交叉口的利用率。

3.4 扩展对比实验

为了进一步说明AILD-ST算法具有应对典型路况的能力，本节选取两种典型的交通环境(高峰和平峰)进行对比实验。在仿真实验中，使用了文献[26]中的测试数据。这些数据来源于典型的四相位道路交叉口，包含了高峰期间的车流量数据与平峰期间的车流量数据，所含信息较为全面，具有一定的说服力和代表性。AILD-ST算法的计算结果与蚁群算法、Webster算法的计算结果(由文献[26]给出)见表2，表2中D为车辆平均延误时间，H为车辆平均停车次数，Q为道路通行能力，c为周期；X1、X2、X3、X4分别为四个相位的有效绿灯时间。

从表2中3种算法的计算结果可以看出：1)高峰流量期间，AILD-ST算法在车辆平均延误时间这一指标上相对于其他两种算法较差，但在车辆平均停车次数和通行能力这两个指标上相对于其他两种算法更优；而在高峰流量期间，一般注重于提高道路的通行能力。2)平峰流量期间，AILD-ST算法在道路通行能力车辆这一指标上相对于其他两种算法较差，但在平均延误时间和平均停车次数上与其他两种算法相近或者更低。综合来看，AILD-ST算法能够在高峰流量期间提高道路的通行能力，进而满足高峰流量期间的需求；在平峰流量期间，AILD-ST算法在保证车辆平均延误时间和平均停车次数较低的情况下，能够满足平峰车辆顺畅通行的需求。因此，AILD-ST算法优于经典的Webster算法和典型的智能优化算法——蚁群算法，能够在一定程度上缓解道路交叉口的交通压力，提高道路交叉口的利用率。

表2 AILD-ST算法与蚁群算法、Webster算法的信号配时性能比较Tab.2 Comparison of signal timing performance (AILD-ST algorithm, ant colony algorithm and webster colony algorithm)

3.5 算法分析

AILD算法的建模对象为蜂群中的蜜蜂个体，其将蜜蜂个体的激发剂、抑制剂与实际问题的参数抽象关联在一起(见AILD-ST算法案例)，在建模过程中不考虑整体的因素。下面从模型的个体入手分析算法的机理。

对于第i个个体，其体内激发剂与抑制剂的含量如公式(1)、(3)所示。在个体成长过程中，激发剂与抑制剂的相对含量——激发抑制比决定了个体是否加快、延缓或者颠倒自身的发育。激发抑制比的变化取决于以下两种方式：

1)方式一

2)方式二

由上述两种激发剂与抑制剂的变化方式可知，蜜蜂个体i响应外界变化的规律如图8和图9所示：参考AILD-ST算法，将交通问题的参数映射为t时刻蜜蜂个体的激发剂与抑制剂，相当于外界对蜂群的输入。蜂群接收此值作为劳动分工的初始值，经过处理后，蜜蜂对外界做出反应，以满足族群劳动分工的要求。此处理过程即依据上述两种方式，计算得到t+1时刻激发剂、抑制剂的含量，响应的结果即依据t+1时刻激发抑制比确定生理年龄变化方向。同理，再将新的结果作为下一次的计算输入，循环处理，多次优化，直到蜜蜂个体产生的分工结果契合种群整体要求。

具体说来，交通问题的延迟时间D与停车次数H分别为激发剂与抑制剂，四个相位对应种群数量为4的蜂群。当某一相位的是延迟时间增加时，即该相位的t时刻激发剂增加，参照图8和图9，该变化会使该相位激发剂在t+1时刻增加，同时对于其他相位t+1时刻的抑制剂有促进作用，其结果是本相位绿灯时间增多，其他相位绿灯时间减少，进而使各相位延迟时间D与停车次数H回到相对平衡的状态，形成一次优化。同理可以推断该相位延迟时间减小、停车次数增加以及停车次数减少三种情形下的各相位绿灯时间变化，其结果也是合理的。蜜蜂个体(单个相位)的激发剂抑制剂变化是与群体内其它蜜蜂(其它相位)息息相关的，所以蜜蜂个体能在与其它蜜蜂交互时得到其它蜜蜂的状态信息(见式(2)及式(4))，当交互次数足够多时，蜜蜂所得到的状态信息的集合就可以反映种群状态，个体也就间接了解了种群信息，并据此做出判断。因此，蜜蜂总是可以在外界条件的变化下实现合理的种群任务分配，显示出强大的群体智能，这也是交通配时实验总能得到优化解的原因。

图8 蜜蜂个体i的发育促进因素Fig.8 Developmental factors of bee individuals i

图9 蜜蜂个体i的发育抑制因素Fig.9 Inhibitory factors of development of bee individuals i

4 结论

本文针对动态环境下的交通信号配时问题，分析了蜂群激发-抑制劳动分工模型和交通信号配时问题的相似性，建立了二者之间的映射关系，提出了一种面向交通信号配时问题的激发-抑制劳动分工信号配时算法(AILD-ST)。结果表明，AILD-ST算法能够很好地处理交通配时这类复杂问题。将AILD-ST算法与典型的智能优化算法(如蚁群算法、蜂群算法)相比较，其优越性主要体现在以下几个方面：

1)建模简单：传统的交通配时优化算法需要针对某一具体的交通流模式设计精确的数理模型，而AILD-ST算法将交通配时问题映射为动态分配问题，映射关系简单，配时问题直接与分工模型对应，建模过程被大大简化。

2)运行高效：典型的优化算法为了得到较好的结果，需要对解空间进行大规模的搜索，算法开销大，导致系统运行时间长，而本文设计的AILD-ST算法原理简单，主要采用低级运算结构，运行效率高。

3)适应性强：本文从生物学现象出发，根据蜂群劳动分工的特点提出激发-抑制劳动分工模型。AILD-ST可以部署于不同路段，且对不同时段的时变交通流模式均具有优于现有算法的良好求解效果。

AILD模型是一种有效的动态自组织任务分配模型，该模型为解决十字交叉口交通信号配时问题以及其他的任务分配问题提供了一种新颖有效的解决思路。下一步的研究重点是深入分析AILD模型的激发-抑制机理(激发剂相当于正反馈作用，内部抑制剂和外部抑制剂相当于负反馈作用)，提出更加方便、实用的激发抑制模型，进一步提高AILD-ST算法的性能。