摘 要： 針對(duì)目前交叉口信號(hào)配時(shí)優(yōu)化目標(biāo)單一、綜合運(yùn)行效率不高的問題，提出一種交叉口信號(hào)配時(shí)多目標(biāo)優(yōu)化方法。考慮綠燈時(shí)間、周期長度和飽和度等約束條件，通過加權(quán)系數(shù)法定義代價(jià)函數(shù)，使交叉口的延誤時(shí)間、停車次數(shù)和通行能力在某種程度上達(dá)到最優(yōu)?；诿庖呖寺∷惴ㄔ谔幚矶嗄繕?biāo)問題中具有最優(yōu)解分布寬廣性、均勻性好等特點(diǎn)，引入環(huán)境變異算子，提出環(huán)境變異免疫克隆算法對(duì)模型求解，增強(qiáng)了算法的全局搜索能力，提高了解的質(zhì)量。仿真結(jié)果表明，與傳統(tǒng)配時(shí)方法和改進(jìn)粒子群算法相比，該文方法能有效減少信號(hào)交叉口的延誤時(shí)間和停車次數(shù)，提高交叉口的運(yùn)行效率。

關(guān)鍵詞： 交叉口； 信號(hào)配時(shí)； 多目標(biāo)優(yōu)化； 環(huán)境變異免疫克隆算法

中圖分類號(hào)： TN911?34； U491 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）16?0019?04

Abstract： To solve the problems of single optimization objective and low efficiency in signal timing， a novel multi?objective optimization method for signal timing of intersections is proposed. In consideration of constraint conditions of green?light duration， cycle length and saturability， the cost function is defined by weighted coefficient method to make delay time， parking times and traffic capacity of intersections optimum to some extent. Based on the characteristics of uniformity and wide?distribution of optimal solution while immune clone algorithm （ICA） is used to solve multi?objective problems， a new environment mutation operator was introduced， and the environment mutation ICA was proposed for model solution， which enhanced the global searching ability of the algorithm and improved the solution quality. The simulation results reveal that， compared with the traditional timing method and inertia weight particle swarm algorithm， the presented method can efficiently reduce average delay， parking times of intersections， and improve the efficiency of traffic signal control.

Keywords： intersection； signal timing； multi?objective optimization； environment mutation immune clone algorithm

信號(hào)交叉口常用的性能評(píng)價(jià)指標(biāo)有停車次數(shù)、通行能力、延誤、排隊(duì)長度、飽和度等[1]。然而，目前國內(nèi)文獻(xiàn)中多以一個(gè)性能指標(biāo)（通常是總延誤）對(duì)交叉口進(jìn)行配時(shí)優(yōu)化，既無法滿足現(xiàn)實(shí)情況中需要滿足多項(xiàng)性能指標(biāo)兼顧的要求，也沒有考慮不同交通狀態(tài)下對(duì)多個(gè)性能指標(biāo)有所側(cè)重要求，具有一定的局限性[2]。因此，信號(hào)交叉口的配時(shí)優(yōu)化問題實(shí)質(zhì)上是一個(gè)多目標(biāo)優(yōu)化的問題。

多目標(biāo)優(yōu)化問題（Multi?objective Optimization Problems，MOP）是指具有兩個(gè)及以上的目標(biāo)函數(shù)的最優(yōu)化問題[3]。這些優(yōu)化目標(biāo)往往彼此間難以直接比較，甚至相互對(duì)立，一個(gè)目標(biāo)的改善甚至有可能引起另一個(gè)目標(biāo)性能的降低，因而難以同時(shí)達(dá)到最優(yōu)。

針對(duì)這些問題，本文選取延誤時(shí)間、停車次數(shù)和最大通行能力作為信號(hào)控制目標(biāo)，建立了相應(yīng)的單交叉口多目標(biāo)優(yōu)化信號(hào)配時(shí)優(yōu)化模型，并提出了基于環(huán)境變異免疫控制算法（Environment Mutation Immune Clone Algorithm，EMICA） 的多目標(biāo)控制方法。通過該算法協(xié)調(diào)好這三個(gè)控制目標(biāo)的平衡，從而得到實(shí)時(shí)的多目標(biāo)最優(yōu)解，進(jìn)而得到最佳的控制策略。

