胡 亮，肖人彬，王英聰

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

0 引言

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

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

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

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

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

1.1 蜂群勞動(dòng)分工現(xiàn)象

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

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

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

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

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

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

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

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

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

結(jié)合以上特點(diǎn)，給出AILD模型的描述如下：

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

(1)

(2)

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

個(gè)體i的抑制劑hi隨時(shí)間變化，其表達(dá)式如下：

(3)

(4)

從上述公式可以看出，若t時(shí)刻蜂群的覓食蜂數(shù)量突然減少，會(huì)導(dǎo)致蜂群整體的激發(fā)劑以及抑制劑總含量降低，同時(shí)個(gè)體i的激發(fā)劑與抑制劑含量未改變。根據(jù)式(3)、(4)可知，t+1時(shí)刻個(gè)體i的抑制劑含量減少。根據(jù)式(1)、(2)可知，t+1時(shí)刻個(gè)體i的激發(fā)劑含量增加。綜上，個(gè)體i的激發(fā)抑制比上升，會(huì)加速向覓食蜂的轉(zhuǎn)化。同理，若t時(shí)刻覓食蜂數(shù)量過多，蜂群整體的激發(fā)劑以及抑制劑總含量增加。由上述公式可知，t+1時(shí)刻個(gè)體i的抑制劑含量增加，激發(fā)劑含量降低，激發(fā)抑制比降低。個(gè)體i的發(fā)育被抑制，由巢內(nèi)到巢外的轉(zhuǎn)化速度減慢，甚至?xí)沟靡捠撤渲匦禄氐匠矁?nèi)。通過上述分析可知，蜂群在激發(fā)-抑制勞動(dòng)分工作用下處于一種動(dòng)態(tài)平衡狀態(tài)。

2 交通信號(hào)配時(shí)問題應(yīng)用

群智能勞動(dòng)分工提供了一種柔性任務(wù)分配方式，對(duì)動(dòng)態(tài)環(huán)境下的分配問題求解具有重要啟發(fā)意義。交通信號(hào)配時(shí)旨在為來自不同方向的交通流分配綠燈時(shí)間，使其分時(shí)通過交叉口。交通信號(hào)配時(shí)是一種典型的時(shí)間分配問題，并且城市交通流具有較高的時(shí)空復(fù)雜性。據(jù)此，以交通信號(hào)配時(shí)問題為例來驗(yàn)證AILD模型的有效性。

2.1 交通信號(hào)配時(shí)問題簡介

在確保交通安全的前提下，交通信號(hào)配時(shí)的主要目的在于最大限度地提高交叉口的使用效率。一方面要合理利用道路交通設(shè)施的資源，提高道路的使用效率，使得道路通行能力最大化；另一方面要以人為本，根據(jù)人的需求，讓延誤時(shí)間和停車次數(shù)盡可能的小。因此，本文選取延誤時(shí)間、停車次數(shù)和通行能力作為衡量指標(biāo)，其中延誤時(shí)間和停車次數(shù)體現(xiàn)了道路使用者的利益，越小越好；通行能力體現(xiàn)了道路的使用效率，越大越好。

第i相位的車輛延誤時(shí)間(s)[26]為

(5)

第i相位的車輛停車次數(shù)(次)[26]為

(6)

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

Qi=si×xi/c

(7)

其中，c為信號(hào)周期時(shí)長(s)，si、yi、li、qi、(i、xi分別為第i相位的飽和流量(pcu/h)、流量比、損失時(shí)間(s)、車流量(pcu/h)、綠信比和綠燈時(shí)間(s)。

據(jù)此得到一個(gè)周期內(nèi)交叉口的車輛平均延誤時(shí)間(s)為

(8)

一個(gè)周期內(nèi)交叉口的車輛平均停車次數(shù)(次)為

(9)

一個(gè)周期內(nèi)交叉口的通行能力(pcu/h)為

(10)

其中，n為相位總數(shù)。

2.2 激發(fā)-抑制勞動(dòng)分工信號(hào)配時(shí)算法

2.2.1 算法原理

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

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

2.2.2 算法步驟

激發(fā)-抑制勞動(dòng)分工信號(hào)配時(shí)算法AILD-ST的實(shí)現(xiàn)步驟如圖4所示，具體說明如下：

圖3 蜂群勞動(dòng)分工與交通信號(hào)配時(shí)之間的映射關(guān)系Fig.3 The mapping relationship between the labor division of bee colony and the timing of traffic signals

圖4 AILD-ST算法計(jì)算過程Fig.4 AILD-ST algorithm calculation process

步驟1：初始化激發(fā)劑、抑制劑等參數(shù)；

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

步驟3：迭代次數(shù)初始值設(shè)定為1；

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

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

步驟8：迭代次數(shù)加1；

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

步驟10：輸出最終進(jìn)化解。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)概述與參數(shù)設(shè)置

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

圖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é)采用兩種典型的算法進(jìn)行對(duì)比分析，一種是傳統(tǒng)的Webster算法，另一種是群智能優(yōu)化算法——蟻群算法和蜂群算法，它們求解的優(yōu)化模型按照文獻(xiàn)[26]給出：

(11)

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

3.2 實(shí)驗(yàn)結(jié)果

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

圖7 實(shí)際交通場(chǎng)景連續(xù)一天各項(xiàng)指標(biāo)的比較Fig.7 Comparison of evaluation indicators in actual traffic scenes one day in a row

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

表1 AILD-ST算法與Webster算法、蟻群算法、蜂群算法的信號(hào)配時(shí)性能比較Tab.1 Comparison of signal timing performance (AILD-ST algorithm, webster colony algorithm, ant colony algorithm and bee algorithm)

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

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

3.4 擴(kuò)展對(duì)比實(shí)驗(yàn)

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

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

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

3.5 算法分析

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

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

1)方式一

2)方式二

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

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

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

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

4 結(jié)論

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

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

2)運(yùn)行高效：典型的優(yōu)化算法為了得到較好的結(jié)果，需要對(duì)解空間進(jìn)行大規(guī)模的搜索，算法開銷大，導(dǎo)致系統(tǒng)運(yùn)行時(shí)間長，而本文設(shè)計(jì)的AILD-ST算法原理簡單，主要采用低級(jí)運(yùn)算結(jié)構(gòu)，運(yùn)行效率高。

3)適應(yīng)性強(qiáng)：本文從生物學(xué)現(xiàn)象出發(fā)，根據(jù)蜂群勞動(dòng)分工的特點(diǎn)提出激發(fā)-抑制勞動(dòng)分工模型。AILD-ST可以部署于不同路段，且對(duì)不同時(shí)段的時(shí)變交通流模式均具有優(yōu)于現(xiàn)有算法的良好求解效果。

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