蜂群激發(fā)抑制算法及其在交通信號配時中的應用

胡 亮，肖人彬，王英聰

(1.華中科技大學人工智能與自動化學院，武漢 430074；2.鄭州輕工業(yè)大學電氣信息工程學院，鄭州 450002)

0 引言

現實生活中的許多問題都可以抽象為分配問題(比如時間分配、空間分配和資源分配等)，這些問題往往具有動態(tài)復雜性。以十字路口交通信號燈的綠燈時間分配為例，來自不同方向的車流量始終是動態(tài)變化的。對這種具有復雜性的動態(tài)分配問題，要求處理算法具有很強的智能性與適應性。目前，群智能算法在此領域已經取得了不錯的成效。

群智能算法以蟻群優(yōu)化和粒子群優(yōu)化為典型代表[1]，相關研究主要集中在組合優(yōu)化和函數優(yōu)化等領域。這些優(yōu)化算法在求解動態(tài)分配問題時，往往只在一些固定場景中有效。當環(huán)境變量與輸入變量的變化范圍很大時，難以保證每次輸出結果的效能，即柔性較差。此外，這些優(yōu)化算法本身還存在著收斂速度慢、容易陷入局部最優(yōu)等問題。

上述研究主要集中在蟻群的刺激-響應勞動分工機制上，而對蜂群的激發(fā)-抑制勞動分工機制的研究相對較少。在已有群智能勞動分工的研究基礎上，針對動態(tài)分配問題，本文提出一種基于蜂群的激發(fā)-抑制勞動分工模型(AILD)。為了驗證AILD模型的有效性，選取了一個典型的時間分配問題——交通信號配時，設計了相應的激發(fā)-抑制勞動分工信號配時算法AILD-ST。采用AILD-ST算法對實際交通流數據進行了交通信號配時求解，并與Webster算法、蟻群算法和蜂群算法進行了對比，結果顯示AILD-ST算法的實用性和有效性。

本文安排如下，第1節(jié)討論蜂群激發(fā)-抑制原理并設計出激發(fā)-抑制勞動分工模型，第2節(jié)將激發(fā)-抑制勞動分工模型應用到交通信號配時問題中并提出激發(fā)-抑制勞動分工信號配時算法，第3節(jié)是將激發(fā)-抑制勞動分工信號配時算法應用于交通配時問題的仿真實驗，第4節(jié)是算法的機理和性能分析，第5節(jié)是對全文工作的總結。

1 激發(fā)-抑制勞動分工模型

1.1 蜂群勞動分工現象

在社會性昆蟲中，族群需要完成各種各樣的任務，如哺育幼蟲、尋找食物、維護巢穴、抵御外敵等。在任何時刻，族群都能并行地執(zhí)行這些任務，這種現象叫做勞動分工。群智能勞動分工主要有兩種模式[13]：一種是以蟻群為代表的形態(tài)行為多型，其中個體執(zhí)行的任務與其大小和體型等有關；另一種是以蜂群為代表的時間行為多型，其中個體執(zhí)行的任務與其生理年齡等有關。本文主要關注蜂群的勞動分工，下面對其進行簡要介紹。

圖1 蜜蜂的行為發(fā)育過程Fig.1 Behavioral development of bees

1.2 激發(fā)-抑制原理

Huang等[16]在研究蜂群的勞動分工時，提出了一種激發(fā)-抑制原理，該原理認為蜂群的勞動分工體現在它們的行為發(fā)育上，而蜂群的行為發(fā)育是由激發(fā)劑和抑制劑共同決定的，且二者具有耦合關系，即年長的蜜蜂體內激發(fā)劑和抑制劑的含量比年幼蜜蜂多。其原理可以簡要描述如下：激發(fā)劑和抑制劑共同維持著蜜蜂在不同任務上的動態(tài)分配平衡。其中保幼激素被認為是蜜蜂的一種激發(fā)劑，促進個體行為發(fā)育，使其工作從巢內向巢穴外轉移。個體之間進行交互時會傳遞抑制劑，對其保幼激素和行為發(fā)育起阻礙作用。比如，當覓食者減少時，抑制劑會減弱，促進激發(fā)劑增加，巢穴內的個體會加速發(fā)育成覓食者；當覓食者較多時，抑制劑會變強，抑制激發(fā)劑的產生，巢穴內個體的發(fā)育會被延遲，甚至一些覓食者會返回巢穴內工作。

圖2 激發(fā)-抑制原理中個體間的交互方式Fig.2 The interaction between individuals in the principle of activating and inhibition

