遗传算法在智能交通系统中的应用.ppt

《遗传算法在智能交通系统中的应用.ppt》由会员分享，可在线阅读，更多相关《遗传算法在智能交通系统中的应用.ppt（31页珍藏版）》请在三一办公上搜索。

1、1,遗传算法在智能交通系统中的应用,报告人:王超 PB02011013 导师：周学海教授2006-6-12,遗传算法在智能交通系统中的应用,2,主要内容,智能交通系统背景介绍遗传算法简介遗传算法在本文中的应用测试数据总结&展望,遗传算法在智能交通系统中的应用,3,智能交通系统简介,智能交通系统ITS Intelligent Transportation System最先进的电子信息技术实现人员（包括驾驶员和管理者）、公路和车辆三者的密切结合和和谐统一新公路交通系统。优点：减少交通拥挤，加强对车辆 的集中管理和调度，为驾驶员提供足够的交通、公安、娱乐等信息提高交通运输效率保障交通安全增强行车的舒

2、适性改善环保质量提高能源的利用率。,遗传算法在智能交通系统中的应用,4,智能交通系统分类,先进的交通管理系统(ATMS)道路、车辆和驾驶员之间建立通讯联系信息检测系统-信息传输系统-信息处理系统-信息发布系统 先进的车辆控制系统（AVCS）辅助在以至替代驾驶员实行控制 先进的驾驶员信息系统（ADIS）向驾驶员提供路况信息，导航营运车辆调度管理系统（CVO）企业用车辆调度先进的大众运输系统（APTS）向公众提供信息，公交车调度,遗传算法在智能交通系统中的应用,5,系统的工作,目的：减少一段时间内每辆到达车辆的平均等待时间手段：参考历史信息和当前路口上下游路口的拥塞来动态地调整路口交通灯的延长时间

3、实现方法：调度算法模糊控制遗传编程,遗传算法在智能交通系统中的应用,6,遗传算法的基本理论,遗传算法(Genetic Algorithms)是基于自然选择和自然遗传机制的搜索算法，它是一种有效的解决最优化问题的方法 染色体编码方法。二进制编码，其等位基因是由二进值符号集0,1所组成的。如：X就可表示一个个体，该个体的染色体长度是n18。十进制编码没有“Hamming Cliffs”01111-10000需要改变所有的位适合范围变异，直观,遗传算法在智能交通系统中的应用,7,遗传算法的基本理论,个体适应度评价。作用：决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求

4、所有个体的适应度必须为正数或零。要点：根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。,遗传算法在智能交通系统中的应用,8,遗传算法的基本理论,遗传算子。基本遗传算法使用下述三种遗传算子选择(selection)：根据各个个体的适应度，按照一定的规则或方法，从当代群体选择出一些优良的个体遗传到下一代群体中。常用的是下面的轮盘赌选择方法。,遗传算法在智能交通系统中的应用,9,遗传算法的基本理论,交叉(crossover)：将群体P(t)内的各个个体随机搭配成对，对每一对个体,以某个概率(称为交叉概率，crossover

5、rate)交换它们之间的部分染色体。均匀交叉点交叉,遗传算法在智能交通系统中的应用,10,遗传算法的基本理论,变异(mutation)：对群体中的每一个个体，以某一概率(称为变异概率，mutation rate)改变某一个或某一些基因座上的基因值为其他的等位基因。,遗传算法在智能交通系统中的应用,11,遗传算法的基本理论,基本遗传其法的运行参数。基本遗传算法有下述4个运行参数，影响运行时间和收敛速度：M：群体大小，即群体中所含个体的数量，一般取为20100。T：遗传运算的终止进化代数，一般取为100500。Pc：交叉概率，一般取为0.40.99。Pm：变异概率，一般取为0.0010.1。,遗传

6、算法在智能交通系统中的应用,12,遗传算法的基本理论,遗传算法的基本步骤,遗传算法在智能交通系统中的应用,13,遗传算法在系统中的应用,我们的系统主要通过模糊控制和调度算法来实现对交通的控制遗传算法的功能就是通过进化生成上面的模糊控制规则表,遗传算法在智能交通系统中的应用,14,遗传算法实现的关键技术,染色体的编码方法一个现有的模糊控制规则表，是一个NN的矩阵，N为车流模糊量的隶属度，在我们的系统中设置为7，VF(很少)、F(少)、FP(较少)、C(中)、MP(较多)、M(多)、VM(很多)，对应的编码为0、1、2、3、4、5、6，这样一个77的矩阵就可以转化成一个编码序列。具体例子如下：,遗

