第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 卷
第3期 肖人彬,等:一种面向时间分配问题的群智能劳动分工新方法 ·443 北京西路 0% 威清路 合群路 中 西 tl, 山 延安西路 ● s 北 t 延安东路〉 l21 华 tl 市西高架路 中山东路 中山西路丫山 路 花溪大道 t山o tls tls 图6贵阳市南明区部分区域路口简化示意图 Fig.6 A simplified diagram of some intersections in nanming district of GuiYang city 1600 东进口 2(a)形成的交通场景为TS21,图8和图2(b)形成 1400 ◆一西进口 的交通场景为TS22。 1200 一。一南进口 北进口 3.2参数设置 1000 800 假设车辆在交叉口处直行、左转和右转的比 600 例分别为60%、20%和20%;对于红绿灯“tl26”,东 400 西进口道上直行车道、左转车道和右转车道的饱 200 和流量分别为1000pcu/h、500pcu/h和500pcu/h, 6:008:0010:0012:0014:0016:0018:0020:00 南北进口道上直行车道、左转车道和右转车道的 时刻 饱和流量分别为2400pcu/h、1200pcu/h和1200 图7红绿灯“t山26”车流量 pcuh;对于红绿灯“tlo”,东西进口道上直行车道、 Fig.7 Traffic flow at the traffic light“tlzs” 左转车道和右转车道的饱和流量分别为2000pcuh、 1200 1000pcu/h和1000pcu/h;南北进口道上直行车道、 一东进口 1000 ◆一西进口 左转车道和右转车道的饱和流量分别为1200pcuh、 一南进口 日一北进口 600pcu/h和600pcu/h;绿灯间隔时间为4s,黄灯 时间为2s,启动损失时间为2s,最短绿灯时间为 600 5s,最长绿灯时间为60s。负相关函数()取 400 e为底数,a-j为自变量的指数函数;正相关函数 200 ()取e为底数,fB为自变量的指数函数。则 6:0080010:001200140016:0018:0020:00 a和B是BSLDA中影响绿灯时间分配的2个关 时刻 键因素。 图8红绿灯“tl30”车流量 本节主要研究上限阈值α和下限阈值B对平 Fig.8 Traffic flow at the traffic light“tlo” 均延误时间、平均停车次数和通行能力3个信号 为了体现信号配时方法在不同交通场景下的 配时评价指标的影响,并以此为依据设置α和 效果,本文选取图7和图8中的两种车流量,并使 B的取值。这里选取图8中6:00~7:00、8:00~ 用图2中的两种相位方案,通过组合得到4种不 9:00和11:00~12:00三个时间段的数据,它们分 同的交通场景。为了方便进行相关描述,本文记 别代表了闲散、顺畅和繁忙3种交通状态。在图 图7和图2(a)形成的交通场景为TS1_1,图7和 2(a)的相位方案下,得到a和B对各项指标的影 图2(b)形成的交通场景为TS12,图8和图 响(见图9)
北京西路 tl45 tl1 tl13 tl7 tl14 tl15 tl16 tl17 tl43 tl44 tl42 tl41 tl40 tl39 tl22 tl51 tl29 tl53 tl30 tl54 tl31 tl32 tl55 tl33 tl56 tl34 tl57 tl58 tl35 tl52 tl23 tl24 tl25 tl26 tl27 tl28 tl18 tl19 tl20 tl21 tl8 tl9 tl2 tl3 tl36 tl10 tl11 tl12 tl37 tl4 tl48 tl49 tl50 tl6 tl tl5 46 tl38 tl47 威清路 延安西路 延安东路 合群路 中 华 北 路 中 华 中 路 中山东路 中山西路 市西高架路 浣 沙 路 花溪大道 宝 山 北 路 陕 西 路 图 6 贵阳市南明区部分区域路口简化示意图 Fig. 6 A simplified diagram of some intersections in nanming district of GuiYang city 6:00 8:00 10:00 12:00 14:00 16:00 18:00 20:00 0 200 400 600 800 1 000 1 200 1 400 1 600 时刻 车流量/(pcu·h−1 ) 东进口 西进口 南进口 北进口 图 7 红绿灯“tl26”车流量 Fig. 7 Traffic flow at the traffic light “tl26” 6:00 8:00 10:00 12:00 14:00 16:00 18:00 20:00 0 200 400 600 800 1 000 1 200 时刻 车流量/(pcu·h−1 ) 东进口 西进口 南进口 北进口 图 8 红绿灯“tl30”车流量 Fig. 8 Traffic flow at the traffic light “tl30” 为了体现信号配时方法在不同交通场景下的 效果,本文选取图 7 和图 8 中的两种车流量,并使 用图 2 中的两种相位方案,通过组合得到 4 种不 同的交通场景。为了方便进行相关描述,本文记 图 7 和图 2(a) 形成的交通场景为 TS1_1,图 7 和 图 2(b ) 形成的交通场景 为 TS1_2, 图 8 和 图 2(a) 形成的交通场景为 TS2_1,图 8 和图 2(b) 形成 的交通场景为 TS2_2。 3.2 参数设置 假设车辆在交叉口处直行、左转和右转的比 例分别为 60%、20% 和 20%;对于红绿灯“tl26”,东 西进口道上直行车道、左转车道和右转车道的饱 和流量分别为 1 000 pcu/h、500 pcu/h 和 500 pcu/h, 南北进口道上直行车道、左转车道和右转车道的 饱和流量分别为 2 400 pcu/h、1 200 pcu/h 和 1 200 pcu/h;对于红绿灯“tl30”,东西进口道上直行车道、 左转车道和右转车道的饱和流量分别为 2 000 pcu/h、 1 000 pcu/h 和 1 000 pcu/h;南北进口道上直行车道、 左转车道和右转车道的饱和流量分别为 1 200 pcu/h、 600 pcu/h 和 600 pcu/h;绿灯间隔时间为 4 s,黄灯 时间为 2 s,启动损失时间为 2 s,最短绿灯时间为 5 s,最长绿灯时间为 60 s。负相关函数 ψ(fi ) 取 e 为底数,α-fi 为自变量的指数函数;正相关函数 ϕ(fi ) 取 e 为底数,fi -β 为自变量的指数函数。则 α 和 β 是 BSLDA 中影响绿灯时间分配的 2 个关 键因素。 本节主要研究上限阈值 α 和下限阈值 β 对平 均延误时间、平均停车次数和通行能力 3 个信号 配时评价指标的影响,并以此为依据设置 α 和 β 的取值。这里选取图 8 中 6:00~7:00、8:00~ 9:00 和 11:00~12:00 三个时间段的数据,它们分 别代表了闲散、顺畅和繁忙 3 种交通状态。在图 2(a) 的相位方案下,得到 α 和 β 对各项指标的影 响 (见图 9)。 第 3 期 肖人彬,等:一种面向时间分配问题的群智能劳动分工新方法 ·443·
·444· 智能系统学报 第14卷 20 3000 2000 10 10 2.0 1.5 0 1.5 0 2.0 0.5 0.5 1.5 0.5 B 1.00 B 1.00 1.00 (a)闲散状态下的平均延误时间 (b)闲散状态下的平均停车次数 (c)闲散状态下的通行能力 1.0 4000 0.9 80 0.8 3000 60 2.0 28 1.5 1.0 5 1.0 05 0.5 15 0.5 B 1.00 B 1.00 B 1.00 (d繁忙状态下的平均延误时间 ()繁忙状态下的平均停车次数 (田繁忙状态下的通行能力 30 1.0 三300 0.9 0.8 2000 10 1000 0 20 1.5 1.0 10 0.5 1.5 1.0 0.s 1.5 0.5 B 1.00 a B 1.00 B 1.00 (g)顺畅状态下的平均延误时间 ()顺畅状态下的平均停车次数 (句顺畅状态下的通行能力 图9上限阈值α和下限阈值B对各项指标的影响 Fig.9 The effects of upper threshold a and lower threshold B on evaluation indicators 从图9中可以看出,在不同的交通状态下, 周期。通行能力与绿信比成正比,其变化趋势 上限阈值α和下限阈值B对同一指标的影响大 与平均停车次数相反。在本文实验中,α选取 致相同。比如,平均延误时间随着α的增大呈 为0.8,B选取为1.3。 减小趋势,随着B的减小呈增大趋势。这是因 3.3对比实验 为平均延误时间受信号周期的影响较大,随着 为了验证本文算法(BSLDA)的有效性,本节 α的增大,更多的相位选择减少绿灯时间,并且 选择与经典的Webster配时方法、人工蜂群算法 绿灯时间的减少量变大,从而使得信号周期变 (ABC)和蚁群算法(ACO)等群智能优化方法进行 短,延误时间变短;随着B的减小,更多的相位 对比实验。求解时,先用Webster方法估计初始 选择增加绿灯时间,并且绿灯时间的增加量变 周期,然后利用等饱和比的方法计算各相位的大 大,从而使得信号周期变长,延误时间变长。平 致信号配时,再用BSLDA进行分配求解。 均停车次数随着B的增大呈增大趋势,随着α的 在4种交通场景下,分别得到4种配时方法 增大呈减小趋势,但是在B较小时又呈增大趋 在每个小时的性能对比情况,如图10和图11所 势。这是因为平均停车次数只受绿信比影响, 示。从图10可以看出,在交叉口和交通流量相同 B增大以后,更多停车次数多的相位难以通过增 的情况下,同一种配时方法在不同的相位方案下 加绿灯时间来增加绿信比,减少停车次数;α增 得到了不同的控制效果。同样的,在图11中也观 大以后,更多停车次数少的相位会让出绿灯时 察到了类似的情形。这进一步说明了,TS11、 间,从而使停车次数多的相位的绿信比变大,停 TS12、TS21和TS22是4种不同的交通场景, 车次数减小;当B较小、α较大时,在每一次的 对于评估交通信号配时方法的效果具有较强的说 分配过程中都存在增加绿灯时间和减少绿灯时 服力。从图10和图11中可以看出,BSLAD得到 间的相位,信号周期保持不变,此时的平均停车 的计算结果比其他算法延误时间和停车次数均有 次数变大,说明当前的信号周期不是最佳信号 减小,并且通行能力得到了提高
(g) 顺畅状态下的平均延误时间 (h) 顺畅状态下的平均停车次数 0 0.5 1.0 1.0 1.5 2.0 0.70 0.75 0.80 β α (i) 顺畅状态下的通行能力 0 0.5 1.0 1.0 1.5 2.0 1 000 2 000 3 000 β α (a) 闲散状态下的平均延误时间 (b) 闲散状态下的平均停车次数 0 0.5 1.0 1.0 1.5 2.0 0.6 0.7 0.8 0.9 1.0 0.6 1.0 β α (c) 闲散状态下的通行能力 0 0.5 1.0 1.0 1.5 2.0 2 000 3 000 4 000 β α (d) 繁忙状态下的平均延误时间 (e) 繁忙状态下的平均停车次数 0 0.5 1.0 1.0 1.5 2.0 0.7 0.8 0.9 β α (f) 繁忙状态下的通行能力 0 0.5 1.0 1.0 1.5 2.0 1 000 2 000 3 000 β α 0 0.5 1.0 1.0 1.5 2.0 10 15 20 β α 平均延误时间/s 0 0.5 1.0 1.0 1.5 2.0 60 80 100 β α 平均延误时间/s 0 0.5 1.0 1.0 1.5 2.0 10 20 30 β α 平均延误时间/s 平均停车次数 平均停车次数 平均停车次数 通行能力/(pcu·h−1 ) 通行能力/(pcu·h−1 ) 通行能力/(pcu·h−1 ) 图 9 上限阈值 α 和下限阈值 β 对各项指标的影响 Fig. 9 The effects of upper threshold α and lower threshold β on evaluation indicators 从图 9 中可以看出,在不同的交通状态下, 上限阈值 α 和下限阈值 β 对同一指标的影响大 致相同。比如,平均延误时间随着 α 的增大呈 减小趋势,随着 β 的减小呈增大趋势。这是因 为平均延误时间受信号周期的影响较大,随着 α 的增大,更多的相位选择减少绿灯时间,并且 绿灯时间的减少量变大,从而使得信号周期变 短,延误时间变短;随着 β 的减小,更多的相位 选择增加绿灯时间,并且绿灯时间的增加量变 大,从而使得信号周期变长,延误时间变长。平 均停车次数随着 β 的增大呈增大趋势,随着 α 的 增大呈减小趋势,但是在 β 较小时又呈增大趋 势。这是因为平均停车次数只受绿信比影响, β 增大以后,更多停车次数多的相位难以通过增 加绿灯时间来增加绿信比,减少停车次数;α 增 大以后,更多停车次数少的相位会让出绿灯时 间,从而使停车次数多的相位的绿信比变大,停 车次数减小;当 β 较小、α 较大时,在每一次的 分配过程中都存在增加绿灯时间和减少绿灯时 间的相位,信号周期保持不变,此时的平均停车 次数变大,说明当前的信号周期不是最佳信号 周期。通行能力与绿信比成正比,其变化趋势 与平均停车次数相反。在本文实验中, α 选取 为 0.8,β 选取为 1.3。 3.3 对比实验 为了验证本文算法 (BSLDA) 的有效性,本节 选择与经典的 Webster 配时方法、人工蜂群算法 (ABC) 和蚁群算法 (ACO) 等群智能优化方法进行 对比实验。求解时,先用 Webster 方法估计初始 周期,然后利用等饱和比的方法计算各相位的大 致信号配时,再用 BSLDA 进行分配求解。 在 4 种交通场景下,分别得到 4 种配时方法 在每个小时的性能对比情况,如图 10 和图 11 所 示。从图 10 可以看出,在交叉口和交通流量相同 的情况下,同一种配时方法在不同的相位方案下 得到了不同的控制效果。同样的,在图 11 中也观 察到了类似的情形。这进一步说明了,TS1_1、 TS1_2、TS2_1 和 TS2_2 是 4 种不同的交通场景, 对于评估交通信号配时方法的效果具有较强的说 服力。从图 10 和图 11 中可以看出,BSLAD 得到 的计算结果比其他算法延误时间和停车次数均有 减小,并且通行能力得到了提高。 ·444· 智 能 系 统 学 报 第 14 卷
第3期 肖人彬,等:一种面向时间分配问题的群智能劳动分工新方法 ·445· ■ Webster BSLDA ABC ACO 0 m0mmmmLmhnm 1234567891011121314 234567891011121314 时间序号 时间序号 (a)TS1-1场景下的平均延误时间 b)TS1-2场景下的平均延误时间 1.0 1.0 2 4 67891011121314 123 4567891011121314 时间序号 时间序号 (c)TS1-1场景下的平均停车次数 (d)TS1-2场景下的平均停车次数 3000 至3000 000 000 000 000 234567891011121314 1234567891011121314 时间序号 时间序号 (e)TS1-1场景下的通行能力 ()TS1-2场景下的通行能力 图10TS11和TS12交通场景下各项指标的比较 Fig.10 Comparison of evaluation indicators in traffic scenes TS1_1 and TS1_2 Webster BSLDA□ABC■ACO 230r 30 10 omhmmn的ma加ana 0 1234567891011121314 1234567891011121314 时间序号 时间序号 (a)TS2-1场景下的平均延误时间 (b)TS2-2场景下的平均延误时间 1.0 1.0 05 0.5 1234567891011121314 1234567891011121314 时间序号 时间序号 (c)TS2-1场景下的平均停车次数 (d)TS2-2场景下的平均停车次数 到 22000 000 0( 1234567891011121314 1234567891011121314 时间序号 时间序号 (e)TS2-1场景下的通行能力 ()TS2-2场景下的通行能力 图11TS21和TS22交通场景下各项指标的比较 Fig.11 Comparison of evaluation indicators in traffic scenes TS2 1 and TS2 2 表1~3统计了4种配时方法在不同交通场 ACO相比,本文所提方法分别减少平均停车次数 景下的整体效果。从表1中可以看出,与Web- 4.5%~8.2%、6.2%~10.0%、2.2%~5.3%。从表3 ster、ABC和ACO相比,本文所提方法分别减少 可以看出,与Webster、.ABC和ACO相比,本文所 平均延误时间11.7%~20.3%、7.6%~17.2%、6.7%~ 提方法分别提高通行量4.3%~19.6%、9.8%一 14.7%。从表2可以看出,与Webster、ABC和 24.6%、4.5%~12.8%
1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 50 100 时间序号 平均延误时间/s (a) TS1-1 场景下的平均延误时间 (b) TS1-2 场景下的平均延误时间 (c) TS1-1 场景下的平均停车次数 (d) TS1-2 场景下的平均停车次数 (e) TS1-1 场景下的通行能力 (f) TS1-2 场景下的通行能力 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 10 20 30 时间序号 平均延误时间/s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0.5 1.0 时间序号 平均停车次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0.5 1.0 时间序号 平均停车次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 000 2 000 3 000 时间序号 通行能力/(pcu·h−1 ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 000 2 000 3 000 时间序号 通行能力/(pcu·h−1 ) Webster BSLDA ABC ACO 图 10 TS1_1 和 TS1_2 交通场景下各项指标的比较 Fig. 10 Comparison of evaluation indicators in traffic scenes TS1_1 and TS1_2 Webster BSLDA ABC ACO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 50 100 时间序号 平均延误时间/s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 10 20 30 时间序号 平均延误时间/s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0.5 1.0 时间序号 平均停车次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0.5 1.0 时间序号 平均停车次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 000 2 000 3 000 时间序号 通行能力/(pcu·h−1 ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 000 2 000 时间序号 通行能力/(pcu·h−1 ) (a) TS2-1 场景下的平均延误时间 (b) TS2-2 场景下的平均延误时间 (c) TS2-1 场景下的平均停车次数 (d) TS2-2 场景下的平均停车次数 (e) TS2-1 场景下的通行能力 (f) TS2-2 场景下的通行能力 图 11 TS2_1 和 TS2_2 交通场景下各项指标的比较 Fig. 11 Comparison of evaluation indicators in traffic scenes TS2_1 and TS2_2 表 1~3 统计了 4 种配时方法在不同交通场 景下的整体效果。从表 1 中可以看出,与 Webster、ABC 和 ACO 相比,本文所提方法分别减少 平均延误时间 11.7%~20.3%、 7.6%~17.2%、6.7%~ 14.7%。从表 2 可以看出,与 Webster、ABC 和 ACO 相比,本文所提方法分别减少平均停车次数 4.5%~8.2%、6.2%~10.0%、2.2%~5.3%。从表 3 可以看出,与 Webster、ABC 和 ACO 相比,本文所 提方法分别提高通行量 4.3%~19.6%、9.8%~ 24.6%、4.5%~12.8%。 第 3 期 肖人彬,等:一种面向时间分配问题的群智能劳动分工新方法 ·445·
·446· 智能系统学报 第14卷 表1平均延误时间对比情况 为选择是由其激发-抑制比来决定的,而激发-抑 Table 1 Comparison of average time delay 制比会随着环境动态变化。行为柔性使得本文方 算法 TS1 1 TS1 2 TS2 1 TS2 2 法在不同的交通情况下都能实现有效的时间分 Webster 24.8869 18.182122.8729 17.3900 配,图10和图11的比较实验恰好证明了这一点。 BSLDA 20.7800 15.4766 18.2286 15.3611 约束条件下的分配问题都是在寻求一种最优 ABC 23.5781 17.5409 22.0256 16.6258 ACO 24.0710 17.2155 21.3662 16.4622 的资源配置方式,传统的求解以优化方法为主。 参照文献[6]对任务分配问题的分类,可将一般的 表2平均停车次数对比情况 分配问题分为确定环境下的静态分配问题和不确 Table 2 Comparison of average stops 次 定环境下的动态分配问题两类。确定环境下的静 算法 TS1 1 TS1_2 TS2 1 TS2 2 态分配问题或者近似静态分配问题(比如将m个 Webster 0.8168 0.7937 0.8075 0.7999 任务分配给n个主体的任务分配问题),适于采用 BSLDA 0.7621 0.7284 0.7490 0.7643 蚁群、蜂群、粒子群等算法,这类方法求解高效。 不确定环境下的动态分配问题(比如交通信号配 ABC 0.8224 0.8096 0.8185 0.8151 时中的动态时间分配问题),适于采用群智能劳动 ACO 0.8005 0.7692 0.7769 0.7813 分工方法,这类方法适应性强。 表3通行能力对比情况 4结束语 Table 3 Comparison of traffic capacity pcu/h 本文通过分析蜂群劳动分工和交通信号配时 算法 TSI 1 TS1_2 TS2 1 TS2_2 的特点,给出了劳动分工与信号配时之间的映射 Webster 2081.5 1815.5 1760.5 1625.1 关系;在BSLDA中设计了3种行为方式,并利用 BSLDA 2490.3 2012.2 2086.1 1694.3 激发剂和抑制剂的相互作用指导信号相位选择恰 ABC 2029.2 1752.3 1674.9 1543.3 当的行为完成时间分配,BSLDA在激发-抑制原 ACO 2207.0 1867.6 1919.0 1621.0 理下具有柔性特点;不同交通情景下的实验结果 表明,与其他方法相比,BSLDA展现出明显的有 3.4讨论分析 效性,适于求解不确定环境下的动态分配问题。 交通信号配时问题可以看成给各相位的车辆 后续工作将从机理分析和扩展研究两个方面 分配绿灯时间,使其分时通过交叉口。对于不同 展开:1)在BSLDA中,激发剂体现了一种正反馈 相位的车辆,既有因早中晚高峰等原因造成的规 作用,抑制剂体现了一种负反馈作用,当正反馈 律性变化,也有因汽车保有量增加等原因造成的 和负反馈达到平衡时,就实现了有效的时间分 非规律性变化。也就是说,各相位的车辆是动态 配,分析其反馈机理;2)将研究对象由单交叉口 变化的。这就要求分配给各相位车辆的绿灯时间 交通信号配时进一步扩展到干线交通信号配时和 不应一成不变,而应随着车流动态变化。因此, 区域交通信号配时。 交通信号配时问题属于动态时间分配问题。 群智能劳动分工的显著特点是:由于个体行 参考文献: 为柔性产生群体分工的可塑性,在行为柔性的作 [1]王喆,王红卫,唐攀,等.考虑资源分配的HTN规划方法 用下,个体能够根据环境变化调整所执行的任 及其应用[).管理科学学报,2013,16(3:53-60 务,从而使得族群在变动环境下仍能实现有效的 WANG Zhe,WANG Hongwei,TANG Pan,et al.HTN 任务分配。群智能劳动分工在动态环境下的分配 Planning method with resource allocation and its applica- 柔性是蜂群等社会性昆虫生态成功的首要原因, tion[J].Journal of management sciences in China,2013, 分配柔性这一特点也被众多学者用于求解动态环 16(3)53-60. 境下的分配问题,并取得了很好的效果。 [2]吕冰洋,郭庆旺.中国要素收入分配的测算经济研究 2012,47(10)y:27-40. 在蜂群劳动分工中,个体的行为柔性是通过 LU Bingyang,GUO Qingwang.Calculation on China's 激发-抑制原理实现的,本文所提出的方法继承 functional income distribution and redistribution[J.Eco- 了这种行为柔性的特点。在本文方法中,每个信 nomic research journal,2012,47(10):27-40. 号相位都有增加绿灯时间、减少绿灯时间和保持 [3]甘敏,彭辉,陈晓红.基于市场微结构模型和进化算法的 绿灯时间不变3种行为选择,信号相位的具体行 资产分配.系统工程学报,2011.26(3):314-321
表 1 平均延误时间对比情况 Table 1 Comparison of average time delay s 算法 TS1_1 TS1_2 TS2_1 TS2_2 Webster 24.886 9 18.182 1 22.872 9 17.390 0 BSLDA 20.780 0 15.476 6 18.228 6 15.361 1 ABC 23.578 1 17.540 9 22.025 6 16.625 8 ACO 24.071 0 17.215 5 21.366 2 16.462 2 表 2 平均停车次数对比情况 Table 2 Comparison of average stops 次 算法 TS1_1 TS1_2 TS2_1 TS2_2 Webster 0.816 8 0.793 7 0.807 5 0.799 9 BSLDA 0.762 1 0.728 4 0.749 0 0.764 3 ABC 0.822 4 0.809 6 0.818 5 0.815 1 ACO 0.800 5 0.769 2 0.776 9 0.781 3 表 3 通行能力对比情况 Table 3 Comparison of traffic capacity pcu/h 算法 TS1_1 TS1_2 TS2_1 TS2_2 Webster 2 081.5 1 815.5 1 760.5 1 625.1 BSLDA 2 490.3 2 012.2 2 086.1 1 694.3 ABC 2 029.2 1 752.3 1 674.9 1 543.3 ACO 2 207.0 1 867.6 1 919.0 1 621.0 3.4 讨论分析 交通信号配时问题可以看成给各相位的车辆 分配绿灯时间,使其分时通过交叉口。对于不同 相位的车辆,既有因早中晚高峰等原因造成的规 律性变化,也有因汽车保有量增加等原因造成的 非规律性变化。也就是说,各相位的车辆是动态 变化的。这就要求分配给各相位车辆的绿灯时间 不应一成不变,而应随着车流动态变化。因此, 交通信号配时问题属于动态时间分配问题。 群智能劳动分工的显著特点是:由于个体行 为柔性产生群体分工的可塑性,在行为柔性的作 用下,个体能够根据环境变化调整所执行的任 务,从而使得族群在变动环境下仍能实现有效的 任务分配。群智能劳动分工在动态环境下的分配 柔性是蜂群等社会性昆虫生态成功的首要原因, 分配柔性这一特点也被众多学者用于求解动态环 境下的分配问题,并取得了很好的效果。 在蜂群劳动分工中,个体的行为柔性是通过 激发–抑制原理实现的,本文所提出的方法继承 了这种行为柔性的特点。在本文方法中,每个信 号相位都有增加绿灯时间、减少绿灯时间和保持 绿灯时间不变 3 种行为选择,信号相位的具体行 为选择是由其激发–抑制比来决定的,而激发–抑 制比会随着环境动态变化。行为柔性使得本文方 法在不同的交通情况下都能实现有效的时间分 配,图 10 和图 11 的比较实验恰好证明了这一点。 约束条件下的分配问题都是在寻求一种最优 的资源配置方式,传统的求解以优化方法为主。 参照文献[6]对任务分配问题的分类,可将一般的 分配问题分为确定环境下的静态分配问题和不确 定环境下的动态分配问题两类。确定环境下的静 态分配问题或者近似静态分配问题 (比如将 m 个 任务分配给 n 个主体的任务分配问题),适于采用 蚁群、蜂群、粒子群等算法,这类方法求解高效。 不确定环境下的动态分配问题 (比如交通信号配 时中的动态时间分配问题),适于采用群智能劳动 分工方法,这类方法适应性强。 4 结束语 本文通过分析蜂群劳动分工和交通信号配时 的特点,给出了劳动分工与信号配时之间的映射 关系;在 BSLDA 中设计了 3 种行为方式,并利用 激发剂和抑制剂的相互作用指导信号相位选择恰 当的行为完成时间分配,BSLDA 在激发–抑制原 理下具有柔性特点;不同交通情景下的实验结果 表明,与其他方法相比,BSLDA 展现出明显的有 效性,适于求解不确定环境下的动态分配问题。 后续工作将从机理分析和扩展研究两个方面 展开:1) 在 BSLDA 中,激发剂体现了一种正反馈 作用,抑制剂体现了一种负反馈作用,当正反馈 和负反馈达到平衡时,就实现了有效的时间分 配,分析其反馈机理;2) 将研究对象由单交叉口 交通信号配时进一步扩展到干线交通信号配时和 区域交通信号配时。 参考文献: 王喆, 王红卫, 唐攀, 等. 考虑资源分配的 HTN 规划方法 及其应用[J]. 管理科学学报, 2013, 16(3): 53–60. WANG Zhe, WANG Hongwei, TANG Pan, et al. HTN Planning method with resource allocation and its application[J]. Journal of management sciences in China, 2013, 16(3): 53–60. [1] 吕冰洋, 郭庆旺. 中国要素收入分配的测算[J]. 经济研究, 2012, 47(10): 27–40. LÜ Bingyang, GUO Qingwang. Calculation on China’s functional income distribution and redistribution[J]. Economic research journal, 2012, 47(10): 27–40. [2] 甘敏, 彭辉, 陈晓红. 基于市场微结构模型和进化算法的 资产分配[J]. 系统工程学报, 2011, 26(3): 314–321. [3] ·446· 智 能 系 统 学 报 第 14 卷
第3期 肖人彬,等:一种面向时间分配问题的群智能劳动分工新方法 ·447· GAN Min,PENG Hui,CHEN Xiaohong.Asset allocation netics,part C:applications and reviews,2012,42(4): based on a market microstructure model and evolutionary 485-494 algorithms[J].Journal of systems engineering,2011,26(3): [12]肖人彬,陶振武.群集智能研究进展.管理科学学报 314-321. 2007,10(3):80-96. [4]万晓榆,冯小龙,王正强,等.基于能量采集异构蜂窝网 XIAO Renbin,TAO Zhenwu.Research progress of 络的功率分配算法研究J】.电子学报,2017,45(9): swarm intelligence[J.Journal of management sciences in 2308-2312. China.2007.10(3):80-96. WAN Xiaoyu,FENG Xiaolong,WANG Zhengqiang,et al. [13]ROBINSON G E.Regulation of division of labor in in- Power allocation algorithm for heterogeneous cellular net- sect societies[J].Annual review of entomology,1992,37: works based on energy harvesting[J].Acta electronica sin- 637-665. ica,2017.45(9):2308-2312 [14]XIAO Renbin,YU Tongyang,GONG Xiaoguang.Model- [5]张嵛,刘淑华.多机器人任务分配的研究与进展.智能 ing and simulation of ant colony's labor division with 系统学报,2008,3(2):115-120 constraints for task allocation of resilient supply chains[. ZHANG Yu,LIU Shuhua.Survey of multi-robot task al- International journal on artificial intelligence tools,2012. location[J].CAAI transactions on intelligent systems, 21(3:1240014. 2008,3(2:115-120 [15]DE LOPE J,MARAVALL D,QUINONEZ Y.Response [6]唐苏妍,朱一凡,李群,等.多Agent系统任务分配方法 threshold models and stochastic learning automata for 综述[J.系统工程与电子技术,2010,32(10):2155-2161. self-coordination of heterogeneous multi-task distribution TANG Suyan,ZHU Yifan,LI Qun,et al.Survey of task al- in multi-robot systems[J.Robotics and autonomous sys- location in multi agent systems[J].Systems engineering tems,2013,61(7):714-720. and electronics,2010,32(10):2155-2161 [16]LOW K H.LEOW W K.ANG M H JR.Autonomic mo- [7]王长军,徐琪,贾永基.单机下异构任务调度的解性质研 bile sensor network with self-coordinated task allocation 究管理科学学报,2015,18(7):70-81. and execution[J].IEEE transactions on systems,man,and WANG Changjun,XU Qi,JIA Yongji.Properties of solu- cybernetics,part C:applications and reviews,2006,36(3): tion for heterogeneous tasks scheduling on single 315-327. machine[J].Journal of management sciences in China, [17]KIM M H,BAIK H,LEE S.Response threshold model 2015,18(7):70-81. based UAV search planning and task allocation[J].Journ- [8]吴花平,黄敏,王兴伟.考虑多个RMAs的单机调度问题 al of intelligent and robotic systems,2014,75(3-4): [).控制与决策,2014,29(12):2253-2258. 625640. WU Huaping,HUANG Min,WANG Xingwei.Single-ma- [18]WANG Yingcong,XIAO Renbin,WANG Huimin.A chine scheduling problem with multi-RMAs[J].Control flexible labour division approach to the polygon packing and decision,2014,2912):2253-2258. problem based on space allocation[J].International journ- [9]姚荣涵,王筱雨,赵胜川,等.基于机动车比功率的单点 al of production research,2017,55(11):3025-3045. 信号配时优化模型).交通运输系统工程与信息,2015, [19)]肖人彬,王英聪.面向群体利益分配的蚁群劳动分工建 15(5):89-95. 模与仿真[).管理科学学报,2016,19(10):1-15。 YAO Ronghan,WANG Xiaoyu,ZHAO Shengchuan,et al. XIAO Renbin,WANG Yingcong.Modeling and simula- An optimization model of signal timing for isolated inter- tion of ant colony's labor division for interest allocation sections based on vehicle specific power[J].Journal of of social groups[J].Journal of management sciences in transportation systems engineering and information techno- China,2016,19(10)y:1-15 1ogy,2015,15(5):89-95. [20]杨佩昆,吴兵.交通管理与控制M).北京:人民交通出 [10们孙棣华,杨陈成,廖孝勇,等.基于公交GPS数据的交叉 版社,2004 口信号配时参数估计[.控制与决策,2018,33(4): [21]HE Jiajia,HOU Zaien.Ant colony algorithm for traffic 724730. signal timing optimization[J].Advances in engineering SUN Dihua,YANG Chencheng,LIAO Xiaoyong,et al. software,2012,43(1):1418. Signal timing estimation for intersections using bus GPS [22]刘爽,岳芳,郭彦东,等.基于模式搜索算法的交叉口信 data[J].Control and decision,2018,33(4):724-730. 号配时优化研究).交通运输系统工程与信息,2011, [11]ZHAO Dongbin,DAI Yujie,ZHANG Zhen.Computa- 11(S129-35. tional intelligence in urban traffic signal control:a LIU Shuang,YUE Fang,GUO Yandong,et al.Optimiza- survey[J].IEEE transactions on systems,man,and cyber- tion research on signal timing for urban intersections
GAN Min, PENG Hui, CHEN Xiaohong. Asset allocation based on a market microstructure model and evolutionary algorithms[J]. Journal of systems engineering, 2011, 26(3): 314–321. 万晓榆, 冯小龙, 王正强, 等. 基于能量采集异构蜂窝网 络的功率分配算法研究[J]. 电子学报, 2017, 45(9): 2308–2312. WAN Xiaoyu, FENG Xiaolong, WANG Zhengqiang, et al. Power allocation algorithm for heterogeneous cellular networks based on energy harvesting[J]. Acta electronica sinica, 2017, 45(9): 2308–2312. [4] 张嵛, 刘淑华. 多机器人任务分配的研究与进展[J]. 智能 系统学报, 2008, 3(2): 115–120. ZHANG Yu, LIU Shuhua. Survey of multi-robot task allocation[J]. CAAI transactions on intelligent systems, 2008, 3(2): 115–120. [5] 唐苏妍, 朱一凡, 李群, 等. 多 Agent 系统任务分配方法 综述[J]. 系统工程与电子技术, 2010, 32(10): 2155–2161. TANG Suyan, ZHU Yifan, LI Qun, et al. Survey of task allocation in multi agent systems[J]. Systems engineering and electronics, 2010, 32(10): 2155–2161. [6] 王长军, 徐琪, 贾永基. 单机下异构任务调度的解性质研 究[J]. 管理科学学报, 2015, 18(7): 70–81. WANG Changjun, XU Qi, JIA Yongji. Properties of solution for heterogeneous tasks scheduling on single machine[J]. Journal of management sciences in China, 2015, 18(7): 70–81. [7] 吴花平, 黄敏, 王兴伟. 考虑多个 RMAs 的单机调度问题 [J]. 控制与决策, 2014, 29(12): 2253–2258. WU Huaping, HUANG Min, WANG Xingwei. Single-machine scheduling problem with multi-RMAs[J]. Control and decision, 2014, 29(12): 2253–2258. [8] 姚荣涵, 王筱雨, 赵胜川, 等. 基于机动车比功率的单点 信号配时优化模型[J]. 交通运输系统工程与信息, 2015, 15(5): 89–95. YAO Ronghan, WANG Xiaoyu, ZHAO Shengchuan, et al. An optimization model of signal timing for isolated intersections based on vehicle specific power[J]. Journal of transportation systems engineering and information technology, 2015, 15(5): 89–95. [9] 孙棣华, 杨陈成, 廖孝勇, 等. 基于公交 GPS 数据的交叉 口信号配时参数估计[J]. 控制与决策, 2018, 33(4): 724–730. SUN Dihua, YANG Chencheng, LIAO Xiaoyong, et al. Signal timing estimation for intersections using bus GPS data[J]. Control and decision, 2018, 33(4): 724–730. [10] ZHAO Dongbin, DAI Yujie, ZHANG Zhen. Computational intelligence in urban traffic signal control: a survey[J]. IEEE transactions on systems, man, and cyber- [11] netics, part C: applications and reviews, 2012, 42(4): 485–494. 肖人彬, 陶振武. 群集智能研究进展[J]. 管理科学学报, 2007, 10(3): 80–96. XIAO Renbin, TAO Zhenwu. Research progress of swarm intelligence[J]. Journal of management sciences in China, 2007, 10(3): 80–96. [12] ROBINSON G E. Regulation of division of labor in insect societies[J]. Annual review of entomology, 1992, 37: 637–665. [13] XIAO Renbin, YU Tongyang, GONG Xiaoguang. Modeling and simulation of ant colony’s labor division with constraints for task allocation of resilient supply chains[J]. International journal on artificial intelligence tools, 2012, 21(3): 1240014. [14] DE LOPE J, MARAVALL D, QUIÑONEZ Y. Response threshold models and stochastic learning automata for self-coordination of heterogeneous multi-task distribution in multi-robot systems[J]. Robotics and autonomous systems, 2013, 61(7): 714–720. [15] LOW K H, LEOW W K, ANG M H JR. Autonomic mobile sensor network with self-coordinated task allocation and execution[J]. IEEE transactions on systems, man, and cybernetics, part C: applications and reviews, 2006, 36(3): 315–327. [16] KIM M H, BAIK H, LEE S. Response threshold model based UAV search planning and task allocation[J]. Journal of intelligent and robotic systems, 2014, 75(3-4): 625–640. [17] WANG Yingcong, XIAO Renbin, WANG Huimin. A flexible labour division approach to the polygon packing problem based on space allocation[J]. International journal of production research, 2017, 55(11): 3025–3045. [18] 肖人彬, 王英聪. 面向群体利益分配的蚁群劳动分工建 模与仿真[J]. 管理科学学报, 2016, 19(10): 1–15. XIAO Renbin, WANG Yingcong. Modeling and simulation of ant colony’s labor division for interest allocation of social groups[J]. Journal of management sciences in China, 2016, 19(10): 1–15. [19] 杨佩昆, 吴兵. 交通管理与控制[M]. 北京: 人民交通出 版社, 2004. [20] HE Jiajia, HOU Zaien. Ant colony algorithm for traffic signal timing optimization[J]. Advances in engineering software, 2012, 43(1): 14–18. [21] 刘爽, 岳芳, 郭彦东, 等. 基于模式搜索算法的交叉口信 号配时优化研究[J]. 交通运输系统工程与信息, 2011, 11(S1): 29–35. LIU Shuang, YUE Fang, GUO Yandong, et al. Optimization research on signal timing for urban intersections [22] 第 3 期 肖人彬,等:一种面向时间分配问题的群智能劳动分工新方法 ·447·