基于上述激發(fā)-抑制原理，Naug等人[17]建立了一個計算仿真模型，該模型進一步描述了激發(fā)-抑制原理中個體間的交互方式，如圖2所示。蜂群中每個個體都包含一個激發(fā)劑A(Activator)和兩個抑制劑I1和I2(Inhibitor)。A是個體內在的激發(fā)劑，對個體自身的行為發(fā)育起促進作用。I1是個體內在的抑制劑，不會阻礙自身的行為發(fā)育，但在個體交互過程中會對其他個體的行為發(fā)育產生抑制作用。I2是個體在交互作用中得到的外在抑制劑，會阻礙自身的行為發(fā)育。最終，蜜蜂體內的激發(fā)劑A和抑制劑I2的相對水平(A/I2)決定個體的行為發(fā)育過程是正常速度還是被加速、延遲或逆轉。

1.3 激發(fā)-抑制模型

根據蜂群的群體性特點，參考Gierer等人的工作[18]，以及激發(fā)劑對細胞生長的促進作用，抑制劑對細胞生長的抑制作用，激發(fā)劑與抑制劑之間的相互作用反饋，同時考慮到激發(fā)-抑制本身是一個具有時變不確定性、自學習性和對外部系統具有高適應性的互動過程，下面提出基于蜂群勞動分工激發(fā)-抑制原理的激發(fā)-抑制勞動分工模型(AILD)。

每個蜜蜂要和群體進行交互，蜜蜂和蜂群之間的交互是通過激發(fā)劑和抑制劑實現的。具體的，激發(fā)劑(用a表示)促進個體發(fā)育成長，抑制劑(用h表示)阻礙個體發(fā)育成長，甚至產生逆生長的作用。激發(fā)劑的激發(fā)特性通過二次函數a2表現出來，同時考慮到抑制劑對激發(fā)劑有抑制作用(抑制劑越大，激發(fā)劑的增量越少；抑制劑越小，激發(fā)劑的增量越大)，通過反函數a2/h來表現抑制劑對激發(fā)劑增長的抑制作用。除了蜂群本身激發(fā)劑和抑制劑的相互作用，還需要考慮環(huán)境因素(食物變化，天氣變化，天敵等)[19,20]對蜂群的影響以及激發(fā)劑和抑制劑自身對時間變化的消散作用。

結合以上特點，給出AILD模型的描述如下：

個體i的激發(fā)劑ai隨時間變化，其表達式如下：

(1)

(2)

式中，hj(t)表示t時刻個體j體內的抑制劑含量，c表示激發(fā)系數，ρ表示群體密度，uaai表示激發(fā)劑的一階衰減項，ρaρ表示環(huán)境產生的激發(fā)劑對個體的影響，i≠j說明同一個個體內的激發(fā)劑與抑制劑不存在直接作用關系，個體只能與群體進行交互。

個體i的抑制劑hi隨時間變化，其表達式如下：

(3)

(4)

從上述公式可以看出，若t時刻蜂群的覓食蜂數量突然減少，會導致蜂群整體的激發(fā)劑以及抑制劑總含量降低，同時個體i的激發(fā)劑與抑制劑含量未改變。根據式(3)、(4)可知，t+1時刻個體i的抑制劑含量減少。根據式(1)、(2)可知，t+1時刻個體i的激發(fā)劑含量增加。綜上，個體i的激發(fā)抑制比上升，會加速向覓食蜂的轉化。同理，若t時刻覓食蜂數量過多，蜂群整體的激發(fā)劑以及抑制劑總含量增加。由上述公式可知，t+1時刻個體i的抑制劑含量增加，激發(fā)劑含量降低，激發(fā)抑制比降低。個體i的發(fā)育被抑制，由巢內到巢外的轉化速度減慢，甚至會使得覓食蜂重新回到巢內。通過上述分析可知，蜂群在激發(fā)-抑制勞動分工作用下處于一種動態(tài)平衡狀態(tài)。

2 交通信號配時問題應用

群智能勞動分工提供了一種柔性任務分配方式，對動態(tài)環(huán)境下的分配問題求解具有重要啟發(fā)意義。交通信號配時旨在為來自不同方向的交通流分配綠燈時間，使其分時通過交叉口。交通信號配時是一種典型的時間分配問題，并且城市交通流具有較高的時空復雜性。據此，以交通信號配時問題為例來驗證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 激發(fā)-抑制勞動分工信號配時算法

2.2.1 算法原理

