城市道路交叉口信號配時多目標優化方法研究

摘 要： 針對目前交叉口信號配時優化目標單一、綜合運行效率不高的問題，提出一種交叉口信號配時多目標優化方法。考慮綠燈時間、周期長度和飽和度等約束條件，通過加權系數法定義代價函數，使交叉口的延誤時間、停車次數和通行能力在某種程度上達到最優。基于免疫克隆算法在處理多目標問題中具有最優解分布寬廣性、均勻性好等特點，引入環境變異算子，提出環境變異免疫克隆算法對模型求解，增強了算法的全局搜索能力，提高了解的質量。仿真結果表明，與傳統配時方法和改進粒子群算法相比，該文方法能有效減少信號交叉口的延誤時間和停車次數，提高交叉口的運行效率。

關鍵詞： 交叉口； 信號配時； 多目標優化； 環境變異免疫克隆算法

中圖分類號： TN911?34； U491 文獻標識碼： A 文章編號： 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

信號交叉口常用的性能評價指標有停車次數、通行能力、延誤、排隊長度、飽和度等[1]。然而，目前國內文獻中多以一個性能指標（通常是總延誤）對交叉口進行配時優化，既無法滿足現實情況中需要滿足多項性能指標兼顧的要求，也沒有考慮不同交通狀態下對多個性能指標有所側重要求，具有一定的局限性[2]。因此，信號交叉口的配時優化問題實質上是一個多目標優化的問題。

多目標優化問題（Multi?objective Optimization Problems，MOP）是指具有兩個及以上的目標函數的最優化問題[3]。這些優化目標往往彼此間難以直接比較，甚至相互對立，一個目標的改善甚至有可能引起另一個目標性能的降低，因而難以同時達到最優。

針對這些問題，本文選取延誤時間、停車次數和最大通行能力作為信號控制目標，建立了相應的單交叉口多目標優化信號配時優化模型，并提出了基于環境變異免疫控制算法（Environment Mutation Immune Clone Algorithm，EMICA） 的多目標控制方法。通過該算法協調好這三個控制目標的平衡，從而得到實時的多目標最優解，進而得到最佳的控制策略。

1 交叉口多目標信號配時優化模型

本文在研究單點道路交叉口的信號配時時，假設交通流數據（如每個車道的機動車交通量）已經獲得，非機動車及行人已轉換成當前交通量。

1.1 多目標信號配時模型

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

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

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

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

（2） 停車率計算。采用穩態模型[8?9]計算進入交叉口每輛車輛的平均停車次數，如式（2）所示：

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

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

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

[Qi=Siλi] （3）

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

1.2 目標函數

將以上三個函數通過加權的方法轉化為目標函數進行求解：

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

式中，[ξi]表示第[i]個目標函數的權重系數。

