張麗霞　唐澤

摘 要： 智能交通燈是智能交通系統(tǒng)的重要組成部分，它能有效增加道路的通行能力，改善交通狀況。采用道路各相位在一個(gè)周期內(nèi)滯留的車(chē)輛數(shù)作為識(shí)別判據(jù)，將遺傳算法應(yīng)用到交通燈控制中，并且利用FPGA的并行計(jì)算優(yōu)勢(shì)，實(shí)現(xiàn)算法的硬件化，減少算法的運(yùn)行時(shí)間。交通燈整體的實(shí)現(xiàn)基于Nios Ⅱ嵌入式處理器。實(shí)驗(yàn)結(jié)果表明，交通燈能根據(jù)車(chē)流量實(shí)現(xiàn)智能配時(shí)，基于FPGA的遺傳算法比基于傳統(tǒng)計(jì)算機(jī)的遺傳算法在運(yùn)行速度上有很大的提高，使得一些大規(guī)模、復(fù)雜的問(wèn)題有了解決的可能性。

關(guān)鍵詞： 智能交通燈； 現(xiàn)場(chǎng)可編程門(mén)陣列； 遺傳算法； Nios Ⅱ

中圖分類(lèi)號(hào)： TN965+.71?34； TP332.3 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）15?0153?05

Application of FPGA?based genetic algorithm in traffic control

ZHANG Lixia1， TANG Ze2

（1. Department of Information Engineering， Sichuan Vocational and Technical College of Communications， Chengdu 611130， China；

2. College of Information Science and Technology， Southwest Jiaotong University， Chengdu 610000， China）

Abstract： Intelligent traffic light is an important part in intelligent transportation system， it can increase road traffic capacity and improve traffic situation effectively. Taking the vehicle number of each direction detained in a period as recognition criterion， genetic algorithm （GA） is applied in traffic lights control system. The advantage of FPGA parallel computing is applied to achieving the algorithm′s hardware implementation， which can reduce running time of the algorithm. The implementation of the integral traffic light system is based on Nios II embedded processor. The experimental results show that traffic light system can realize intelligent timing according to traffic flow. FPGA?based GA has great improvement in operating speed in comparison with the GA which is based on traditional computer. It makes the problems of large scale and complex have solved possibility.

Keywords： intelligent traffic light； FPGA； genetic algorithm； Nios Ⅱ

0 引 言

隨著機(jī)動(dòng)車(chē)數(shù)量的快速增長(zhǎng)，道路的擁擠程度也隨之增加。單一的交通信號(hào)燈控制方法往往難以適應(yīng)復(fù)雜多變的交通流，造成空等、浪費(fèi)時(shí)間等現(xiàn)象，影響道路的通行能力；所以智能交通燈的出現(xiàn)勢(shì)在必行[1]。本文采用在道路叉口各相位單位時(shí)間內(nèi)到達(dá)和離開(kāi)車(chē)輛數(shù)的差來(lái)作為識(shí)別判據(jù)，結(jié)合道路飽和度，提出感應(yīng)控制和基于遺傳算法的自適應(yīng)控制。遺傳算法廣泛應(yīng)用于智能控制中，但大部分的應(yīng)用都采用具有馮諾依曼或哈弗結(jié)構(gòu)的計(jì)算機(jī)去實(shí)現(xiàn)，因?yàn)檫@兩種結(jié)構(gòu)是串行計(jì)算的原因，遺傳算法在運(yùn)行時(shí)間上往往不是很理想，當(dāng)面臨一些大規(guī)模、復(fù)雜問(wèn)題時(shí)，往往導(dǎo)致計(jì)算無(wú)法實(shí)現(xiàn)[2]。而現(xiàn)場(chǎng)可編程門(mén)陣列（Field Programmable Gate Array，F(xiàn)PGA）的出現(xiàn)及它的并行計(jì)算優(yōu)勢(shì)，使得基于FPGA的遺傳算法在運(yùn)行時(shí)間上會(huì)有數(shù)量級(jí)的提高[3]。這樣不僅提高了系統(tǒng)的性能，也增加了遺傳算法的實(shí)用性。交通燈整體基于Altera公司Nios Ⅱ嵌入式處理器的SoPC（System on a Programmable Chip）方案，即把用戶(hù)定義的遺傳算法邏輯模塊與Nios Ⅱ處理器聯(lián)合構(gòu)成SoPC系統(tǒng)。Nios Ⅱ處理器具有完全可定制和重新配置的特性，可根據(jù)不同的應(yīng)用場(chǎng)合添加制定各種外設(shè)、存儲(chǔ)器和接口等設(shè)備，靈活性強(qiáng)，升級(jí)換代的成本低，利于產(chǎn)品的生存[4]。