1 交叉口多目標(biāo)信號(hào)配時(shí)優(yōu)化模型

本文在研究單點(diǎn)道路交叉口的信號(hào)配時(shí)時(shí)，假設(shè)交通流數(shù)據(jù)（如每個(gè)車道的機(jī)動(dòng)車交通量）已經(jīng)獲得，非機(jī)動(dòng)車及行人已轉(zhuǎn)換成當(dāng)前交通量。

1.1 多目標(biāo)信號(hào)配時(shí)模型

交叉口信號(hào)控制的優(yōu)化目標(biāo)包括延誤時(shí)間、停車次數(shù)、最大通行能力、飽和度、油耗、尾氣排放等。其中尤以前4項(xiàng)最為重要，一般來說其他項(xiàng)均可以由這幾項(xiàng)導(dǎo)出[4?5]。因此，本文把交叉口的總延誤、總停車次數(shù)、最大通行能力三個(gè)指標(biāo)作為優(yōu)化對(duì)象，以飽和度為約束，利用加權(quán)的方法合并成目標(biāo)函數(shù)并求解。假設(shè)交叉口信號(hào)有n個(gè)相位，下面是信號(hào)配時(shí)中需要優(yōu)化三個(gè)指標(biāo)的函數(shù)表達(dá)式，將各相位的有效綠燈時(shí)間作為自變量：

（1） 延誤時(shí)間計(jì)算。延誤時(shí)間是指在交叉口處由于交通流沖突或信號(hào)燈控制引起的行駛時(shí)間損失。韋伯斯特（Webster）提出了延誤時(shí)間的計(jì)算公式[6?7]如下：

[Di=C1-λi221-yi+yi22qiλiλi-yi] （1）

式中：[Di]表示第[i]相位的車輛平均延誤時(shí)間，單位為s；[C]為周期，單位為s；[λi]為綠信比表示第[i]相位有效綠燈時(shí)間與信號(hào)周期的比值；[yi]為第[i]相位的相位流量比；[qi]為第[i]相位的相位車流到達(dá)率，單位為pcu/h。

（2） 停車率計(jì)算。采用穩(wěn)態(tài)模型[8?9]計(jì)算進(jìn)入交叉口每輛車輛的平均停車次數(shù)，如式（2）所示：

[Hi=0.91-λi1-yi+NiqiC] （2）

式中：[Hi]表示第[i]相位的車輛平均起停次數(shù)；[Ni]表示在未飽和交叉口，某相位的平均滯留車輛數(shù)。

（3） 通行能力計(jì)算。采用HCM2000理論[5，10]，先將交叉口各進(jìn)口道劃分為若干車道組，然后計(jì)算各車道組的通行能力：

[Qi=Siλi] （3）

式中：[Qi]表示第[i]相位的通行能力；[Si]為車道組[i]的飽和流率。

1.2 目標(biāo)函數(shù)

將以上三個(gè)函數(shù)通過加權(quán)的方法轉(zhuǎn)化為目標(biāo)函數(shù)進(jìn)行求解：

[f=ξ1Di+ξ2Hi+ξ3Qi] （4）

式中，[ξi]表示第[i]個(gè)目標(biāo)函數(shù)的權(quán)重系數(shù)。

為了使建立的優(yōu)化模型更好地符合實(shí)際狀況，模型應(yīng)能夠根據(jù)不同交通狀態(tài)對(duì)各指標(biāo)有所側(cè)重：如交通狀態(tài)趨向擁擠時(shí)要確保發(fā)揮路口的最大通行能力，而非擁擠狀態(tài)時(shí)應(yīng)盡可能減少路口信號(hào)控制的延誤和停車次數(shù)。首先評(píng)判這幾個(gè)指標(biāo)的相對(duì)重要性，根據(jù)式（5）、式（6）建立相應(yīng)的模糊矩陣[R=ri，j]，其中[ri，j]表示[i]相對(duì)于[j]的重要性，并根據(jù)式（7）、式（8）求解。

[R=rD，DrD，HrD，QrH，DrH，HrH，QrQ，DrQ，HrQ，Q] （5）

[ri，j=0， ij ri，j=2， i?j ] （6）

令：

