劉 鵬 闞亞斌 聶 鑫

（海軍大連艦艇學(xué)院 大連 116018）

1 引言

目前在交通流的研究中有兩個(gè)主要的研究?jī)?nèi)容：一個(gè)是從宏觀的角度上使用圖論等方法對(duì)交通流進(jìn)行模擬優(yōu)化；另一個(gè)是從微觀的角度上，以交通流中的車輛作為基本研究對(duì)象。細(xì)胞自動(dòng)機(jī)（Cellular Automata，CA）離散和并行的特征，與微觀角度上的交通流非常相似，再由于細(xì)胞自動(dòng)機(jī)能夠模擬復(fù)雜系統(tǒng)的潛能，所以細(xì)胞自動(dòng)機(jī)被廣泛地應(yīng)用于交通流的研究中。其中，由Biham，Middleton和Levine提出的二維交通流理想模型（BML模型）［2］已成為研究城市路網(wǎng)結(jié)構(gòu)中交通流特性的重要基礎(chǔ)。在 BML 模型之上，Nagatani［3］研究了車輛的非對(duì)稱分布情況，F(xiàn)ukui等［4］則研究了車輛非勻速行駛的狀況。此外，人們還提出了一些其它改進(jìn)策略，來(lái)模擬更為切合實(shí)際的交通行為。

演化算法（Evolutionary Algorithms，EA）［5］近年來(lái)已成為工程優(yōu)化和計(jì)算機(jī)智能研究的一個(gè)熱點(diǎn)。文獻(xiàn)［6～7］等將演化算法用于對(duì)交通流模型的優(yōu)化，進(jìn)行城市交通流控制的分析與預(yù)測(cè)。然而，基于軟件的交通流模擬與演化優(yōu)化方式普遍效率低下，極大地限制了交通流模型的實(shí)時(shí)應(yīng)用能力。這主要是因?yàn)槠鋵?duì)細(xì)胞群體的演化采用的是串行處理方式，這樣會(huì)在演化算法的適應(yīng)值評(píng)價(jià)階段消耗大量的時(shí)間。

本文正是從細(xì)胞自動(dòng)機(jī)模型的內(nèi)在并行性角度出發(fā)，對(duì)基于演化硬件（Evolvable Hardware，EHW）［8］的交通流模型自適應(yīng)優(yōu)化進(jìn)行了研究。利用現(xiàn)場(chǎng)可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）［9］極大地提高了細(xì)胞自動(dòng)機(jī)的演化效率，并在演化硬件平臺(tái)上，將BML模型表示成自適應(yīng)、可重構(gòu)的硬件電路模塊，通過軟硬件協(xié)同演化目標(biāo)電路的配置串，實(shí)現(xiàn)BML模型的在線演化。同時(shí)對(duì)該模型進(jìn)行了改進(jìn)，通過實(shí)現(xiàn)交通燈信號(hào)依據(jù)實(shí)時(shí)車流狀況進(jìn)行自適應(yīng)調(diào)節(jié)，表明了將其用于智能交通控制領(lǐng)域的可行性［10］。

2 細(xì)胞自動(dòng)機(jī)交通流模型

2.1 二維交通流模型

二維交通流模型中最典型的就是BML模型。BML模型是1992年美國(guó)學(xué)者Biham，Middleton和Levine提出的一個(gè)細(xì)胞自動(dòng)機(jī)交通流模型。該模型通過模擬交通燈，控制車輛的移動(dòng)。如圖1所示，標(biāo)1的格子表示東西向車輛，標(biāo)2的格子表示南北向車輛，標(biāo)0的格子表示當(dāng)前時(shí)刻該位置無(wú)車輛。

圖1 BML模型

