（控制理论与控制工程专业论文）基于遗传算法的od矩阵推算和混合交通信号相位优化研究.pdf

堑 江垄兰鱼塑主兰竺堕查 摘要 智能交通系统是将先进的信息技术、计算机技术、运筹学、人工智能等有效 地综合运用于交通运输和服务控制，从而形成准确高效的综合交通系统。 0 d 矩阵推算和混合交通信号相位优化是智能交通系统领域中两个重要的优 化问题。目前o d 反推大多采用极大熵模型，其求解算法存在主要不足是很难选 取合适初始解。我国信号控制仍以定时式为主，其配时方案的优化大多属于预先 设定范围内的优化。 遗传算法是一种借鉴生物界自然选择思想和自然遗传机制的全局随机搜索 算法，在解决大空间、全局寻优等复杂问题时具有独特优越性。 本文提出结合遗传算法和l e v e n b e 蜡一m a r q u a r d t 算法的混合进化算法求解极 大熵o d 反推模型。仿真结果表明，该混合算法比遗传算法求解速度更快，并克 服了l e v e n b e r g m a r q l 脚_ d t 算法对初始解的依赖性，对于较大规模交通网络的o d 反推具有较好的精度。 本文从中国混合交通流的国情出发，提出混合交通信号相位优化算法对信号 相位进行全局优化。针对待优化变量一信号相位的特殊性，即存在很多约束条件， 设计了两种混合交通信号相位解空间搜索算法，即基于问题驱动的相位合并优化 算法和改进合作型协同进化遗传算法。设计并实现单交叉口信号灯优化软件，对 软件的输出进行分析，并将其嵌入到仿真软件中，帮助用户设计信号灯配时方案。 本文的章节安排如下： 第一章着重介绍了智能交通系统领域中的两个优化问题，即o d 矩阵推算和 信号灯优化，以及优化算法一遗传算法。第二章描述了0 d 反推的基本原理及数 学描述，重点阐述了求解极大熵0 d 反推模型的混合进化算法，并进行仿真实验， 最后通过分析仿真结果得出结论。第三章阐述混合交通信号相位优化算法的设计 路线、目标函数和解空间，总结出混合交通孤立交叉口信号相位的约束条件和设 计规则。在第四章中，确定混合交通信号相位优化过程中对解空间的搜索方法， 提出基于问题驱动的相位合并优化算法和改进合作型协同进化遗传算法用于混 合交通信号相位全局优化，最后简要介绍信号相位配时。第五章描述单交叉口信 号灯优化软件的功能、界面、数据结构以及程序流程，对软件的输出进行分析， 并将其嵌入到仿真软件中，帮助用户设计信号灯配时方案。第六章总结全文，并 对未来的工作进行展望。 关键词：o d 反推，混合交通，信号相位优化，遗传算法，l e v e n b e r g m a r q u a r d t 算法 a b s t r a c t i n t c l l i g e mn a n s p o r t a t i o ns y s 钯m ( i t s ) 印p l i e sa d v a n c e dt e c l l n 0 1 0 9 i e ss u c h a s i n f b 皿a t i o n ，c o m p u t e r 叩e r a t i o n a lr e s e a r c h a i l da r t 湎c i a l i n t e l l i g e n c e ，e t c ，i n 廿蛆s p o n a t i o na i l ds e 九，i c ec o n 仃0 1 t of b 皿髓e 仃e c t i v e 的n s p o r t a t i o ns y s t e m o dm a 缸xe s t i m a d o na n ds i g a lp h a s eo p t i m i 黯t i o nu n d e rm i x e dt r a f f i c c o n d i t i o na r et w oo fm ei m p o r t a i l to p t i m i z a h o np r o b l 眦si nt h ef i e l do fi t s t h e e n 仃o p ym a 】【i m i z i n g ( e m ) m o d e li sam a i na p p r o a c ht o s 0 1 v et l l eo dm a m x e s t i m a t i o np r o b l e l ，b u tt l l ec w e n ta l 酬m m ss o l v i n gm ee mm o d e la r el i m i t e db y t l l ed i f n c i l l 曰o fc h o o s i n gap r o p e ri n i t i a ls o l u t i o nf o rs e a r c h i n gp m c e d l a c c o r d i n g t om ec 啪tr 0 直d 蛆d 订a f f i cc o n d i t i o n s ，s i g n a lc o n b li nc h i n ai sm a i n l yt i m i n g c o n 臼r 0 1 t h ec u r r c n to p t i i n i z a t i o na l g o r i t h m so n 昀f f i cl i g h t sm a i n l yd on o tb e l o n gt o 9 1 0 b a lo p t i m i z a t i o n g e n e t i ca l g o r i 山m ( g a ) i sa g l o b a lr a l n d o ms e a r c ha l g o r i m m ，w h i c hu s e s 血ei d c a o f n a t l l r a ls e l e c ta n dn a t l l r a lh e r e d i 母i nl i v i l l gn a t u r cf o rr e f b r e n c e ，a n dh a sa d v a n t a g e s w h i l es o l v i i l gt l l ec o m p l i c a t e dp r o b l e m sw h i c ha r el a r g es p a c ea n dg l o b a ls e a r c h ，e t c ai i l i x c de v o l u t i o n a r ya l g 硎t l l i n ( a ) i n t e 舯t i n gg a 距dl e v e n b e r g m a r q u a r d ta l g o r i 岫l ( l m a ) i sp r e s e n t c d h e r ct os o l v et l l ee m m o d e l t h en 啪e r i c a l r e s u l t ss h o wt l l a tm e a p e r f b n n sm u c hb e t t e rt l l a ng a 粕du v 【ai ns o l v i n gt h ee m m o d e l a c c o r d i n gt ot l l es i t i i 撕o no fc h i n at h a tt l l e r ca r eac o 璐i d e r a b l en u m b e ro f b i c y c l e s o nt l l e r o a d s ，s i g n a lp h a s e 叩t i m i z a t i o na l g o f i t t l mu n d c rm i x e d 仃a f 疗c c o n d i t i o ni sp r e s e 玎曲d a s 也e r ea r em a n yc o n s 仃i c 协s i 霉1 a lp h 器e ，t w om e t h o d s ， n a m e l yp h 髂er n e f g e 叩t i i i l i z a t i o nb a s e do nq u e s t i o nd r i v ea n di n l p r o v e dc o o p e r a t i v e c o e v o l u t i o n a r yg e n e d ca 1 9 0 d t h ma r ed e s i g n e dt os e a r c ht h es o l u t i o ns p a c e s i n g l e i n t e r s e c t i o n 扛桶cl i g b t so p t i l i z a t i o ns o f h v a r ei sd e s i 印e da n di m p l e m e n t e d ，a n dt h e o u t i m to f 也es o 脚a r ei sa n a l y s e d i na d d i t i o n ，也i ss o 矗w a f eh a sb e c ne m b e d d e di n t o m ei n t e r s e c t i o ns i 舢1 a t i o ns o r w a r et oh e l pt h eu s e r sd e s i g nm ep h a s es e q u e n c ea n d t h ec o r r e s p o n d i n gd i s 仃i b u t i o no f t h et r a 伍c1 i g h t s t h et h e s i si sa r ：m n g e da sf 0 1 l o w s ： l nc h a p t c r1 ，俩oo f 血eo p t i i n i z a t i o np r o b l e 船i nm ef i e l do fi t s ，n a n l e l yo d m 删xe s t i l n a t i o na n d 妇f f i cl i 曲t sc o n 仃o l ，a n do n eo 曲m i z a t i o na l g o r i m m ，n a m e l y g e n e t i ca l g o r i t h ma r ei n 血o d u c e d i nc h a p t 盯2 ，b a s i cp r i n c i p l ea n dm a t h e m a t i c d e s c 却t i o no fo dm 删xe s t i i n a t i o na r ed c s c 曲e d ，髓d 血e nam i x e de v 0 1 u t i o n a r y a l g o f i l mi sp r e s e n t e dt o s o i v e l e0 一dm a 缸xe s t i m a t i o np m b l e m f i n a l l y m e i l t a b s t r a c t a l g o r i t l l mi st e s t e db yt l l es i m u l a t i o ne x p 谢m e n ta n d 也en m n 酣c a lr c s u l t ss h o wi t s e 伍c i e n c y 1 nc h 印t e r3 ，m ed e s i g nm e t h o d ，t l l eo b j e c t i v e 劬c t i o na n d 血es o l u t i o n s p a c eo ft h es i 班a lp h a s eo p t i m i z a t i o na l g o r i m mu n d e rm i x e d 打a m cc o n d i t i o na r e d e s c 啪e d t h ec o n s m c t so ft l l e s i g n a lp h a s ea 1 1 dm ep h a s ed e s 咖n 1 1 e s a r e s 咖a r i z e d i nc h 印t e r4 ，押om e t h o d s ，n 锄e l yp h a s em e r ：g eo p d m i z a t i o na l 鲥t h m b a s e do nq u e s t i o nd r i v ea n di m p r o v e dc o o p e m t i v ec o e v o i u t i o n a r ) rg e n e t i ca l g o r i t h m 盯e p r e s e n t e dt o s e 盯c ht h es 0 1 u t i o n s p a c e f i n a l l y ，s i g n a lp h 嬲ed i s 缸b u t i o ni s 面d u c e d i nc h a p t e r5 ，m ef 洫c t i o n ，i n t 剧e ，d a t as 咖c n l r ea n dp r o c e d u r eo f s i n g l ei t e r s e c t i o n 圩a 伍cl i g h 忸叩t i m i z a t i o ns o f h v a r ca r ed e s c r i b e d ，a n dt h eo u t p u to f t h es o f t w a r ei sa m l y z e di a d d i t i o r l m i ss o f t w 雏et l a sb e e ne n l b e d d e di n 的t h e i n t e r s e c d o ns i m u l a t i o ns o f t w a r et oh e l pt l l eu s e r sd e s i g n l ep h a s es e q u e n c ea n dt h e c o r r e s p o d i n gd i s m b u t i o no ft l l et r a m cl i 曲t s a n d 丘n a n y ，c h 印t e r6i sac o n c l u s i o n w i mt h es m m a r yo f t h et l l e s i sa n dp m s p e c tr e s e a k h k e y w o r d s ：o dm a 砸xe s t i m a t i o n ，m i x e dt r a 伍c ，s i g i l a lp h a s eo 埘m i z a t i o n ， g e n e t i c 越g 嘶m m ，l e v 衄b e r g - m 哪u a r d ta l g o r i l i n 浙江大学硕士学位论文 第1 章绪论 摘要：本章概述了智能交通系统的基本构成及研究方向，着重介绍了该领域中 的两个优化问题，即0 d 矩阵推算和信号灯优化，并介绍了求解上述优化问题的 算法一遗传算法，最后描述了本论文的章节安排。 关键词：智能交通，o d 矩阵推算，信号灯控制，遗传算法 1 1 智能交通系统 智能交通系统( i n t e l l i g tt r a 璐p o m t i o ns y s t e m ，简称i t s ) 是将先进的计 算机技术、信息技术、通信技术、控制技术和人工智能等有效地综合运用于交 通运输、服务控制和车辆制造等，把车辆、道路、使用者紧密结合起来，形成 一种实时、准确、高效的综合运输系统【。 当现有的道路基础设旖建设满足不了快速增长的交通需要，必须依靠高科 技来优化现有的道路运输系统，进行有效的交通管理，于是i t s 应运而生。 智能交通系统基本构成包括先进的交通管理系统、先进的旅行者信息系统、 先进的公共运输系统、先进的车辆控制系统、商用车辆运营系统和自动公路系 统。 目前i t s 的研究方向集中在交通规划、管理、控制与诱导以及交通模型开 发等方面。交通出行矩阵( o r i g i n d e s t i n a t i o n m a 仃i x ，简称0 d 矩阵) 推算和信 号灯优化是其中两个重要的优化问题。 1 2 o d 矩阵推算 1 2 1o d 矩阵的概念 o d 矩阵是交通网络中所有起点( o r i 西n ) 与终点( d e s 缸a i i o n ) 之间出行交 换数量的表格，是对路网中交通需求最本质的反映。 交通工程领域中有3 种不同性质的o d 矩阵：区域o d 矩阵、线路o d 矩阵和节 点o d 矩阵1 2 l 。本文研究的o d 矩阵是指区域o d 矩阵，指从一个交通区至另一个 交通区的出行量分布矩阵。 0 d 矩阵是交通规划、管理和控制中不可缺少的基础性数据资料，是进行城 市交通规划与管理、公路网规划与管理的基本依据。交通流分配在交通管理中起 着关键性的作用，在均衡交通状态下，进行交通流量分配的前提就是必须事先知 堑兰垄堂鱼堡主主堡垒查 1 3 2 定时式控制中的几个重要概念 ( 1 ) 关键车道 每个相位绿灯时段长度不是由所有通行车道决定的，而是由一组疏散时间最 长的车道决定，这就是关键车道。关键车道简化了信号灯配时的分析。 ( 2 ) 饱和流量f 2 l 】 一次连续的绿灯信号时间内，进口道上一列连续车队能通过进口道停车线的 最大流量。影响因素：交叉口几何因素、渠化方式以及各流向交通冲突等。 ( 3 ) 交通流量盯：某一定时段内实际通过的车辆数。 ( 4 ) 通行能力吼：道路交通设施中，在要考察的地点或者断面上，单位时间 内能通过的最多交通单元【18 1 。 吼= 吼。萼 ( 5 ) 交通流量比 y ：苎! 塑羞丝圭熏銮望量! 塑! 堕! ：旦t 第i 相饱和交通量( 辆时) 吼 ( 6 ) 饱和度 各车道饱和度是各车道实际到达交通量与该车道通行能力之咄1 8 l 。 x ：旦：尘：l ，。三 q cq ，t e gt e g 要使工 l ，即可 毕( 一般交叉口，x 上限为o 9 5 ) 1 3 3 单路口交通信号控制研究现状 1 3 3 1 国外研究现状 英国学者f w 曲s t e r 在5 0 年代提出了一套理论和方法( 以下称w 曲s t e r 法) ， 具有高严谨性及适应性。孤立交叉口的配时设计，大多是在w e b s t e r 法的基础上 发展起来的。1 9 8 0 年，澳大利亚的r 阿克塞立科在w 曲s t c r 法的基础上引入了 “停车补偿系数”，并将它与车辆延误时间结合在一起，用以评价信号配时方案 的优化程度 2 2 】。1 9 8 4 年，日本学者m n a k a t s u y 锄a 等【2 3 】将p a p p i s 法加以推广， 提出两个理想的交叉路口的信号灯模糊线控制方法，但它和实际应用有较大的差 第一章绪论 距。1 9 9 5 年，南韩学者j e e - h y o n gl e e 等【2 4 1 提出分散控制方法，对信号化交叉口 群进行模糊控制。 实际应用的研究成果主要是英国的t r a n s y t ( t r a 伍cn e t w o r ks m d yt 0 0 1 ) 系 统和s c o o t ( s p l i i _ c y c l e o 凰e to p t i m i z a t i o nt e c h n i q u e ) 系统、澳大利亚的 s c a t s ( s y d n e yc o o r d j n a t c da d 印t i v e1 h 艏cs y s t e m ) 等。t 鼬n s y t 系统是一种脱 机操作的定时控制系统，是最成功的静态系统之一。t 黜s y t 也存在许多不足， 不足之处主要是计算量很大，周期长度不进行优化。s c 0 0 t 系统【2 5 是在 t 黜n s y t 的基础上形成的，其模型及优化原理均与t r a n s y t 相仿。不同的是 s c o o t 是方案形成方式的控制系统。s c a t s 是一种以方案选择式优选配时方案 与单点感应控制作调整结合的实时区域自适应交通信号控制系统，由澳大利亚开 发，是目前世界上最先进的交通信号控制系统之一。 1 - 3 3 2 国内研究现状 我国对城市交通管理与控制的研究起步较晚。对于交叉口的优化控制研究更 多的局限于理论研究，一类是信号配时优化，另一类是信号相位优化。 杨锦冬、杨东援建立了城市信号控制交叉口信号周期时长的优化模型 2 6 ： 陈森发等提出两级递阶分解一协调模糊线控制田】的新方法；董超俊等采用双层反 馈神经网络进行城市交通控制信号配时优化【2 8 】；顾怀中等提出模拟退火信号配 时优化算法 2 9 ) ；陈小锋等提出基于遗传算法的交通信号动态优化方法 3 0 l ：焦敏 朵等提出交叉口信号配时的人工蚂蚁优化 3 l 】；徐良杰等提出基于一种新的混合 算法的交通流控制优化模型田】。 以上方法均是对信号周期和绿信比的优化，以下是目前国内学者对于相位方 案设计的一些研究成果。 马万经等提出二次过街条件下行人相位的设计方法 3 3 1 ，即运用相位组合技 术，对 行人相位的设计方法 3 3 1 ，即运用相位组合技 术，对行人相位与机动车相位的各种可能的组合。王浩等提出根据交叉口设计合 理安排相位相剧34，考虑了交叉口车流轨迹、左转车导流线设置、左转车待行 区设置等与相位相序的关系。赵晓华等提出应用混杂系统最优控制的两状态法， 寻找单交叉口信号灯的最佳相位轮转次序和最佳绿信比1 3 5 】。杨晓光等通过设置 行人专用相位前后通行能力和人均过街延误的对比分析，得出了两相位交叉口行 人专用相位的设置条件p 。胡准庆等提出，通过对不同种类车辆设计不同信号 相位的方法，大大减少不同流量之间的相互影响和制约作用 3 ”。尹宏宾、徐建 闽针对专用道、车流方向及车流组成，提出了6种典型交叉口的信号相位设计方 案【38】。同济大学的杨晓光等提出在相位设计时加入诱导信息，根据不同的道路 第一章绪论 1 4 2 遗传算法的特点 遗传算法是一种仿生算法，它模拟的机制是一切生命和职能的进化过程。主 要有以下几个优点： ( 1 ) 并行性。进化计算的操作对象是一组可行解而非单个可行解，搜索轨 道有多条而非一条。 ( 2 ) 通用性。进化计算的评价只需目标函数的取值信息而不需其梯度等高 价值信息，适用于任何大规模、高非线性、不连续、多峰函数以及没有明确解析 表达式的目标函数优化。 ( 3 ) 可操作性。进化计算操作的对象是编码后的可行解，目标函数作为其 个体的适应度函数。 尽管进化算法具有很多优越性，但它同样具有很多不足： ( 1 ) 算法的收敛速度会随着编码长度的增加而降低。 ( 2 ) 随着进化进行，种群失去多样性而早熟收敛。 1 4 - 3 协同进化算法 针对进化算法求解复杂系统存在的不足，借鉴生态学协同进化的理论，p o t t e r & d e j o n g 等提出了协同进化算法( c o e v o l u t i o n a r ) ra l g 嘶t h m ) 。协同进化算法与 传统进化算法的最大差异在于进化种群、编码方法大不相同，进而带来适应度评 估方法的不同。协同进化中，各子种群独立进化，只有在适应度评估的时候才进 行信息的交换；个体不是对待求解问题的所有变量编码，而是对部分变量编码； 对个体进行适应度评估的时候，单个种群中的个体仅是待优化系统的一个部分， 对其单独评估是无法完成的，必须将其和其他部分构成一个整体，才可利用目标 函数进行适应度评估，即个体适应度不是仅由目标函数决定。 协同进化算法主要有两种：竞争型协同进化算法和合作型协同进化算法。本 论文重点介绍合作型协同进化算法。 1 4 4 合作型协同进化算法 合作型协同进化算法将复杂系统中待优化变量分组，将一个复杂的多变量系 统转换为多个相对简单的少变量系统，这就是种群分割。种群分割是合作型协同 进化算法的关键技术之一。对分组后的多个少变量系统分别编码，形成多个独立 的子种群，各予种群独立进化。这就是协同进化算法与传统进化算法在进化种群 和编码方法两方面的差异。只有在进行适应度评估的时候，子种群之间才进行信 第一章绪论 协同进化算法与传统进化算法的一个重要差异在于适应度评估方法的不同。 图1 3 详细阐述了其中一个种群个体适应度的计算。计算个体适应度的第一步就 是从其他种群中选择代表个体。目前，我们常用的选择代表个体的方法是选择目 前每个种群的最优个体作为代表个体。然后，在待评估个体和从其他种群选择的 个体之间建立协作关系。最后，应用协作关系到目标问题上来计算适应度。适应 度严格分配到待评估个体，并没有和其他种群参与协作的代表个体共享。 1 5 论文主要内容简介 本文围绕智能交通系统领域中两个优化问题即o d 矩阵推算、混合交通信号 灯优化及优化算法一遗传算法展开，详细介绍了求解极大熵o d 反推模型的混合 进化算法、混合交通信号相位优化算法以及单交叉口信号灯优化软件。其中第二 章描述了o d 反推问题的基本原理及其数学描述，重点阐述了求解0 d 反推极大 熵模型的混合进化算法，并进行仿真实验，最后通过分析仿真结果得出结论；第 三章介绍了混合交通信号相位优化算法的设计路线、目标函数和解空间，重点阐 述了混合交通孤立交叉口信号相位的约束条件和设计规则；第四章介绍了混合交 通信号相位优化过程中对解空间的搜索方法，即基于问题驱动的相位合并优化算 法和改进合作型协同进化遗传算法在混合交通信号相位优化中的应用，最后介绍 了信号相位配时；第五章描述了单交叉口信号灯优化软件的功能、界面、数据结 构以及程序流程，对软件的输出进行分析，并将其嵌入到仿真软件中，帮助用户 设计信号灯配时方案；第六章总结全文，并对末来的工作进行展望。 1 0 第二章应用混合进化算法求解极大熵0 d 反推模型 极大熵原理为基础的极大熵( m e ) 模型5 4 1 、以最小二乘原理为基础的广义最小二 乘( g l s ) 模型【5 5 】、以信息论原理为基础的最小信息量( i m ) 模型阳、以极大似然原 理为基础的极大似然( m l ) 模型闻等。 采用路段交通量推算o d 矩阵所需数据主要有：路段交通量信息、先验o d 矩阵信息以及路径选择信息。 2 2o d 反推问题的数学描述 在众多的0 d 矩阵推算模型中，极大熵模型由于其模型结构简单、推算精度 高且求解方便，应用最为广泛。它认为车辆的出行是随机的，每种可能出现的 o d 分布状态，都有一个相应的存在概率，实际存在的o d 分布状态，就是存在 概率最大的一个，其数学描述为： 假设刀为o d 量的交通分区数目，则待估计的o d 量个数为： k n t m 1 ) 。调 查交通量的路段数目设为 厶根据路段流量守恒，有下面m 个线性方程组成立： 卫 f ，p ? = v ，女= 1 ，2 ，肘 扣 ( 2 3 ) 其中，表示观测的第七个路段流量， 表示第f 个o d 量的值，芦产表示第f 个o d 量在第_ | 个路段上的分配比，( o 计1 ) 。 上述方程组( 2 3 ) 可用向量的形式表示为： p r = r p = p 矗砖 p ；露p ； p ? p ：p ： 矿= ( n ，叱，v “) 7( 2 4 ) 即尸是m w 维矩阵，r 是维列向量，矿是m 维列向量。其中p ，矿已知， r 为待求向量。一般情况下，由于肘 o ( 2 6 ) 引入l 哪n g e 乘子 三( r ，a ) = s ( d a 1 ( p r 一矿)( 2 7 ) 对上述优化问题进行转换，将有约束问题转化为无约束问题。j 等酬一p ：1 ( 2 s ) 霄 “1。【2 邵 l p ? e x p ( 一厶一以p ：) = v 。 上述方程组是含有m+1个未知数o，l，”，九m和m+1个方程的非线性方程 组。求解原目标优化问题转化成求解上述非线性方程组，求出o，九l”，m后， 再由式(29)求得r。 _ l f = e x p ( 一厶一以p ；) ，f = 1 ，2 ， i = l 2 3 求解0 d 反推极大熵模型的混合进化算法 ( 2 9 ) 基于极大熵模型的0 d 反推需要求解一个优化问题，目前求解该优化问题的 算法对初值要求非常严格，如牛顿法【58 1 、l e v e n b e r g - m a r q l 珀f d t 算法 5 9 】 ( l e v e n b e r g - m a r q u r d ta l g o r i 恤n ，l m a 以下简称l m 算法) 等。牛顿迭代法思 想直观自然，易于被接受，但在实际应用时却往往受到很多条件的限制。最大的 m， i | 。 鼢 ，d。 叭 扣 第二章应用混合进化算法求解极大熵0 d 反推模型 限制之一是牛顿迭代法收敛所要求的初值必须取自解的某个小邻域，对初值要求 比较严格。l m 算法是在牛顿法基础上形成的比较有效的求解非线性方程组的迭 代算法，其基本思想是将非线性问题逐次线性化形成迭代程序。l m 算法是神经 网络、高斯一牛顿法与梯度下降法的结合，既有神经网络的自学习特性，也有高 斯牛顿法的快速收敛特性，还有梯度下降法的全局搜索特性【6 “。但l m 算法对 初值准确性要求较高，易发散。 遗传算法【6 1 ( g e n e t i ca l g o r i t l l m ) 是一种模拟自然进化过程搜索最优解的方 法，在使用时有其它方法难以企及的优势：它不要求目标函数满足诸如连续性、 导数存在和单峰等假设【6 ”。然而遗传算法也存在根本性缺陷：演化过程中容易发 生“过早收敛”现象。“过早收敛”是指遗传算法在演化过程中长时间甚至永久 停滞在某一局部最优解，而不是全局最优解上【6 2 1 。传统的遗传算法局部搜索能力 较差，尤其是接近局部最优解时，收敛速度比较慢，最终搜索得到的结果往往不 是全局最优解，而是局部最优解。 针对已有算法存在的不足，本文提出结合遗传算法和l m 算法的混合进化算 法求解极大熵o d 反推模型。混合进化算法思想是结合遗传算法和l m 算法各自 优势，首先用遗传算法搜索满足精度要求的最优解( 以下简称“最优解”) 邻域 内的解，将其对应的个体作为l m 算法初值，然后进一步搜索“最优解”。通过 遗传算法的迭代获得离“最优解”较近的高质量初始值，提高l m 算法搜索“最 优解”的效率。具体算法步骤如下： s t e p l ：初始化产生一种群。 s t 印2 ：用遗传算法求解，得到“最优解”邻域内的解及其对应的个体。 采用实数编码，其优势在于可以大大缩短编码长度，且染色体比较直观：第f 个基因代表第f 个上口g ，硼弘乘子，个体长度就是三昭聊群乘子个数，即方程组中 未知数个数。适应度函数为2 0 0 0 百其中 j = 。以最大进化代数为 停机准则，即f m ，即方程组中未知量 的个数大于方程的个数，因此仅由式( 2 ，1 ) 不能唯一确定o d 矩阵，必须采用数学 优化模型，如设立目标函数： m in 以e k v ) ( 2 2 ) 式(2 2 ) 中，r 为o d 估计矩阵；f 为先验o d 矩阵；y 为路段观测交通量向量； v 为按丁分配的交通量向量。 根据 浙江大学移硕士学位论文 突以及垂直方向机动车与非机动车左转的冲突。 从行人安全的角度考虑不允许出现的行人和机动车，非机动车的冲突包括： ( 1 ) 行人过街和机动车的冲突；( 2 ) 行人过街和非机动车的冲突。 另外，因为本优化问题是为特定的交叉口设计最优的相位序列配时方案，因 此交叉口的实际车流量是必不可少的约束条件。 3 4 2 3 相位相序的约束 相位相序的约束包括： 1 连续性约束。对同一个交通流设置两种以上相位时，这些相位在时间上 要保证连续性；对同一进口道的不同方向车流在不同相位中放行时，应将它们所 在信号相位连续显示。 2 交叉口不同相位交通流平稳衔接【“，避免车流潜在的交叉冲突。 3 一般情况下，先放直行后放左转。 4 相位绿灯间隔时间最小【7 。 5 相序设计应遵循在保证交通安全的前提下，使损失时间最小的原则7 0 1 。 3 4 3 混合交通信号相位的设计规则 信号配时设计基本规则： 1 每种相位模式都使用尽可能少的相位数，形态规则的交叉口的相位模式 的相位数不宜超过6 个。十字路口信号相位大多为5 相位或者6 相位；丁字路口 信号相位大多为3 相位；渠化比较粗或者没有的十字路口一般采用两相位控制。 2 道路具有机动车、非机动车分隔线且道路宽度大于1 5 m ，应设非机动车 道信号灯【2 1 1 。非机动车较多，对机动车干扰较大时，需设非机动车信号灯。一般 情况下，非机动车信号灯从属于机动车信号灯。通过人行横道的行人高峰小时流 量超过5 0 0 人次，应设置人行横道信号灯【2 ”。当人行横道太长，绿末行人无法安 全通过交叉口时，可考虑在中间设置安全岛，供行人驻足，道路中央分隔带的宽 度较大时，可实施行人二次过街方案。 3 信号配时设计应与空间设计相协调【_ 7 0 】。 4 信号相位应根据交通流实际流量及特征灵活组合1 7 m 。对向车流大体均衡 的情况下，可选择对向对称；如果获得通行权的几股车流中，有一股车流所需的 通行时间较长，这时可以利用早断早起技术，截断通行时间较小的车流，放行与 通行时间长的车流不冲突的其它车流。 5 左转信号相位设计规则：左转车流包括保护式、冲突式和无对向式左转 三种方式，其中保护式左转相位分为三种模式：双向左转相位、左转+ 直行混合 式相位、左转保护+ 冲突混合式相位【7 l l 。 设置左转专用相位的前提条件为有左转专用车道。因此，进口道只有一条车 第三章混合交通信号相位优化算法设计 道无左转专用车道时不能设置左转专用相位。有3 个以上车道的方向车流要分出 专门的相位。左转车每周期平均到达3 辆时，宜用左转专用相位【2 ”。同一相位各 相关进口道左转车每周期平均到达量相近时，宜用双向左转专用相位，否则宜用 单向左转专用相位【2 ”。专门的左转相位一般都是双向左转。 6 直行相位的设计【7 1 1 分为两个过程：( 1 ) 设置直行相位的判断规则：( 2 ) 车道 配置规则，为直行相位分配适当车道。直右信号相位时间在相位周期中占比例较 大。 7 一般不考虑右转机动车和行人的冲突。右转机动车相位的设计：一是迟 启；二是放在其他相位。 3 0 塑兰查堂鱼丝主堂堡垒圭 第4 章混合交通相位优化解空间搜索算法 摘要：本章介绍了混合交通信号相位优化过程中对解空间的搜索方法，即基于 问题驱动的相位合并优化算法和改进合作型协同进化遗传算法在混合交通信号 相位优化中的应用。最后介绍了信号相位的配时。 关键词：混合交通相位优化，解空间，相位合并，协同进化遗传算法 路口信号控制【6 9 】的作用是：减少路口内的冲突点，控制路口内冲突，明确不 同流向、不同种类交通流通过路口的时间路权。路口信号控制的内容有：根据放 行方法和路口渠化条件确定信号相位，根据路口内冲突情况和路口内空闲时间最 少的要求确定信号相序，根据各流向上到达的流量情况确定信号配时。 对解空间的搜索方法是混合交通信号相位优化算法的核心，本章详细介绍两 种搜索方法，即基于问题驱动的相位合并优化算法和改进合作型协同进化遗传算 法在混合交通信号相位优化中的应用。 4 1 基于问题驱动的相位合并优化算法 基于问题驱动的相位合并优化算法就是根据一系列问题进行相应的合并操 作，最终得到最优的相位序列的过程。合并的对象是根据约束条件确定的所有方 向所有可能的子相位。对于图3 2 中的十字路口，子相位的解集为南东北西方向 的机动车左转、直行和右转，非机动车左转和直行以及行人过街。判断是否合并 的标准是交叉口车辆平均延误时间有没有减少。合并的意义在于保证在可行解空 间中寻优，且可以保证每个周期每个子相位车流至少通行一次。合并相位的绿灯 时间取被台并相位的绿灯时间的最大值，以保证每个子相位的车流在合并相位中 放行车流数量不会大幅度减少。图4 1 为假定道路交通组织合理的前提下，相位 合并优化算法的设计思想。图4 2 为相位合并优化算法的总体框架。 图4 1 相位合并优化算法设计思想 甲由筹 i 第四章混合交通相位优化解空间搜索算法 图4 2 相位合并优化算法总体框架 4 1 1 交叉口空间交通组织定制 定制的交叉口空间交通组织包括： 1 交叉口形状 2 对向是否对称 对向直行、左转、右转渠化是否对称? 相应车道数是否大致相同? 3 单行道情况 4 进出口车道个数和宽度 5 有无机动车、非机动车分隔带( 有无自行车道) 6 有无人行横道，有无驻足岛 7 有无公交专用车道 8 有无机动车、非机动车可变车道 浙江大学 硕士学位论文 9 有无左转待行区 l0 车道渠化，渠化类型包括： ( 1 ) 左转专用车道 ( 2 ) 直左混合车道 ( 3 ) 右转专用车道 ( 4 ) 直行专用车道 ( 5 ) 直右混合车道 ( 6 ) 回转车道 ( 7 ) 左转掉头混合车道( 左转导向车道准许掉头标志) 4 1 2 信号相位规则定制 定制的信号相位规则包括： 1 对向是否对称? ( 对向空间交通组织大体相同的情况下可选) 2 机动车、非机动车以及行人问题 ( 1 ) 机非是否分离( 是否具有非机动车信号灯) ? ( 2 ) 是否具有人行横道信号灯? ( 3 ) 行人是否二次过街? 3 左转问题 ( 1 ) 是否禁止左转? ( 2 ) 是否需要左转专用相位? ( 3 ) 是否可设置双向左转专用相位? 4 右转问题 ( 1 ) 是否具有机动车右转箭头灯( 绿灯时是否禁止机动车右转弯) ? ( 2 ) 是否对右转机动车实行迟启控制? 5 回转问题 ( 1 ) 回转是否放在垂向赢行? 6 冲突问题 ( 1 ) 某方向直行与其对向左转冲突是否允许? ( 2 ) 某进口的直行与之右边进口的左转冲突是否允许? ( 3 ) 出口汇入冲突是否允许? 4 1 3 基于问题驱动的相位合并优化算法步骤及流程图 基于问题驱动的相位合并优化算法步骤如下： s o 印l ：根据影响可行相位的空间路权分配问题确定所有可能的子相位。 s t 印2 ：根据用户的要求进行合并。例如，若用户要求对向信号灯对称的话， 则合并所有的对向子相位，子相位数目减少一半。 第四章混合交通相位优化解空问搜索算法 s t e d 3 ：合并流量相差不大、不存在严重冲突的子相位。冲突的判断通过计算 冲突矩阵与相位向量的值再与相位向量转置的值获得：结果为1 ，则相位中存在 冲突；结果为0 ，则相位中不存在冲突。下同。 s t e d 3 1 ：对东、西、南、北方向的相位分别进行合并。 s t e d 3 2 ：合并对向的相位。 s t e d 3 3 ：合并垂向的相位。 或者 s t 印3 1 ：对南方向所有可能合并的相位进行罗列，包括两两合并和三个相 位合并两种类型。形如( a b ) 、( a c ) 、( a e ) 、( a b c ) s t 印3 2 ：从北方向中找出可以和( a b ) 合并的相位，得到( a b x ) 等，依次对 ( a c ) 、( a e ) 、( a b c ) 等进行类似的操作。 s t 印3 3 ：从东方向中找出可以和( 衄x ) 合并的相位，得到( a b x y ) 等，依次 进行下去。 s t 印3 4 ：从西方向中找出可以和( a b x y ) 合并的相位，依次进行下去。 s t e p 3 5 ：对东、北、西方向实施类似的操作。 s t e p 4 ：根据影响相位拆分与叠加的问题进行相位微调。 s t e p 5 ：合并流量相差不大、存在一般冲突，合并后交叉口车辆平均延误时间 有所较少的子相位，最终得到满足用户要求的一个相位序列。 步骤同s c c p 3 1 s 唧3 3 或s t e p 3 1 s t 印3 5 。 s t 印6 ：对上述相位序列进行信号配时。 s t e p 7 ：对最佳配时的信号相位序列进行评价。 根据用户要求获得可行相位，进而进行相位合并时，查阅问题答案的顺序( 即 s t 印1 和s t e p 2 的详细步骤) 如下： ( 1 ) 交叉口形状 ( 2 ) 单行道情况 ( 3 ) 对向是否对称? ( 4 ) 有无人行横道? ( 5 ) 是否具有人行横道信号灯? ( 6 ) 有无驻足岛? ( 7 ) 行人是否二次过街? ( 8 ) 有无机动车、非机动车分隔带( 有无自行车道) ? ( 9 ) 机非是否分离( 是否具有非机动车信号灯) ? ( 1 0 ) 是否禁止左转? ( 1 1 )有无左转专用车道? ( 1 2 )有无直左混合车道? 浙江大学硕士学位论文 ( 1 3 ) 是否需要左转专用相位? ( 1 4 )有无左转待行区? ( 1 5 )有无回转车道? ( 1 6 ) 有无左转掉头混合车道( 左转导向车道准许掉头标志) ? ( 1 7 )回转是否放在垂向直行? ( 1 8 ) 有无右转专用车道? ( 1 9 )有无直右混合车道? ( 2 0 ) 右转车迟启? ( 2 1 ) 是否具有机动车右转箭头灯( 绿灯时是否禁止机动车右转弯) ? ( 2 2 ) 有无直行专用车道? ( 2 3 ) 出口汇入冲突是否允许? ( 2 4 ) 某方向直行与其对向左转冲突是否允许? ( 2 5 ) 某进口的直行与之右边进口的左转冲突是否允许? 算法流程图如图4 3 。 图4 3 基于问题驱动的相位合并优化算法流程图 塑兰垄堂鱼塑主兰堡垒圭 4 2 改进合作型协同进化遗传算法在混合交通信号相位优化 中的应用 4 1 节介绍的基于问题驱动的相位合并优化算法是一种粗糙的优化算法，可 以保证得到的相位是合理的，但是优的程度不能保证。原因是：某种合并方式可 以减少交叉口的车辆平均延误时间，但是或许存在其他的合并方式，