在蜂群勞動分工中，不同的蜜蜂執(zhí)行不同的任務完成任務分配。在交通信號配時中，不同的信號相位占據不同的綠燈時間完成時間分配。圖3給出了蜂群勞動分工與交通信號配時之間的映射關系，在此基礎上交通信號配時問題的求解準則為：某一信號相位的延誤時間越長，則其激發(fā)劑越大，在激發(fā)-抑制原理作用下，該相位的綠燈時間將會增加；其它信號相位的停車次數越大，則該相位感知到的抑制劑越大，在激發(fā)-抑制原理作用下，該相位的綠燈時間將會減小。

通過激發(fā)劑和抑制劑的變化，AILD-ST自適應地調整各信號相位的綠燈時間，從而完成時間分配。AILD-ST采用進化的方式進行求解，不需要建立優(yōu)化模型，具有原理簡明、易于實現等特點。

2.2.2 算法步驟

激發(fā)-抑制勞動分工信號配時算法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：初始化激發(fā)劑、抑制劑等參數；

步驟2：根據車流量信息和Webster算法得到初始的各信號相位綠燈時間x1、x2、x3、x4，各信號相位平均延誤時間D1、D2、D3、D4，以及各信號相位停車次數H1、H2、H3、H4；

步驟3：迭代次數初始值設定為1；

步驟5：種群進化，根據公式(1)-(4)更新激發(fā)劑和抑制劑；

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

步驟8：迭代次數加1；

步驟9：若迭代次數小于N，則轉至步驟4繼續(xù)進化。

步驟10：輸出最終進化解。

3 仿真實驗

3.1 實驗概述與參數設置

本實驗使用的交通數據來自于2014中國“云上貴州”大數據商業(yè)模式大賽——智能交通算法大挑戰(zhàn)。中國“云上貴州”大數據商業(yè)模式大賽利用貴州省貴陽市南明區(qū)交通流量數據(包括公交車GPS信息、出租車GPS信息、高德公司普通市民導航數據等)，在充分脫敏與保護用戶隱私的前提下，模擬貴陽市整體的十字路口交通情況。圖5是貴陽市南明區(qū)部分區(qū)域的簡化道路與紅綠燈位置圖，其中紅綠燈用tli來表示。選取交通數據文件“flow0901”中紅綠燈ID為“tl18”的6:00～20:00時間段的交通數據進行處理，如圖6所示。這一時間段內車流量變化較明顯，對于評估信號配時方法的效果具有較強的說服力。

圖5 貴陽市南明區(qū)部分區(qū)域路口簡化示意圖Fig.5 Simplified schematic diagram of intersections in some areas of Nanming District, Guiyang City

圖6 紅綠燈“tl18”車流量Fig.6 Traffic light "tl18" traffic

本節(jié)采用兩種典型的算法進行對比分析，一種是傳統的Webster算法，另一種是群智能優(yōu)化算法——蟻群算法和蜂群算法，它們求解的優(yōu)化模型按照文獻[26]給出：

(11)

實驗中所涉及的參數設置如下：假設車輛在交叉口處直行、左轉和右轉的比例分別為60%、20%和20%，相應的直行車道、左轉車道和右轉車道的飽和流量分別為1 500pcu/h、1 200pcu/h和1 200pcu/h。交叉口綠燈間隔時間為4s，黃燈時間為3s，啟動損失時間為3s，最短綠燈時間為15s，最長綠燈時間為90s。激發(fā)系數c為0.2，激發(fā)劑產生速率為3，抑制劑產生速率為5，源密度為1，激發(fā)劑的衰減系數為0.26，激發(fā)劑的衰減系數為15，步長k為4，最大迭代次數N為100。實驗環(huán)境說明如下：本文采用Matlab語言編程實現AILD-ST算法，并在CPU主頻為3.6GHz、內存為4 GB的PC機上進行實驗。

3.2 實驗結果

為了檢驗AILD-ST算法的性能，選取蜂群算法、蟻群算法和Webster算法進行對比實驗。求解時，先用Webster方法估計初始周期，然后利用等飽和比的方法計算各相位的大致信號配時，再用AILD-ST進行分配求解。計算統計一天的結果見表1，表1中D為車輛一天平均延誤時間；H為車輛一天平均停車次數；Q為道路平均每小時通行能力。本實驗的仿真結果如圖7所示。

圖7 實際交通場景連續(xù)一天各項指標的比較Fig.7 Comparison of evaluation indicators in actual traffic scenes one day in a row

3.3 實驗結果分析