為了使建立的優化模型更好地符合實際狀況，模型應能夠根據不同交通狀態對各指標有所側重：如交通狀態趨向擁擠時要確保發揮路口的最大通行能力，而非擁擠狀態時應盡可能減少路口信號控制的延誤和停車次數。首先評判這幾個指標的相對重要性，根據式（5）、式（6）建立相應的模糊矩陣[R=ri，j]，其中[ri，j]表示[i]相對于[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）

進行歸一化后可得：

[ξi=IiIi] （8）

這種利用模糊矩陣的加權系數法對三個性能指標進行平衡，大大降低了交警設置指標權重的復雜程度和主觀性，從而通過調整[ξi]的值使得交叉口在不同交通狀態下均能在某種程度上達到最優。

1.3 約束條件

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

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

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

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

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

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

[0.7≤X≤0.9] （11）

2 信號配時優化算法

本文所要解決的多目標約束優化問題可以定義如下[11]：

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

式中：[fA]為優化目標函數；[A=a1，a2，…，am]為[Rm]空間內變量集；[G]為所有可行解集合；[g·]為約束函數。本文采用十進制編碼，所有變量歸一化在[0，1）區間。

2.1 代價函數設計

由于配時優化模型中約束條件的存在，需要進行約束處理。而罰函數法是處理約束條件最常用的方法之一，故采用罰函數的方式來處理，代價函數可寫為：

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

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

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

（1） 當兩個個體都符合約束條件時，目標函數值小的排序靠前；

（2） 當兩個個體有一個不符合約束條件時，目標函數值小而且約束條件值小的排序靠前；

（3） 當兩個個體有一個不符合約束條件且目標函數值小與約束條件值小條件不同時成立時，則以約束條件的比值為概率，隨機排序。

2.2 環境變異免疫克隆算法算子描述

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

（1） 初始化。初始化抗體群，設定算法參數，抗體號i=1，進化代數t=0；

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

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

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

（3） 克隆增殖[TCc]。克隆增殖主要是對抗體群進行復制，因此克隆后種群[AP]包括兩部分：一部分是克隆子群記為[APC]；另一部分是原抗體群：

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

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

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

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

式中：[E]為環境變量；[r1]為學習系數；[r2]為遺忘系數；[r3]為修改系數。

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

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

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

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

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

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

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

3 仿真結果及分析

為了驗證本文方法的有效性，以典型的四相位信號交叉口為例（即假設右轉車流不受信號控制），計算各相位的有效綠燈時間，信號控制方案如圖1所示，交叉口各進口各向交通量如表1所示[8]，其中非機動車交通量已經換算為標準小轎車交通量。

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

由表2可以看出，與原有配時方案相比，經過兩種算法優化后總延誤和總停車次數兩個指標均得到一定程度的改善。原方案的總延誤為16 648 s，經改進粒子群算法優化后最小延誤為10 683 s，比原方案減少了35.8%，而經本文算法優化后的最小延誤為9 883 s，較原方案降低了40.6%。原方案總停車次數為212次，經改進粒子群算法優化后最小停車次數為170次，比之前降低了19.8%，而經本文算法優化后的最小停車次數為163次，較原方案降低了23.1%。可以看出在總延誤和總停車次數兩個指標上，本文算法的優化結果均好于改進粒子算法得到的結果。但由于交叉口周期時長的減小，從而使交叉口最大通行能力有所下降，可由于本文不探討交叉口過飽和度的通行狀態，一般達不到交叉口的最大通行能力，可以說交叉口最大通行能力的略微下降對整個交叉口的運行效率幾乎無影響。綜上所述，兩種算法在優化結果上均取得了較好的結果，但本文算法在處理交叉口信號控制多目標優化的綜合性能要強于改進粒子群算法優化。

4 結 論

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

參考文獻

[1] 王錦錦.改進交叉口性能評價及多目標優化配時研究[D].重慶：重慶大學，2012.

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

[3] 王光遠.城市交通信號多目標自適應控制[D].大連：大連理工大學，2010.

[4] 蘇長慧，夏桂梅.基于改進微粒群算法的單點信控交叉口配時優化[J].太原科技大學學報，2014，35（3）：198?201.

[5] 曹娟娟，卲維.基于改進粒子群算法的多目標單交叉口信號優化控制[J].長沙大學學報，2012，26（2）：69?71.

[6] 伍尚昆，陳翠宜，祝勝林.基于多種群蟻群算法的交叉路口信號配時優化[J].計算機應用與軟件，2014，31（5）：83?88.

[7] 崔明月，劉紅釗，劉偉，等.改進的非劣遺傳算法在多目標優化中的應用[J].南陽師范學院學報，2014，13（12）：8?12.

[8] 劉金明.基于多目標規劃的城市道路交叉口信號配時研究[D].北京：北京交通大學，2011.

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

[10] 陳小紅.混合交通環境下城市道路交通信號控制優化模型研究[D].北京：北京交通大學，2012.

[11] 徐海黎，解祥榮，莊健，等.工業機器人的最優時間與最優能量軌跡規劃[J].機械工程學報，2010，46（9）：19?25.

[12] 徐海黎，朱志松，王恒，等.環境變異免疫克隆算法解決有約束優化問題[J].系統仿真學報，2011，23（11）：2412?2416.

[13] 焦李成，尚榮華，馬文萍，等.多目標優化免疫算法、理論和應用[M].北京：科學出版社，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] 尚榮華，焦李成，公茂果，等.免疫克隆算法求解動態多目標優化問題[J].軟件學報，2007，18（11）：2700?2711.

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

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