基于FPGA的遺傳算法在交通控制中的應用

張麗霞　唐澤

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

關鍵詞： 智能交通燈； 現場可編程門陣列； 遺傳算法； 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 引 言

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

1 遺傳算法的硬件實現

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

圖1 遺傳算法流程圖

1.1 遺傳算法的運行參數

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

表1 遺傳算法的運行參數

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

1.2 遺傳算法的硬件結構

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

1.3 算法的工作原理

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

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

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

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

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

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

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

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

（6） 輸出。當達到進化代數后，輸出最優個體。

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

1.4 算法的實現及測試

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

[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]

選取的函數是幾個比較基本的、容易驗證的求極值函數，常常用于遺傳算法的性能測試中[3]。

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

表2 仿真測試結果

[函數＼&實現方式＼&最優個體值＼&適應度值＼&運行時間＼&工作頻率＼&[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 交通燈控制系統

現在大部分交通信號燈都采用固定周期控制，難以滿足復雜多變的交通狀況，造成資源浪費[6]。本文提出基于道路飽和度的感應控制和自適應控制，這樣就能根據道路在每個時刻具體的交通流去分配控制方法。基于VHDL的計數模塊用于對一個周期內各相位到達和離開車輛數的計數。交通燈控制系統的整體框圖見圖5。

2.1 交通燈的模型及參數

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

圖5 交通燈系統框圖

圖6 十字路口示意圖

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

圖7 各相位示意圖

2.2 交通燈控制方法

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

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

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

圖8 交通燈流程圖

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

2.3 基于遺傳算法的優化模型

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

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

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

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

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

[T=i=14ti] （3）

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

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

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

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

式中[D]是一人為設定的常數。

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

3 仿真分析

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

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

表3 路口模擬數據

[＼&到達率＼&離開率＼&上周期滯留車輛數 /輛＼&相位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可以看到最大適應度為99 690，接近100 000，最優個體為101010010010111001010000，即[t1=42]s，[t2=18] s，[t3=57] s，[t4=16]s，周期[T=133] s。仿真結果見表4。

圖9 仿真截圖

表4 仿真結果

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

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

4 結 論

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

參考文獻

[1] 楊兆生.新一代智能化交通控制系統關鍵技術及其應用[M].北京：中國鐵道出版社，2008.

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

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

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

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

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

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

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

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

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