1 遺傳算法的硬件實(shí)現(xiàn)

遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。遺傳算法的基本思想是系統(tǒng)維持一個(gè)種群，種群由一組染色體構(gòu)成，染色體是一組數(shù)據(jù)結(jié)構(gòu)，它表示所求解問(wèn)題的一個(gè)可能解。種群通過(guò)競(jìng)爭(zhēng)和受控變異不斷進(jìn)化，從而得到越來(lái)越優(yōu)的解[5]。遺傳算法的求解過(guò)程[6]見(jiàn)圖1。

圖1 遺傳算法流程圖

1.1 遺傳算法的運(yùn)行參數(shù)

遺傳算法在本文中所用到的參數(shù)見(jiàn)表1。

表1 遺傳算法的運(yùn)行參數(shù)

[種群規(guī)模＼&基因長(zhǎng)度＼&遺傳代數(shù)＼&交叉概率＼&變異概率＼&32＼&24＼&127＼&0.875＼&0.070 3＼&]

1.2 遺傳算法的硬件結(jié)構(gòu)

由于采用VHDL語(yǔ)言一次性編寫(xiě)遺傳算法的工作量太大，工程太復(fù)雜，也容易出錯(cuò)；所以本文對(duì)遺傳算法編寫(xiě)的主要思想是把遺傳算法看作一個(gè)電路，而這個(gè)電路由若干的子模塊構(gòu)成。這樣只要確定每個(gè)子模塊的工作順序就可以使整個(gè)遺傳算法正常工作。這樣把遺傳算法拆解為一個(gè)個(gè)的子模塊不僅簡(jiǎn)化了程序編寫(xiě)的難度，而且在算法升級(jí)改進(jìn)時(shí)只需要更改其中的某一個(gè)子模塊，升級(jí)的成本更低。從遺傳算法的實(shí)現(xiàn)原理著手，基于FPGA的遺傳算法主要包括初始化模塊、隨機(jī)數(shù)模塊、適應(yīng)度模塊、存儲(chǔ)模塊、選擇模塊、交叉模塊、變異模塊、地址產(chǎn)生模塊、地址選通模塊、輸出模塊和控制模塊等。硬件框圖如圖2所示。

1.3 算法的工作原理

基于FPGA的遺傳算法的工作流程主要有以下幾步：

（1） 初始化模塊最先開(kāi)始工作，它先隨機(jī)的產(chǎn)生一個(gè)種群和種群對(duì)應(yīng)的地址。當(dāng)種群個(gè)體達(dá)到預(yù)定個(gè)數(shù)后，個(gè)體選通模塊只選通變異模塊產(chǎn)生的個(gè)體，這樣在結(jié)果上看來(lái)初始化模塊已停止工作。

圖2 基于FPGA的遺傳算法框圖

（2） 個(gè)體的選通。從圖3的工作流程可以看出，變異模塊也會(huì)產(chǎn)生新的個(gè)體，為了避免和初始化產(chǎn)生的個(gè)體相沖突，個(gè)體選擇模塊根據(jù)一定的時(shí)序約束，有序的對(duì)變異模塊和初始化模塊產(chǎn)生的個(gè)體進(jìn)行選通。