[Ii=j=1nri，j] （7）

進(jìn)行歸一化后可得：

[ξi=IiIi] （8）

這種利用模糊矩陣的加權(quán)系數(shù)法對(duì)三個(gè)性能指標(biāo)進(jìn)行平衡，大大降低了交警設(shè)置指標(biāo)權(quán)重的復(fù)雜程度和主觀性，從而通過調(diào)整[ξi]的值使得交叉口在不同交通狀態(tài)下均能在某種程度上達(dá)到最優(yōu)。

1.3 約束條件

為了保證行人和行車安全，需要在配時(shí)前添加一定的約束條件，由式（9）～式（11）給出。

（1） 綠燈時(shí)間約束[1]。一般情況下，有效綠燈時(shí)間最小不小于12 s，最大不大于100 s。

[gimin≤gi≤gimax ， 1≤i≤n] （9）

（2） 周期約束[1]。信號(hào)周期過短會(huì)對(duì)行人車輛安全通過交叉口造成威脅，過大也不會(huì)增加通行能力，所以一般最短信號(hào)周期時(shí)長可取30～40 s，最大不大于180 s。

[Cmin≤C=i=1ngi+li≤Cmax] （10）

（3） 飽和度約束[1]。因在過飽和情況下，采用優(yōu)化算法往往也難以起到良好的優(yōu)化效果，而飽和度在0.7和0.9之間時(shí)，交叉口可以獲得較好的運(yùn)行條件，故飽和度取0.7～0.9。

[0.7≤X≤0.9] （11）

2 信號(hào)配時(shí)優(yōu)化算法

本文所要解決的多目標(biāo)約束優(yōu)化問題可以定義如下[11]：

[min fAs.t. A∈G， G=ai∈Rm gix≤0 i∈1，m ， j∈1，0] （12）

式中：[fA]為優(yōu)化目標(biāo)函數(shù)；[A=a1，a2，…，am]為[Rm]空間內(nèi)變量集；[G]為所有可行解集合；[g·]為約束函數(shù)。本文采用十進(jìn)制編碼，所有變量歸一化在[0，1）區(qū)間。

2.1 代價(jià)函數(shù)設(shè)計(jì)

由于配時(shí)優(yōu)化模型中約束條件的存在，需要進(jìn)行約束處理。而罰函數(shù)法是處理約束條件最常用的方法之一，故采用罰函數(shù)的方式來處理，代價(jià)函數(shù)可寫為：

[fCA=fA+rg?A] （13）

式中：[rg]為懲罰系數(shù)；[?A]為罰函數(shù)。

雖然罰函數(shù)法有著簡單易行的優(yōu)點(diǎn)，但實(shí)際上選取合適的懲罰系數(shù)相當(dāng)困難。懲罰系數(shù)[rg]太小可能導(dǎo)致懲罰力度過小，影響優(yōu)化函數(shù)的尋優(yōu)方向[11?12]；懲罰系數(shù)[rg]過大則會(huì)引發(fā)計(jì)算的困難容易引起早熟收斂[13]；因此，如何選擇合適的懲罰系數(shù)[rg]或懲罰函數(shù)的形式是解決有約束優(yōu)化問題的關(guān)鍵。罰函數(shù)可以調(diào)節(jié)個(gè)體的適應(yīng)度值，對(duì)群體的排序產(chǎn)生影響。文獻(xiàn)[14]中采用概率排序的形式，使得群體在目標(biāo)函數(shù)和約束條件中得到動(dòng)態(tài)的平衡。本文在參考文獻(xiàn)[14]核心思想的同時(shí)，也制定了以下三條規(guī)則，以能夠保證目標(biāo)函數(shù)值小、約束條件值也不大個(gè)體的基因也有機(jī)會(huì)在群體中傳播[11?12]：

（1） 當(dāng)兩個(gè)個(gè)體都符合約束條件時(shí)，目標(biāo)函數(shù)值小的排序靠前；

（2） 當(dāng)兩個(gè)個(gè)體有一個(gè)不符合約束條件時(shí)，目標(biāo)函數(shù)值小而且約束條件值小的排序靠前；

（3） 當(dāng)兩個(gè)個(gè)體有一個(gè)不符合約束條件且目標(biāo)函數(shù)值小與約束條件值小條件不同時(shí)成立時(shí)，則以約束條件的比值為概率，隨機(jī)排序。

2.2 環(huán)境變異免疫克隆算法算子描述

免疫克隆算法是近年來新興的進(jìn)化算法之一。人們受生物免疫系統(tǒng)的啟發(fā)，通過對(duì)免疫應(yīng)答過程及免疫細(xì)胞克隆的模擬而提出的一種啟發(fā)式搜索算法。它提供噪聲忍耐、自組織、記憶等學(xué)習(xí)機(jī)理，具有保持群分布多樣性的特點(diǎn)[15]。免疫克隆算法較成功地解決了多目標(biāo)優(yōu)化中最優(yōu)解分布的寬廣性、均勻性及向著最優(yōu)Pareto?前端逼近等問題。本文借鑒了免疫克隆算法在解決多目標(biāo)優(yōu)化問題中的優(yōu)勢(shì)，并基于以前的工作，利用EMICA算法來解決有交叉口信號(hào)控制的優(yōu)化問題。本文信號(hào)配時(shí)優(yōu)化算法的核心就是EMICA算法?；贓MICA算法的多目標(biāo)尋優(yōu)步驟如下，詳細(xì)步驟[12]如下：

（1） 初始化。初始化抗體群，設(shè)定算法參數(shù)，抗體號(hào)i=1，進(jìn)化代數(shù)t=0；

（2） 疫苗選擇[TCs]。在人類免疫系統(tǒng)中，抗原一般指問題及其約束，抗體一般是指問題的候選解[16?17]，疫苗則是由先驗(yàn)知識(shí)而得到的對(duì)最佳個(gè)體基因的估計(jì)。在EMICA算法中將每代親和度最高的抗體認(rèn)為是疫苗：

[TCsAPt=maxi∈1，NfCAt] （14）

式中：[APt]為第[t]代的抗體集；[N]為種群規(guī)模。

（3） 克隆增殖[TCc]?？寺≡鲋持饕菍?duì)抗體群進(jìn)行復(fù)制，因此克隆后種群[AP]包括兩部分：一部分是克隆子群記為[APC]；另一部分是原抗體群：

