遗传算法在智能交通系统中的应用
报告人: 王超 PB02011013 导师： 周学海教授 2006-6-12
1
主要内容
❖ 智能交通系统背景介绍 ❖ 遗传算法简介 ❖ 遗传算法在本文中的应用 ❖ 测试数据 ❖ 总结&展望
遗传算法在智能交
通系统中的应用
2/31
智能交通系统简介
❖ 智能交通系统
➢ ITS —Intelligent Transportation System
排队长度 车流 量模 糊子
排队长度 集
排队长 度模糊值
排队长 度模糊值
模 糊 控 制 规 则
绿灯追 加时间 模糊值
绿灯
追加 时间 模糊
绿灯追 加时间
子集
表
❖ 遗传算法的功能就是通过进化生成上面的模糊控
制规则表
遗传算法在智能交 通系统中的应用
13/31
遗传算法实现的关键技术
❖ 染色体的编码方法
➢ 一个现有的模糊控制规则表，是一个N×N的矩阵，N 为车流模糊量的隶属度，在我们的系统中设置为7， VF(很少)、F(少)、FP(较少)、C(中)、MP(较多)、 M(多)、VM(很多) ，对应的编码为0、1、2、3、4、5、 6，这样一个7×7的矩阵就可以转化成一个编码序列。
遗传算法在智能交 通系统中的应用
11/31
遗传算法的基本理论
❖ 遗传算法的基本步骤
群体 P(t)
初始 化
个体评价
解集 合
终止条件
不满足
选择
满足 结束
交叉
变异
解码
群体 P(t＋1)
遗传算法在智能交 通系统中的应用
12/31
遗传算法在系统中的应用
❖ 我们的系统主要通过模糊控制和调度算法来实现 对交通的控制
基本位变异
A:1010 1 01010
A:1010 0 01010
变异点
遗传算法在智能交 通系统中的应用
10/31
遗传算法的基本理论
❖ 基本遗传其法的运行参数。基本遗传算法有下述 4个运行参数，影响运行时间和收敛速度：
➢ M：群体大小，即群体中所含个体的数量，一般取为 20—100。
➢ T：遗传运算的终止进化代数，一般取为100—500。 ➢ Pc：交叉概率，一般取为0.4—0.99。 ➢ Pm：变异概率，一般取为0.001—0.1。
❖ 实现方法：
➢ 调度算法 ➢ 模糊控制 ➢ 遗传编程
遗传算法在智能交
通系统中的应用
5/31
遗传算法的基本理论
❖遗传算法(Genetic Algorithms)是基于自然选择和 自然遗传机制的搜索算法，它是一种有效的解决 最优化问题的方法
❖ 染色体编码方法。
➢ 二进制编码，其等位基因是由二进值符号集{0,1}所组 成的。如：
模板:0010000000
A: 1001011100 B: 0011110011
点交叉
A:10110111 00 B:00011100 11
单点交叉
交叉点
遗传算法在智能交 通系统中的应用
A:10110111 11 B:00011100 00
9/31
遗传算法的基本理论
➢ 变异(mutation)：对群体中的每一个个体，以某一概 率(称为变异概率，mutation rate)改变某一个或某一 些基因座上的基因值为其他的等位基因。
LP
VM
VS
VS
S
S
SP
SP
C
❖ 上面的表格编码所得的结果为：0123456 0123456 0123455 0123345 0123344 0112234 0011223。编码长度为 7 ×7 = 49 位。
➢ 要点：根据不同种类的问题，必须预先确定好由目标 函数值到个体适应度之间的转换规则，特别是要预先 确定好当目标函数值为负数时的处理方法。
遗传算法在智能交
通系统中的应用
7/31
遗传算法的基本理论
❖ 遗传算子。基本遗传算法使用下述三种遗传算子
➢ 选择(selection)：根据各个个体的适应度，按照一定 的规则或方法，从当代群体选择出一些优良的个体遗 传到下一代群体中。常用的是下面的轮盘赌选择方法。
➢ 最先进的电子信息技术 ➢ 实现人员（包括驾驶员和管理者）、公路和车辆三者的密切结
合和和谐统一新公路交通系统。 ➢ 优点：
减少交通拥挤， 加强对车辆 的集中管理和调度， 为驾驶员提供足够的交通、公安、娱乐等信息 提高交通运输效率 保障交通安全 增强行车的舒适性 改善环保质量 提高能源的利用率。
❖ 营运车辆调度管理系统（CVO）
➢ 企业用车辆调度
❖ 先进的大众运输系统（APTS）
➢ 向公众提供信息，公交车调度
遗传算法在智能交
通系统中的应用
4/31
系统的工作
❖ 目的：减少一段时间内每辆到达车辆的平均等待 时间
❖ 手段：参考历史信息和当前路口上下游路口的拥 塞来动态地调整路口交通灯的延长时间
遗传算法在智能交
通系统中的应用
8/31
遗传算法的基本理论
➢ 交叉(crossover)：将群体P(t)内的各个个体随机搭配 成对，对每一对个体,以某个概率(称为交叉概率， crossover rate)交换它们之间的部分染色体。
均匀交叉
A: 1011011100 B: 0001110011
均匀交叉
遗传算法在智能交
通系统中的应用
3/31
智能交通系统分类
❖ 先进的交通管理系统 (ATMS)
➢ 道路、车辆和驾驶员之间建立通讯联系 ➢ 信息检测系统 -信息传输系统 -信息处理系统 -信息发布系统
❖ 先进的车辆控制系统（AVCS）
➢ 辅助在以至替代驾驶员实行控制
❖ 先进的驾驶员信息系统（ADIS）
➢ 向驾驶员提供路况信息，导航
X＝100111001000101101 就可表示一个个体，该个体的染色体长度是n＝18。
➢ 十进制编码
没有“Hamming Cliffs”
▪ 01111->10000需要改变所有的位
适合范围变异，直观
遗传算法在智能交
通系统中的应用
6/31
遗传算法的基本理论
❖ 个体适应度评价。
➢ 作用：决定当前群体中每个个体遗传到下一代群体中 的机会多少。为正确计算这个概率，这里要求所有个 体的适应度必须为正数或零。
➢ 具体例子如下：
遗传算法在智能交 通系统中的应用
14/31
遗传算法在系统中的应用
时间的 模糊量
当前车流的模糊量
VF
F
FP
C
MP
M
VM
VF
VS
S
SP
C
LP
L
VL
F
VS
S
SP
C
ห้องสมุดไป่ตู้
LP
L
VL
下一相 FP
VS
S
SP
C
LP
L
L
位车流
的模糊
C
VS
S
SP
C
C
LP
L
量
MP
VS
S
SP
C
C
LP
LP
M
VS
S
S
SP
SP
C