（计算机软件与理论专业论文）基于改进遗传算法的城市交通诱导策略研究.pdf

南京邮i u 人学硕j 二研究生学位论文 摘要 摘要 基于动态信息的城市交通诱导策略( 简称为：路径诱导策略) 是智能交通系统( i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m s ，简称i t s ) 研究的一个重要方面，旨在通过向驾驶员提供基于实时 交通信息的最佳行驶路径来达到诱导出行行为，减少车辆在道路上的逗留时间，进而实现 改善城市交通和避免交通拥挤、阻塞的目的，是目前国内i t s 的开发应用热点之一。路径 诱导策略是一种框架体系，包括路径诱导算法与路径诱导模型，它确定如何对车辆实施诱 导、有效均衡路网中的交通流。 论文重点对基于动态信息的城市交通诱导策略中的路径诱导算法及其与交通控制策 略的集成进行了深入研究。提出了一种新型的路径诱导算法，即邻近交叉遗传算法( v i c i n i t y c r o s s o v e rg e n e t i ca l g o r i t h m s ，简称v c g a ) 。v c g a 采用邻近交叉算子，即染色体交叉处 发生在邻近节点之间，邻近交叉算子的特点使交叉新个体具有多样性，消除了简单遗传算 法中早熟收敛的不足，提高了算法收敛到全局最优解的概率；采用前向变异策略，有效地 抑制了算法的退化；采用稳态繁殖遗传方式，更好地保护了适应度高的遗传个体，使所求 最优路径更加贴近实时的交通状态，切实达到诱导目的，提高整体路网的运行效率。 本文实现了路径诱导策略与交通控制策略的集成。路径诱导策略和交通信号灯控制策 略是城市智能交通管理最重要的两个方面，但目前路径诱导策略中大多只考虑路段的行驶 时间，忽略了交叉口的等待通行时间。而实际上，城市道路系统中交叉口的延误占整个行 程时间的很大部分，甚至超过路段行驶时间n 1 ，因此交叉口的延误是一个不可忽略的重要 因素。在本文提出的路径诱导算法中，对适应度函数的设计考虑了交叉口延误的影响，从 而实现了路径诱导策略与交通控制策略的集成。 本文对邻近交叉遗传算法( v c g a ) 进行实现，并基于此算法通过m a t l a b 对河北省保 定市裕华路区域部分交通路段进行仿真。仿真结果表明v c g a 是相当有效的，且收敛速度 更快，性能更稳定。本文所研究的内容适应当前科学技术的发展与更新，具有一定的实用 价值。 主题词：遗传算法；城市交通诱导策略；智能交通系统 南京邮f 也人学硕j ：f i j f 究生学位论文 a b s t r a c t a b s t r a c t u r b a nt r a f f i cf l o wg u i d a n c es t r a t e g yb a s e do nd y n a m i ct r a f f i cf l o wd a t ai sa ni m p o r t a n t r e s e a r c hi nt h ef i e l do fi n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ( i t s ) ，w h i c hg u i d et h eb e h a v i o r so f t r a v e l e r sb yp r o v i d i n gt h e m 、析t ho p t i m a lr o u t eb a s e do nr e a l t i m et r a f f i ci n f o r m a t i o n a sar e s u l t t h et r a v e lt i m ec a nb es a v e da n dt h et r a f f i cc o n g e s t i o nc a nb ea v o i d e d r o u t eg u i d a n c es t r a t e g yi s ak i n do ff r a m e w o r k ，i n c l u d i n gt h ei n d u c t i o no ft h em o d e la n da l g o r i t h m i n d u c e d r o u t e g u i d a n c es t r a t e g yi n d u c e dv e h i c l e sa n db a l a n c e dt h en e t w o r ko ft r a f f i cf l o w i nt h i sp a p e r , a u t h o ra n a l y z e so p t i m i z a t i o nm e a n sb a s e do nt h er e s e a r c ho ft h er o u t e g u i d a n c es t r a t e g ya n dt h ei n t e g r a t i o no fr o u t eg u i d a n c es t r a t e g ya n dt r a f f i cc o n t r o ls t r a t e g y b a s e do ns g a ( s i m p l eg e n e t i ca l g o r i t h m ) ，an e wr o u t eg u i d a n c ea l g o r i t h mi sb r o u g h to u t v i c i n i t yc r o s s o v e rg e n e t i ca l g o r i t h m s ( v c g a ) t h ep r i m a r ya d v a n t a g e so fv c g a a r es h o w n a sb e l o w ：t h es t e a d y s t a t er e p r o d u c t i o np r o t e c t st h eo p t i m i z e dg e n e t i ci n d i v i d u a l s ，t h ev i c i n i t y c r o s s o v e rm a k e st h eg e n e t i ci n d i v i d u a l sd i v e r s i f i e d ，a n df o r w a r dm u t a t i o nd e p r e s s e st h e a l g o r i t h md e v o l u t i o n se f f e c t i v e l y r e a l - t i m er o u t eg u i d a n c ei m p l i e st h et r a f f i cs t a t eh a st i m e l y c h a n g e ，v e h i c l e st r a v e lr o u t i n gp l a n 埘mi nr o u t i n gg u i d a n c es t r a t e g yh a v en o tf i x e d n e s s ，a n di t w e l lt a k ep l a c ec h a n g e 澌t ht h er e a l t i m et r a f f i cs t a t ec h a n g e i nr o u t i n gg u i d a n c ep r o c e s s ，t h e a p p l i c a t i o n o fr e a l - t i m et r a f f i ci n f o r m a t i o nd a t ae n a b l et h er o u t i n gg u i d a n c es t r a t e g yt oh a v e t i m e l i n e s sa n dd y n a m i c ，m o r e o v e rt h i sc h a r a c t e r i s t i cw i l lc a u s et h er o u t i n gg u i d a n c et oc o n f o r m t ot h er o a dn e tr e a l i t yc o n d i t i o n ，a l s of u r t h e ri n c r e a s e dt h es y s t e mu s a b i l i t y u s u a l l y , o n l yt h el i n kt r a v e lt i m ei sc o n s i d e r e da n dv e h i c l e sc r o s s i n gt i m ei sn e g l e c t e d i n f a c t ，t h ev e h i c l e sc r o s s i n gt i m ea c c o u n tf o rm u c ho ft h et r a v e l i n gt i m e ，e v e nl o n g e rt h a nt h el i n k t r a v e lt i m e w ei n t e g r a t e dt h er o u t i n gg u i d a n c es t r a t e g ya n dt r a f f i cc o n t r o ls t r a t e g yb a s e do n f i t n e s sf u n c t i o n a tt h ee n do ft h ep a p e r , w eg i v es i m u l a t i o n so fb a od i n gt r a n s p o r t a t i o nn e ta n dp r o v e dt h e e f f i c i e n c yo fv c g a f i n a l l y , w ep u tf o r w a r ds o m ef u r t h e ri m p r o v e m e n ts u g g e s t i o n t h e c o n t e n tw h i c ht h i sp a p e rs t u d i e si ss u i t a b l ef o rt h ec u r r e n ts c i e n t i f i ca n dt e c h n o l o g i c a l d e v e l o p m e n ta n dr e n e w a l ，a n dh a ss o m ep r a c t i c a lv a l u e k e y w o r d s ：g e n e t i ca l g o r i t h m ；u r b a nt r a f f i cf l o wg u i d a n c es t r a t e g y ； i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m s i i - 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：霉峰日期：a 匹9 l 耻 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：翟峰导师签 期：塑轴阻l 南京邮i 乜人学硕j - 。“湘) l 生学位论文 第1 章绪论 1 绪论 1 1 课题背景 交通运输是国家兴旺发达的重要标志之一。由于交通运输的发展，促使物资交流和人 们往来活动日趋频繁，并大大地缩短了时间，提高了工作进程。然而随着交通运输的高速 发展，也带来了许多弊病，尤其是地面的汽车交通运输，不论是发达国家还是发展中国家， 都存在着不同程度的问题。近半个世纪以来，交通拥挤、道路阻塞、交通事故频繁正越来 越严重地困扰着世界各国的大城市。 在我国，随着我国汽车工业的发展和城市化进程的加快，城市机动车年增长瞠1 在1 5 以上。天津市2 0 0 4 年新增轿车六万辆，总量超过3 0 万辆，增长速度为2 0 。目前北京市汽 车拥有量为3 0 0 多万辆预计2 0 2 0 年将是现在的2 5 倍。广州市近1 0 年来机动车增长速度为 1 7 。2 0 0 8 年底全国汽车拥有量为6 4 0 0 多万辆，其中城市约占7 0 ，造成城市交通负荷的 快速增加。 目前解决城市交通问题的途径主要有：1 ) 综合治理，充分挖掘现有交通潜力；2 ) 合理 规划，加快道路交通改造和建设步伐。修建道路是解决交通问题的一个最直接途径。但由 于历史原因导致城市规划不合理，使得改造现有道路任重道远；城市内可供修建道路的空 间越来越少：即使修路，公路建设的步伐也总是赶不上车辆的增加速度。3 ) 开发利用各种 新型公共交通工具，形成完备的公交体系。4 ) 加强管理，建立科学的交通管理体制。大量 的交通拥堵给人民的生活、工作带来诸多不便，增加了巨大的社会成本，严重阻碍了城市 的持续健康发展，影响了城市的运转效率，在客观上阻碍了社会、经济的发展。如何针对 城市的交通现状采取措施，治理交通拥堵，保证城市交通的畅达，已成为城市交通建设乃 至城市经济、社会发展的当务之急。因此，在不可能大规模建设交通设施的情况下，提高 路网的管理水平，充分发挥现有交通设施的作用，引导交通流合理的在路网上分布运行， 提高其使用率，对于我国城市的长远发展具有积极深远的意义。智能交通系统( i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m s ，简称i t s ) 这一崭新概念伴随着科学技术的进步而出现，为解决交 通问题带来了新的思路。 南京邮电人学顾f | j 研究生学位论文第l 章绪论 1 2 本文的研究内容和本人的工作 基于动态信息的城市交通诱导策略( 简称为：路径诱导策略) 是智能交通系统( i t s ) 研 究的一个重要方向，路径诱导策略是一种框架体系，包括路径诱导算法与路径诱导模型， 其特点是把人、车、路综合起来考虑，通过引导用户的出行行为改善路网的交通状况，防 止交通阻塞发生，减少车辆在道路上的逗留时间，并且最终实现交通流在路网中各个路段 上的合理分配。 本论文主要对路径诱导策略中的路径诱导算法及其与交通控制策略的集成进行了深 入研究。 1 路径诱导算法 路径诱导策略的核心是路径诱导算法，在研究现有路径诱导策略的基础上，本文提出 了基于邻近交叉遗传算法( v i c i n i t yc r o s s o v e rg e n e t i ca l g o r i t h m s ，简称v c g a ) 的城市交 通诱导策略。v c g a 在简单遗传算法的基础上，对简单遗传算法的交叉操作和变异操作都 进行了改进，并采用了稳态繁殖方式，使所求最优路径更加贴近实时的交通状态，切实达 到诱导目的，提高了整体路网的运行效率。 1 ) 交叉操作的改进 交叉操作是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用， 是产生新个体的主要方法。交叉操作中交叉算子的设计至少要保证交叉后仍是一条路径， 同时考虑交叉后子个体应具有多样性，本文提出了交叉处发生在邻近节点之间的交叉办 法，即邻近交叉算子。两条路径交叉的条件是：从拓扑中去掉起点和讫点以及它们的关联 边后，这两条路径中仍存在邻近节点。否则交叉不发生。邻近交叉算子的特点使交叉新个 体具有多样性，减少了大量无用路径以及环路的产生，提高了算法收敛到全局最优解的概 率。 变异操作的改进 遗传算法中的变异操作是产生新个体的辅助方法，它决定了遗传算法的局部搜索能 力，同时保持种群的多样性。根据本文提出的交叉算子的特点，变异操作采用前向变异操 作，既保留路径后部、变异前部的办法，前向变异有效地抑制了算法的退化，保持了种群 的多样性。 3 ) 稳态繁殖 在遗传算法的运行过程中，由于选择、交叉、变异算子会破坏当前群体中适应度最好 的个体，为了使当前群体中所有适应度最好的个体尽可能地保留到下一代群体中，本文采 堕室! ! ! ! ! ! 旦叁兰竺! 里 塑兰兰堡笙兰笙! 童笪堡 用稳态繁殖法。 改进的交叉操作和变异操作的相互配合，共同完成对搜索空间的全局搜索和局部搜 索，减小了算法的搜索范围，同时交叉和变异运算不会破坏适应度最好的个体；在选择、 交叉、变异运算后采用稳态繁殖法可以加快算法的收敛速度，并能保证找到所有的最优解。 2 路径诱导策略与交通控制策略的集成 路径诱导策略和交通信号灯控制策略是城市智能交通管理最重要的两个方面，但目前 路径诱导策略中大多只考虑路段的行驶时间，忽略了交叉口的等待通行时间。而实际上， 城市道路系统中交叉口的延误占整个行程时间的很大部分，甚至超过路段行驶时间，因此 交叉口的延误是一个不可忽略的重要因素。在本文提出的路径诱导算法中，对适应度函数 的设计考虑了交叉口延误的影响，从而实现了路径诱导策略与交通控制策略的集成。 1 3 论文结构和主要内容 第1 章：绪论 本章介绍了课题的产生背景、研究方法、目的和意义。 第2 章：城市交通诱导策略相关技术 本章主要对城市交通诱导策略相关技术进行了详尽的介绍。 第3 章：邻近交叉遗传算法 本章主要对简单遗传算法进行介绍，包括遗传算法基本知识、优缺点等，并详细阐述 本文提出的基于邻近交叉遗传算法的路径诱导算法，论述此算法的优点。 第4 章：基于邻近交叉遗传算法的城市交通诱导策略设计与实现 本章基于邻近交叉遗传算法，实现了对城市交通诱导策略的设计。 第5 章：仿真结果及分析 仿真实验在河北省保定市裕华路区交通网中选取了部分交通网，使用m a t l a b 进行仿真 实验。将邻近交叉遗传算法与简单遗传算法进行比较，结果证明本文提出的算法收敛速度 更快，性能更稳定。 第6 章：结论与展望 对本文的研究内容进行了总结，并明确了下一步研究的方向。 南京邮电人学硕_ 研究生学位论文第2 章城市交通诱导策略相关技术 2 城市交通诱导策略相关技术 2 1 城市交通诱导策略 基于动态信息的城市交通诱导策略( 简称为：路径诱导策略) 是一种框架体系，包括路 径诱导算法与路径诱导模型，它确定如何对车辆实施诱导、有效均衡路网中的交通流，并 且在控制系统的集成等方面应有较强的可行性。从本质上讲，路径诱导策略同交通分配十 分相似，因此路径诱导策略的研究大部分基于交通分配理论。对于路径诱导策略来说，必 须考虑车辆在路口由于不同的控制策略而引起的延误时间，因此对路径诱导策略的研究必 须考虑交通控制系统的影响。a l l s h o p 第一次把控制引用到分配问题中，他建议考虑信号 配时对路径选择行为的影响，并提出逐步优化分配( i o a ) 算法口1 。f i s k 把寻求与最优信号 配时一致的均衡流量问题表述为一个s t a c k e l b e r g 博弈问题h 。y a n gh 和y a g a rs 将交通流 在信号交叉口的延误分为信号延误和排队延误，建立了交通分配和信号控制的两层规划模 型，并根据问题的特点提出基于敏感问题的分析的下降算法嵋1 。殷亚峰等考虑了交通网络 的动态特性建立一个动态网络信号配时的多层规划模型阻1 。 路径诱导策略的研究应该以动态交通分配为基础，充分考虑路径诱导的特点以及交通 管理和驾驶员等的决策心理，通常从以下几个方面进行考虑： 2 1 1 诱导策略的基本原则 路径诱导策略是交通管理者、驾驶员等交通参与者之间的一个博弈过程，在这个过程 中，交通管理者期望实现系统最优，每个驾驶员则根据所拥有的信息修正行为策略以提高 自己的盈利，从而构成交通诱导演化中的宏观结构与驾驶员微观行为之间相互影响的自组 织现象。路径诱导策略的制定必须基于驾驶员接受诱导路径的盈利大于不接受诱导路径的 盈利，并且这种盈利要超过一定的百分比，这样才能使路径诱导策略尽快达到好的演化稳 定状态，真正体现路径诱导策略的价值。 2 1 2 控制系统影响下的路径诱导策略 路径诱导策略的制定必须考虑到车辆在路口由于不同的控制策略而引起的延误时间 等，因此对路径诱导策略的研究必须考虑交通控制系统的影响。路径诱导策略是将时变的 交通出行合理分配到不同的路径上，以降低个人的出行的费用，通过在空间上对人们产生 南京邮电人学颂二l 研究生学位论文 第2 章城市交通诱导策略相关技术 的交通需求进行合理的配置，提高路网的运行效率；交通控制是通过调整路口的信号配时 方案来减少车辆在路口的延时时间和停车次数，减小城市交通网上的交通延误，提高道路 的通行能力。因此，研究路径诱导策略，应该充分了解路径诱导策略与交通控制的相互作 用和相互影响。 2 1 3 千道与普通道路相互作用下的路径诱导策略 在北京、上海等大城市，高速干道在城市交通中起着主导性的作用。有效的路径诱导 策略首先必须实现对高速干道的最大利用，充分发挥干道的作用。因而，要对高速干道的 交通进行有效的诱导，就必须深入研究干道和普通道路之间的相互作用，在此基础上实行 有效的诱导。 2 1 4 突发事件下的路径诱导策略 突发事件包括交通事故、车辆抛锚、警车、消防车等等。显然，突发事件发生后就会 阻塞一条或多条车道，造成路段通行能力下降而引起交通拥挤或堵塞，在这种情况下对交 通流进行诱导被认为是路径诱导策略最能发会作用的地方，当然突发事件发生的时间、地 点都带有随机性，是无法预知的，因此研究突发事件下的路径诱导策略更具有实用性和挑 战性。 我国交通诱导系统正处于建设与发展中，使用什么样的路径诱导策略，如何诱导等问 题是研究的重点。 2 2 路径诱导算法的关键问题及其处理 2 2 1 评价指标的确定 评价指标主要体现在路阻函数上，它应该包括：出行途中占用的时间、支付的能源或 票价等货币量以及产生的车辆磨损、环境污染等非货币量。路阻最低应该是指以上因素的 综合最小值或单项最小值。然而，从可计量性和数据可获得性方面看，在实际考虑出行费 用时，一般采用被占用的时间或能够反映被占用时间长短的其他指标，如票价、排队长度、 耗油量、拥挤程度等。因此，在路径选择中，设计了出行时间、行驶距离、拥挤程度、道 路质量和综合费用五种路阻，供不同出行者选择使用。为了便于研究，本文只对出行时间 路阻进行了研究。当路网上的交通流分布均匀、不存在局部拥挤而且道路设施等级相近时， 南京邮电人学硕i ：研究生学位论文第2 章城市交通诱导策略相关技术 这五种路阻并不矛盾。但当交通流分布明显不均匀、局部拥挤现象严重或网络中的道路等 级相差较大时，以这五种路阻定义的最佳路径是不一致的。将路段i 的各种路阻p 定义为： ( 1 ) 几何距离表示的路阻 c l ，= 厶，是静态路阻形式，其中厶是路段f 的长度。适用于网络道路质量相近、交通 流分布均匀的情况，这时指定o d 对之间的最佳路径是固定不变的。 ( 2 ) 道路质量表示的路阻 反映城市道路质量的指标主要有路面、车道数、车道宽、车道功能划分、坡度、倾向 净空等。道路质量最好的路径是指o d 之间所有路段的质量指标都具有较高的等级，而不 考虑路程和行驶时间的长短以及可能存在的拥挤。为了计量路段质量的高低，按理想程度 将质量指标划分为四个等级，用1 4 评分法为其赋值。其中1 分为最高等级，而4 分为最低 等级。路段的综合质量c ，可由各指标的线性加权得到： c 2 i = f n p - n e + f r s 必| + w l + 允g i + f f f j + 凡s i 其中只、r 墨、形、q 、鼻和s 分别是车道数、路面、车道宽、坡度、车道功能 划分和侧向净空六项指标的得分，南、厶、尼、石和石分别是其非负权值系数。这两 类指标的权值可通过实地调查和专家调查并进行特殊处理得到。g 。是一个静态指标，其 值在一定时期内是固定不变的。 ( 3 ) 平均行程时间表示的路阻 c 3 ，( 后) = ( 后) ，是常用的动态路阻形式。指在第k 个时段，车辆在该路段上运行所用的 平均时间，包括行驶时间和停车延误时间( 包括交叉口延误) 。 ( 4 ) 拥挤程度表示的路阻 在交通网络中，“拥挤 是指道路上的车辆不能以正常速度行驶的现象，表现为行驶时 间延长和停车延误增加。一般可用排队长度和路段的流量与通行能力之比来衡量。在安装有 自适应式交通信号系统的城市路网中，除与路段的几何线形有关外，路段的通行能力还与其 上流量以及其他路段流量的大小有关，是动态变化的而非定值，因而是很难测量的。此外， 如用队长作为反映拥挤的指标，则在对流量、运行时间进行检测和预测的同时，还需要对路 段出口处的排队长度进行监测和预测，增加了大量的检测和计算工作。为了尽可能减少检测 和预测工作量，定义如下的反映拥挤程度的路阻：q ，( 七) = t , ( k ) t o 。其中，( 七) 是七时段f 路 段的平均运行时间，而“是车辆以规定的最高速度通过该路段所需的时间，是固定值。这是 南京邮电人学硕- 3 _ - 研究生学位论文 第2 章城市交通诱导策略相关技术 一个动态数阻，c 4 。( 尼) 值越小，拥挤程度越低，c 4 ，( 尼) 值越大，拥挤越严重。拥挤程度最低 的路径是指连接o d 的所有路段都具有较小的c 4 ( 尼) 值，而不考虑总行驶时间和行驶路程的 长短。 ( 5 ) 综合路阻 出行者在选择路径时可能同时考虑出行时间、行驶距离、拥挤程度和道路质量因素： 或考虑其中的某几个因素，追求出行的综合效益。因此，设计的综合路阻为： c 5 ( 尼) = h ( c t ，c 2 ，c 3 j ( 后) ，c 4 。( 尼) ) 。即c 5 ，( 后) 是4 个单项路阻的某种组合，它也是一个动态 指标。出行者在进行路径选择时，可根据需要确定不同的路阻表达方式，从而得到相应的 最佳行驶路线。 2 2 2 全局优化问题 单纯的最优路径对单个用户导航是有效的，但在整个交通网中使用就会发生问题。例 如在第一个动态信息广播周期，大量用户精确搜索到一条最优路径，此路径就会被大量使 用，拥挤随即可能发生。英国的c h r i sw r i g h t 于2 0 0 1 年指出i t s 实施后会产生一个问题， 即在相同时间里，有许多人在同一时刻使用同一路线，结果将导致交通混乱。因此路径诱 导策略须采用全局优化算法，充分平衡网络中负载。 2 2 3 实时性 智能交通系统中的路径诱导算法实时性因素很重要，失去这一点，任何算法都无应用 价值。特别是在某些通信时延无法消除的情况下，路径诱导算法的快速、高效具有重要意 义。相对而言，精确性要求可以不太高。 2 2 4 驾驶员的行为 驾驶员的行为人是最主要的不确定因素。驾驶员在道路网上行驶时，有可能根据当时 的交通情况和当时的心理状态产生新的想法。这种不确定行为已无法用纯效学方法( 数学模 型) 描述和预测。另外驾驶员能否接受路径诱导策略的指示也有不确定性。 南京邮电大学硕- j ：研究生学位论文 第2 章城市交通诱导策略相关技术 2 2 5 交通控制策略 路径诱导策略必须充分考虑城市路网中的交通控制策略，为了避免拥堵，优化交通流 在路网上的分配，交管部门越来越多地在路网上采取了一些禁行措施，例如将某路段设置 为单行线，某时段禁止某车型的车辆通行，某路口禁止车辆左转、右转等。 2 3 路径诱导算法 目前，求解最优路径的算法随叫有很多，如d i j k s t r a 算法、a 算法、神经网络算法和 遗传算法等，其中从图论理论发展起来的d i j k s t r a 算法是解决该问题最有效的，在基于交 通网络的路径分析算法中，大都以该算法作为基础，并根据网络特性进行改进n 们。但由于 基于动态信息的城市交通诱导策略对动态性、实时性要求较高，使得路径分析算法并不适 合应用。据此，很多学者尝试在路径诱导策略中引入智能算法，如神经网络算法n 1 1 、模拟 退火算法n 副、遗传算法n 3 1 等，其中将遗传算法应用于动态路径诱导较为成功。 2 3 1 d i j k s t r a 算法 交通网络分析是指通过一定方法，评价路网特征的区位特征及特征之间的相互关系， 分析个体在交通网络中一定时间内可能的活动范围。交通网络分析的重点是路径分析，而 路径分析的核心为最优路径。以最短路径为主的最优路径是交通网络分析的一个热点，它 往往是建立在抽象的数学模型即网络模型的基础上，该模型中最短路径分析就是在指定网 络两节点间找一个阻碍强度最小的路径，它不仅包括距离最短还可以引伸到其他变量如时 间、费用、线路容量等。从图论理论发展起来的d i j k s t r a 算法是解决该问题最有效的，在 基于交通网络的路径分析算法中，大都以该算法作为基础。 d i j k s t r a 算法首先设置一个辅助向量d ，它的每个分量盔表示当前所有找到的从起始点 1 ，到每个终点v 的最短路径的长度。设置d 的初始状态为：若从v 到v 有弧，则吃为弧上的 权值：否则令z 为0 0 。 d ，= m i n d , i v ) 显然，长度为d 的路径就是从v 出发的长度最短的一条路径。设s 为己求得最短路径 的终点的集合，则可以证明：下一条最短路径( 终点为x ) 或者是弧( ，x ) ，或者是中间只 经过s 中的顶点而最后到达顶点x 的路径，因此，下一条长度次短的最短路径的长度必为 南京邮电人学顾t - - j i ) f 究生学位论文第2 章城市交通诱导策略相关技术 嘭2m f n zlv j s ) 其中z 或者是弧( v ，_ ) 上的权值，或者是矾( s ) 和弧( k ，v f ) 上的权值之和。根据以 上原理可得到如下描述的最短路径生成算法： ( 1 ) 利用邻接矩阵c 来表示带权有向图g ，其元素气表示弧( v i ，0 ) 上的权值：若弧 ( _ ，) 不存在，则将勺设为。令s 为已找到从出发的最短路线的终点的集合，将其初 始化为空集。z 用表示从屹出发到终点v 的可能到达的最短距离，取其初始值为： 4 = 巴，矿 ( 2 ) 选择0 ，使得 乃= i 血 4 iu 矿一s ) 则_ 就是当前从屹出发的最短路径的终点。令 s = s u 吩) ( 3 ) 修改从k 出发到集合矿一s 中任一顶点的可达最短距离，如果 d j + c i k ih i 等 - 他篱- d ( 聊。 证明由于s g a 按适配值采用比例选择策略，则hnp ( f ) 中元素得以选择的期望值为 磊，孚舭i 等 由于交叉操作时随机选取1 到z 一1 中的某一位置并交换两父代的对应子串，则属于模式日 南京邮电人学硕i ：研究生学位论文 第3 荜邻近交叉遗传算法 的个体经交叉后仍属于日的概率不小于卜见零等。而每个个体经变异操作后未被破坏 的概率为( 1 一p 。) 。川。此外，尸( ，) 不属于1 t 的个体也有可能经交叉、变异后属于h 。因 此，p ( t + 1 ) 中属于日的个体数目的期望值不小于 酬等卜。篱卜 通常s g a 中p 。取值很小，则 h 。等卜 t 他罟卜c 1 _ 见罟_ d ( 聊肼 从而，模式定理得证。 推论在s g a 中，阶次低、定义长度短且适配值超过平均适配值的模式在种群中的数 目的期望值以指数级递增。 尽管模式定理在一定意义上解释了s g a 的有效性，但还存在以下缺点： ( 1 )模式定理仅适用于基于二进制编码的s g a ，对其他编码方式此定理未必成 l 卫： ( 2 )模式定理仅提供一个期望值的下界，仍不能说明算法的收敛性。 ( 3 )模式定理对算法参数的选取不能够提供实用的指导，对算法操作也有依赖 性。 隐含并行性定理n 9 1 设s 为一小正数，。 0 ，若 0 ，f ，= 1 , 2 ，刀。 ( 3 ) 正则的，若a 0 ，且存在自然数k ，使a 0 。 ( 4 ) 随机的，若彳0 ，= 1 ，i = 1 ，2 ，疗。 ( 5 ) 规约的，若彳。且经过相同的行和列初等变换后可转化为r 吴爿的形式，其中c 和 丁均为方阵。 ( 6 ) 不可约的，若a 0 且不可约。 ( 7 ) 稳定的，若a 是随机的且所有行相同。 ( 8 ) 列容的，若彳是随机的且每一列中至少有一个正数。 引理3 2 2 1若c ，m 和s 为随机阵，且m 0 ，s 为列容的，则c m s 0 。 证明记a = c m ，b = a s 。由于c 为随机阵，则c 的每一行中至少存在一个正数。 从而，v i ，0 , 2 ，刀) ，= m 蚵 0 ，即a 0 。进而，由于s 为列容的，则 k = l v f ， 1 ，2 ，以) ，b o = 0 。i 故c m s o 得证。 k = l 引理3 2 2 2 若尸为正则随机阵，则p 收敛到一个全正稳定随机阵，即 p ”= 1 ，l ，1 7 p l ，p 2 ，p 。】，其中【p l ，p 2 ，p 。】尸= p l ，p 2 ，p 。】 ， p f = 1 ， ，= l p ，= 。l i 。r a 。p ：，k o ，即 p ，p 2 ，p 。】7 是p7 的特征值为1 且各分量均为正数的特征向量。 引理3 2 2 3 若 p = 酬 是随机的，其中c 为m 维严格正随机方阵，r 0 ，t 0 ，则 南京邮电人学硕j j 研究生学位论文 第3 章邻近交叉遗传算法 儿雕 是一个稳定的随机阵，其中 同时， k - l r 。：l i m y t r c 扣j t _ 。u i = 0 p 。_ 1 1 ，1 九m 跏删善p g 。1 p 2 l i m p ：，k o 其中p 0 ( 1 m ) ，p = o ( m + 1 刀) 。 3 2 2 2 标准遗传算法的马氏链描述n 9 1 在s g a 中，令所有个体形成的有限空间为q ，所有种群对应的整个状态空间为g ， 其中每一种群为一个状态，一旦染色体长度，和种群数目给定且有限时，则q 的维数lql 有限，g 的维数igl - iqi n 也有限。由于算法中每一代状态的转移依赖于选择、交叉和变 异操作，且与进化代数无关，因此s g a 可视为一个有限状态的齐次马氏链。 鉴于算法中三个遗传操作时循环往复执行的，我们按“交叉专变异选择”顺序 来考虑算法中的状态转移。从而，表征马氏链的状态转移矩阵尸为矩阵c ，m 和s 的乘 积，其中，c ，m 和s 分别为交叉、变异和选择操作所决定的状态转移矩阵。 1 交叉操作 交叉操作可视为状态空间上的随机函数，记交叉操作决定的状态转移矩阵为 c = ( c 口) | g l x | g i ，其中勺为状态f 经交叉操作转移到状态的概率。由于一个状态通过交叉操 1 0 7 作总要转移到状态空间的另一个状态，因此勺= 1 显然成立，即c 为随机矩阵。 = i 2 变异操作 在s g a 中，变异操作是独立作用于种群内各个体的每一位基因上，记变异操作决定 的状态转移矩阵为m = f ，) 删g i ，其中m f 为从状态f 经变异操作转移到状态的概率。由 于染色体的每个基因具有相同的变异概率 o ，贝1 jm l ，= p ：9 ( 1 一p 。) 肛嘞 o ，其中日l ， 为状态f 与状态歹之间具有不同基因的位置的总数。例如，状态 ( 1 0 0 0 ) ，( 0 1 1 1 ) ，( i o i o ) n 状 态 ( 1 1 0 0 ) ，( 1 1 1 0 ) ，( 0 1 0 1 ) ) 之间的h 盯为7 。因此，m 为严格正的随机矩阵。 南京邮电大学硕：卜研究生学位论文第3 章邻近交叉遗传算法 3 选择操作 在s g a 中，交叉和变异操作后得到的种群经选择操作后又将转移到另一个种群，记 选择操作决定的状态转移矩阵为s = ( ) | g | x i g l 。考虑比例选择策略，种群中染色体x ，被选 中的概率为 | f ( x f ( x 。) 0 七= l 则种群i 经选择操作后保持不变的概率 nn 兀( 厂( ) 厂( 以) ) o j = l k = l 因此，转移矩阵s 是随机且列容的。 通过对上述三个操作的概率描述，我们对s g a 的马氏链描述做了一个简单的介绍，下 面我们将对算法的收敛性进行阐述。 3 2 2 3 标准遗传算法的收敛性 定理3 2 2 1 若s g a 中交叉概率p 。 o ，1 】，变异概率p 。( o ，1 ) ，并且算法采用比 例选择策略，则s g a 的状态转移矩阵p = c m s 是严格正的n 9 1 。 定理3 2 2 2s g a 不能够以概率1 收敛到全局最优解。 证明 令p ( t ) = x 。( f ) ，x ( f ) 为算法第f 代的种群，其最优适配值为 z t = m a x f ( x k ( f ) ，k = 1 , 2 ，n ) ，设f 为全局最优的适配值。由定理3 2 2 1 和引理3 2 2 2 知， s g a 以任意状态f 为极限分布的概率l i m p ：= p j 。 0 ， 因此， f - ；i m p z 。= 厂 1 一p 7 1 。 上述定理从概率意义上说明了s g a 不能够收敛到全局最优，其原因在于算法中最优 解的遗失。因此，只要在算法中每代保留当前最优解，无论是在选择之前还是在选择之后， 算法将最终收敛到全局最优。 定理3 2 2 3 每代在选择操作后保留最优解的s g a 以概率1 收敛到全局最优解。 证明由于算法采用了保优技术，为方便起见，我们将保留下来的各代的最优个体存 放在种群的第一号位置，但它不参与遗传操作。即，在第，代进化时的种群为 ( x o - 1 ) ，x ( ，) ，x ( ，) ) ，其中x ( f 1 ) 表示算法搜索至第，一l 代所得到的最佳个体。从 而，算法对应马氏链的状态空间维数变为lqi + 1 。然后，我们将包含相同的最优解的状态 南京邮电人学硕上研究生学位论文第3 荦邻近交叉遗传算法 仍按在原状态空间的顺序进行排列，而对包含不同最优解的状态按最优解的适配值从大到 小进行排列。由此，新的交叉、变异和选择操作对应的状态转移矩阵可表示为 c + = d g a g ( c ，c ，c ) ，m + = a j a g ( m ，m ，m ) 和s + = ( s ，s ，s ) 。 在选择操作后，算法要将当前种群中的最优解与前一代保留下来最优解进行比较，这 一操作也可用矩阵u = ) 表示。显然，状态r ( t ) = ( x ( f 一1 ) ，x 。( f ) ，x ( f ) ) 转移到 j 厂( f + 1 ) = ( x + ( f ) ，x lo + 1 ) ，x ( f + 1 ) ) 的概率为： 1 1 ， f m a x ( f ( x 。o ) ) ，f ( x ( f ) ) ) = x o ) p r ( r ( t + 1 ) il ，( f ) ) = a n d ( x i ( f ) 9o 0 9 x ， ) ) = ( x l o + 1 ) ，x o + 1 ) ) l0 ， e l s e u = u l l u 2 lu 2 2 u i o l lu 剑2 u j q i 列 其中为lqi iqi 阶矩阵，ru 。为单位矩阵。从而，马氏链的一步转移矩阵为 p + = c + m + s + u = d i a g ( c m s ，c m s 9 - 9c m s ) c m s u l l c m s u 2 ic m s u 2 2 c m s u l o i lc m s u 吲2 c m s u 删q 显然，p + 为可约的随机矩阵，r c m s u 。严格正。进而，考虑到p + 中第一位状态由 好到坏的排列顺序可知， = c 鼍u2l。，=cms；u22r 0t ：删剑 0 c m s u i q c m s u b t 珊c m s u i = i ； i ，= l；。 1 illl 【 j【- z q 刮 塑塞些! ! 叁兰竺：! 型! ! ! 竺兰竺笙兰丝! 翌型丝銮墨望! 主堑鲨 最优个体的状态，也即算法能够以概率1 搜索到全局最优解。 除了讨论算法的收敛性，对带有保优操作的遗传算法的收敛速度进行估计也是很重要 的研究内容。 设带有保优操作的遗传算法对应于有限状态为马氏链 z 。) ，行向量万为给定每一状 态的概率，p 为一步转移矩阵，则经n 次转移后，各状态的概率为n p ”。若种群中全部个 体相同且均为最优，则称此状态为吸收态。显然，马氏链 z 。) 中有如下三种性质的状态： ( 1 ) 吸收态；( 2 ) 可一步转移到吸收态的非吸收态；( 3 ) 经p 可一步转移到另一状态， 而此状态转移到吸收态的概率为零。从而，一步转移矩阵p 可分解为 尸= 瑚 其中，。为描述吸收态的k 阶单位矩阵，r 为描述能转移到吸收态的状态的( igi _ 七) k 阶 矩阵，q 为描述其他状态