BML模型的演化規(guī)則是（如圖2）：奇數(shù)時(shí)刻，東西方向?yàn)榫G燈，南北方向?yàn)榧t燈，東西方向的車輛如果前進(jìn)方向的單元格是空的，則可以向前移動(dòng)一格；偶數(shù)時(shí)刻，東西方向?yàn)榧t燈，南北方向?yàn)榫G燈，南北方向的車輛如果前進(jìn)方向的單元格是空的，則可以向前移動(dòng)一格。即奇數(shù)時(shí)刻?hào)|西方向的車輛在其所處的行按一維細(xì)胞自動(dòng)機(jī)交通流模型規(guī)則移動(dòng)，偶數(shù)時(shí)刻南北方向的車輛在其所處的列按一維細(xì)胞自動(dòng)機(jī)交通流模型移動(dòng)。循環(huán)邊界的BML模型模擬結(jié)果表明當(dāng)車輛密度大于某一臨界值時(shí)，交通會(huì)完全阻塞（如圖3）。

圖2 BML模型的演化規(guī)則

圖3 BML模型（100×100，車輛密度50%）

2.2 改進(jìn)的交通流模型

傳統(tǒng)BML模型適合理論研究，根據(jù)實(shí)際應(yīng)用情況，對(duì)傳統(tǒng)BML模型需要做一些應(yīng)用上的改進(jìn)。

1）傳統(tǒng)的BML模型采用的是循環(huán)邊界，但是實(shí)際生活中某一區(qū)域內(nèi)的車輛不是循環(huán)運(yùn)動(dòng)的，絕大多數(shù)的車輛只是通過該區(qū)域，交通堵塞并不是BML模型中的循環(huán)等待。所以本文的模型中假設(shè)邊界固定為0，即假設(shè)下一時(shí)刻沒有車輛加入該區(qū)域，而且脫離該區(qū)域的車輛都能加速離開，即不對(duì)區(qū)域內(nèi)的車輛產(chǎn)生堵塞影響。

2）傳統(tǒng)的BML模型都是根據(jù)時(shí)刻的奇偶性判斷執(zhí)行什么規(guī)則，保證了各條道路的通行時(shí)間的公平分配，但是假如相交的道路車流量不同，同樣的控制時(shí)間，車流量大的道路上交通壓力更大，車輛的總體堵塞時(shí)間也更長(zhǎng)，對(duì)交通整體效率而言是不利的。應(yīng)該根據(jù)車流量來(lái)決定如何控制交通。

基于上述假設(shè)，細(xì)胞自動(dòng)機(jī)交通流模型的問題就是：在某種全局狀態(tài)下，采取什么樣的控制措施（即紅綠等各控制多長(zhǎng)時(shí)間），能夠使得該細(xì)胞自動(dòng)機(jī)的全局狀態(tài)變?yōu)槿?而經(jīng)過的時(shí)間最短（即細(xì)胞自動(dòng)機(jī)的迭代次數(shù)最少）。

該問題與細(xì)胞自動(dòng)機(jī)密度分類問題很相似，鑒于演化計(jì)算在密度分類問題上的良好表現(xiàn)，本文采用演化計(jì)算的方法優(yōu)化該問題。

圖4 二維細(xì)胞自動(dòng)機(jī)交通流模型邊界

3 自適應(yīng)交通控制方法

3.1 演化交通流模型

我們采用遺傳算法來(lái)優(yōu)化交通流模型，遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。算法從任意初始化群體出發(fā)，通過選擇、交叉和變異操作，在群體中一代一代地進(jìn)入到搜索空間中越來(lái)越好的區(qū)域，直至抵達(dá)最優(yōu)解點(diǎn)，其本質(zhì)是一種求解問題的高效并行搜索方

法［11］。

在遺傳算法求解的過程中，適應(yīng)值計(jì)算通常被認(rèn)為是最耗時(shí)的部分，于是我們將這一部分在硬件上實(shí)現(xiàn)。配置串種群的生成和遺傳操作部分使用軟件方式實(shí)現(xiàn)。所以，整個(gè)算法優(yōu)化過程使用了軟硬件協(xié)同演化的設(shè)計(jì)思想，種群中的每一個(gè)染色體，都被下載到硬件上，計(jì)算其適應(yīng)值，然后反饋給軟件部分進(jìn)行遺傳操作，直至滿足搜索條件，找到最優(yōu)的染色體。這個(gè)染色體就代表了在當(dāng)前道路車流狀況下，最優(yōu)的紅綠燈信號(hào)配時(shí)策略。