[TCcAP=TCcA1 TCcA2 … TCcAPtTTCcAi=Ik×Ai] （15）

式中，[Ik]為[k]維單位行矩陣；[k]為克隆規(guī)模。

（4） 環(huán)境變異[TCe]。環(huán)境變異主要是對(duì)克隆子群[APC]進(jìn)行環(huán)境影響因素的變異操作。這樣做有兩個(gè)好處：一是在群體中較優(yōu)個(gè)體周圍探索前進(jìn)方向，從而提高免疫算法效率；二是通過環(huán)境變量獲取進(jìn)化過程中的歷史經(jīng)驗(yàn)，使算法在一定程度上具有學(xué)習(xí)能力：

[TCeACt=ACt+r1Et ， ACt?APCtEt=r2Et-1+r3TCsAPt-ACt] （16）

式中：[E]為環(huán)境變量；[r1]為學(xué)習(xí)系數(shù)；[r2]為遺忘系數(shù)；[r3]為修改系數(shù)。

（5） 克隆變異[TCm]。通過式（13）對(duì)克隆子群[APC]進(jìn)行變異操作：

[TCmgCj1j2=gmj1j2 ， flippm=1gCj1j2 ， 其他 gCj1j2∈ACit] （17）

式中：[flip?]為伯努利試驗(yàn)；[gCij]為克隆個(gè)體的基因位；[gmij]為變異基因位；[pm]為變異概率。

（6） 克隆選擇[TCr]。克隆選擇是從克隆進(jìn)化后的群體中選擇優(yōu)秀個(gè)體，進(jìn)而形成新的種群的過程。若克隆子群個(gè)體的親和度大于克隆母體的親和度，則將該個(gè)體替代母體，從而使高親和力抗體中的優(yōu)秀基因得到更好地保存和發(fā)展。

[TCrAit，APCt=ACt+1，max， fACt+1，max>fAit且 fACt+1，max≥∨j=1kfACjAit， 其他 ] （18）

式中，[ACt+1，max]為最大親和度個(gè)體。

