（系统工程专业论文）交通控制若干相关问题的研究.pdf

中文摘要随着经济发展和社会进步，交通运输已经成为人们经济生活中不可缺少的重要组成部分，它对保证社会经济体系及日常生活的正常运转发挥着越来越大的作用。近2 0 年来，世界各国先后建立了四通八达的交通运输网络，但交通工具的增长速度远远高于道路和其它交通设施的增长，因此随之引起交通拥堵、环境污染、交通事故等一系列交通问题，也造成了巨大的物质与经济损失。这些情况表明，单纯依靠修建道路与交通设施和采用传统的管理方式来解决交通问题，不仅成本昂贵、环境污染严重，而且其缓解交通拥堵、提高交通运输效果也是十分有限的。因此近年来人们越来越重视对交通控制的研究。尽管交通控制问题已经提出一个多世纪，控制理论也发展了6 0 多年，但由于交通流本身的不确定性和复杂性，给交通控制的研究带来了很大的麻烦，因此真正从控制理论角度出发研究交通流的动态特性等问题，一直是交通控制领域研究的一个难点。本文首先全面的介绍了聚类算法，分析了聚类算法在交通流模糊控制中的应用，然后提出了一个改进的模糊聚类算法，并将其应用到交通模糊控制的模糊化中，可令模糊控制的输入更客观、更科学。接下来介绍了现在交通仿真系统的发展和面向对象仿真技术。然后基于交通控制和软件工程的思想设计开发了单个路口不确定交通流控制仿真软件，该软件对于不确定交通流下的交通实时控制具有良好的仿真效果。最后，本文在交通流不确定条件下进行仿真试验，获得大量数据，对交通控制动态特性的研究进行了初步探索，实现了从控制理论角度出发，对单个路口的交通流控制的动态特性试验研究，总结出若干控制变奄与交通流的控制指标问的对应关系，获得了有实际意义的结论。关键词：交通控制，交通仿真，不确定件，模糊聚类，动态特性a b s t r a c ta se c o n o m ya n ds o c i e t yd e v e l o p e d ，t r a f f i ch a sb e c o m et h ei n d i s p e n s a b i l i t yp a r to fl i f e ，i th a sm o r ea n dm o r ee f f e c to ng u a r a n t e e i n gt h ee c o n o m i cs y s t e ma n dh u m a nl i f e i nr e c e n tt w e n t yy e a r s ，t r a f f i cn e t w o r kh a sb e e ne s t a b l i s h e df a u l t l e s s l yb ym a n yc o u n t r i e s b u t , b u i l d i n gn e wr o a d sa n do t h e rt r a 伍cf a c i l i t i e sc a nn o tm e e tt h ef a s ti n c r e a s eo ft h ea m o u n to fv e h i c l e ，s om o r et r a f f i cp r o b l e m ss u c ha st r a 衢cj a m ，e n v i r o n m e n tp o l l u t i o n ，a n dt r a f f i ca c c i d e n te m e r g e ，w h i c hc o s th u g ee x p e n s e a sa b o v e ，i m p r o v i n gt r a f f i cb yb u i l d i n gr o a da n df a c i l i t yo rm a n a g i n gt r a f f i ci nc o n v e n t i o n a lw a yc o s t sd e a r l ya n dp o l l u t e se n v i r o n m e n ts e r i o u s l y , i ta l s oh a sl i t t l ee f f e c t0 nr e l a x i n gt r a f f i cj a ma n da d v a n c i n gt r a f f i c 。s om o r ea n dm o r es t u d yo i lt r a f f i cc o n t r o lh a sc o m e m o r et h a no n eh u n d r e dy e a r sh a v ep a s s e ds i n c et h ep r o b l e mo ft r a f f i cc o n t r o lw a sp r e s e n t e d ，a n dt h ec o n t r o lt h e o r yh a sd e v e l o p e df o rm o r et h a ns i x t yy e a r s ，b u tt h er e s e a r c ho nd y n a m i cc h a r a c t e r i s t i c so ft r a f f i cf l o wu s i n gc o n t r o lt h e o r yi ss t i l lad i f f i c u l tj o bd u et oc o m p l i c a t i o na n dt h ei n h e r e n tu n c e r t a i n t yo ft r a f f i cf l o ww h i c hb r i n gl o t so fp r o b l e m so nt r a f f i cc o n t r o ls t u d y a tf i r s t ，c l u s t e r i n ga r i t h m e t i ci sp r e s e n t e d ，c l u s t e r i n ga r i t h m e t i ca p p l i c a t i o no ff u z z yc o n t r o lo ft r a f f i cf l o wi sa n a l y z e d t h e na ni m p r o v e dc l u s t e r i n ga r i t h m e t i ci sp r e s e n t e d ，t h ei m p r o v e da l g o r i t h mw h i c hc a l lm a k et h ei n p u to ff u z z yc o n t r o lm o r ee x t e r n a la n dm o r es c i e n t i f i ci sa p p l i e dt ot h ef u z z i f i c a t i o no f t r a f f i c 呦c o n t r 0 1 t h e f tt h ed e v e l o p m e n to ft r a f f i cs i m u l a t i o ns y s t e ma n do b j e c t o r i e n t e ds i m u l a t i o nt e c h n o l o g ya r ep r e s e n t e d a f t e rt h a t ，as i m u l a t i o ns o f t w a r eo fu n c e r t a i nt r a f f i cf l o wc o n t r o lo fi n t e r s e c t i o ni sp r o g r a m m e dw h i c hi sb a s e do nt r a f f i cc o n t r o la n ds o f t w a r ee n g i n e e r i n g t h i ss o f t w a r eh a sb e t t e re f f e c to nr e a l t i m et r a f f i cc o n t r o lu n d e ru n c e r t a i nt r a f i l ef l o w a tl a s t ，t h es i m u l a t i o ne x p e r i m e n t sa r ed o n eu n d e ru n c e r t a i nt r a f f i cf l o w , al a r g eq u a n t i t yo fd a t ai sa c q u i r e df r o ms i m u l a t i o ne x p e r i m e n t s t h er e s e a r c ho nd y n a m i cc h a r a c t e r i s t i c so ft r a f f i cc o n t r o li sd o n ea sap r e l i m i n a r ys t u d y a f t e rs t u d yo nt h ed y n a m i cc h a r a c t e r i s t i co ft r a f f i cf l o wj nt h ei n t e r s e c t i o nu s i n gc o n t r o lt h e o r y ,r e l a t i o n s h i p sb e t w e e nc o n t r o lp a r a m e t e r sa n ds t a t e so ft r a f f i cf l o wa r ec l a r i f i e da n ds o m eu s e f u lc o n c l u s i o n sa r eo b t a i n e d k e yw o r d s ：t r a f f i cc o n t r o l ，t r a f f i cs i m u l a t i o n ，u n c e r t a i n t y ，f u z z yc l u s t e r i n g ，d y n a m i cc h a r a c t e r i s t i c独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得苤鲞基堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名：身槌签字日期：门年阿万一学位论文版权使用授权书本学位论文作者完全了解鑫鲞盘堂有关保留、使用学位论文的规定。特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：身持互导师签名：签字日期：弘寸年月日颂1 纪九签字日期：叩年月矽日第一章序论第一章序论1 1 城市交通实时控制介绍随着现代科学技术和工业的迅速发展，新兴城市不断涌现以及城市规模不断扩大，城市间社会活动和贸易交往更加频繁，交通需求也随之迅速增长。然而交通拥阻确严重制约了城市交通运作的效率，给经济、社会等方面带来了诸多不利影响，给整个社会带来的经济损失难以估量，它已成为一个严重制约社会经济发展的“瓶颈”。研究交通问题，解决交通拥阻已成为一个世界范围内的、极具挑战性的课题。目前解决交通拥阻的办法主要有两种：一是在交通规划方面增加交通供给和削减交通需求；二是在现有道路的基础上，对交通流进行科学的组织和管理控制，充分发挥现有交通网络的通行潜力，这正是交通领域控制问题研究的目的。现有的很多交通控制系统缺乏实时性的特点，这些系统中有很多不合理、不科学的假设，例如假设交通流服从某一概率分布不变等，这种思想设计的交通系统不可能真正发挥作用。城市交通应该是随机的、不确定的产生交通流，控制机应该实时的根据交通状态的变化调整控制参数，本文正是基于这种实时的思想进行交通控制的若干相关问题研究。1 2 本文关注的三个问题交通控制领域已经有很多人正在研究， 日还有很多问题没有解决，本人主要对其中的三个问题进行了研究，即交通模糊控制的模糊化怎样更合理，避免传统的人为主观因素过多、交通仿真怎样更符合实际，更能反应交通流的不确定性，更能实时的响成交通控制信号、不确定条件下交通控制如何研究，交通控制参数与控制效果函数有怎样的对应关系。这三个问题是作者在实际研究中遇到并关注的问题。1 3 本文关注问题的研究现状聚类分析这门科学币在蓬勃发展，目前已提出了许多不同的聚类方法来解决聚类问题，在交通模糊控制中，现有的模糊化方法主要是根据人们的经验确定模糊化的边界值，使得交通流状态的模糊化带有很大的主观性，进而影响交通模糊控制的效果。而传统的模糊聚类算法又存在预先确定聚类数等缺陷。为了对交通流状态进行客观的模糊化，本文设计了改进的模糊聚类算法对交通流状态模糊化，使得模糊化的结果更科学、吏准确。道路交通系统仿真是应用系统仿真技术研究交通行为，对交通运动随时间和空间的变化进行跟踪描述的技术。它在道路运输系统及其各组成部分的分析和评价中发挥着霞要的作用。近年来，随着计算机虚拟现实技术向实用化方面的发展，研制驾驶模拟器，对交通系统进行仿真研究成为嗣际上交通运输研究领域一个重要的发展方向，并取得了显箸的成果。美国、德国、日本、第一章序论英国等发达国家先后研制了各种大型的开发型驾驶模拟器，并成功地应用于道路安全评价、智能运输系统设计、路网评价、驾驶员行为特征研究、汽车安全性研究等领域。对道路交通实施仿真受到广泛重视并得到应用，如对道路通行能力的模拟，对平面交叉路口的模拟，在交通控制系统中为寻找最佳配时方案对控制效果的模拟等。然而传统交通仿真系统在不确定性方面存在缺陷，没有很好反应交通流随机的特点，这正是本文研究的问题之一。人们对交通的管理主要通过对交通流、信号灯等的控制来实现。城市交通控制也是交通领域最复杂最难解决的问题。交通控制主要通过对信号灯的控制起到疏导交通流的目的。交通信号灯控制通过对相位的周期、绿信比等控制参数的调整使控制效果最优。因此，在不确定性交通流中如何更好的配置各控制参数，对控制特性进行研究有着重要的意义。尽管交通控制问题已经提出一个多世纪了，控制理论也已经发展了6 0 多年，但是由于交通本身的复杂性和不确定性，因此真正从控制理论角度出发研究交通控制的动态特性等问题一直是交通控制领域的一个难点。本文以交通流泊松分布为例，应用自行开发的交通仿真软件，研究绿信比、周期的变化对控制效果的影响。对交通控制特性进行分析，为以后进一步深入研究打下基础。1 4 论文结构针对以上问题，本文第二章首先对聚类分析进行了全面的介绍，设计了便于模糊化交通流的改进聚类算法，讨论了m 参数对于算法的影响；接下来本文第三章对交通仿真系统进行了介绍，阐述了面向对象编程的思想，应用第二章的改进聚类算法处理交通流数据，获得不同种类的交通流出车情况，并以此作为依据设计了不确定交通流仿真系统。最后第四章介绍了不确定条件下的交通控制动态特性研究，应用第二章的结论聚类车辆产生情况，在第三章的仿真系统的辅助下分析了单点路口控制参数的变化对控制效果的影响。2第二章基于m f c m 的改进聚类算法及其在交通中的应用第二章基于虾c m 的改进聚类算法及其在交通中的应用2 1 研究背景及问题的提出当今在交通流控制领域出现了许多的控制算法，模糊控制算法就是其中很有效的一种。如何将路口交通流状态模糊聚类是交通模糊控制需要首先解决的基本问题。现有的交通模糊控制算法都是根据经验人为地确定模糊聚类的边界值，使得交通流状态的模糊化带有很大的主观性，进而影响交通模糊控制的效果。为了对交通流状态进行科学的模糊聚类，本章提出了一种基于m f c m 算法的分级递减聚类( h i e r a r c h i c a ls u b t r a c t i v ec l u s t e r i n g ，h s c ) 算法，利用m f c m 算法寻找类中心，再自适应确定该类中心的隶属度阈值，将聚类进行分级处理，实现未知类数数据集的聚类。交通流状态近似服从高斯分布，该改进算法对于未知聚类数、服从高斯分布的数据集具有聚类效果好，收敛速度快的特点。本章最后用服从二维高斯分布的交通流数据对算法进行了验证。2 2 聚类分析的基本理论聚类分析这门科学正在蓬勃发展，聚类就是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有任何关于分类的先验知识，仅靠事物问的相似性作为类属划分的准则。聚类分析是把一个没有类别标记的样本集按某种准则划分成若：l 二个子集，使相似的样本尽可能归为一类，而不相似的样本尽量划分到小同的类中。确定数据集中样本相似性的常用方法是欧式距离，目前已提出了许多不同的聚类方法来解决聚类问题，聚类分析从技术上大体分为硬聚类方法、模糊聚类方法和可能性聚类方法。传统的聚类分析是一种硬划分，它将样本对各个类的隶属度取成0 和1 两种值，取值为0 表示不属于这一类，取值为1 表示该样本属于这一类，把每个待辨识的对象严格的划分到某类中，具有非此即彼的性质，因此这种类别划分的界限是分明的。传统的硬聚类方法包括c 一均值，i s o d a t a ，f o r g y ，w i s h 等方法，硬聚类算法具有花费时问少的优点，但其缺点也是明显的，因为实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，具有亦此亦彼的性质，这样硬聚类割断了样奉与样本之间的联系，使得所得的聚类结果偏差较大，并且容易陷入局部最优解。模糊集理论的提出为软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析，模糊聚类方法将样本对各个类的隶属度扩展到区问 0 ，1 ，该类方法是基于z a d e h 在1 9 6 5 年提出的模糊集理论，模糊聚类顾及到了样本与样本之问的联系，认为每个样本与各个聚类中心都有一个第二章基于m f c m 的改进聚类算法及其在交通中的应用隶属关系，模糊聚类能够有效的对类与类之间有交叉的数据集进行聚类，所得的聚类结果明显优于硬聚类，模糊聚类大体上分为下面几种：基于模糊相似关系的聚类方法、基于数据集的凸分解、基于目标函数的聚类方法、基于模糊关系的传递闭包、聚类神经网络和基于先进的优化算法的聚类方法。模糊聚类要求各类每个样本对各类的隶属度之和为l ，这一要求是对划分情况的概率约束。模糊聚类表达了样本类属的中介性，建立起了样本对于类别的不确定性描述，更能客观地反应现实世界，从而成为聚类分类研究的主流。随着计算机的发展和实际问题的需要，基于目标函数的聚类方法已成为聚类分析的主流，这一方面是因为将聚类问题描述成优化问题易于与经典数学的非线性规划领域联系起来，可用现代数学方法来求解。另一方面是由于算法的求解过程比较容易用计算机来实现，本课题涉及到的m f c m 算法就是该算法的一个分支。2 3 聚类分析的数学模型设x = x 1 ，x 2 ，x n ) 是待聚类分析的对象的全体( 称为论域) ，x 中的每个对象( 称为样本) x k ( k = 1 ，2 ，n ) 常用有限个参数值来刻画，每个参数值刻画x k 的某个特征伽，于是对象x k 就伴随着一个向量p ( x k ) = ( x k l ，x k 2 ，”，x k s ) ，其中x k j ( j 2 1 ，2 ，s ) 是x k 在第j 个特征上的赋值，p ( x k ) 称为x k 的特征向量或模式矢量，聚类分析就是分析论域x 中的n 个样本所对应的模式矢量间的相似性，按照各样本间的距离远近关系把x l ，x 2 ，x n 划分成多个不相交的子集x 1 x 2 ，x c ，并要求满足下列条件：x ，ux ，u ux ，= x ，彳，nx i = o ，1 i ，c( 2 3 1 )jl，j，在硬划分中，样本x k ( 1 k i * 1 ) 对子集( 类) x i ( 1 i c ) 的隶属关系可用隶属函数表示为u 白= 髟乏主他3 2 ，其中，要求每个样本能且只能隶属于某一类，同时要求每个子集( 类) 都是非空的。在模糊划分中，样本集x 被划分成c 个模糊子集x l ，x 2 ，x c ，而且样本的隶属函数从0 ，1 二值扩展剑 0 ，1 区间，满足条件e ，= f r 掰琅i 甜詹，侈，? 歹j 掰埔= l , v k ；o “， 玎，v i )( 2 3 3 )4第二章基于m f c m 的改进聚类算法及其在交通中的应用2 4 聚类趋势检验聚类趋势检验的主要目的是确定待聚类样本是否可聚，若可聚，才可以接下来进行聚类操作和聚类分析。聚类趋势检验已有大量相关的资料和算法，早期的工作主要局限在二维空间中，依靠许多形式的嵌块抽样( q u a d r a ts a m p li n g ) 方法，在生态学中有较多应用，还有基于近邻信息、局部邻域的模式计数或最小生成树( m s t ，m i n i m u ms p a n n i n gt r e e ) 的方法，该方法由于计算上的考虑只限于二维或三维空间。现在应用最为广泛的方法为距离信息法，因为点与点之间的距离蕴含了研究模式空间分布状态的丰富信息。不过，当数据个数n 比较大时，逐对求出点与点之间的距离将会造成严重的计算负担，因此人们提出了多种获取距离信息的方法，利用m o n t ec a r l o 和统计假设检验的方法研究聚类趋势问题，并取得了良好的效果，这部分理论已经非常完善，这里不再赘述。2 5 传统的模糊聚类算法介绍2 5 1 传统的模糊聚类算法现在常用的模糊聚类算法大致分为四种：谱系模糊聚类算法( h c m ) 、基于模糊等价关系的聚类算法、图论聚类算法( 模糊最大支撑树算法) 、基于目标函数的模糊聚类算法。当待分类的样本数量较少时经常使用前三种算法，但实际上待分类样本数量往往很大，这时最好的方法是基于目标函数的模糊聚类算法，该方法把聚类分析归结成一个带约束的非线性规划问题，通过优化求解获得数据集的最优模糊划分和聚类。该方法解决问题的范围广，可以转化为优化问题而借助经典数学的非线性规划理论求解，易于计算机实现，所以随着计算机的应用和发展，基于目标函数的模糊聚类算法成为了研究热点。在基于目标函数的聚类算法中模糊c 均值( f c m ，f u z z yc m e a n s ) 类型算法的理论最为完善，应用最为广泛。模糊c 均值类型的算法最早是从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，从此类内平方误差和( w g s s ，w i t h i n g r o u p ss u mo fs q u a r e de r r o r ) j 】成为聚类目标函数的普遍形式。为极小化该目标函数而采取的p i k a r d 跌代优化方案就是著名的硬c 均值( h c m ) 算法和i s o d a t a ( i t e r a t i r es e l f - o r g a n i z i n gd a t aa n a l y s i st e c h n i q u ea ) 算法。模糊划分概念提出后，d u n n 首先把w g s s 函数j l扩展到j 2 类内加权平均误差和函数，后来b e z d e k 又弓f 入了一个参数m ，把j 2推广到一个目标函数的无限族，并给出了交替优化( a o ，a 1 t e r n a t iv eo p t i m i z a t i o n ) 算法，即为人们所熟知的f c m 算法。从此，奠定了f c m 算法在模糊聚类中的地位。第二章基于m f c m 的改进聚类算法及其在交通中的应用2 5 2 传统的模糊聚类算法的缺点前三种算法不能适用于大数据量的情况“1 ，因此在实际应用中受到限制。基于目标函数的模糊聚类算法( f c m ) 不管数据集在特征空间中是否存在自然结构，给定一个分类数c ，就输出数据集的c 划分。因此，该算法存在一个不合理的假设：带分析的数据集是可聚的。这一不合理假设的存在使得现有f c m 类犁的算法不分析数据集的可聚性，而硬性对数据施加一定的隶属关系。这样造成了即使数据在特征空间中是均匀分布的，不存在任何聚类结构，f c m 类型的算法也会毫无道理的对数据集进行模糊c 划分，从而使得对聚类分析结果的解释产生团难。f c m 类型的算法要求类别数( 聚为多少类) c 事先给定，需要有关数据集的先验知识，这就影响了聚类算法的客观科学性，而且存在聚类结果的正确性和聚类数目的合理性问题。对于大多数开发性数据而言，关于数据的空间分布及结构的先验知识是很少的，或者一点也没有，有时人们反而希望聚类的结果能够揭示这些信息，这些弱点限制了f c m 类型算法的实际应用。2 5 3 肝c m 算法介绍改进的模糊c 一均值聚类( m f c m ) 算法是近年提出的有效聚类方法。m f c m 与f c m相比，由于没有对隶属度进行归一化，克服了数据野值对聚类的收敛性的影响，使最终聚类结果对预先确定的聚类数目不十分敏感，获得的各个聚类中心都能接近实际的类中心。但它和f c m 算法一样，需要给定类别数的初始值。m f c m 算法如下：彳= 一，工：，x 。) cr p 为有限数据集合，将该数据集中的数据分为c 类( 1 c n ) ，则x 的一个非退化模糊c 一划分矩阵u = 伽。) r ”m f c m 算法中，u 满足对于上面的聚类，定义数据点到类别中心的加权距离平方和为目标函数：( 2 5 1 )心n，- - 1 t - - 五i ”m( 2 5 2 )式中：吒= i | x ，一，川为欧氏距离测度，v 2 ，。， ，：，匕) 为聚类中心集合，拼，为第i个数据x ，相对于第j 类的隶属度值，b 是模糊化因子，1 b o o 。对于式( 2 5 2 )6疗i l聆 占c”v( 1 兹) 。1 拓、v f ，曼n 盟，办占。c，( 1 ) 一( 材f ) 6 薯v = 号- 一，w( ) 6i = l( 2 5 3 )( 2 5 4 )式中s 0 ，合适的s 值可以使获得的聚类中心接近于实际中心。m f c m 算法是通过对式( 2 5 3 ) 、式( 2 5 4 ) 迭代运算收敛到目标函数的局部极小点。为了使算法稳定，可以用f c m ( f u z z yc - m e a n s ) 算法的聚类结果或中间结果对m f c m 进行初始化。由于放松了隶属度条件，使m f c m 最终聚类结果对类别数初始值c 不十分敏感。为了表述方便，将初始化类别数c = 2 时的m f c m 算法称为m f 2 m 算法，可以证明m f 2 m 算法具有如下特点：若实际类别数c ， 2 时，该算法虽然没有给出全部聚类中心，却能正确聚类出其中的两类：若实际类别数c ，= 1 时，该算法并没有将样本集强行分为两类，而只在样本集中央给出两个近似重合于实际类中心的聚类中心2 6h s c 算法描述本章提出了一种基于m f c m 算法的分级递减聚类( h i e r a r c h i c a ls u b t r a c t i v ec l u s t e r i n g ，h s c ) 算法，利用m f c m 算法寻找类中心，再自适应确定该类中心的隶属度阈值，将聚类进行分级处理，实现未知类数数据集的聚类。交通流状态近似服从高斯分布，该改进算法对于未知聚类数、服从高斯分布的数据集具有聚类效果好，收敛速度快的特点。本章最后用服从二维高斯分布的交通流数据对算法进行了验证。分级递减聚类( h s c ) 算法，其摹本思想如下：设x “为第t 级数据集( t = l ，2 ，) ，将原始数据集作为第一级数据集x ，用m f 2 m 对其进行聚类，得到两个实际的类中心向母，再通过设置隶属度阈值的方法，将所得的两个聚类中心所代表的实翰i 类从原数据集中分离出去，将剩下的数据样本点作为下一级数据集x 汜，用同样的方法继续聚类，并确定下一级7第二章基于m f c m 的改进聚类算法及其在交通中的应用数据集，直到聚类完成为止。根据m f 2 m 聚类特点知，当x n 的实际类数c ，为奇数时，第( c ，+ 1 ) 2 级的数据集实际上就是一类，此时将得到两个重叠或非常接近的类中心u ，u ：，按下述方式将得到的两类合成一类：v = ( 1 ，i + l p 2 ) 2 ，甜? = ( 甜，l + u 1 2 ) 2( 2 6 1 )式中： ，+ 和u ? 为该类的中心和隶属度。为了得到在第t 级m f 2 m 算法聚类后的下一级数据集x i t + 1 ，可以选取适当的隶属度阈值h “，由该级划分矩阵u “按下式进行确定x + 1 。若磁：“， ，j = l ，2贝0i d x o + 1 ，i = 1 , 2 ，刀o 式中：上标为对应的级数，隶属度值u t j 是关于距离d t j 的单调递减函数，因此可以根据各类中心到该类边缘的距离确定隶属度阈值 。假设原始数据集中各类数据都服从高斯分布，我们可以近似将每一类数据点看作是处在以该类中心为球心的封闭球中( 对于二维数据，为封闭圆) ，r ，为类j 的封闭球半径，球外的点可以认为是噪声点，对于封闭球半径r ；，可以通过以下分析确定：对于一个子类的数据分布，假设其类中心为v ，各样本点距离类中心v ，的最小距离和最大距离分别为和，雌，将区间 ，m 。 分成n 个等距离的子区间：眈，l 】，【厂l ，厂2 】 ，【厂小】，其中r 0 = m a i n ，h = r m 。，区问宽度为a r 。分别以，吒，h 为半径，以点v 。为中心作圆( 对于高维数据作超球体) ，则相邻圆之间形成圆环区域序nc ，c ：，c 。定义圆环c k 内的数据样本点的数目为频数 ，k = l ，2 ，on 。对于二维高斯型分布的数据，设其方差为仃，可以证明：当a r 1 1 0 4 5 0 时，频数序列 六 是递减序列，即该子类边缘对应频数值的第一个极小值，当a r 1 1 0 4 5 0 时，频数序列 以) 先增后减，即该子类边缘对应频数值的第二个极小值，而z 为第一个极小值，对于高维数据集也有类似的规律，因此，对应一个给定的类中心v ，该类边缘应位于其频数序列 五) 中的第一个极大值后的第一个极小值所对应的半径区间【0 ，饥。】内，将该区间的中间值作为该子类的聚类半径r j ，有：，= ( 乃+ 乃+ i ) 2( 2 6 3 )8第二章基于m f c m 的改进聚类算法及其在交通中的应用将0 代入( 2 5 3 ) 式得隶属度阂值勺：”f l r1 1 ，( 61 )厅。= 丁。, 2 一( 2 6 4 )j”n厶4 1 d ：) 1 l i f f i l考虑到数据集会存在噪声点的影响，会有少量的数据点出现在设置的各类封闭球的外面，从而在获得了全部的聚类中心后，还会有未聚类数据。为了确定算法结束，假设允许最后未被聚类的数据数占x “中数据总数1 3 的最大比例值为a ，则允许最后未聚类数据点的数目为：h = a 宰刀( 1 ( 2 6 5 )若刀什1 n t h ，则认为不再有新的聚类中心。由于各级数据集的数目不同，所以不同级聚类过程中，式( 2 5 3 ) 的分母也不同，从而不同级的隶属度没有可比性。要得到统一的类划分矩阵u ，可以由式( 2 5 3 ) 和各级聚类中心对原始数据集x “计算u 。h s c 算法处理步骤：步骤1 ：聚类趋势检验，若待分类样本可聚，则转向步骤2 ，否则停止步骤2 ：初始化x ，占，b ，t ，a r 和口。步骤3 ：根据m f c m 算法将x 分成2 类，得到划分矩阵u d 和聚类中心v n ，：”。步骤4 ：计算d ： i 1 ，：”一v ：7 l f 若d n t h ，则t = t + l ，返回步骤3 。9第二章基于m f c m 的改进聚类算法及其在交通中的应用步骤9 ：由式( 2 5 3 ) 和各级聚类中心，计算原始数据集x 1 的类划分矩阵u ，算法结束。在算法中，需要设置的参数有e 、b 、r 和a 。其中，为一较小值即可，如= 0 0 3 ；b 为模糊度，一般可取b = 2 ；区问宽度r 可在0 0 4 - 0 1 0间取值，若已知各类方差较大，则r 可取较大值，否则，取较小值；a 在0 0 0 8 -0 0 3 之i 、日j 取值，若数据样本总数较大，贝, j j a 可取较小值，否则取较大值。2 7 聚类有效性判断聚类有效性判断的目的是确定分类的结果是否有效或比较哪种聚类方法对于某一实际聚类问题更有效。聚类结果的有效性判断可应用统计学中的f 统计量知识：引入f 统计量f ，置一引2 ( r - 1 )f = _ 等乇- 一f ( r j ，刀一，夕，凡f ，f ，x ，一i j 2 ) f i n - r )其中r l 为数据总数，r 为分类数，哆为第i 类中的数据个数，1n i1n- i2 吉吾x j 为第1 类中数据的平均值，趸2 吉吾x j 为所有数据的平均值( j = l ，2 ，。，嚏) 为第i 类中的元素，分子表征类与类间的距离，分母表征类内元素间距离，f 值越大分类越合理，对给定的置信度a ，查f 临界值表得f 。，然后将f 值与f a 做比较，若f f 。，根据数理统计方差理论，表明类间羞异显著，分类有效。得到聚类结果。若f r 。，分类可接受。表2 给出了传统的f c m 算法和本章提出的基于m f c m的h s c 算法的应用效果比较，可以看出基于m f c m 的h s c 算法聚类效果更好，算法所需运行时间更少。表2 不同聚类算法的比较f 统计量运行时间( m s )传统的f c m 算法7 4 0 3 25 3 6 2基于m f c m 的h s c 算法1 1 6 3 2 l8 9 3d 得到结果即分为七类，我们不妨用“非常好”、“很好”、“比较好”、“中”、“比较差”、“很差”、“非常差”七个模糊值来描述表1 的交通流状态。e 针对每个样本数据对于七个聚类中心的隶属度，应用统计学和模糊数学的知识即可很容易地构造出隶属度函数，这里不再赘述。2 1 0 加权指数对算法的影响对于模糊聚类的目标函数jm ( u ，p ) ：n 壹( ui k ) m ( di k ) 2 ，加权指数m 对k = l i = l于聚类算法有很大的影响。因此，对于基于目标函数的模糊聚类算法中的加权指数的研究是十分必要的。2 。1 0 1 参数m 的意义nc对于jm ( u ，p ) = ( ui k ) m ( d 。k ) 2 ，k = l i = l将j m 对m 求导：半= 艺i = l 羔k = l f ，甜旗夕”培厂列磕夕f ，d 埔夕3f ”= t g r u 。) 1 1 1 l 苌| d 。) 21 l + 时该算法失去模糊划分能力，从而变成硬c 划分，这不是我们所希望的，因此在实际中总选m l ：m 佃时，该算法得到的隶属度均为1 c ，样本隶属于各类的程度相等，使得类分结果太模糊而且得到c 个一样的聚类原型，达不到聚类的目的。参数m 控制聚类结果的模糊性，m 越大聚类结果越模糊，通常希望聚类的结果不要太模糊，这就要求在调用该算法时，m 的取值不要太大，那么，小的m 值是否就一定对应好的聚类结果呢，答案是否定的，因为较大加权指数m 还具有抑制噪声的功能，在从噪声污染的数据中获取模式样本的模糊聚类应用中起着重要作用，参数m 抑制噪声的功能是通过对隶属函数加以较大权重，是隶属度普遍较低的点( 噪声点) 对目标函数的贡献较小，使得它们在确定聚类中心和隶属函数时被忽略。本课题应用基于模糊决策的参数m 优选方法确定i n 的值：2 1 0 2 模糊决策理论模糊决策理论是b e ll m a n 和z a d e h 提出的一种决策分析工具。假设给定一个模糊目标g 和一个模糊约束c ，那么一个决策由g 和c 的交集形成，即d=gnc( 2 1 0 2 )当g 和c 作为模糊集处理时，它们分别由其隶属度函数来刻画，模糊决策的隶属度函数可以表示为d d l x ) _ m i n u g x ) u c x ) 最终的决策结果为满足式( 1 7 - 3 ) 的决策空间中的备选解，即材d ia lj2 飞x u d ( a jj j2 1 0 3 基于模糊决策的参数m 优选方法在研究加权指数m 的优选方案的过程中，选择了模糊决策方法，利用模糊决策解决问题的关键在于构造合适的模糊目标、模糊约束以及它们的隶属函数，这样就可以利用模糊操作做出决策。聚类的目的就是要对给定的数据集进行合理的分类，使相似的样本归为一类，而不相似的样本尽量划分到不同的类中。从数学的角度讲，就是要使分类后1 4第二章基于m f c m 的改进聚类算法及其在交通中的应用的样本集类内距离尽可能小，类问距离尽可能大，类内加权平方误差和函数( w g s s ) 即为衡量这一要求的最合适的工具。而加权指数m 的选取也必须以合理聚类为最终目标。因此，参数m 优选这一问题的模糊目标为g = m i n j 。f ，u ，p 爿所r ，佃夕夕此外，该聚类算法在完成模糊聚类的同时还要求数据集的划分尽可能的分明，以便于正确的区分每个样本的类属关系。冈此，这就给参数m 的选择加上了一个约束，即所选取的m 值不要使聚类算法的聚类结果太模糊。参数i l l 优选决策的模糊约束就定义为c = m i n h 。f ，u ：c ) l m r ，佃夕，其中h 。f ，彤j c = 一丢l o g 。f ，掰，。夕fno以i 7 7 j( 2 1 0 6 )为划分熵1 阳刚，a ( 1 ，+ ) 为对数的底数，且约定u i k = 0 时，有甜睹t o g 。m 睹夕= 0 。样本集的划分越分明就越有利于分类，因此，对于给定m 值，希望模糊聚类的划分熵越小越好。由以上分析可知，关于参数m 优选的模糊决策可表示为m i n j m u 1 p ) 所2 翟k 日。驯一 聊砌也就是说，最佳加权指数i l l 的确定转化为一个带约束的非线性规划问题。这样一来，就可以通过模糊决策来确定i l l 的最佳取值。为了进行模糊决策，还需要定义模糊目标g 的隶属度函数。从模糊聚类的目标来看，目标函数越小越好，因此，我们用单边的钟形函数定义模糊目标的隶属函数，并映射为参数m 的函数：，1 p l甜g f ，打j = e x p 一口j i 三毛乏；赫，2 1 0 9 )其中，a 为一大于l 的可调节的参数，实际应用中一般取a = 1 5 。模糊约数c 的模糊隶属度函数定义为“咖丽焉1夕l + p 二j 羔m a x ln lu ：l i其中，为一较大的正常数，实际应用中一般取为p = l o ，由式( 1 7 9 ) 可知，对于给定参数m ，聚类算法的结果越模糊，对应的隶属度就越小，这恰好符合定义的模糊约束极小划的模糊聚类划分熵。定义了最优加权指数m 决策的模糊日标、模糊约束以及对应的隶属函数后，即可利用模糊决策的方法获得m ，也就是说，最优加权指数m 取为模糊目标和模第二章基于m f c m 的改进聚类算法及其在交通中的应用糊约束所对应的模糊子集的交集中最大隶属度所对应的m 值，由下式可求得：r t l = a r g m a x m i n u g m ) ，髓c ( r e ) i l lv m按式( 2 1 ) 所得到的m 将能保证，既以较大的隶属度极小化聚类目标函数，又以较大的隶属度极小化模糊聚类的划分熵，使聚类算法得到的模糊聚类既能表达样本间的相近信息，又能保证样本类分的明晰性，因此也必然对应于好的模糊聚类结果。2 1 1 本章小结人们需要通过分类来总结规律，因此，分类问题的研究具有十分重要的意义，将分类问题应用到交通领域，对于交通控制起到很大的辅助作用，传统的具类分析是一种硬化分，每个研究对象能且只能被划分到某一类中，而交通流状态的分类问题往往伴随着模糊性，在很多时候一组交通流状态是否属于一个子类不是泾渭分明的，因此用模糊聚类的方法描述交通流状态的分类就特别的方便。本章通过对m f c m 算法进行部分改进，并将其应用到交通流状态的模糊聚类中，目的是更科学的确定交通流状态的分类结果，实际的应用结果证明了该算法的有效性。m f c m 算法是近年提出的有效聚类方法，但需要给定类别数的初始值，交通流状态的模糊化是在未知类别数的情况下对近似服从高斯分布的数据集进行聚类，本幸提出的改进算法( h s c 算法) 对于未知聚类数、服从高斯分布的数据集具有聚类效果好，收敛速度快的特点。该算法对于服从其它分布的数据集的聚类效果还有待进一步的研究。1 6第三章交通状态仿真第三章路口交通流微观仿真3 1 路口交通流微观仿真的意义和现状交通运输是一个综合行业，它涉及到车辆、人员、道路、环境、能源等多方面的因素，长期以来，交通工程学的研究人员将它们作为一个大系统来考虑，智能运输系统( i n t e lli 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 ) 的中心思想方法是利用最先进的计算机、通讯、控制等科学技术，使交通运输达到人一车一路综合协调的新境界。对道路交通实施仿真在很早就已经受到重视，并得到广泛应用，如对道路通行能力的模拟，对平面交叉路口的模拟，在交通控制系统中为寻找最佳配时方案对控制效果的模拟等。实验证明仿真是研究交通控制的最有效工具之一。关于交通仿真的概念形成于5 0 年代，到6 0 年代才确认了交通仿真的有效性和可行性，国际上在交通状态仿真领域已取得一些成就，建立了各种模型，并在实际中得到广泛应用，比较典型的仿真模型有：1 s i g o p 模型：宏观的优化模型，用于信号控制的优化。2 t r a n s y t 模型：宏观的优化模型，预估模型比s i g o p 更可靠。3 n e t s i m 模型：网络微观交通仿真，模型涉及了实际应用中常见的道路设计、交通控制管理方式的描述。更多的面向不同的应用的仿真模型，如高速公路交通模型( s c o t ) 、城市道路交通模型( s i m n e t ) ，交叉口仿真( t e x a s ) 等。国内对交通仿真技术的研究仍处于非常零散的状态，缺乏系统而全面的研究。交通仿真技术作为智能运输系统的项重要内容在同内一直未受到足够的重视。3 2 传统交通流仿真的缺陷目前我国应用的交通状态仿真系统主要依靠进口，国外已经开发了许多交通仿真模型，可是人多数仿真模型并不适用于i t s 的分析。原因是多方面的，一个重要的原因是很多交通仿真模型开发于9 0 年代以前，那时i t s 还