算法實(shí)現(xiàn)的步驟如下：

1）隨機(jī)生成配置串種群。

2）將配置串下載到FPGA，連同已經(jīng)做好的Rule_we和Rule_ns演化規(guī)則模塊，生成電路。

3）輸入細(xì)胞種群的初始狀態(tài)。

4）計(jì)算此配置串的適應(yīng)值，并返回結(jié)果。繼續(xù)評(píng)價(jià)這一代種群中的下一個(gè)個(gè)體。

5）當(dāng)種群中的個(gè)體全部評(píng)價(jià)完畢后，通過一系列的遺傳操作，生成新一代配置串種群，然后再執(zhí)行第2）步，直至滿足遺傳代數(shù)，找到最優(yōu)解。

遺傳算法的目的是找到最優(yōu)的紅綠燈信號(hào)時(shí)間配置，使當(dāng)前狀態(tài)下的所有車輛能盡快地全部離開。這里，我們不考慮使某一輛車離開該路段的時(shí)間長(zhǎng)短，而是考慮全體車輛，也就是說(shuō)，使得細(xì)胞格點(diǎn)矩陣的狀態(tài)全部演化為0的時(shí)間越短越好，所以定義適應(yīng)值評(píng)價(jià)函數(shù)F：

式（3）中的f為細(xì)胞自動(dòng)機(jī)的演化規(guī)則，StN表示t時(shí)刻i細(xì)胞的鄰居細(xì)胞狀態(tài)，求使得對(duì)于所有的1≤i≤N×N，上式成立的t，即為該配置串的適應(yīng)值。且取種群中t值最小的個(gè)體，即為當(dāng)前最優(yōu)配置串［12］。

3.2 算法流程

演化計(jì)算的設(shè)計(jì)：

1）編碼方式：以規(guī)則執(zhí)行順序作為個(gè)體，0表示東西向車輛通行，1表示南北向車輛通行，采用二進(jìn)制的編碼方式，種群存儲(chǔ)與二維矩陣popu中，第一維是種群大小，第二維是每個(gè)個(gè)體占的多少個(gè)32位整數(shù)；

2）適應(yīng)值評(píng)價(jià)方法：以迭代的次數(shù)作為個(gè)體的適應(yīng)值，存儲(chǔ)于矩陣fitness中；

3）選擇策略：采用輪盤賭的方式選擇父體；

4）控制參數(shù)選?。悍N群規(guī)模：popusize，雜交概率：pc，變異概率：pm；

5）遺傳算子設(shè)計(jì)：雜交采用兩點(diǎn)雜交，單點(diǎn)變異；

6）終止條件確定：每次演化的最大代數(shù)為maxage，運(yùn)行代數(shù)age超過最大代數(shù)后演化終止；

7）種群替換策略：每次保留keepsize個(gè)最優(yōu)個(gè)體，每代產(chǎn)生其余popusize-keepsize個(gè)個(gè)體，合并成為新種群。

演化計(jì)算算法步驟：

Step0將待演化的細(xì)胞自動(dòng)機(jī)的初態(tài)寫入TFCCA中，寫入傳統(tǒng)規(guī)則（即規(guī)則為0x55555555）計(jì)算傳統(tǒng)控制方法需要的時(shí)間，轉(zhuǎn)Step1；

Step1初始化種群。隨機(jī)產(chǎn)生popusize個(gè)個(gè)體，因?yàn)橐趥鹘y(tǒng)規(guī)則的基礎(chǔ)上優(yōu)化，而且其具有一定的合理性，所以在初始化種群中應(yīng)該包含該個(gè)體。初始化age=0，轉(zhuǎn)Step2；