由表1的計算結果可知，AILD-ST算法在延誤時間、平均停車次數以及通行能力這三組測試實驗中都優(yōu)于Webster算法、蜂群算法和蟻群算法。其中在延誤時間方面，本文算法相對其它算法能減少平均延誤時間7.1%、9.3%和11.3%；在停車次數方面，本文算法相對其它算法能減少平均停車次數2.7%、3.5%和3.3%；在通行能力方面，本文算法相對其它算法能增大通行能力21.5%、15.3%和5.7%。

通過觀察圖6可以看出，交通路口的流率比從早上六點開始不斷上升，一直到早上九點的時候到達峰值，然后開始一直下降。通過觀察圖7可以看出，隨著交通路口流率比的增加，平均停車次數不斷增加，通行能力先增加后下降，延誤時間先增加后下降。從而使得控制信號目標在路口閑散狀態(tài)下更加側重減少延誤時間和停車次數，而在擁堵狀態(tài)下則更加側重減少延誤時間和提高通行能力。這種方式可以實現不同交通狀態(tài)下交通路口管理效能最大化。

表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算法繼承了蜂群勞動分工的特點，以任務動態(tài)分配的方式完成時間動態(tài)分配，根據實時變化的車流量動態(tài)調節(jié)各個相位的綠燈時間，使其增加、不變或者減少，從而到達全局最優(yōu)。相比Webster算法、蜂群算法和蟻群算法，AILD-ST算法優(yōu)化性能更佳，說明對單路口控制實例，本文設計的AILD-ST算法具有好的應用效果，可以根據車流量動態(tài)調節(jié)綠燈時間，能夠在一定程度上緩解交通壓力，提升道路的流暢度。

綜合來看，AILD-ST算法能夠在高峰流量期間提高道路的通行能力，進而滿足高峰流量期間的需求；而平峰流量期間，在保證車輛平均延誤時間和平均停車次數較低的情況下，能提高道路通行能力。因此，AILD-ST算法優(yōu)能夠在一定程度上緩解道路交叉口的交通壓力，提高道路交叉口的利用率。

3.4 擴展對比實驗

為了進一步說明AILD-ST算法具有應對典型路況的能力，本節(jié)選取兩種典型的交通環(huán)境(高峰和平峰)進行對比實驗。在仿真實驗中，使用了文獻[26]中的測試數據。這些數據來源于典型的四相位道路交叉口，包含了高峰期間的車流量數據與平峰期間的車流量數據，所含信息較為全面，具有一定的說服力和代表性。AILD-ST算法的計算結果與蟻群算法、Webster算法的計算結果(由文獻[26]給出)見表2，表2中D為車輛平均延誤時間，H為車輛平均停車次數，Q為道路通行能力，c為周期；X1、X2、X3、X4分別為四個相位的有效綠燈時間。

從表2中3種算法的計算結果可以看出：1)高峰流量期間，AILD-ST算法在車輛平均延誤時間這一指標上相對于其他兩種算法較差，但在車輛平均停車次數和通行能力這兩個指標上相對于其他兩種算法更優(yōu)；而在高峰流量期間，一般注重于提高道路的通行能力。2)平峰流量期間，AILD-ST算法在道路通行能力車輛這一指標上相對于其他兩種算法較差，但在平均延誤時間和平均停車次數上與其他兩種算法相近或者更低。綜合來看，AILD-ST算法能夠在高峰流量期間提高道路的通行能力，進而滿足高峰流量期間的需求；在平峰流量期間，AILD-ST算法在保證車輛平均延誤時間和平均停車次數較低的情況下，能夠滿足平峰車輛順暢通行的需求。因此，AILD-ST算法優(yōu)于經典的Webster算法和典型的智能優(yōu)化算法——蟻群算法，能夠在一定程度上緩解道路交叉口的交通壓力，提高道路交叉口的利用率。

表2 AILD-ST算法與蟻群算法、Webster算法的信號配時性能比較Tab.2 Comparison of signal timing performance (AILD-ST algorithm, ant colony algorithm and webster colony algorithm)

3.5 算法分析

AILD算法的建模對象為蜂群中的蜜蜂個體，其將蜜蜂個體的激發(fā)劑、抑制劑與實際問題的參數抽象關聯在一起(見AILD-ST算法案例)，在建模過程中不考慮整體的因素。下面從模型的個體入手分析算法的機理。

