曹娟娟，邵 維

(長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙 410004)

基于改進(jìn)粒子群算法的多目標(biāo)單交叉口信號(hào)優(yōu)化控制＊

曹娟娟，邵 維

(長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙 410004)

交叉口信號(hào)配時(shí)優(yōu)化，對(duì)緩解城市的交通擁堵，提高城市道路通行能力具有非常重要的意義.以各相位進(jìn)道口上的停車(chē)次數(shù)、總延誤和通行能力作為目標(biāo)進(jìn)行優(yōu)化，并依據(jù)實(shí)時(shí)交通量數(shù)據(jù)來(lái)調(diào)節(jié)對(duì)應(yīng)的權(quán)重系數(shù)，實(shí)現(xiàn)信號(hào)控制的自適應(yīng)調(diào)節(jié).模型的求解利用基于克隆選擇的粒子群算法，得出信號(hào)配時(shí)方案，并與傳統(tǒng)的webster算法作比較.

單交叉口;信號(hào)配時(shí);多目標(biāo);克隆選擇;粒子群優(yōu)化算法

伴隨著我國(guó)國(guó)民經(jīng)濟(jì)持續(xù)、快速發(fā)展，機(jī)動(dòng)車(chē)擁有量急劇增加，這為交通運(yùn)輸行業(yè)帶來(lái)了繁榮景象;然而，大多數(shù)城市的交通卻處于相當(dāng)緊張的狀態(tài)，交通擁堵已成為大城市突出的社會(huì)問(wèn)題之一.其中提高交通信號(hào)控制系統(tǒng)的科學(xué)性是城市道路交叉口智能監(jiān)控系統(tǒng)研究的核心問(wèn)題，對(duì)緩解日趨緊張的交通問(wèn)題，減少交通事故和交通擁擠現(xiàn)狀有著非常重要的意義.

針對(duì)城市道路交叉口的交通流特性，提出了多目標(biāo)自適應(yīng)優(yōu)化控制方法，對(duì)單個(gè)交叉路口的不同優(yōu)化指標(biāo)(停車(chē)次數(shù)、延誤時(shí)間、通行能力)進(jìn)行分析建模，采用多目標(biāo)改進(jìn)粒子群算法求解，盡量滿足單個(gè)路口的多個(gè)目標(biāo)優(yōu)化需求［1，2］.

1 交通信號(hào)配時(shí)優(yōu)化模型

1.1 信號(hào)控制目標(biāo)分析

交叉口信號(hào)控制目標(biāo)包括延誤、飽和度、停車(chē)次數(shù)、通行能力、油耗、尾氣排放、噪音、運(yùn)營(yíng)成本等.在這些目標(biāo)中的基本量?jī)H包括延誤、停車(chē)次數(shù)、通行能力、飽和度、排隊(duì)長(zhǎng)度.其他的量均可以由基本量導(dǎo)出.因此本文僅以停車(chē)次數(shù)、延誤、通行能力三個(gè)指標(biāo)做為目標(biāo)函數(shù)進(jìn)行優(yōu)化控制.

延誤分析［3］:采用webster延誤時(shí)間計(jì)算公式，總延誤時(shí)間計(jì)算公式為:

其中:C為信號(hào)周期(s);gi為相位i的有效綠燈時(shí)間;yi為交叉口第i相位交通流量與飽和流量之比;qi為相位i的車(chē)流量(pcu/h).

停車(chē)次數(shù)分析:交叉口車(chē)輛總的停車(chē)次數(shù)為:

總的通行能力分析:信號(hào)交叉口的通行能力是指在一定的道路條件和交通管制條件下，某一入口車(chē)道單位時(shí)間內(nèi)所

能通過(guò)的最大交通量，以車(chē)道為基本單位.

其中:Si為第i相位的飽和流量(pcu/h).

因?yàn)橐惶熘薪煌ㄐ枨罅坎粩嘧兓?，所以?duì)交叉口的信號(hào)配時(shí)的要求側(cè)重點(diǎn)也不一樣，在交通處于閑散或者順暢的狀態(tài)時(shí)，控制目標(biāo)側(cè)重于暢通舒適最大，即延誤和停車(chē)次數(shù)最小;在交通處于繁忙或擁堵?tīng)顟B(tài)時(shí)，控制目標(biāo)側(cè)重于管理效率最高，即更偏重于通行能力最大.所以根據(jù)交通需求量的不同，調(diào)節(jié)三個(gè)目標(biāo)函數(shù)的權(quán)重系數(shù)(隨交通量不同而實(shí)時(shí)變化的性能指標(biāo))，期望能使交叉口達(dá)到最好的交通狀態(tài).三個(gè)權(quán)重系數(shù)為:

其中:Y為交叉口流率比.

1.2 交通信號(hào)配時(shí)建模

本文以典型的單交叉口四相為信號(hào)控制為例，交叉口有東西南北四個(gè)方向，每個(gè)方向都有直行、右轉(zhuǎn)、左轉(zhuǎn)三個(gè)方向的車(chē)流.具體相位信號(hào)控制方案如圖1:

圖1 典型四相位圖

根據(jù)道路交通流數(shù)據(jù)，以總延誤時(shí)間、停車(chē)次數(shù)最小和通行能力最大為目標(biāo)，利用隨交通量實(shí)時(shí)變化的權(quán)重系數(shù)，建立相應(yīng)的目標(biāo)優(yōu)化函數(shù)如下:

其中:gmin為相位i最小的有效綠燈時(shí)間，(s);gmax為相位i最長(zhǎng)的有效綠燈時(shí)間，(s);li為相位i的損失時(shí)間，(s);cmax為最大周期時(shí)間，(s).

上述的約束條件約束了道路交叉口的飽和度k.為了避免飽和度過(guò)小，我們?cè)O(shè)定參數(shù)0.75，同樣為了避免飽和度過(guò)大，設(shè)定參數(shù)0.95，它們的取值是可變的.

2 基于克隆選擇的粒子群算法

2.1 粒子群算法基本介紹

粒子群算法(PSO)是一種新發(fā)展起來(lái)的，進(jìn)化的優(yōu)化算法.這種算法最開(kāi)始是由Eberhart博士和kennedy博士提出來(lái)的.在這種算法中，有一種我們稱(chēng)為“粒子”的東西，它類(lèi)似于鳥(niǎo)類(lèi)捕食活動(dòng)中的一只鳥(niǎo)，即我們優(yōu)化問(wèn)題中得一個(gè)解.每一個(gè)粒子都有一個(gè)相對(duì)應(yīng)的適應(yīng)值，這種適應(yīng)值是被優(yōu)化的函數(shù)決定的.除此之外，每個(gè)粒子還有它們飛翔的方向和距離，這個(gè)是由一個(gè)可變的速度決定的.最后這些粒子就進(jìn)行搜索，它們的搜索是通過(guò)在整個(gè)解的空間中跟蹤著當(dāng)前的最優(yōu)粒子進(jìn)行的.

PSO首先會(huì)產(chǎn)生一些隨機(jī)粒子(隨機(jī)解).隨后粒子會(huì)在整個(gè)空間中尋找并且相互之間會(huì)進(jìn)行比較，進(jìn)行更新，這樣通過(guò)一次次的迭代尋找到全局的一個(gè)最優(yōu)解.在各次迭代中有兩個(gè)最優(yōu)解，粒子會(huì)不斷地尋找這兩個(gè)最優(yōu)解并且更新自己.其中一個(gè)是當(dāng)前在全部群體中可以找到的最優(yōu)解，這個(gè)稱(chēng)為全局最優(yōu)解gbest，而另外一個(gè)是粒子自己找到的最優(yōu)解，這個(gè)稱(chēng)為個(gè)體最優(yōu)解pbest.在粒子尋找最優(yōu)解時(shí)，粒子會(huì)自動(dòng)更新自己的速度和位置，更新的公式如下:

其中:c1和c2為學(xué)習(xí)因子，取正數(shù);w為慣性權(quán)因子，根據(jù)需要優(yōu)化的目標(biāo)函數(shù)取適當(dāng)?shù)闹?r1和r2取0－1之間的隨機(jī)數(shù)，隨機(jī)數(shù)是呈均勻分布的.

2.2 基于克隆選擇的粒子群算法

粒子群算法也存在很多缺陷，比如在算法運(yùn)行中，會(huì)出現(xiàn)“聚集”現(xiàn)象.這種現(xiàn)象是指當(dāng)其中一個(gè)粒子找到了一個(gè)目前最優(yōu)解，那么其余的粒子將迅速地向那個(gè)聚集.這樣會(huì)導(dǎo)致群體發(fā)散.除此之外，還容易出現(xiàn)搜索精度低，結(jié)果是局部最優(yōu)解的結(jié)果，我們稱(chēng)之為早熟收斂現(xiàn)象［4，5］.

基于克隆選擇的PSO算法的原理:將克隆選擇機(jī)制融入粒子群算法中，最開(kāi)始隨機(jī)產(chǎn)生一些粒子;然后算出各個(gè)粒子的適應(yīng)度值，并且比較得到的適應(yīng)度值，根據(jù)優(yōu)劣甄選出個(gè)體最優(yōu)解pbest和全局最優(yōu)解gbest;再來(lái)把算法中的粒子看作是克隆選擇算法中的抗體并且算出它的親和度.克隆復(fù)制我們挑選出的親和度高的抗體(粒子)，再變異那些復(fù)制后的抗體(粒子);最后更新粒子的位置和速度.

算法設(shè)計(jì):

(1)初始化

隨機(jī)初始化整個(gè)種群中的各個(gè)微粒的原始位置和速度.

(2)適應(yīng)度

計(jì)算各個(gè)微粒的適應(yīng)度值并且比較得到的適應(yīng)度值，根據(jù)它的優(yōu)劣甄選出個(gè)體最優(yōu)解pbest和全局最優(yōu)解gbest，判斷是否滿足條件，若滿足結(jié)束條件，則停止運(yùn)行并輸出結(jié)果.否則繼續(xù).