（7） 判斷。判斷是否滿足終止條件，不滿足終止條件則返回步驟（3），并將前一個(gè)時(shí)刻的最終抗體群作為下一個(gè)時(shí)刻的初始種群，若滿足終止條件則算法結(jié)束。

3 仿真結(jié)果及分析

為了驗(yàn)證本文方法的有效性，以典型的四相位信號(hào)交叉口為例（即假設(shè)右轉(zhuǎn)車流不受信號(hào)控制），計(jì)算各相位的有效綠燈時(shí)間，信號(hào)控制方案如圖1所示，交叉口各進(jìn)口各向交通量如表1所示[8]，其中非機(jī)動(dòng)車交通量已經(jīng)換算為標(biāo)準(zhǔn)小轎車交通量。

程序采用VC++ 6.0語言編寫。參數(shù)設(shè)置：群體規(guī)模N=200，克隆規(guī)模k=5，變異概率pm=0.01，環(huán)境變量學(xué)習(xí)參數(shù)r1=random（0.0，1.2），環(huán)境變量遺忘參數(shù)r2=random（0.6，0.7），環(huán)境變量修改參數(shù)r3=random（0.0，1.4）。采用連續(xù)100 代不能提高群體的最優(yōu)解時(shí)停止為算法終止條件。其中，最小周期和最大周期分別為40 s和180 s，總損失時(shí)間為16 s，飽和度限制在0.7～0.9之間。原配時(shí)方案得到的結(jié)果，利用文獻(xiàn)[8]提出的改進(jìn)粒子群算法優(yōu)化得到的結(jié)果，及采用本文提出的算法優(yōu)化后的結(jié)果如表2所示。