圖3 基于FPGA的遺傳算法工作流程

（3） 地址選通。存儲(chǔ)器中每個(gè)存儲(chǔ)的數(shù)據(jù)都有一個(gè)對(duì)應(yīng)的存儲(chǔ)地址，這樣方便數(shù)據(jù)的讀和寫(xiě)。首先分析基于FPGA的遺傳算法中都有哪些地址：第一，初始化種群時(shí)對(duì)初始化個(gè)體的存儲(chǔ)地址；第二，變異模塊產(chǎn)生的個(gè)體在存儲(chǔ)時(shí)的地址；第三，選擇模塊從存儲(chǔ)器中讀取數(shù)據(jù)時(shí)的地址。由以上三點(diǎn)可以看出，為了各地址的不沖突，地址選通模塊會(huì)根據(jù)工作狀態(tài)有序地選通地址，即當(dāng)其中一個(gè)地址工作時(shí)，禁用其他兩地址。

（4） 適應(yīng)度值計(jì)算模塊。適應(yīng)度的計(jì)算是遺傳算法中的重要部分，它代表所求解問(wèn)題的數(shù)學(xué)模型。

（5） 遺傳操作。遺傳操作是遺傳算法的核心部分，它包括選擇、交叉和變異操作。經(jīng)過(guò)遺傳操作后會(huì)產(chǎn)生全新的適應(yīng)度值更優(yōu)的個(gè)體。

（6） 輸出。當(dāng)達(dá)到進(jìn)化代數(shù)后，輸出最優(yōu)個(gè)體。

圖3虛框部分表示遺傳算法一次完整的遺傳操作所經(jīng)歷的步驟。

1.4 算法的實(shí)現(xiàn)及測(cè)試

遺傳算法采用VHDL語(yǔ)言編程，在Quartus Ⅱ軟件里進(jìn)行仿真。所用到的器件為Altera公司的Cyclone Ⅲ EP3C5E144C8。為了測(cè)試算法的正確性，采用下面的測(cè)試函數(shù)進(jìn)行仿真，測(cè)試函數(shù)如下所示：

[f1（x）=50 000+50x-x2，0≤x≤255]

[ f2（x）=100-n=13（-x）n， 0≤x≤255]

[ f3（x）=n=13x2n， 0≤xn≤255]

選取的函數(shù)是幾個(gè)比較基本的、容易驗(yàn)證的求極值函數(shù)，常常用于遺傳算法的性能測(cè)試中[3]。

表2所示為三個(gè)函數(shù)的仿真結(jié)果。軟件實(shí)現(xiàn)的遺傳算法采用C語(yǔ)言編寫(xiě)，運(yùn)行在主頻為2.4 GHz，內(nèi)存1 GB的微機(jī)上，通過(guò)Microsoft VC++ 6.0平臺(tái)仿真實(shí)現(xiàn)。從表2的結(jié)果可以看出，硬件實(shí)現(xiàn)的遺傳算法在運(yùn)行速度上比軟件快3個(gè)數(shù)量級(jí)，且能得到和軟件相近的結(jié)果。其中[f3（x）]的仿真截圖見(jiàn)圖4。

表2 仿真測(cè)試結(jié)果

[函數(shù)＼&實(shí)現(xiàn)方式＼&最優(yōu)個(gè)體值＼&適應(yīng)度值＼&運(yùn)行時(shí)間＼&工作頻率＼&[f1（x）]＼&軟件＼&25＼&55 625＼&0.5 s＼&2.4 GHz＼&硬件＼&25＼&55 625＼&646.4 μs＼&25 MHz ＼&[f2（x）]＼&軟件＼&254＼&13 475 464＼&0.9 s＼&2.4 GHz＼&硬件＼&255＼&16 516 705＼&646 μs＼&25 MHz＼&[f3（x）]＼&軟件＼&16 580 607＼&193 600＼&1.2 s＼&2.4 GHz＼&硬件＼&16 383 999＼&191 035＼&1.301 ms＼&25 MHz＼&]