(3)計(jì)算抗體(粒子)的偏好度.

由上所得的粒子的位置、速度、適應(yīng)度等值，把第i個(gè)粒子的偏好力定義如下:

第i個(gè)微粒與全局最優(yōu)微粒在第j維上的位置分別由pij與gbestj表示.因此，粒子的適應(yīng)度值越小，粒子與與最優(yōu)解離得越遠(yuǎn)，所以它的偏好力就越小，相反則越大.

(4)克隆復(fù)制

在整個(gè)群體中，根據(jù)上述所得到的微粒偏好力的大小對(duì)各個(gè)粒子執(zhí)行克隆操作，這種操作要求是獨(dú)立的、按比例的.第i個(gè)粒子被克隆(復(fù)制)的數(shù)量為

當(dāng)中n是種群大小.因此，粒子的偏好力越大就越優(yōu)良，會(huì)克隆(復(fù)制)出更多的子微粒，以此來(lái)保存比較優(yōu)秀的個(gè)體.

(5)變異

對(duì)克隆(復(fù)制)的各個(gè)子微粒，要判斷是否執(zhí)行克隆高頻變異，判斷的依據(jù)為概率大小.進(jìn)化中加入克隆高頻變異，提供了粒子飛出局部極值的可能.

(6)克隆選擇

為了避免算法退化，我們需要混合父代粒子與子代粒子.粒子經(jīng)過(guò)克隆復(fù)制、變異后，從它的的父代粒子與子代粒子中，挑選出一個(gè)適應(yīng)度值最高的最優(yōu)粒子作為下一代粒子.

(7)粒子更新

更新粒子的速度和位置.

(8)判斷

沒(méi)有達(dá)到結(jié)束條件，返回步驟2.達(dá)到結(jié)束條件，算法結(jié)束.

3 仿真實(shí)例

以典型的四相位信號(hào)交叉口為例(信號(hào)控制方案如圖1)，對(duì)其相位的有效綠燈時(shí)間進(jìn)行配時(shí)計(jì)算.假設(shè)交叉口的車(chē)流有關(guān)數(shù)據(jù)如表1.

表1 交通狀態(tài)順暢、繁忙時(shí)各方向交通流數(shù)據(jù)

參數(shù)設(shè)置如下:初始群體規(guī)模為20，最大迭代次數(shù)為500 次，慣性權(quán)值為0.65，加速常數(shù)為 c1=c2=1.5.

其中，交叉口各相位的最小和最大有效綠燈時(shí)間定為10s和90s，最大周期時(shí)間為180s，總的損失時(shí)間為24s.

采用webster算法和基于克隆選擇的粒子群算法求解信號(hào)配時(shí)方案.計(jì)算結(jié)果整理得到表2.

表2 兩種算法的優(yōu)化效果比較

4 結(jié)論

從結(jié)果可以看出，提出的基于克隆選擇的粒子群算法更能實(shí)現(xiàn)各狀態(tài)下減少停車(chē)次數(shù)和延誤，增大通行能力的目標(biāo).將本算法與webster算法得出的結(jié)果進(jìn)行比較，車(chē)輛的停車(chē)次數(shù)、延誤和通行能力等指標(biāo)都得到改善，而且針對(duì)交通流的到達(dá)規(guī)律對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化求解，從而得出最優(yōu)交通信號(hào)配時(shí)方案，使各個(gè)方向到達(dá)的交通流能夠在最合理的周期時(shí)間和最恰當(dāng)?shù)南辔粌?nèi)順利地通過(guò)交叉路口，滿足實(shí)際的交通控制需求.在算法性能方面，該算法在標(biāo)準(zhǔn)粒子群算法中融合了克隆選擇算法思想，增加了種群的多樣性，加快算法收斂速度，提高最優(yōu)解的精度.

［1］李曉娜.單交叉口自適應(yīng)控制方法的研究［D］.大連:大連理工大學(xué)碩士學(xué)位論文，2006.

［2］萬(wàn)偉，陳鋒.基于遺傳算法的單交叉口信號(hào)優(yōu)化控制［J］.計(jì)算機(jī)工程，2007，(16):217 －219.

［3］顧懷中.交叉口交通信號(hào)配時(shí)模擬退火全局優(yōu)化算法［J］.東南大學(xué)學(xué)報(bào)(自然科學(xué)版)，1998，(3):68 －72.

［4］陳群，晏克非.基于遺傳算法的城市交叉口實(shí)時(shí)信號(hào)控制研究［J］.交通與計(jì)算機(jī)，2005，(1):15 －18.

［5］劉麗玨，蔡自興.基于克隆選擇的粒子群優(yōu)化算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，(9):1708 －1710.

U41

A

1008－4681(2012)02－0069－03

2011－11－08

曹娟娟(1987－)，女，重慶人，長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院碩士生.研究方向:交通運(yùn)輸規(guī)劃與管理.

(責(zé)任編校:晴川)