Step2計(jì)算種群適應(yīng)值，轉(zhuǎn)Step3；

Step3種群排序（按適應(yīng)值降序），轉(zhuǎn)Step4；

Step4 age是否大于maxage？是，轉(zhuǎn)Step6；否，設(shè)置臨時(shí)種群的個(gè)體數(shù)tpsize=0，轉(zhuǎn)Step5；

Step5產(chǎn)生下一代。

Step5.1 tpsize＞=popusize-keepsize？ 是 ，轉(zhuǎn)Step5.5；否，轉(zhuǎn)step5.2；

Step5.2隨機(jī)產(chǎn)生一個(gè)0到1之間的數(shù)r，如果r＜pc，執(zhí)行雜交操作，

轉(zhuǎn)Step5.3；如果r＞1-pm，執(zhí)行變異操作，轉(zhuǎn)Step5.4；

Step5.3按輪盤賭方式選擇兩不同的父體，隨機(jī)產(chǎn)生的兩個(gè)數(shù)（0～indvsize-1）決定雜交位置，對(duì)這兩者之間的編碼互換，將兩個(gè)新個(gè)體插入到臨時(shí)種群中，tpszie=tpsize+2，轉(zhuǎn)Step5.1；

Step5.4按輪盤賭的方式選擇一個(gè)父體，隨機(jī)產(chǎn)生一個(gè)數(shù)（0～indvsize-1）作為變異位置，將變異后得到的個(gè)體插入臨時(shí)種群中，tpsize=tpsize+1，轉(zhuǎn)Step5.1；

Step5.5將臨時(shí)種群中的個(gè)體替換原種群中第keepsize個(gè)之后的個(gè)體，計(jì)算這些新個(gè)體的適應(yīng)值，age=age+1，轉(zhuǎn)Step3；

Step6結(jié)束，將種群popu中第一個(gè)個(gè)體輸出。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

演化計(jì)算基本參數(shù)設(shè)置：

演化計(jì)算的種群規(guī)模為50，雜交概率為0.7，變異概率為0.2，每代保留上代10最優(yōu)個(gè)體，最大代數(shù)200。因?yàn)閷?shí)驗(yàn)的目的是與傳統(tǒng)執(zhí)行順序比較，所以優(yōu)秀的個(gè)體應(yīng)該執(zhí)行時(shí)間不會(huì)大于傳統(tǒng)規(guī)則的執(zhí)行時(shí)間，所以實(shí)驗(yàn)中演化計(jì)算個(gè)體的編碼長(zhǎng)度（indvsize）選擇和傳統(tǒng)規(guī)則執(zhí)行相同時(shí)間的長(zhǎng)度（在演化計(jì)算的Step0步已經(jīng)獲得該值）。超過該值的部分沒有任何作用，發(fā)生在該部分內(nèi)雜交和變異中對(duì)結(jié)果不產(chǎn)生影響，如果產(chǎn)生影響，那說(shuō)明該個(gè)體的執(zhí)行時(shí)間比執(zhí)行傳統(tǒng)規(guī)則所需的時(shí)間更多，為避免浪費(fèi)評(píng)價(jià)時(shí)間，當(dāng)個(gè)體執(zhí)行時(shí)間超過傳統(tǒng)規(guī)則執(zhí)行時(shí)間時(shí)，立即結(jié)束評(píng)價(jià)。

實(shí)驗(yàn)設(shè)計(jì)：

分析車輛不同密度（0.1，0.3，0.5，0.7，0.9，1）和不同橫縱車輛比（1∶1，1∶2，1∶3）情況下，演化計(jì)算對(duì)交通流細(xì)胞自動(dòng)機(jī)演化硬件的優(yōu)化效率。每種車輛密度和橫縱車輛比下，隨機(jī)產(chǎn)生100個(gè)細(xì)胞自動(dòng)機(jī)的初態(tài)進(jìn)行測(cè)試。