7、传算法在智能交通系统中的应用,15,遗传算法在系统中的应用,上面的表格编码所得的结果为：0123456 0123456 0123455 0123345 0123344 0112234 0011223。编码长度为7 7=49 位。,遗传算法在智能交通系统中的应用,16,遗传算法在系统中的应用,适应度函数的确定平均等待时间 在路口的模型中，假设有8个车道。每个车道要分别计算，需要假设各个车道的流出速率。对于某个车道，如果是绿灯结束的情况：a若上次剩下的车全部离开，又因为是以匀速离开，则在本次绿灯时间内的的等待时间为：上次剩下的车辆数离开时间2。【新来的车可以不考虑】b 若上次剩下的车没有走完，则在

8、本次绿灯时间内的等待时间为：离开的车辆数本次绿灯时间2（新来的车辆没有走的车辆）本次绿灯时间。,遗传算法在智能交通系统中的应用,17,遗传算法在系统中的应用,对于某个车道，如果是红灯结束的情况：在本次红灯时间内的等待时间为：（红灯开始时候已经在等待的车辆红灯时间内到来的车辆）本次红灯时间。注意点：左转的车道和直行的车道拥有不一样的流出速度，一般来说直行的车要比左转的快一些。,遗传算法在智能交通系统中的应用,18,遗传算法在系统中的应用,遗传算法的参数设置初始种群的产生初始化种群时，为了保证每个基因都存在于第一代的个体中，人为地制定一条染色体m_genesi=i/7，其余的popnum-1条染色

9、体由随机产生，必须保证满足每个基因的基因型在0到6之间。交叉个体按照交叉概率Pc=80%进行杂交。交叉采用均匀杂交，随机产生与染色体等长的二进制杂交模板，0 表示对应位不交换，1 表示交换。然后根据模板对两个父代施行杂交，产生两个后代。均匀杂交能搜索到点式杂交无法搜索到的模式，比较适合用于较小的群体规模。而点式交叉搜索到的模式比较少，在群体规模较小时，其搜索能力将受到一定的影响。,遗传算法在智能交通系统中的应用,19,遗传算法在系统中的应用,变异个体按照变异概率Pm=20进行变异，而被选中的个体的每位基因又按照5的概率进行变异。变异时候需要注意不能超出编码的范围。新一代个体的产生在对一代个体进

10、行交叉和变异操作之后，生成一个数目比初始种群数目大的种群。对于该种群每条染色体计算其适应度，并按照适应度大小将所有染色体排列，并取最大的种群数目个作为下一代的种群。,遗传算法在智能交通系统中的应用,20,遗传算法在系统中的应用,其他参数的设置主要影响遗传算法的运行时间。种群规模popNum;进化代数generationNum;计算适应度函数时的模拟运行时间 totalTime;计算适应度函数时的模拟运行次数 runTime;交叉概率crossRate;变异概率mutateRate;个体基因的变异概率Genome.m_mutationrate;染色体长度genomeLength;每个基因的取值范

11、围genomeRange;,遗传算法在智能交通系统中的应用,21,遗传算法在系统中的应用,算法流程图,遗传算法在智能交通系统中的应用,22,相关测试,运行时间测试种群规模的影响,遗传算法在智能交通系统中的应用,23,相关测试,进化代数的影响,遗传算法在智能交通系统中的应用,24,相关测试,仿真时间的影响,遗传算法在智能交通系统中的应用,25,相关测试,仿真次数的影响,遗传算法在智能交通系统中的应用,26,相关测试,控制效果测试建立一个路口模型（4相位8车道）4个相位8个车道到来速度（平均分布）离开速度（直行和左行）3种不同的方法比较传统的交通灯经验矩阵遗传算法,遗传算法在智能交通系统中的应用,

12、27,相关测试,遗传算法在智能交通系统中的应用,28,总结和展望,总结本文把遗传算法应用在模糊控制规则的生成中，再通过计算出来的模糊控制对应关系来管理十字路口，得到了比较优化的效果。编码方案适应度函数算子,遗传算法在智能交通系统中的应用,29,总结和展望,展望限制关系,遗传算法在智能交通系统中的应用,30,总结和展望,按照适应度调节变异概率为了使算法更加快速的收敛，对适应值大的个体在较小范围内搜索,对适应值小的个体在较大范围搜索。其中r为随机数,为0,1区间上的随机数,f(max)为当前群体的最大适应值。函数的值域为0,y,当f增大时,(f,y)趋近于0的概率增大,即当 f增大时,变异操作对vk的影响减小。,遗传算法在智能交通系统中的应用,31,谢 谢！,