基于FPGA的遺傳算法在交通控制中的應(yīng)用

張麗霞　唐澤

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

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

中圖分類號： TN965+.71?34； TP332.3 文獻標識碼： A 文章編號： 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 引 言

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

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

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

圖1 遺傳算法流程圖

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

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

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

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

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

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

1.3 算法的工作原理

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

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

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

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

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

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

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

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

（6） 輸出。當達到進化代數(shù)后，輸出最優(yōu)個體。

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

1.4 算法的實現(xiàn)及測試

遺傳算法采用VHDL語言編程，在Quartus Ⅱ軟件里進行仿真。所用到的器件為Altera公司的Cyclone Ⅲ EP3C5E144C8。為了測試算法的正確性，采用下面的測試函數(shù)進行仿真，測試函數(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ù)是幾個比較基本的、容易驗證的求極值函數(shù)，常常用于遺傳算法的性能測試中[3]。

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

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

[函數(shù)＼&實現(xiàn)方式＼&最優(yōu)個體值＼&適應(yīng)度值＼&運行時間＼&工作頻率＼&[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)在大部分交通信號燈都采用固定周期控制，難以滿足復雜多變的交通狀況，造成資源浪費[6]。本文提出基于道路飽和度的感應(yīng)控制和自適應(yīng)控制，這樣就能根據(jù)道路在每個時刻具體的交通流去分配控制方法?；赩HDL的計數(shù)模塊用于對一個周期內(nèi)各相位到達和離開車輛數(shù)的計數(shù)。交通燈控制系統(tǒng)的整體框圖見圖5。

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

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

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

圖6 十字路口示意圖

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

圖7 各相位示意圖

2.2 交通燈控制方法

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

（1） 根據(jù)車流量計算每個相位的飽和度，當飽和度[λ]在（0，0.8）這個區(qū)間時，執(zhí)行感應(yīng)控制[9]，因為飽和度在小于0.8時道路不是很擁擠，感應(yīng)控制一般能滿足道路交通狀況。感應(yīng)控制分為半感應(yīng)控制和全感應(yīng)控制[9]。用主、次干道車流量是否相差大這一標準來判斷是半感應(yīng)模式還是全感應(yīng)模式。設(shè)主干道的車流量為[m，]次干道的車流量為[n，]若[n

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

圖8 交通燈流程圖

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

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

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

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

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

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

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

[T=i=14ti] （3）

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

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

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

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

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

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

3 仿真分析

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

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

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

[＼&到達率＼&離開率＼&上周期滯留車輛數(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)個體為101010010010111001010000，即[t1=42]s，[t2=18] s，[t3=57] s，[t4=16]s，周期[T=133] s。仿真結(jié)果見表4。

圖9 仿真截圖

表4 仿真結(jié)果

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

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

4 結(jié) 論

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

參考文獻

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

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

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

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

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

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

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

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

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

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