對于第i個個體，其體內激發(fā)劑與抑制劑的含量如公式(1)、(3)所示。在個體成長過程中，激發(fā)劑與抑制劑的相對含量——激發(fā)抑制比決定了個體是否加快、延緩或者顛倒自身的發(fā)育。激發(fā)抑制比的變化取決于以下兩種方式：

1)方式一

2)方式二

由上述兩種激發(fā)劑與抑制劑的變化方式可知，蜜蜂個體i響應外界變化的規(guī)律如圖8和圖9所示：參考AILD-ST算法，將交通問題的參數映射為t時刻蜜蜂個體的激發(fā)劑與抑制劑，相當于外界對蜂群的輸入。蜂群接收此值作為勞動分工的初始值，經過處理后，蜜蜂對外界做出反應，以滿足族群勞動分工的要求。此處理過程即依據上述兩種方式，計算得到t+1時刻激發(fā)劑、抑制劑的含量，響應的結果即依據t+1時刻激發(fā)抑制比確定生理年齡變化方向。同理，再將新的結果作為下一次的計算輸入，循環(huán)處理，多次優(yōu)化，直到蜜蜂個體產生的分工結果契合種群整體要求。

具體說來，交通問題的延遲時間D與停車次數H分別為激發(fā)劑與抑制劑，四個相位對應種群數量為4的蜂群。當某一相位的是延遲時間增加時，即該相位的t時刻激發(fā)劑增加，參照圖8和圖9，該變化會使該相位激發(fā)劑在t+1時刻增加，同時對于其他相位t+1時刻的抑制劑有促進作用，其結果是本相位綠燈時間增多，其他相位綠燈時間減少，進而使各相位延遲時間D與停車次數H回到相對平衡的狀態(tài)，形成一次優(yōu)化。同理可以推斷該相位延遲時間減小、停車次數增加以及停車次數減少三種情形下的各相位綠燈時間變化，其結果也是合理的。蜜蜂個體(單個相位)的激發(fā)劑抑制劑變化是與群體內其它蜜蜂(其它相位)息息相關的，所以蜜蜂個體能在與其它蜜蜂交互時得到其它蜜蜂的狀態(tài)信息(見式(2)及式(4))，當交互次數足夠多時，蜜蜂所得到的狀態(tài)信息的集合就可以反映種群狀態(tài)，個體也就間接了解了種群信息，并據此做出判斷。因此，蜜蜂總是可以在外界條件的變化下實現合理的種群任務分配，顯示出強大的群體智能，這也是交通配時實驗總能得到優(yōu)化解的原因。

圖8 蜜蜂個體i的發(fā)育促進因素Fig.8 Developmental factors of bee individuals i

圖9 蜜蜂個體i的發(fā)育抑制因素Fig.9 Inhibitory factors of development of bee individuals i

4 結論

本文針對動態(tài)環(huán)境下的交通信號配時問題，分析了蜂群激發(fā)-抑制勞動分工模型和交通信號配時問題的相似性，建立了二者之間的映射關系，提出了一種面向交通信號配時問題的激發(fā)-抑制勞動分工信號配時算法(AILD-ST)。結果表明，AILD-ST算法能夠很好地處理交通配時這類復雜問題。將AILD-ST算法與典型的智能優(yōu)化算法(如蟻群算法、蜂群算法)相比較，其優(yōu)越性主要體現在以下幾個方面：

1)建模簡單：傳統的交通配時優(yōu)化算法需要針對某一具體的交通流模式設計精確的數理模型，而AILD-ST算法將交通配時問題映射為動態(tài)分配問題，映射關系簡單，配時問題直接與分工模型對應，建模過程被大大簡化。

2)運行高效：典型的優(yōu)化算法為了得到較好的結果，需要對解空間進行大規(guī)模的搜索，算法開銷大，導致系統運行時間長，而本文設計的AILD-ST算法原理簡單，主要采用低級運算結構，運行效率高。

3)適應性強：本文從生物學現象出發(fā)，根據蜂群勞動分工的特點提出激發(fā)-抑制勞動分工模型。AILD-ST可以部署于不同路段，且對不同時段的時變交通流模式均具有優(yōu)于現有算法的良好求解效果。

AILD模型是一種有效的動態(tài)自組織任務分配模型，該模型為解決十字交叉口交通信號配時問題以及其他的任務分配問題提供了一種新穎有效的解決思路。下一步的研究重點是深入分析AILD模型的激發(fā)-抑制機理(激發(fā)劑相當于正反饋作用，內部抑制劑和外部抑制劑相當于負反饋作用)，提出更加方便、實用的激發(fā)抑制模型，進一步提高AILD-ST算法的性能。