第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201807014 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190422.0854.002.html 一种面向时间分配问题的群智能劳动分工新方法 肖人彬，王英聪2 (1.华中科技大学人工智能与自动化学院，湖北武汉430074,2.郑州轻工业大学电气信息工程学院，河南郑 州450002) 摘要：本文以给不同信号相位的车辆分配绿灯时间的交通信号配时问题为代表，将群智能劳动分工应用到时 间分配问题的求解中，提出一种新颖的蜂群劳动分工算法(bee swarm labor division algorithm,BSLDA)。首先从 时间分配的视角对交通信号配时问题进行分析，然后将激发-抑制原理引入BSLDA,为每个信号相位定义了激 发剂和抑制剂，并设计了增加绿灯时间、诚少绿灯时间和保持绿灯时间3种行为。在群智能劳动分工激发-抑 制原理作用下，BSLDA中的每个信号相位都能根据环境变化选择恰当的行为完成时间分配。最后采用真实的 交通流数据进行仿真实验，结果表明本文方法适于求解不确定环境下的交通信号配时问题。 关键词：群智能；劳动分工；任务分配：激发-抑制原理；个体-个体交互：自组织；时间分配；交通信号配时 中图分类号：TP18 文献标志码：A文章编号：1673-4785(2019)03-0438-11 中文引用格式：肖人彬，王英聪.一种面向时间分配问题的群智能劳动分工新方法.智能系统学报，2019,14(3)：438-448. 英文引用格式：XIAO Renbin,WANG Yingcong.A new approach to labor division in swarm intelligence for time allocation prob- lem[J].CAAI transactions on intelligent systems,2019,14(3):438-448. A new approach to labor division in swarm intelligence for time allocation problem XIAO Renbin',WANG Yingcong (1.School of Artificial Intelligence and Automation,Huazhong University of Science and Technolgy,Wuhan 430074,China; 2.School of Electrical and Information Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China) Abstract:In this paper,we use the labor division in swarm intelligence to solve the time allocation problem represented by the traffic signal timing problem of allocating green light time to signal phases,and propose a new bee swarm labor division algorithm(BSLDA).The traffic signal timing problem is analyzed from the perspective of time allocation,and the activator-inhibitor mechanism under labor division is introduced in BSLDA.For each signal phase,BSLDA defines one activator,one inhibitor and three behaviors(ie.,increasing green light time,reducing green light time and keeping green light time).With the activator-inhibitor mechanism,each signal phase in BSLDA could choose appropriate beha- vior according to environmental change to achieve the time allocation.The real traffic flow data is used in the simula- tion experiment,and the results show that the proposed approach is effective and suitable for the dynamic traffic signal timing problem in uncertain environment. Keywords:swarm intelligence;labor division;task allocation;activator-inhibitor mechanism;individual-individual in- teractions;self-organization;time allocation;traffic signal timing 在现实生活中经常会遇到各种各样的分配问 题，比如资源分配山、收入分配、资产分配)、功 收稿日期：2018-07-17.网络出版日期：2019-04-22 率分配、任务分配等，因此关于分配问题的研 基金项目：国家自然科学基金项目(61702463,51875220)：河南 究得到广泛关注。以任务分配为例，从静态任务 省科技攻关项目(192102210111) 通信作者：肖人彬.E-mail:rbxiao@hust.edu.cn 分配到动态任务分配，从集中式任务分配到分布
DOI: 10.11992/tis.201807014 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190422.0854.002.html 一种面向时间分配问题的群智能劳动分工新方法 肖人彬1 ，王英聪2 （1. 华中科技大学 人工智能与自动化学院，湖北 武汉 430074; 2. 郑州轻工业大学 电气信息工程学院，河南 郑 州 450002） 摘 要：本文以给不同信号相位的车辆分配绿灯时间的交通信号配时问题为代表，将群智能劳动分工应用到时 间分配问题的求解中，提出一种新颖的蜂群劳动分工算法 (bee swarm labor division algorithm, BSLDA)。首先从 时间分配的视角对交通信号配时问题进行分析，然后将激发–抑制原理引入 BSLDA，为每个信号相位定义了激 发剂和抑制剂，并设计了增加绿灯时间、减少绿灯时间和保持绿灯时间 3 种行为。在群智能劳动分工激发–抑 制原理作用下，BSLDA 中的每个信号相位都能根据环境变化选择恰当的行为完成时间分配。最后采用真实的 交通流数据进行仿真实验，结果表明本文方法适于求解不确定环境下的交通信号配时问题。 关键词：群智能；劳动分工；任务分配；激发–抑制原理；个体–个体交互；自组织；时间分配；交通信号配时 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)03−0438−11 中文引用格式：肖人彬, 王英聪. 一种面向时间分配问题的群智能劳动分工新方法[J]. 智能系统学报, 2019, 14(3): 438–448. 英文引用格式：XIAO Renbin, WANG Yingcong. A new approach to labor division in swarm intelligence for time allocation problem[J]. CAAI transactions on intelligent systems, 2019, 14(3): 438–448. A new approach to labor division in swarm intelligence for time allocation problem XIAO Renbin1 ，WANG Yingcong2 (1. School of Artificial Intelligence and Automation, Huazhong University of Science and Technolgy, Wuhan 430074, China; 2. School of Electrical and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China) Abstract: In this paper, we use the labor division in swarm intelligence to solve the time allocation problem represented by the traffic signal timing problem of allocating green light time to signal phases, and propose a new bee swarm labor division algorithm (BSLDA). The traffic signal timing problem is analyzed from the perspective of time allocation, and the activator-inhibitor mechanism under labor division is introduced in BSLDA. For each signal phase, BSLDA defines one activator, one inhibitor and three behaviors (i.e., increasing green light time, reducing green light time and keeping green light time). With the activator-inhibitor mechanism, each signal phase in BSLDA could choose appropriate behavior according to environmental change to achieve the time allocation. The real traffic flow data is used in the simulation experiment, and the results show that the proposed approach is effective and suitable for the dynamic traffic signal timing problem in uncertain environment. Keywords: swarm intelligence; labor division; task allocation; activator-inhibitor mechanism; individual-individual interactions; self-organization; time allocation; traffic signal timing 在现实生活中经常会遇到各种各样的分配问 题，比如资源分配[1] 、收入分配[2] 、资产分配[3] 、功 率分配[4] 、任务分配[5]等，因此关于分配问题的研 究得到广泛关注。以任务分配为例，从静态任务 分配到动态任务分配，从集中式任务分配到分布 收稿日期：2018−07−17. 网络出版日期：2019−04−22. 基金项目：国家自然科学基金项目 (61702463，51875220)；河南 省科技攻关项目 (192102210111). 通信作者：肖人彬. E-mail：rbxiao@hust.edu.cn. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019
第3期 肖人彬，等：一种面向时间分配问题的群智能劳动分工新方法 ·439· 式任务分配，不同的应用背景和实际需求，推动 1 时间分配视角下的交通信号配时 着任务分配问题研究的不断发展。 问题分析 时间分配是一类重要的分配问题，旨在提高 可重复使用资源的利用率。例如：在生产调度 1.1问题描述 中，单机调度问题研究如何将一台机器按时间顺 交通信号配时指的是利用交通信号灯对道路 序分配给等待加工的工件，以提高生产效率： 上的车辆和行人进行指挥，其作用在于保障交叉 在交通管理中，交通信号配时研究如何在时间上 口的交通安全和充分发挥交叉口的通行效率20。 将互相冲突的交通流予以分类，使其在不同时间 交通信号配时问题主要涉及信号相位的确定、配 通过交叉口10。如果将机器和交叉口看成有限 时参数的选择以及运行效率的衡量3个方面。 资源，将工件和交通流视为主体，则时间分配问 首先，信号相位指在某个或者某几个方向上 题可以界定为：将有限的资源在时间维度上进行 的交通流同时得到通行权的时间带，信号相位及 分割，并安排各主体在不同时间段内轮流使用该 其组合顺序构成相位方案四。以普遍存在的十字 资源。 交叉口为例（见图1），其在东、西、南、北4个方向 作为一种典型的颇具代表性的时间分配问 上都有左行、直行和右行3个方向的车流，图2描 题，交通信号配时是缓解城市交通拥堵的关键环 述了2种常用的四相位方案。 节之一。在交通信号配时中，来自不同方向的 交通流均可通过交叉口，而在任一时刻只能有一 股或几股互不冲突的交通流通过交叉口。因此， 时间分配问题的一个显著特点就是不同的主体按 分时方式共享资源。简而言之，时间分配问题就 是将一个时间周期划分为若干时间段，然后把时 西 间段分配给不同的主体。任务分配问题一般指将 一个总任务划分为若干子任务，然后把子任务分 配给不同的主体去执行。基于这种相似性，任务 分配方法同样可以用来求解时间分配问题，而群 南 智能劳动分工是实现任务分配的一种重要方式。 图1十字交叉口 群智能指众多简单的主体通过交互作用所表 Fig.1 A sketch of the intersection 现出来的宏观智能行为)，它是那些具有社会性 特征的群居生物个体合作进行某些活动时才会产 生的涌现现象。在社会性昆虫中，不同的个体执 行不同的任务，这种现象叫做劳动分工)。群智 第一相位 第二相位第三相位 第四相位 (a)方案一 能劳动分工是一种自下而上的任务分配方式，无 需全局信息和中心控制即可实现有效的任务分 ￥ t 配，而且能够适应动态变化的环境。群智能劳动 第一相位 第二相位 第三相位 第四相位 分工的这一特点吸引了众多学者的关注，并被用 (b)方案二 于解决一些任务分配问题，比如供应链中的任务 图2四相位方案 分配、群机器人系统中的任务分配)、无线传 Fig.2 Four phases scheme 感网络中的任务分配、无人机群中的任务分配叼 其次，交通信号配时的主要设计参数有信号 等。此外，群智能劳动分工也被用于求解其他分 周期和绿信比2。信号周期指从起始相位到终 配问题，比如布局问题的空间分配和社会群体 止相位所经历的时间，用C表示，单位为$。绿 间的利益分配。本文以交通信号配时为代表， 信比指在一个信号周期内，某一相位的有效绿灯 将群智能劳动分工用于求解时间分配问题。先从 时长x与信号周期时长C之比，一般用1表示， 时间分配的视角对交通信号配时问题进行分析， 1=x/C。 然后提出一种求解交通信号配时问题的群智能劳 最后，配时参数下交通效益的评价指标包括 动分工方法，并通过实例分析与讨论，阐述了面向 延误时间、停车次数和通行能力等，其中延误时 时间分配问题的群智能劳动分工方法的优越性。 间和停车次数体现了道路使用者的利益，通行能
式任务分配，不同的应用背景和实际需求，推动 着任务分配问题研究的不断发展[6]。 时间分配是一类重要的分配问题，旨在提高 可重复使用资源的利用率。例如：在生产调度 中，单机调度问题研究如何将一台机器按时间顺 序分配给等待加工的工件，以提高生产效率[7-8] ； 在交通管理中，交通信号配时研究如何在时间上 将互相冲突的交通流予以分类，使其在不同时间 通过交叉口[9-10]。如果将机器和交叉口看成有限 资源，将工件和交通流视为主体，则时间分配问 题可以界定为：将有限的资源在时间维度上进行 分割，并安排各主体在不同时间段内轮流使用该 资源。 作为一种典型的颇具代表性的时间分配问 题，交通信号配时是缓解城市交通拥堵的关键环 节之一[11]。在交通信号配时中，来自不同方向的 交通流均可通过交叉口，而在任一时刻只能有一 股或几股互不冲突的交通流通过交叉口。因此， 时间分配问题的一个显著特点就是不同的主体按 分时方式共享资源。简而言之，时间分配问题就 是将一个时间周期划分为若干时间段，然后把时 间段分配给不同的主体。任务分配问题一般指将 一个总任务划分为若干子任务，然后把子任务分 配给不同的主体去执行。基于这种相似性，任务 分配方法同样可以用来求解时间分配问题，而群 智能劳动分工是实现任务分配的一种重要方式。 群智能指众多简单的主体通过交互作用所表 现出来的宏观智能行为[12] ，它是那些具有社会性 特征的群居生物个体合作进行某些活动时才会产 生的涌现现象。在社会性昆虫中，不同的个体执 行不同的任务，这种现象叫做劳动分工[13]。群智 能劳动分工是一种自下而上的任务分配方式，无 需全局信息和中心控制即可实现有效的任务分 配，而且能够适应动态变化的环境。群智能劳动 分工的这一特点吸引了众多学者的关注，并被用 于解决一些任务分配问题，比如供应链中的任务 分配[14] 、群机器人系统中的任务分配[15] 、无线传 感网络中的任务分配[16] 、无人机群中的任务分配[17] 等。此外，群智能劳动分工也被用于求解其他分 配问题，比如布局问题的空间分配[18]和社会群体 间的利益分配[19]。本文以交通信号配时为代表， 将群智能劳动分工用于求解时间分配问题。先从 时间分配的视角对交通信号配时问题进行分析， 然后提出一种求解交通信号配时问题的群智能劳 动分工方法，并通过实例分析与讨论，阐述了面向 时间分配问题的群智能劳动分工方法的优越性。 1 时间分配视角下的交通信号配时 问题分析 1.1 问题描述 交通信号配时指的是利用交通信号灯对道路 上的车辆和行人进行指挥，其作用在于保障交叉 口的交通安全和充分发挥交叉口的通行效率[20]。 交通信号配时问题主要涉及信号相位的确定、配 时参数的选择以及运行效率的衡量 3 个方面。 首先，信号相位指在某个或者某几个方向上 的交通流同时得到通行权的时间带，信号相位及 其组合顺序构成相位方案[21]。以普遍存在的十字 交叉口为例 (见图 1)，其在东、西、南、北 4 个方向 上都有左行、直行和右行 3 个方向的车流，图 2 描 述了 2 种常用的四相位方案。 北 南 西 东 图 1 十字交叉口 Fig. 1 A sketch of the intersection 第一相位 第二相位 第三相位 第四相位 (a) 方案一 第一相位 第二相位 第三相位 第四相位 (b) 方案二 图 2 四相位方案 Fig. 2 Four phases scheme λ = x/C 其次，交通信号配时的主要设计参数有信号 周期和绿信比[22]。信号周期指从起始相位到终 止相位所经历的时间，用 C 表示，单位为 s。绿 信比指在一个信号周期内，某一相位的有效绿灯 时长 x 与信号周期时长 C 之比，一般用 λ 表示， 。 最后，配时参数下交通效益的评价指标包括 延误时间、停车次数和通行能力等，其中延误时 间和停车次数体现了道路使用者的利益，通行能 第 3 期 肖人彬，等：一种面向时间分配问题的群智能劳动分工新方法 ·439·
·440· 智能系统学报 第14卷 力体现了道路的使用效率2。以第i相位为例， 常用的求解方法以智能优化方法为主，包括遗传 车辆延误时间2（单位为s)为 算法、粒子群算法2、蚁群算法2川、模拟退火算 Di= C(1-)2,1- gi 法2等。这些算法在求解交通信号配时问题时存 21-%+24+2S1.8A,-90 在收敛速度慢、效率低等问题2，而且在不同交 车辆停车次数（单位为次）为 通场景下的求解效果差异大，说明算法的适应性 0.9(1-1) H:= 较差。群智能劳动分工可以弥补这一欠缺，其显 1-y: 著特点就是在动态环境下仍能实现有效的任务分 通行能力P(单位为pcuh)为 配。据此本文从分配的视角出发，利用群智能劳 0=S 动分工方法来求解交通信号配时问题。下面首先 式中S、少、9：、，分别为第i相位的饱和流量 引入群智能劳动分工中的激发-抑制原理，然后 (pcu/h)、流量比、车流量(pcu/h)和绿信比。 一个周期内交叉口的车辆平均延误时间为 建立蜂群劳动分工与交通信号配时之间的映射关 系，进而提出一种面向交通信号配时问题的蜂群 D-Dal 劳动分工算法。 2.1群智能劳动分工中的激发-抑制原理 车辆平均停车次数为 以蜂群为代表的时间行为多型是群智能劳动 H-∑Ha/∑4 分工的一种主要模式，其中个体所执行的任务与 其生理年龄有关。具体的，蜜蜂在其生命周期 通行能力为 内一般会经历从哺育蜂到储存蜂以及觅食蜂的一 个行为发育过程，分别对应哺育、储存食物、觅食 等任务。根据蜂群的需要，蜜蜂能够延迟、加速、 式中n为相位总数。 甚至逆转其行为发育过程2。蜜蜂在柔性发育的 1.2时间分配特性 作用下，能够适应动态变化的环境，从而始终实 以图1所示的交叉口和图2所示的相位方案 现有效的任务分配。 为例，交通信号配时问题就是分别给4个相位的 Huang等2在研究蜂群的时间行为多型的时 车辆分配通行权，使其在通过交叉口时保持有序 候，提出了一种激发-抑制原理。该原理认为，蜜 状态，以减少交通拥堵、避免交通事故等。在一 蜂的行为发育是由激发剂和抑制剂共同决定的， 个信号周期内，车辆在交叉口处的通行权体现在 且二者具有耦合关系，即年长蜜蜂体内激发剂和 绿灯时间上。因此，交通信号配时问题可以看成 抑制剂的含量比年幼蜜蜂多。保幼激素被认为是 给各相位的车辆分配绿灯时间，是一个典型的时 蜜蜂的激发剂，促进其行为发育，该发育过程伴 间分配问题。时间分配问题的显著特点是分时使 随着蜜蜂从巢内工作向巢外工作的转移。蜜蜂之 用，该特点在交通信号配时问题上表现为共享性 间进行交互时会传递抑制剂，对其行为发育起阻 和独占性。共享性指来自不同相位的车辆均可通 碍作用。激发剂和抑制剂共同维持着蜜蜂在不同 过交叉口，独占性指任一时刻只能有一个相位的 任务上的动态分配平衡。比如：当觅食者减少 车辆通过交叉口。 时，抑制剂会减弱，巢穴内的蜜蜂会加速发育成 由上述分析可知，交通信号配时问题的时间 觅食者；当觅食者较多时，抑制剂会变强，巢穴内 分配特性表现为来自不同相位的车辆分时通过交 蜜蜂的发育会被延迟，甚至觅食者会返回巢穴内工作。 叉口。一般而言，通过交叉口的车流量是在动态 激发-抑制原理以个体-个体交互的方式完成 变化的，既有规律性的变化（如潮汐交通），也有非 任务分配，Naug等Bol进一步描述了激发-抑制原 规律性的变化（如汽车保有量的增加）。动态变化 理中个体间的交互方式，如图3所示。蜂群中每 的车流量要求配时参数（如信号周期时长、绿灯 只蜜蜂都包含1个激发剂A(Activator)和2个抑 时长等)能做出适应性的动态调整。 制剂L,和I(Inhibitor)。A是蜜蜂内在的激发剂， 2求解交通信号配时问题的群智能 对蜜蜂自身的行为发育起促进作用。1，是蜜蜂内 劳动分工方法 在的抑制剂，不会阻碍自身的行为发育，但在个 体交互过程中会对其他蜜蜂的行为发育产生抑制 对于交通信号配时问题，一般以延误时间最 作用。2是蜜蜂在交互作用中得到的外在抑制 短、停车次数最少和通行能力最大为目标函数。 剂，会阻碍自身的行为发育。最终，激发剂A和
力体现了道路的使用效率[23]。以第 i 相位为例， 车辆延误时间[24] (单位为 s) 为 Di = C(1−λi) 2 2(1−yi) + 1−λi 2qi + qi 2S iλi(S iλi −qi) 车辆停车次数[24] (单位为次) 为 Hi = 0.9(1−λi) 1−yi 通行能力[24] (单位为 pcu/h) 为 Qi = S iλi 式中 Si、 y i、 qi、 λ i 分别为第 i 相位的饱和流量 (pcu/h)、流量比、车流量 (pcu/h) 和绿信比。 一个周期内交叉口的车辆平均延误时间为 D = ∑n i=1 Diqi/ ∑n i=1 qi 车辆平均停车次数为 H = ∑n i=1 Hiqi/ ∑n i=1 qi 通行能力为 Q = ∑n i=1 Q 式中 n 为相位总数。 1.2 时间分配特性 以图 1 所示的交叉口和图 2 所示的相位方案 为例，交通信号配时问题就是分别给 4 个相位的 车辆分配通行权，使其在通过交叉口时保持有序 状态，以减少交通拥堵、避免交通事故等。在一 个信号周期内，车辆在交叉口处的通行权体现在 绿灯时间上。因此，交通信号配时问题可以看成 给各相位的车辆分配绿灯时间，是一个典型的时 间分配问题。时间分配问题的显著特点是分时使 用，该特点在交通信号配时问题上表现为共享性 和独占性。共享性指来自不同相位的车辆均可通 过交叉口，独占性指任一时刻只能有一个相位的 车辆通过交叉口。 由上述分析可知，交通信号配时问题的时间 分配特性表现为来自不同相位的车辆分时通过交 叉口。一般而言，通过交叉口的车流量是在动态 变化的，既有规律性的变化 (如潮汐交通)，也有非 规律性的变化 (如汽车保有量的增加)。动态变化 的车流量要求配时参数 (如信号周期时长、绿灯 时长等) 能做出适应性的动态调整。 2 求解交通信号配时问题的群智能 劳动分工方法 对于交通信号配时问题，一般以延误时间最 短、停车次数最少和通行能力最大为目标函数。 常用的求解方法以智能优化方法为主，包括遗传 算法[24] 、粒子群算法[25] 、蚁群算法[21] 、模拟退火算 法 [26]等。这些算法在求解交通信号配时问题时存 在收敛速度慢、效率低等问题[27] ，而且在不同交 通场景下的求解效果差异大，说明算法的适应性 较差。群智能劳动分工可以弥补这一欠缺，其显 著特点就是在动态环境下仍能实现有效的任务分 配。据此本文从分配的视角出发，利用群智能劳 动分工方法来求解交通信号配时问题。下面首先 引入群智能劳动分工中的激发–抑制原理，然后 建立蜂群劳动分工与交通信号配时之间的映射关 系，进而提出一种面向交通信号配时问题的蜂群 劳动分工算法。 2.1 群智能劳动分工中的激发–抑制原理 以蜂群为代表的时间行为多型是群智能劳动 分工的一种主要模式，其中个体所执行的任务与 其生理年龄有关[13]。具体的，蜜蜂在其生命周期 内一般会经历从哺育蜂到储存蜂以及觅食蜂的一 个行为发育过程，分别对应哺育、储存食物、觅食 等任务。根据蜂群的需要，蜜蜂能够延迟、加速、 甚至逆转其行为发育过程[28]。蜜蜂在柔性发育的 作用下，能够适应动态变化的环境，从而始终实 现有效的任务分配。 Huang 等 [29]在研究蜂群的时间行为多型的时 候，提出了一种激发–抑制原理。该原理认为，蜜 蜂的行为发育是由激发剂和抑制剂共同决定的， 且二者具有耦合关系，即年长蜜蜂体内激发剂和 抑制剂的含量比年幼蜜蜂多。保幼激素被认为是 蜜蜂的激发剂，促进其行为发育，该发育过程伴 随着蜜蜂从巢内工作向巢外工作的转移。蜜蜂之 间进行交互时会传递抑制剂，对其行为发育起阻 碍作用。激发剂和抑制剂共同维持着蜜蜂在不同 任务上的动态分配平衡。比如：当觅食者减少 时，抑制剂会减弱，巢穴内的蜜蜂会加速发育成 觅食者；当觅食者较多时，抑制剂会变强，巢穴内 蜜蜂的发育会被延迟，甚至觅食者会返回巢穴内工作。 激发–抑制原理以个体–个体交互的方式完成 任务分配，Naug 等 [30]进一步描述了激发–抑制原 理中个体间的交互方式，如图 3 所示。蜂群中每 只蜜蜂都包含 1 个激发剂 A(Activator) 和 2 个抑 制剂 I1 和 I2 (Inhibitor)。A 是蜜蜂内在的激发剂， 对蜜蜂自身的行为发育起促进作用。I1 是蜜蜂内 在的抑制剂，不会阻碍自身的行为发育，但在个 体交互过程中会对其他蜜蜂的行为发育产生抑制 作用。I2 是蜜蜂在交互作用中得到的外在抑制 剂，会阻碍自身的行为发育。最终，激发剂 A 和 ·440· 智 能 系 统 学 报 第 14 卷
第3期 肖人彬，等：一种面向时间分配问题的群智能劳动分工新方法 ·441· 抑制剂2的相对水平(A0决定蜜蜂的行为发育 蜂群劳动分工 交通信号配时 是按照正常速度还是被加速、延迟或逆转。 蜜蜂 信号相位 个体交互 生理年龄 绿灯时间 激发剂 延误时间 抑制剂 停车次数 个体1 个体2 图4蜂群劳动分工与交通信号配时之间的映射关系 图3激发-抑制原理中个体间的交互方式 Fig.4 The mapping relation between bee swarm's labor Fig.3 The interaction between individuals in activator-in- division and traffic signal timing hibitor mechanism 2.3蜂群劳动分工算法 2.2映射关系 基于图4描述的映射关系，本节提出一种面 激发-抑制原理可以简述为：激发剂促进蜜蜂 向交通信号配时问题的蜂群劳动分工算法(bee 生理年龄的增长，抑制剂阻碍蜜蜂生理年龄的增 swarm labor division algorithm,BSLDA)BSLDA 长，激发剂和抑制剂共同影响蜜蜂的生理年龄， 的核心要点是：某一信号相位的延误时间越长 从而决定蜜蜂所执行的任务。此外，在蜂群中激 则其激发剂越大，在激发-抑制原理作用下，其绿 发剂和抑制剂还具有耦合关系，表现为年长蜜蜂 灯时间将会增加；延误时间越长，相应的停车次 体内激发剂和抑制剂的含量比年幼蜜蜂多。在利 数也越大，则抑制剂越大，在激发-抑制原理作用 用激发-抑制原理解决实际分配问题时，这种耦 下，其他相位的绿灯时间将会减小。BSLDA通过 合关系可根据具体情况进行适当放宽。比如，文 激发剂和抑制剂调整各信号相位的绿灯时间完成 献[31-32]利用激发-抑制原理分别设计了3种方 时间分配，具有原理简要明晰、便于实现的特点。 法来解决机器人间的任务分配问题，这些方法均 激发-抑制原理需要对激发剂和抑制剂进行 比较，而延误时间和停车次数的量纲和量级都不 没有考虑激发剂和抑制剂的耦合关系。 同，难以直接比较。这里以经典F-B配时法的控 在蜂群劳动分工中，不同的蜜蜂执行不同的 制方案(TRRL)对应的延误时间和停车次数为标 任务完成任务分配。在交通信号配时中，不同的 准数，建立相对性能指标。 信号相位占据不同的绿灯时间完成时间分配。 一 第1相位车辆延误时间的相对指标为 般而言，某一信号相位的车辆延迟时间长（或者 RD:=D/DTTRL (1) 停车次数多)，说明该信号相位的绿灯时间短，此 第1相位车辆停车次数的相对指标为 时应该增加其绿灯时间。同时，在信号周期固定 RH:=H:/HTTRL (2) 或有限的情况下，还应减小其他信号相位的绿灯 第i相位的激发剂为 时间。 A;=RD (3) 基于上述分析，为了借鉴蜂群劳动分工的任 第i相位的抑制剂为 务分配来实现交通信号配时的时间分配，图4给 I=RH (4) 出了劳动分工与交通信号配时之间的映射关系。 第i相位的激发抑制比为 该映射主要包括：1)将交叉口交通信号灯的每一 个信号相位看作一只蜜蜂：2)将信号相位的绿灯 f-AI (5) 时间看作蜜蜂的生理年龄；3)将信号相位的延误 式中：n为信号相位的个数，这里假设蜜蜂与其他 时间看作蜜蜂的激发剂：4)将信号相位的停车次 所有蜜蜂都进行交互。 数看作蜜蜂的抑制剂。由于本文直接将生理年龄 激发-抑制原理是通过激发-抑制比来控制蜜 与分配变量时间对应起来，在激发剂和抑制剂的 蜂的生理年龄。相应地，在BSLDA中，通过激发- 耦合关系中应释放对年龄的约束，即耦合关系变 抑制比来决定信号相位的绿灯时间，具体如下： 为激发剂含量多的个体产生的抑制剂也多。同 1)当后<a(a为上限阈值)时，相位i的绿灯时 时，延误时间和停车次数之间呈指数关联趋势， 间减小，相应的减小量为 恰好满足这种耦合关系。 4=(f) (6)
抑制剂 I2 的相对水平 (A/I) 决定蜜蜂的行为发育 是按照正常速度还是被加速、延迟或逆转。 个体交互 A/I A I1 I2 A/I A I1 I2 个体 1 个体 2 图 3 激发–抑制原理中个体间的交互方式 Fig. 3 The interaction between individuals in activator-inhibitor mechanism 2.2 映射关系 激发–抑制原理可以简述为：激发剂促进蜜蜂 生理年龄的增长，抑制剂阻碍蜜蜂生理年龄的增 长，激发剂和抑制剂共同影响蜜蜂的生理年龄， 从而决定蜜蜂所执行的任务。此外，在蜂群中激 发剂和抑制剂还具有耦合关系，表现为年长蜜蜂 体内激发剂和抑制剂的含量比年幼蜜蜂多。在利 用激发–抑制原理解决实际分配问题时，这种耦 合关系可根据具体情况进行适当放宽。比如，文 献[31-32]利用激发–抑制原理分别设计了 3 种方 法来解决机器人间的任务分配问题，这些方法均 没有考虑激发剂和抑制剂的耦合关系。 在蜂群劳动分工中，不同的蜜蜂执行不同的 任务完成任务分配。在交通信号配时中，不同的 信号相位占据不同的绿灯时间完成时间分配。一 般而言，某一信号相位的车辆延迟时间长 (或者 停车次数多)，说明该信号相位的绿灯时间短，此 时应该增加其绿灯时间。同时，在信号周期固定 或有限的情况下，还应减小其他信号相位的绿灯 时间。 基于上述分析，为了借鉴蜂群劳动分工的任 务分配来实现交通信号配时的时间分配，图 4 给 出了劳动分工与交通信号配时之间的映射关系。 该映射主要包括：1) 将交叉口交通信号灯的每一 个信号相位看作一只蜜蜂；2) 将信号相位的绿灯 时间看作蜜蜂的生理年龄；3) 将信号相位的延误 时间看作蜜蜂的激发剂；4) 将信号相位的停车次 数看作蜜蜂的抑制剂。由于本文直接将生理年龄 与分配变量时间对应起来，在激发剂和抑制剂的 耦合关系中应释放对年龄的约束，即耦合关系变 为激发剂含量多的个体产生的抑制剂也多。同 时，延误时间和停车次数之间呈指数关联趋势[21] ， 恰好满足这种耦合关系。 蜜蜂 信号相位 生理年龄 绿灯时间 激发剂 延误时间 抑制剂 停车次数 蜂群劳动分工 交通信号配时 图 4 蜂群劳动分工与交通信号配时之间的映射关系 Fig. 4 The mapping relation between bee swarm’s labor division and traffic signal timing 2.3 蜂群劳动分工算法 基于图 4 描述的映射关系，本节提出一种面 向交通信号配时问题的蜂群劳动分工算法 (bee swarm labor division algorithm, BSLDA)。BSLDA 的核心要点是：某一信号相位的延误时间越长， 则其激发剂越大，在激发–抑制原理作用下，其绿 灯时间将会增加；延误时间越长，相应的停车次 数也越大，则抑制剂越大，在激发–抑制原理作用 下，其他相位的绿灯时间将会减小。BSLDA 通过 激发剂和抑制剂调整各信号相位的绿灯时间完成 时间分配，具有原理简要明晰、便于实现的特点。 激发–抑制原理需要对激发剂和抑制剂进行 比较，而延误时间和停车次数的量纲和量级都不 同，难以直接比较。这里以经典 F-B 配时法的控 制方案 (TRRL) 对应的延误时间和停车次数为标 准数，建立相对性能指标。 第 i 相位车辆延误时间的相对指标为 RDi = Di/D TTRL i (1) 第 i 相位车辆停车次数的相对指标为 RHi = Hi/H TTRL i (2) 第 i 相位的激发剂为 Ai = RDi (3) 第 i 相位的抑制剂为 Ii = RHi (4) 第 i 相位的激发抑制比为 fi = Ai/ ∑n j=1 j,i Ij (5) 式中：n 为信号相位的个数，这里假设蜜蜂与其他 所有蜜蜂都进行交互。 激发–抑制原理是通过激发–抑制比来控制蜜 蜂的生理年龄。相应地，在 BSLDA 中，通过激发– 抑制比来决定信号相位的绿灯时间，具体如下： f 1) 当 i < α (α为上限阈值) 时，相位 i 的绿灯时 间减小，相应的减小量为 ∆ − i = ψ(fi) (6) 第 3 期 肖人彬，等：一种面向时间分配问题的群智能劳动分工新方法 ·441·
·442· 智能系统学报 第14卷 式中()为f的负相关函数。当激发抑制比低于 5)根据式(6)或式(7)计算各相位的绿灯时间 上限阈值时，绿灯时间减小，且激发抑制比越小， 变化量： 绿灯时间的减少量越大。 6)根据绿灯时间的修正方法确定各信号相位 2)当f>B(B为下限阈值)时，相位i的绿灯时 的绿灯时间及信号周期； 间增加，相应的增加量为 7)若达到最大迭代次数，转至8)，否则转 4=f) (7) 至2)： 式中)为f的正相关函数。当激发-抑制比高于 8)输出结果。 下限阈值时，绿灯时间增加，且激发抑制比越大， 绿灯时间的增加量越大。 初始化相位方案及参数 3)当α≤≤时，相位i的绿灯时间保持不变。 为进一步提高算法效率，在每一次时间分配 计算相位的激发剂和抑制剂 过程中，对各相位绿灯时间的变化量进行修正： 当所有相位都选择减少绿灯时间时，以最大减少 量作为总的减少量，并按照减少比例分给各相 确定相位的激发抑制比 位，此时信号周期变短；当所有相位都选择增加 绿灯时间时，以最大增加量作为总的增加量，并 更新相位的绿灯时间 按照增加比例分给各相位，此时信号周期变长； 当一部分相位选择增加绿灯时间，而另一部分相 位选择减少绿灯时间时，通过归一化处理，使得 满足停止准则 时间的增加量等于时间的减少量，此时信号周期 保持不变；当所有相位都选择保持绿灯时间不变 时，达到一个时间分配平衡。 输出结果 BSLDA在解决交通信号配时问题时，每个信 号相位都有增加绿灯时间、减少绿灯时间和保持 图5蜂群劳动分工算法的实现流程 Fig.5 The implementation process of BSLDA 绿灯时间不变3种行为选择。具体选择哪一种行 为，是由信号相位的激发-抑制比决定的，激发剂 3 实例分析与讨论 与信号相位自身的延误时间有关，抑制剂与其他 31交通数据 信号相位的停车次数有关。信号相位的激发剂、 本文使用的交通数据来自于2014年中国“云 抑制剂和激发抑制比会随着绿灯时间、交通流量 上贵州”大数据商业模式大赛一智能交通算法 以及信号周期等变化，使得同一信号相位在不同 大挑战。该数据描述了贵阳市南明区的主干路段 交通场景下的行为选择不同，进而能够适应环境 在6：00~20：00时间段内通过各交叉路口的车流 的变化。 量情况。图6是贵阳市南明区部分区域的简化道 图5描述了BSLDA的实现流程，具体步骤为： 路与红绿灯位置图，其中红绿灯用山，来表示。本 1)初始化相位方案、配时参数以及算法参 文选取交通数据文件“f1ow0901”中红绿灯D为 数，包括相位总数n、信号周期C、绿灯时间x、最 “tl26”和“tl3o”的交通数据，通过处理得到红绿灯 大迭代次数N、上限阈值a、下限阈值B、负相关 “t6”和tl0”的车流量情况，如图7和8所示。图7 函数(f)以及正相关函数(f)等； 中从南进口驶入的车流整体上处于较高的车流量 2)根据式(3)和式(4)分别计算各相位的激发 水平，图8中从西进口驶入的车流整体上处于较 剂和抑制剂； 高的车流量水平，即不同路口、不同方向的车流 3)根据式（⑤）计算各相位的激发抑制比： 存在较大差异。图7和图8中的交通数据反映出 4)若所有相位的激发抑制比都落在上限阈 了车流的高度动态性，对于评估信号配时方法的 值a和下限阈值B之间，转至8)，否则转至5)： 效果具有较强的说服力
ψ(fi) f 式中 为 i的负相关函数。当激发抑制比低于 上限阈值时，绿灯时间减小，且激发抑制比越小， 绿灯时间的减少量越大。 f 2) 当 i > β ( β 为下限阈值) 时，相位 i 的绿灯时 间增加, 相应的增加量为 ∆ + i = ϕ(fi) (7) ϕ(fi) f 式中 为 i的正相关函数。当激发–抑制比高于 下限阈值时，绿灯时间增加，且激发抑制比越大， 绿灯时间的增加量越大。 α ⩽ f 3) 当 i ⩽ β 时，相位 i 的绿灯时间保持不变。 为进一步提高算法效率，在每一次时间分配 过程中，对各相位绿灯时间的变化量进行修正： 当所有相位都选择减少绿灯时间时，以最大减少 量作为总的减少量，并按照减少比例分给各相 位，此时信号周期变短；当所有相位都选择增加 绿灯时间时，以最大增加量作为总的增加量，并 按照增加比例分给各相位，此时信号周期变长； 当一部分相位选择增加绿灯时间，而另一部分相 位选择减少绿灯时间时，通过归一化处理，使得 时间的增加量等于时间的减少量，此时信号周期 保持不变；当所有相位都选择保持绿灯时间不变 时，达到一个时间分配平衡。 BSLDA 在解决交通信号配时问题时，每个信 号相位都有增加绿灯时间、减少绿灯时间和保持 绿灯时间不变 3 种行为选择。具体选择哪一种行 为，是由信号相位的激发–抑制比决定的，激发剂 与信号相位自身的延误时间有关，抑制剂与其他 信号相位的停车次数有关。信号相位的激发剂、 抑制剂和激发抑制比会随着绿灯时间、交通流量 以及信号周期等变化，使得同一信号相位在不同 交通场景下的行为选择不同，进而能够适应环境 的变化。 图 5 描述了 BSLDA 的 实现流程，具体步骤为： ψ(fi) ϕ(fi) 1) 初始化相位方案、配时参数以及算法参 数，包括相位总数 n、信号周期 C、绿灯时间 x、最 大迭代次数 N、上限阈值 α、下限阈值 β、负相关 函数 以及正相关函数 等； 2) 根据式 (3) 和式 (4) 分别计算各相位的激发 剂和抑制剂； 3) 根据式 (5) 计算各相位的激发抑制比； 4) 若所有相位的激发抑制比都落在上限阈 值 α 和下限阈值 β 之间，转至 8)，否则转至 5)； 5) 根据式 (6) 或式 (7) 计算各相位的绿灯时间 变化量； 6) 根据绿灯时间的修正方法确定各信号相位 的绿灯时间及信号周期； 7) 若达到最大迭代次数，转至 8)，否则转 至 2)； 8) 输出结果。 初始化相位方案及参数 计算相位的激发剂和抑制剂 确定相位的激发抑制比 更新相位的绿灯时间 满足停止准则 输出结果 Y N 图 5 蜂群劳动分工算法的实现流程 Fig. 5 The implementation process of BSLDA 3 实例分析与讨论 3.1 交通数据 本文使用的交通数据来自于 2014 年中国“云 上贵州”大数据商业模式大赛—智能交通算法 大挑战。该数据描述了贵阳市南明区的主干路段 在 6:00～20:00 时间段内通过各交叉路口的车流 量情况。图 6 是贵阳市南明区部分区域的简化道 路与红绿灯位置图，其中红绿灯用 tli 来表示。本 文选取交通数据文件“flow0901”中红绿灯 ID 为 “tl 26”和“tl 30”的交通数据，通过处理得到红绿灯 “tl26”和“tl30”的车流量情况，如图 7 和 8 所示。图 7 中从南进口驶入的车流整体上处于较高的车流量 水平，图 8 中从西进口驶入的车流整体上处于较 高的车流量水平，即不同路口、不同方向的车流 存在较大差异。图 7 和图 8 中的交通数据反映出 了车流的高度动态性，对于评估信号配时方法的 效果具有较强的说服力。 ·442· 智 能 系 统 学 报 第 14 卷