4.2 結(jié)果與分析

實(shí)驗(yàn)結(jié)果如表1。

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

從表1中可以看出，在同等的車輛密度情況下，車輛分布越不平衡，演化效果越明顯。這是因?yàn)閭鹘y(tǒng)的0，1規(guī)則交替執(zhí)行順序是給兩個(gè)方向的車輛分配同樣的通行時(shí)間，這樣的時(shí)間分配給車流量大的道路壓力較大，而車流量小的道路浪費(fèi)了通行時(shí)間，從而導(dǎo)致交通整體效率下降，而演化出的規(guī)則執(zhí)行順序則能給車流量大的方向安排更多的執(zhí)行時(shí)間，從而使整體優(yōu)化。

車輛密度從0.1增長(zhǎng)到0.5的過程中，同等橫縱車輛比下，車輛密度越大，演化效果越明顯。這是因?yàn)檐嚵髁亢苄〉那闆r下，車輛堵塞情況少，按不同的執(zhí)行次序?qū)嚵鬏v影響不大。

車輛密度從0.7增長(zhǎng)到1的過程中，在同等橫縱車輛比下，車輛密度越大，演化效果越差。這是因?yàn)檐嚵鬏v很大時(shí)，堵塞情況非常嚴(yán)重，按不同的執(zhí)行順序并不能有效減少車輛的堵塞。

圖5是三種橫縱車輛比下演化計(jì)算在各種車輛密度下的優(yōu)化程度比較。從圖5中可以看出，演化計(jì)算優(yōu)化的效果在車輛密度為0.5左右達(dá)到峰值，而這也是在循環(huán)邊界中堵塞的臨界密度。

圖5 優(yōu)化比例分布

演化計(jì)算作為一種通用的算法，它的搜索能力很強(qiáng)，其它算法即使能進(jìn)行更大程度的優(yōu)化但是優(yōu)化程度的走勢(shì)與演化計(jì)算是相同的。根據(jù)以上的實(shí)驗(yàn)結(jié)果和分析我們可以推廣出一個(gè)一般的結(jié)論：車流量小的時(shí)候，堵塞情況非常少，交通調(diào)節(jié)不明顯，當(dāng)車流量非常大的時(shí)候，堵塞情況非常嚴(yán)重，交通調(diào)節(jié)效果也不明顯。在車流量為某個(gè)值附近進(jìn)行正確的交通調(diào)節(jié)才可以發(fā)揮交通調(diào)節(jié)的最大作用。

5 結(jié)語(yǔ)

本文提出了一種在實(shí)際生活中有現(xiàn)實(shí)指導(dǎo)意義的改進(jìn)的BML模型。將BML模型通過演化計(jì)算演化該細(xì)胞自動(dòng)機(jī)，尋找最好的交通控制規(guī)則。實(shí)驗(yàn)結(jié)果表明，演化計(jì)算確實(shí)對(duì)交通控制起到了優(yōu)化的作用，而且優(yōu)化效果呈現(xiàn)出一定的規(guī)律性。通過分析還可以得出一個(gè)一般的結(jié)論：車流量小的時(shí)候，堵塞情況非常少，交通調(diào)節(jié)不明顯，當(dāng)車流量非常大的時(shí)候，堵塞情況非常嚴(yán)重，交通調(diào)節(jié)效果也不明顯。在車流量為某個(gè)值附近進(jìn)行正確的交通調(diào)節(jié)才可以發(fā)揮交通調(diào)節(jié)的最大作用。本章的設(shè)計(jì)系統(tǒng)在設(shè)計(jì)驗(yàn)證方面起到了作用，證明了基于細(xì)胞自動(dòng)機(jī)演化硬件的交通控制系統(tǒng)可以有效地提高交通控制能力，在系統(tǒng)的實(shí)際應(yīng)用中，還需要提供車流量采集等設(shè)備才能完整地形成一個(gè)實(shí)用的系統(tǒng)。