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

1遗传算法在智能交通系统中的应用报告人:王超PB02011013导师：周学海教授2006-6-12遗传算法在智能交通系统中的应用2/31主要内容智能交通系统背景介绍遗传算法简介遗传算法在本文中的应用测试数据总结&展望遗传算法在智能交通系统中的应用3/31智能交通系统简介智能交通系统ITS—IntelligentTransportationSystem最先进的电子信息技术实现人员（包括驾驶员和管理者）、公路和车辆三者的密切结合和和谐统一新公路交通系统。优点：减少交通拥挤，加强对车辆的集中管理和调度，为驾驶员提供足够的交通、公安、娱乐等信息提高交通运输效率保障交通安全增强行车的舒适性改善环保质量提高能源的利用率。遗传算法在智能交通系统中的应用4/31智能交通系统分类先进的交通管理系统(ATMS)道路、车辆和驾驶员之间建立通讯联系信息检测系统-信息传输系统-信息处理系统-信息发布系统先进的车辆控制系统（AVCS）辅助在以至替代驾驶员实行控制先进的驾驶员信息系统（ADIS）向驾驶员提供路况信息，导航营运车辆调度管理系统（CVO）企业用车辆调度先进的大众运输系统（APTS）向公众提供信息，公交车调度遗传算法在智能交通系统中的应用5/31系统的工作目的：减少一段时间内每辆到达车辆的平均等待时间手段：参考历史信息和当前路口上下游路口的拥塞来动态地调整路口交通灯的延长时间实现方法：调度算法模糊控制遗传编程遗传算法在智能交通系统中的应用6/31遗传算法的基本理论遗传算法(GeneticAlgorithms)是基于自然选择和自然遗传机制的搜索算法，它是一种有效的解决最优化问题的方法染色体编码方法。二进制编码，其等位基因是由二进值符号集{0,1}所组成的。如：X＝100111001000101101就可表示一个个体，该个体的染色体长度是n＝18。十进制编码没有“HammingCliffs”01111-10000需要改变所有的位适合范围变异，直观遗传算法在智能交通系统中的应用7/31遗传算法的基本理论个体适应度评价。作用：决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。要点：根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。遗传算法在智能交通系统中的应用8/31遗传算法的基本理论遗传算子。基本遗传算法使用下述三种遗传算子选择(selection)：根据各个个体的适应度，按照一定的规则或方法，从当代群体选择出一些优良的个体遗传到下一代群体中。常用的是下面的轮盘赌选择方法。遗传算法在智能交通系统中的应用9/31遗传算法的基本理论交叉(crossover)：将群体P(t)内的各个个体随机搭配成对，对每一对个体,以某个概率(称为交叉概率，crossoverrate)交换它们之间的部分染色体。均匀交叉点交叉A:1011011100B:0001110011A:1001011100B:0011110011均匀交叉模板:0010000000A:1011011100B:0001110011A:1011011111B:0001110000单点交叉交叉点遗传算法在智能交通系统中的应用10/31遗传算法的基本理论变异(mutation)：对群体中的每一个个体，以某一概率(称为变异概率，mutationrate)改变某一个或某一些基因座上的基因值为其他的等位基因。A:1010101010变异点A:1010001010基本位变异遗传算法在智能交通系统中的应用11/31遗传算法的基本理论基本遗传其法的运行参数。基本遗传算法有下述4个运行参数，影响运行时间和收敛速度：M：群体大小，即群体中所含个体的数量，一般取为20—100。T：遗传运算的终止进化代数，一般取为100—500。Pc：交叉概率，一般取为0.4—0.99。Pm：变异概率，一般取为0.001—0.1。遗传算法在智能交通系统中的应用12/31遗传算法的基本理论遗传算法的基本步骤终止条件个体评价群体P(t)选择交叉变异群体P(t＋1)解码解集合初始化结束满足不满足遗传算法在智能交通系统中的应用13/31遗传算法在系统中的应用我们的系统主要通过模糊控制和调度算法来实现对交通的控制遗传算法的功能就是通过进化生成上面的模糊控制规则表排队长度排队长度排队长度模糊值排队长度模糊值绿灯追加时间模糊值绿灯追加时间车流量模糊子集模糊控制规则表绿灯追加时间模糊子集遗传算法在智能交通系统中的应用14/31遗传算法实现的关键技术染色体的编码方法一个现有的模糊控制规则表，是一个N×N的矩阵，N为车流模糊量的隶属度，在我们的系统中设置为7，VF(很少)、F(少)、FP(较少)、C(中)、MP(较多)、M(多)、VM(很多)，对应的编码为0、1、2、3、4、5、6，这样一个7×7的矩阵就可以转化成一个编码序列。具体例子如下：遗传算法在智能交通系统中的应用15/31遗传算法在系统中的应用上面的表格编码所得的结果为：0123456012345601234550123345012334401122340011223。编码长度为7×7=49位。时间的模糊量当前车流的模糊量VFFFPCMPMVM下一相位车流的模糊量VFVSSSPCLPLVLFVSSSPCLPLVLFPVSSSPCLPLLCVSSSPCCLPLMPVSSSPCCLPLPMVSSSSPSPCLPVMVSVSSSSPSPC遗传算法在智能交通系统中的应用16/31遗传算法在系统中的应用适应度函数的确定－平均等待时间在路口的模型中，假设有8个车道。每个车道要分别计算，需要假设各个车道的流出速率。对于某个车道，如果是绿灯结束的情况：a若上次剩下的车全部离开，又因为是以匀速离开，则在本次绿灯时间内的的等待时间为：上次剩下的车辆数×离开时间÷2。【新来的车可以不考虑】b若上次剩下的车没有走完，则在本次绿灯时间内的等待时间为：离开的车辆数×本次绿灯时间÷2＋（新来的车辆＋没有走的车辆）×本次绿灯时间。遗传算法在智能交通系统中的应用17/31遗传算法在系统中的应用对于某个车道，如果是红灯结束的情况：在本次红灯时间内的等待时间为：（红灯开始时候已经在等待的车辆＋红灯时间内到来的车辆）×本次红灯时间。注意点：左转的车道和直行的车道拥有不一样的流出速度，一般来说直行的车要比左转的快一些。遗传算法在智能交通系统中的应用18/31遗传算法在系统中的应用遗传算法的参数设置初始种群的产生初始化种群时，为了保证每个基因都存在于第一代的个体中，人为地制定一条染色体m_genes[i]=i/7，其余的popnum-1条染色体由随机产生，必须保证满足每个基因的基因型在0到6之间。交叉个体按照交叉概率Pc=80%进行杂交。交叉采用均匀杂交，随机产生与染色体等长的二进制杂交模板，0表示对应位不交换，1表示交换。然后根据模板对两个父代施行杂交，产生两个后代。均匀杂交能搜索到点式杂交无法搜索到的模式，比较适合用于较小的群体规模。而点式交叉搜索到的模式比较少，在群体规模较小时，其搜索能力将受到一定的影响。遗传算法在智能交通系统中的应用19/31遗传算法在系统中的应用变异个体按照变异概率Pm=20％进行变异，而被选中的个体的每位基因又按照5％的概率进行变异。变异时候需要注意不能超出编码的范围。新一代个体的产生在对一代个体进行交叉和变异操作之后，生成一个数目比初始种群数目大的种群。对于该种群每条染色体计算其适应度，并按照适应度大小将所有染色体排列，并取最大的种群数目个作为下一代的种群。遗传算法在智能交通系统中的应用20/31遗传算法在系统中的应用其他参数的设置主要影响遗传算法的运行时间。种群规模popNum;进化代数generationNum;计算适应度函数时的模拟运行时间totalTime;计算适应度函数时的模拟运行次数runTime;交叉概率crossRate;变异概率mutateRate;个体基因的变异概率Genome.m_mutationrate;染色体长度genomeLength;每个基因的取值范围genomeRange;遗传算法在智能交通系统中的应用21/31遗传算法在系统中的应用算法流程图终止条件群体P(t)交叉变异初始化结束满足不满足适应度计算排序并选择遗传算法在智能交通系统中的应用22/31相关测试运行时间测试种群规模的影响种群规模的影响23.60946.35970.21893.6402040608010050100150200种群规模运行时间(s)种群规模的影响遗传算法在智能交通系统中的应用23/31相关测试进化代数的影响进化代数的影响22.87546.59370.4379402040608010050100150200进化代数运行时间(s)进化代数的影响遗传算法在智能交通系统中的应用24/31相关测试仿真时间的影响仿真时间的影响33.6447.4659.67172.48401020304050607080500100015002000仿真时间(s)运行时间(s)仿真时间的影响遗传算法在智能交通系统中的应用25/31相关测试仿真次数的影响仿真次数的影响47.7571.84393.5120.6402040608010012014010203040仿真次数运行时间(s)仿真次数的影响遗传算法在智能交通系统中的应用26/31相关测试控制效果测试建立一个路口模型（4相位8车道）4个相位8个车道到来速度（平均分布）离开速度（直行和左行）3种不同的方法比较传统的交通灯经验矩阵遗传算法遗传算法在智能交通系统中的应用27/31相关测试遗传算法在智能交通系统中的应用28/31总结和展望总结本文把遗传算法应用在模糊控制规则的生成中，再通过计算出来的模糊控制对应关系来管理十字路口，得到了比较优化的效果。编码方案适应度函数算子遗传算法在智能交通系统中的应用29/31总结和展望展望限制关系时间的模糊量当前车流的模糊量VFFFPCMPMVM下一相位车流的模糊量VF5556666F4445555FP3334444C2223333MP1112222M0001111VM0000000遗传算法在智能交通系统中的应用30/31总结和展望按照适应度调节变异概率为了使算法更加快速的收敛，对适应值大的个体在较小范围内搜索,对适应值小的个体在较大范围搜索。其中r为随机数,δ为[0,1]区间上的随机数,f(max)为当前群体的最大适应值。函数的值域为[0,y],当f增大时,Δ(f,y)趋近于0的概率增大,即当f增大时,变异操作对vk的影响减小。　　　　0)7),((0)7),((rvpfitvrvpfitvvkkkkk　　)1(),(2)max1(ffyyf遗传算法在智能交通系统中的应用31/31谢谢！