由表2可以看出，與原有配時(shí)方案相比，經(jīng)過兩種算法優(yōu)化后總延誤和總停車次數(shù)兩個(gè)指標(biāo)均得到一定程度的改善。原方案的總延誤為16 648 s，經(jīng)改進(jìn)粒子群算法優(yōu)化后最小延誤為10 683 s，比原方案減少了35.8%，而經(jīng)本文算法優(yōu)化后的最小延誤為9 883 s，較原方案降低了40.6%。原方案總停車次數(shù)為212次，經(jīng)改進(jìn)粒子群算法優(yōu)化后最小停車次數(shù)為170次，比之前降低了19.8%，而經(jīng)本文算法優(yōu)化后的最小停車次數(shù)為163次，較原方案降低了23.1%?？梢钥闯鲈诳傃诱`和總停車次數(shù)兩個(gè)指標(biāo)上，本文算法的優(yōu)化結(jié)果均好于改進(jìn)粒子算法得到的結(jié)果。但由于交叉口周期時(shí)長的減小，從而使交叉口最大通行能力有所下降，可由于本文不探討交叉口過飽和度的通行狀態(tài)，一般達(dá)不到交叉口的最大通行能力，可以說交叉口最大通行能力的略微下降對(duì)整個(gè)交叉口的運(yùn)行效率幾乎無影響。綜上所述，兩種算法在優(yōu)化結(jié)果上均取得了較好的結(jié)果，但本文算法在處理交叉口信號(hào)控制多目標(biāo)優(yōu)化的綜合性能要強(qiáng)于改進(jìn)粒子群算法優(yōu)化。

4 結(jié) 論

進(jìn)行信號(hào)配時(shí)優(yōu)化時(shí)，綜合考慮了交叉口的總延誤時(shí)間、總停車次數(shù)和最大通行能力三個(gè)常用評(píng)價(jià)指標(biāo)，并應(yīng)用加權(quán)的方法定義了目標(biāo)函數(shù)，克服了以往優(yōu)化方法目標(biāo)過于單一的缺點(diǎn)，更加符合實(shí)際環(huán)境中多項(xiàng)性能指標(biāo)的控制需求。使用模糊矩陣的方法來確定三個(gè)性能指標(biāo)的權(quán)重系數(shù)，簡化了人們對(duì)指標(biāo)權(quán)重判斷的復(fù)雜性和主觀性，解決了在不同交通狀態(tài)下確定權(quán)重的方法一致性問題。算法性能上，引入了多目標(biāo)問題求解上有諸多優(yōu)勢(shì)的免疫克隆算法，并在其中融合了環(huán)境變異算子，將環(huán)境對(duì)個(gè)體進(jìn)化的影響積累到克隆變異操作中，提高了免疫克隆算法的搜索效率和穩(wěn)定性。對(duì)典型的四相位信號(hào)交叉口信號(hào)配時(shí)的仿真結(jié)果表明，與現(xiàn)有算法相比，本文算法更能夠得到高質(zhì)量的解，有助于緩解交通擁堵的狀況。下一步的研究工作是將提出的基于環(huán)境變異免疫克隆算法的交叉口信號(hào)控制多目標(biāo)優(yōu)化方法在實(shí)際交叉口中加以應(yīng)用，利用前期開發(fā)的視頻車檢器獲取交通流量等信息，從而使交叉口通行更為順暢，同時(shí)也更加節(jié)能和環(huán)保。

參考文獻(xiàn)

[1] 王錦錦.改進(jìn)交叉口性能評(píng)價(jià)及多目標(biāo)優(yōu)化配時(shí)研究[D].重慶：重慶大學(xué)，2012.

[2] 曹成濤，徐建閩.單交叉口交通多目標(biāo)控制方法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46 （16）：20?22.

[3] 王光遠(yuǎn).城市交通信號(hào)多目標(biāo)自適應(yīng)控制[D].大連：大連理工大學(xué)，2010.

[4] 蘇長慧，夏桂梅.基于改進(jìn)微粒群算法的單點(diǎn)信控交叉口配時(shí)優(yōu)化[J].太原科技大學(xué)學(xué)報(bào)，2014，35（3）：198?201.

[5] 曹娟娟，卲維.基于改進(jìn)粒子群算法的多目標(biāo)單交叉口信號(hào)優(yōu)化控制[J].長沙大學(xué)學(xué)報(bào)，2012，26（2）：69?71.

[6] 伍尚昆，陳翠宜，祝勝林.基于多種群蟻群算法的交叉路口信號(hào)配時(shí)優(yōu)化[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（5）：83?88.

[7] 崔明月，劉紅釗，劉偉，等.改進(jìn)的非劣遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用[J].南陽師范學(xué)院學(xué)報(bào)，2014，13（12）：8?12.

[8] 劉金明.基于多目標(biāo)規(guī)劃的城市道路交叉口信號(hào)配時(shí)研究[D].北京：北京交通大學(xué)，2011.

[9] 肖婧，王科俊，畢曉君.交叉口混合交通流高維多目標(biāo)信號(hào)優(yōu)化控制[J].公路交通科技，2014，31（11）：108?115.

[10] 陳小紅.混合交通環(huán)境下城市道路交通信號(hào)控制優(yōu)化模型研究[D].北京：北京交通大學(xué)，2012.

[11] 徐海黎，解祥榮，莊健，等.工業(yè)機(jī)器人的最優(yōu)時(shí)間與最優(yōu)能量軌跡規(guī)劃[J].機(jī)械工程學(xué)報(bào)，2010，46（9）：19?25.

[12] 徐海黎，朱志松，王恒，等.環(huán)境變異免疫克隆算法解決有約束優(yōu)化問題[J].系統(tǒng)仿真學(xué)報(bào)，2011，23（11）：2412?2416.

[13] 焦李成，尚榮華，馬文萍，等.多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用[M].北京：科學(xué)出版社，2010：114.

[14] RUNARSSON Thomas Philip，YAO Xin. Stochastic ranking for constrained evolutionary optimization [J]. IEEE transactions on evolutionary computation （S1089?778X），2000，4（3）： 284?294.

[15] 尚榮華，焦李成，公茂果，等.免疫克隆算法求解動(dòng)態(tài)多目標(biāo)優(yōu)化問題[J].軟件學(xué)報(bào)，2007，18（11）：2700?2711.

[16] 秦亮，張文廣，史賢俊，等.基于免疫克隆算法的多目標(biāo)聚類方法[J].信息與控制，2013，42（1）：8?12.

[17] 林滸，彭勇.面向多目標(biāo)優(yōu)化的適應(yīng)度共享免疫克隆算法[J].控制理論與應(yīng)用，2011，28（2）：206?214.