圖4 [f3（x）]的仿真截圖

2 交通燈控制系統(tǒng)

現(xiàn)在大部分交通信號(hào)燈都采用固定周期控制，難以滿(mǎn)足復(fù)雜多變的交通狀況，造成資源浪費(fèi)[6]。本文提出基于道路飽和度的感應(yīng)控制和自適應(yīng)控制，這樣就能根據(jù)道路在每個(gè)時(shí)刻具體的交通流去分配控制方法?；赩HDL的計(jì)數(shù)模塊用于對(duì)一個(gè)周期內(nèi)各相位到達(dá)和離開(kāi)車(chē)輛數(shù)的計(jì)數(shù)。交通燈控制系統(tǒng)的整體框圖見(jiàn)圖5。

2.1 交通燈的模型及參數(shù)

信號(hào)相位指在一個(gè)交叉口某個(gè)方向的交通流（或幾個(gè)方向交通流的組合）同時(shí)得到的通行權(quán)或被分配得到這些通行權(quán)的時(shí)間帶。以交叉口的一條進(jìn)道[j]為例，將相位[i]實(shí)際進(jìn)入道口[j]的交通量[qij]與進(jìn)口道[j]的飽和流量[sj]（交叉口上游有充分的需求量時(shí)，單位綠燈時(shí)間的最大通過(guò)數(shù)）的比值稱(chēng)為相位[i]該進(jìn)口道的飽和度[λij，]每個(gè)相位[i]所控制的交叉口各進(jìn)口道飽和度的最大值稱(chēng)為相位[i]的飽和度[λi。]交叉口所有相位的飽和度之和稱(chēng)為該交叉口的飽和度[7][λ]。

圖5 交通燈系統(tǒng)框圖

圖6 十字路口示意圖

十字路口的車(chē)流走向示意圖見(jiàn)圖6，車(chē)輛檢測(cè)器分上游線(xiàn)圈和下游線(xiàn)圈[8]，其安裝距離根據(jù)不同道路情況而定。一般把十字路口分為4個(gè)相位，見(jiàn)圖7。

圖7 各相位示意圖

2.2 交通燈控制方法

交通燈的工作狀態(tài)一共有3個(gè)，工作流程主要有以下幾步：

