基于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.