（1） 根據(jù)車(chē)流量計(jì)算每個(gè)相位的飽和度，當(dāng)飽和度[λ]在（0，0.8）這個(gè)區(qū)間時(shí)，執(zhí)行感應(yīng)控制[9]，因?yàn)轱柡投仍谛∮?.8時(shí)道路不是很擁擠，感應(yīng)控制一般能滿(mǎn)足道路交通狀況。感應(yīng)控制分為半感應(yīng)控制和全感應(yīng)控制[9]。用主、次干道車(chē)流量是否相差大這一標(biāo)準(zhǔn)來(lái)判斷是半感應(yīng)模式還是全感應(yīng)模式。設(shè)主干道的車(chē)流量為[m，]次干道的車(chē)流量為[n，]若[n

感應(yīng)控制的原理如圖8所示，當(dāng)主干道的綠時(shí)到達(dá)[Tmin1]時(shí)，通過(guò)車(chē)輛感應(yīng)器判斷次干道是否有車(chē)輛進(jìn)入，如果有則次干道的綠燈亮且維持的時(shí)間為[Tmin2，]如果次干道沒(méi)有車(chē)輛通過(guò)則主干道的綠時(shí)在[Tmin1]后持續(xù)發(fā)亮到最大綠時(shí)[Tmax，]此時(shí)次干道如果沒(méi)有車(chē)輛進(jìn)入則判斷次干道是否有行人需要通過(guò)（通過(guò)人行道安裝的紅外感應(yīng)器判斷），如果有行人通過(guò)則次干道的綠燈亮且維持最小綠時(shí)[Tmin2。]一般取[Tmin1=T2，][Tmin2=T5，][Tmax=][0.8T，]其中[T]為周期。

圖8 交通燈流程圖

（2） 當(dāng)飽和度[λ]在[0.8，1）這個(gè)區(qū)間時(shí)，交叉口趨于或處于飽和，路口交通狀況復(fù)雜多變[10]，采用感應(yīng)控制已經(jīng)不能滿(mǎn)足復(fù)雜多變的交通流。此時(shí)執(zhí)行基于遺傳算法的實(shí)時(shí)自適應(yīng)控制策略，它能根據(jù)實(shí)時(shí)的交通流去預(yù)測(cè)下一周期的配時(shí)，最大化道路的流通能力。

2.3 基于遺傳算法的優(yōu)化模型

遺傳算法的優(yōu)化目標(biāo)是讓一個(gè)周期內(nèi)各相位剩余排隊(duì)車(chē)輛數(shù)的總和最小。以第1相位為例，總周期為[T，]車(chē)輛到達(dá)率（車(chē)輛單位時(shí)間內(nèi)到達(dá)的數(shù)量）為[r1，]離開(kāi)率（車(chē)輛單位時(shí)間內(nèi)離開(kāi)的數(shù)量）為[m1，]相位1的綠時(shí)為[t1，]則相位1在周期[T]內(nèi)剩余排隊(duì)的車(chē)輛數(shù)為：

[S=S*+T? r1- m1? t1] （1）

式中：[S*]為上一周期相位1滯留的車(chē)輛數(shù)。則在總周期[T]內(nèi)4相位滯留車(chē)輛數(shù)為：

[S=i=14[Si+T?ri-ti?mi]] （2）

式中：[Si]為上一周期第[i]相位滯留的車(chē)輛數(shù)。

[T=i=14ti] （3）

考慮到行人過(guò)馬路時(shí)的安全需要，每相位最短綠燈時(shí)間[10]不得小于6 s，一般要滿(mǎn)足條件式（4）：

[6≤ti≤T-18] （4）

從以上分析可知，為了使路口的通行能力最大，要使目標(biāo)函數(shù)[S]的取值最小。各相位的到達(dá)率和離開(kāi)率由車(chē)輛檢測(cè)器測(cè)得，為常數(shù)。所以[S]是以時(shí)間[ti]為自變量的目標(biāo)函數(shù)。遺傳算法一般求最大問(wèn)題，所以遺傳算法中的適應(yīng)度函數(shù)[f=D-S，]即有：

[fitness=D-i=14[Si+T?ri-ti?mi]] （5）

式中[D]是一人為設(shè)定的常數(shù)。

遺傳算法采用24位二進(jìn)制對(duì)個(gè)體進(jìn)行編碼，個(gè)體中的每6位為一個(gè)相位的時(shí)間。第1相位配時(shí)為第23～18位，第2相位配時(shí)為第17～12位，第3相位配時(shí)為第11～6位，第4相位配時(shí)為第5～0位。

3 仿真分析

本文采用一組模擬數(shù)據(jù)來(lái)仿真在自適應(yīng)控制下的結(jié)果，模擬數(shù)據(jù)見(jiàn)表3，在Quartus Ⅱ軟件里進(jìn)行仿真。遺傳算法的參數(shù)見(jiàn)表1。為了方便VHDL的編程，把表3中的路口模擬數(shù)據(jù)都同時(shí)擴(kuò)大100倍，由式（5）設(shè)遺傳算法的適應(yīng)度函數(shù)為：

[fitness=100 000-i=14[Si+T?ri-ti?mi]] （6）

表3 路口模擬數(shù)據(jù)

[＼&到達(dá)率＼&離開(kāi)率＼&上周期滯留車(chē)輛數(shù) /輛＼&相位1＼&0.22＼&0.8＼&5＼&相位2＼&0.06＼&0.6＼&3＼&相位3＼&0.25＼&0.79＼&12＼&相位4＼&0.08＼&0.6＼&1＼&]

從圖9可以看到最大適應(yīng)度為99 690，接近100 000，最優(yōu)個(gè)體為101010010010111001010000，即[t1=42]s，[t2=18] s，[t3=57] s，[t4=16]s，周期[T=133] s。仿真結(jié)果見(jiàn)表4。

圖9 仿真截圖

表4 仿真結(jié)果

[＼&配時(shí) /s＼&滯留車(chē)輛數(shù) /輛＼&相位1＼&42＼&0＼&相位2＼&18＼&0＼&相位3＼&57＼&0＼&相位4＼&16＼&2＼&]

從表4的仿真結(jié)果看出，經(jīng)過(guò)優(yōu)化后的各相位配時(shí)使得除了相位4其他各相位的滯留車(chē)輛數(shù)為0，總體上的車(chē)輛滯留數(shù)從優(yōu)化前的21到優(yōu)化后的2輛，使得道路的通行能力得到提高。相位3，4的時(shí)間總和大于相位1，2的時(shí)間和，這與模擬數(shù)據(jù)中相位3，4的車(chē)流量大而相位1，2的車(chē)流量小相吻合。說(shuō)明優(yōu)化方法是有效的、可行的。

4 結(jié) 論

文中提出的智能交通燈能根據(jù)路口不同的交通狀況（飽和度）選擇不同的工作模式，最大程度滿(mǎn)足各種交通流環(huán)境下交通燈最優(yōu)的工作要求。仿真結(jié)果表明，基于遺傳算法的自適應(yīng)工作模式能夠根據(jù)交通流狀況做出最優(yōu)配時(shí)，滿(mǎn)足交通燈實(shí)時(shí)控制的要求?；贔PGA的遺傳算法在運(yùn)行速度上有了很大的提高，讓一些復(fù)雜、大規(guī)模問(wèn)題有了解決的可能性，也使得遺傳算法的應(yīng)用范圍和實(shí)用性得以擴(kuò)大。文中基于FPGA的遺傳算法相較于傳統(tǒng)遺傳算法，在結(jié)構(gòu)上并未作優(yōu)化，這是本文在未來(lái)需要改進(jìn)的主要內(nèi)容。

參考文獻(xiàn)

[1] 楊兆生.新一代智能化交通控制系統(tǒng)關(guān)鍵技術(shù)及其應(yīng)用[M].北京：中國(guó)鐵道出版社，2008.

[2] 湯歡，趙曙光.基于FPGA實(shí)現(xiàn)的遺傳算法[J].電子測(cè)量技術(shù)，2009，31（1）：151?153.

[3] 王脂丹，于盛林.基于FPGA的遺傳算法硬件實(shí)現(xiàn)研究[J].儀器儀表用戶(hù)，2006，13（2）：10?12.

[4] 蔡偉綱.NiosⅡ軟件架構(gòu)解析[M].西安：西安電子科技大學(xué)出版社，2007.

[5] 周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，1999.

[6] 王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[7] 吳兵，李曄.交通管理與控制[M].北京：人民交通出版社，2003.

[8] 張麗霞，楊仁懷，唐澤.基于NiosⅡ的單點(diǎn)自適應(yīng)控制器設(shè)計(jì)研究[J].電子科技，2014（8）：105?111.

[9] 張麗霞.基于NIOS Ⅱ的單點(diǎn)自適應(yīng)控制器設(shè)計(jì)研究[D].成都：西南交通大學(xué)，2011.

[10] 張飛舟，范耀祖.交通工程控制[M].北京：中國(guó)鐵道出版社，2005.