粒子群算法在动态交通分配问题的应用本科毕业设计

1、摘 要动态交通分配在交通控制与诱导中起重要作用，因其能充分考虑交通路网中的复杂性、时变性和随机性等典型交通流特性，比静态交通分配更有优势。传统的优化算法计算量大且容易使性能指标陷入局部最优，极大地限制算法在理论和实际上的应用，采用粒子群算法可以使求解变得简洁和方便。本文主要研究动态系统最优模型，通过分析动态交通分配的特点，构建了动态交通分配模型，并运用引入惯性权重的改进粒子群算法，以总花费时间最小为优化目标对多路径交通网络进行研究。最后在多路径小型交通网络中进行matlab仿真，仿真结果体现了该模型的有效性和改进的粒子群算法的优越性，提高了模型的应用价值。关键词 动态交通分配；粒子群算法；优化

2、算法；多路径；仿真abstractdynamic traffic assignment plays an significant role in traffic management and guidance. it has an advantage over the static traffic assignment, because it takes full consideration of the typical traffic flow characteristics such as complexity, time variation and probability, etc. t

3、raditional optimization algorithms seriously restrict the application and development of the model in a large amount of calculation or easy to fall into local optimal value of performance index, but it can be simple and convenient to solve such problems via particle swarm optimization(pso). this pap

4、er mainly studies the optimal model of dynamic system, which is based on the minimum of total spent time as the objective function. the dynamic traffic assignment model is built via to analysis its characteristics, and using improved particle swarm optimization with inertia weight factor. finally, m

5、atlab simulation is carried out in a multipath traffic network, the simulation result shows the validity of dynamic traffic assignment model, the superiority of improved particle swarm optimization and the value of the model. key words dynamic traffic assignment pso algorithm optimization multipath

6、simulation目 录摘 要iabstractii第1章 绪论11.1 引言11.2 智能交通系统概论11.2.1 智能交通系统研究现状11.2.2 智能交通系统的组成21.2.3 城市智能交通控制与管理系统31.3 动态交通分配的研究现状41.4 动态交通分配理论的应用51.5 本文章节安排5第2章 动态交通分配模型72.1 动态交通分配72.1.1 动态交通分配概述72.1.2 动态交通分配模型82.2 约束条件分析92.2.1 流量守恒92.2.2 非负约束92.2.3 先进先出规则102.2.4 路段容量限制102.3 优化算法102.4 本章小结11第3章 粒子群优化算法123.

7、1 粒子群优化算法简介123.1.1 算法的基本原理123.1.2 算法流程133.1.3 算法的特点143.1.4 参数的意义153.1.5 算法的优缺点153.2 粒子群优化算法的改进163.2.1 算法的研究方向163.2.2 算法的改进173.2.3 算法的拓扑结构研究173.3 粒子群优化算法的应用183.4 本章小结19第4章 粒子群算法在动态交通分配问题的应用204.1 带惯性权重因子的改进算法204.2 研究算例204.2.1 动态交通分配模型204.2.2 动态交通分配求解214.2.3 动态交通分配算法的讨论234.3 本章小结23结 论24参考文献25致 谢26附录 动态

8、交通流分配模型程序27第1章 绪论1.1 引言随着科技社会的发展，人们对交通工具的需求越来越大，其中小型汽车的数量日益增多造成的交通堵塞、交通事故频发等众多的交通问题，对社会和人们的生活、经济，甚至是整个人类的生存环境构成了巨大的威胁。在这种背景下，如何综合地处理道路上现存的交通问题成为交通控制与管理的主要研发方向。利用现代化手段管理城市交通运输，科学和有效地引导和分配车流量，使现有交通网络的运行效率得到有效地提高，这是发展城市交通的主要方式，智能运输系统（intelligent transportation system，简称its）因此应运而生。its是社会公认的解决城市和高速公路交通拥堵

9、和提高驾驶员行车安全的主要措施，也是交通管理领域学者们研究的前沿问题。作为道路路网规划的最后一个环节，交通分配具有不可替代的地位，它是方案设计的理论基础，也是方案实施的最终目的。静态交通流分配模型中交通量配流不具有时变性，没有考虑到实时变化的交通因素的影响，无法根据实时的交通状况来动态诱导车辆，更无法避免出现个别路段交通拥堵的状况，该模型一般用于较长时间的交通计划。相比之下，动态交通分配模型考虑了时变的od交通量需求，能预测时变的交通路况下错综复杂的交通行为，在its中的动态路径诱导中起到关键性作用，因此这方面的研究具有非常重要的理论与应用意义。1.2 智能交通系统概论智能交通系统是将现行的信

10、息技术、网络处理技术、车辆控制技术、电子传感技术和数据通讯传输技术等综合地应用于整个交通运输管理中，并且把使用者、车辆、道路紧密地联系起来，建立起一种在大路网、全方位发挥作用的，实时、高效、精确的综合交通管理系统。智能化交通运输服务和管理，促使路网上的车流量保持在最佳状态，减少交通堵塞情况和交通事故的发生，提高路段的最大通行能力，促使整个交通运输的安全性、能动性和生产效率得到提高。1.2.1 智能交通系统研究现状20世纪中期，美国领先对电子路径诱导系统进行开创性研究，为现在its的动态路线诱导系统drgs（dynamic route guidance systems）提供了最初的经验。1990

11、年，美国交通运输部成立了ivhs（intelligent vehicle-highway system）组织，并于1994年正式更名为its america（intelligent transportation system of america）组织。目前美国已经在its的整体组织及规划、开发、运作实验等方面进行的大量的投资和部署，其电子收费系统、轨道自动驾驶等its技术处于世界领先地位。自上个世纪八十年代以来，西欧国家在“欧洲高效安全交通系统计划（prometheus）”和“保障车辆安全的欧洲道路基础设施计划（drive）”两大计划推进下进行交通智能化项目的探讨、研发与应用。之后在第10届

12、its世界大会上，欧洲its研发组织ertico首先提出esafety道路安全计划的基本理念，获得欧盟委员会的认可并被列入欧盟的规划项目中。日本的its研发起步于20世纪90年代，经过20年的发展，初步完成了基础技术和核心技术的开发，目前处于实用技术开发的阶段。由其开发的smartway计划将建立“安全安心的汽车社会”为主要研发方向，现在尚在技术普及阶段，20052010年期间将围绕人车路协调系统、智能汽车系统等五个重点项目进行研究。与国外相比，我国对its的研究时间较迟，但随着信息技术、计算机控制技术和通信技术等现代技术的快速发展，我国加快了对its关键技术的研究速度。以国家its建设内容为

13、指导，形成了主要发展规划：以协调公路智能与车载智能的合作为前提，以智能化道路基础设施为核心，促进人、车、路三者为一体协调发展。十二五计划中将重点发展新一代城市智能交通控制系统，综合交通运输和服务的优化技术，构建智能评价交通系统的平台标准。1.2.2 智能交通系统的组成目前社会上认可的智能交通系统主要有7个构成部分。（1）先进的交通信息服务系统（atis） atis以完善的信息网络为基础。驾驶者通过传输设备，向交通管理中心提供所处地的现时交通状况信息；atis得到这些信息后进行提取，及时向出行者提供交通信息；出行者根据这些路网资讯选择通行道路，选用自己的通行工具。如果车上设置了gps设备，该系统

14、甚至可以预先为驾驶员确定行驶路线。 （2）先进的交通管理系统（atms）atms一般由交通管理者掌控，可以用来监视和管理路网交通状况，在车道、车辆和驾驶员之间提供服务。该系统实时监视道路系统中的交通事故、气象状况和道路状况，运用卓越的计算机信息处理技术和车辆识别监控技术，根据采集到的信息对路网上的车流量运行状况进行控制。 （3）先进的公共交通系统（apts）apts以联结各种智能控制技术来发展公共交通运输业，使公交客运实现快速便捷、经济实惠、运载大的目标，利用公交车站上的候车屏幕向乘客提供车辆的运行情况。在公交汽车管理方面，可以以班车的运行状态为依据合理安排首末班车时间、发车间隔等计划，提高工

15、作效率和候车者满意度。 （4）先进的车辆控制系统（avcs）avcs主要通过研发先进的控制技术使驾驶员驾驶汽车时能够在道路上安全、通畅地行驶。该系统给予驾驶警告和帮助服务，以及控制车辆躲避障碍物等自动驾驶技术。 （5）货运管理系统该系统根基在高速道路网和信息控制系统的基础上，结合物流理论进行智能化控制的物流管理系统，集成gps技术、物流信息及网络传输技术，以建立有效的货物运输方案，提高货运效率为目的。 （6）电子收费系统（etc）etc通过安装在车辆上的车载接收器与安装在收费站etc车道上的探测发射器进行通讯，车辆通过收费站时不需停车就能智能缴纳路桥费，收费中心通过计算机网络传输与银行平台处理

16、后将所收纳的费用清分给相关的业主，极大地提高了收费站的通行能力。图1-1为电子收费系统结构。警察局车辆户口数据库数据库账单寄出银行联网系统主机外围设备摄像机读写器图1-1 电子收费系统结构（7）紧急救援系统（ems）ems的基础是atis、atms和相关的救援组织和设备，借助这两个系统有机地联合交通监控中心与专业救援机构，提供紧急处理车辆故障事件、人员应急救护、排除事故车辆等服务。1.2.3 城市智能交通控制与管理系统城市交通控制系统是综合城市交通道路中交通红绿灯的配时、路网数据的收集与交通诱导的智能控制技术，能统一监视局部或整个城市的交通监控系统的运行，主要由指挥中心控制系统、自动化的交通管

17、理系统、路网视频监控系统、信号灯配时控制系统、信息搜集及传输和处理平台和gps车辆定位系统等几个子系统组成。智能交通信息管理平台是集成信息化、智能化的新型交通管理工具，可对交通运输系统中的信息资源进行整合，并具有按一定标准完成多源异构的大量数据的接收、存储、处理、发布等功能，实现管理部门间信息传输，为交通运输组织在交通控制方案的制定、改进方面提供数据支撑。图1-2为城市智能交通控制与管理系统的结构。交通管理信息系统软件平台交通事件事故视频检测系统交通诱导系统交通事件快速处理系统gps车辆定位系统供电防雷系统信息传输系统闭路电视监控系统超速检测系统电子警察系统信号控制系统业务支撑平台硬件平台交通

18、管理自动化系统其它信息应用系统指挥中心控制系统图1-2 城市智能交通控制与管理系统的结构1.3 动态交通分配的研究现状交通配流问题作为路网规划的一个有机构成部分，对其的研究向来是学术界感兴趣的项目。交通分配方法按照平衡准则可以分为平衡模型与非平衡模型。非平衡模型又可分为有容量限制分配模型、最短路分配模型及多路径分配模型等，这些模型构造简单、计算方便，但在应用时与实际效果相差较大。而平衡模型作为新发展起来的新式交通分配模型，这类模型与非平衡模型相比，具有条理清晰、结构缜密、结果合理，适用于大规模研究的优点。但这类模型常因为维数太大、变量较多、约束因素太多，使得对这类模型的建模比较麻烦，影响了其实

19、际应用的效果。从对出行者选择路径方面的假定来看，将动态交通分配模型划分为预测型和反映型。预测性模型指的是出行者根据某一段时间的交通状况预先决定自己的最优行驶路径，这条最优路径是根据以往经验中在该路段行驶花费的实际成本得到的。反映型模型是指出行者根据实时的交通状况来选择费用最低的路径。但由于城市交通状况具有时变性，反映型模型可能使相同起始点和出行时间的出行者，由于在不同时刻出发，使得他们最终所选择的路径所消耗的时间不同。根据研究方法可以将动态交通流划分五类：（1）数学规划建模方法；（2）计算机模拟方法；（3）最优控制理论建模方法；（4）不动点理论建模方法；（5）变分不待式与非线性互补理论建模方法

20、等1。1.4 动态交通分配理论的应用动态交通分配是在己知的交通需求和交通运行状况下，分析实时路网的最优交通流分配情况，其需要优先考虑的是对各个时刻产生的出行需求的科学预测，在确定时变交通需求量的基础上，再对路网交通量进行合理的分配。交通出行明确的目的性决定了od矩阵在动态交通配流中的重要地位，所以在交通量分配中假设od需求矩阵是己知的确定量。除了己知的各时段交通需求外，也要设定好路网构造和路段的限制特性。动态交通分配在体现城市交通路网的适应性、随机性、时变性还有对城市路网管制的各种措施的评价上，比静态交通分配更具有实用性。（1）可以对交通拥挤特性进行全面分析。交通堵塞在不同的时间区间内发生在不

21、同的区域，交通拥挤在一定范围内限制了城市交通流的分布扩张。为了分析交通拥挤情况的特性，必须建立起动态的交通配流模型，对车流量进行合理分配。动态交通配流模型充分考虑到时变的交通需求和路网特性，能够计算出交通流的分布量，于是可以预测交通阻塞发生的时段和位置，并采取及时的解决对策。（2）为智能交通系统(its)提供主要的技术支持。动态交通分配模型以均衡分配交通量为基础，能够立刻地采取妥善的管理或诱导措施控制交通流，提高路网通过率，这也是动态交通分配的最终目标。人们对于交通管理持有的观念由以往通过开发和铺设道路，增加和设置交通管理设施来提高交通路网的通行效率，转变到通过改善交通管理和评估交通路网实时状

22、态来增加路网通过效率。在这一方面，动态的交通流模型不仅能更精确、科学地描述路网中交通流的时间、空间分布模式，也能更确切地模拟出高峰期和非高峰期间车流量的交通特性。（3）可以对交通流进行最优控制。动态交通分配集合了交通需求随时间变化的路网特性，可以检测某一时刻的瞬时的交通流分布情况，因此，它能及时预测交通堵塞事件的发生，从而为信号灯的配时提供精确的信息，让车辆通畅运行。1.5 本文章节安排全文内容分为四章，按照粒子群算法对多路径路网进行建模和仿真实验，模拟车辆在动态路网中的路径选择与最优配流问题，具体章节的安排主要如下：第一章，本文的绪论部分。重点叙述了交通分配的背景以及意义，并对智能交通系统和

23、动态交通分配进行简单的叙述。第二章，动态交通流分配模型理论的概述。分别对动态交通流分配模型的建立、约束条件和相关术语与符号进行了详细的介绍，并比较分析几种常用优化方法的基本思想和优缺点。第三章，详细介绍了基本粒子群算法的原理、流程、特点等，以及该算法的研究进展。第四章，根据实际情况，建立交通分配模型，以简单的多路径交通路网为算例，求解分时段的动态交通分配情况，验证该模型的合理性和有效性。第2章 动态交通分配模型2.1 动态交通分配动态分配是交通流理论发展、不断完善的趋势，是交通控制与管理实际应用之需。在交通需求管理中，不仅要制定科学、合理的交通规划设计服务，还要制定完善的交通管理控制方案服务，

24、将其应用到交通控制和诱导中。its的研究与实施，迫切需要对动态交通分配理论提出更多的需求，使得理论能够应用在实际中。图2-1体现了动态交通分配在交通诱导与控制中的作用。数据采集交通过程参数提取动态交通分配输出数据整理交通诱导交通管理图2-1 交通管理、诱导与分配之间的关系图由图2-1可以看出，动态交通分配为交通管理和交通诱导提供了数据输出，而交通管理与诱导则是动态交通分配要达到的终极目标。交通管理通过变换红绿灯信号的配时方案来改变车流的通行情况；而动态交通诱导则通过路况信息输出、车辆诱导系统等技术手段改变车流在时间和空间上的传播。2.1.1 动态交通分配概述动态交通分配（dynamic tra

25、ffic assignment，简称dta）根据出行的起、止点，按照一定的交通规则和实际的交通状况对各路径车流量进行合理分配，并为交通参与者提供最优路线引导以及其他丰富的实时交通路况来达到改善交通运行的目的，防止交通拥挤的发生，最终实现交通路网各个路段上交通流的最优分配。动态交通分配理论已经经历了20多年的发展，各国学者对它进行了多方面的探究，不断提出改良和合适的模型。动态交通流分配模型能再现实际交通状态，在计算机上模拟网络中车辆随着实时车流量的变化而改变其行车路线的情况，而这种交通状态是出行者对路径选择的结果2。从merchant和memhauster3为动态交通网络模型相关问题所作出的具有

26、开创性的研究工作以来，动态交通流分配模型及其理论已经历了30余年的发展历程。从研究趋势上看，动态交通分配模型研究的内在实质包括了如下四个方面： （1）动态交通需求；（2）狭义动态交通分配。对交通路网状况、行程时间、排队、起始点理想行驶路径等随时空变更的规律进行研究，在交通供给状况和交通需求已知的状况下，得出其最好的车流量分布模式，为实时交通控制与管理提供借鉴； （3）路网特性的时变规律和道路状况的影响： （4）各种环境因素对路网状态的聚集影响，如交通信息发布事件、频率、内容及覆盖率等。2.1.2 动态交通分配模型本文取用时段0，将之分为若干个时段，每个时段间隔相等。当交通流量变化较大时，时间段

27、应细分，以能够较为真实地反映交通流量变化的情况为基本原则。将各时间段分为1，其中各时段总的均衡模型，满足fifo规则：（2-1） s.t. （2-2）（2-3）（2-4） （2-5）（2-6）（2-7）式中 时段0，的网络总阻抗；时段时网络总阻抗；时段时在路段上的交通流量；路段的阻抗函数，即车辆通过路段的时间；时段时od对，间第条路径上的交通量；以节点为终点的所有路9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999段集合；

28、如果路段在连接od对，的路径上，其值为1，否则为0；各个时段路段上交通流入量；各个时段路段上交通流出量。2.2 约束条件分析2.2.1 流量守恒流量守恒是指对于任何一个节点来说，驶入该节点的车辆数与驶出该节点的车辆数相等。在实际的交通网络中，每一个路段上的车流量并非一成不变的，随着时间的变化，在每个节点上都有可能产生不同数量的新车流量4。假设车辆在任意时刻路段上的流量为：（2-8）或（2-9）那么，流量守恒约束条件为：（2-10）式中 节点为目的地的所有路段的集合；以节点为出发点的所有路段的集合；车辆在时刻进入路段并以节点作为目的地的交通量； 车辆在时刻驶入路段并以节点作为目的地的车辆流入率。

29、2.2.2 非负约束根据实际经验可知，在任何一个时刻，交通网络中的任何一个路段上的车流量都应为非负值，详细表示为：，（2-11）2.2.3 先进先出规则先进先出规则（first in first out，简称fifo）是carry于1992年首先提出的。该规则假定先进入路段的车辆必须先离开路段，即同时进入同一路段的车辆必须花费相同的时间，并以相同的速度行驶，行驶过程中不存在超车的现象。这一假定明确了路径行程时间、输入流和输出流三者之间的关系。在动态交通路网中，当所求解的交通路网存在多个终点时，fifo规则则会造成模型的解域出现非凸集合可行域的情况，当模型符合不了该规则时，模型的解不合理，由此可

30、见fifo规则的局限性。fifo规则不是模型必须具备的条件，但它能使交通分配中的路段模型得到化简，从而简化整个dta模型，在一定程度上是一个很好的约束因素。在建立动态分配模型的过程中，该规则只是要求模型具有有效性，并非必然会出现在模型的约束条件中，只要能正确建立路段流出函数，就能自动满足fifo规则。2.2.4 路段容量限制路段容量限制是指单位时间内通过一条路径或道路某一截面的最大车辆数，其单位通常为辆/小时。路段的容量限制是反映该道路车辆承载能力的一个重要的物理量，体现了道路的一种特性。当道路上存在的车辆数在路段容量限制的范围内时，在道路上驾驶会相对畅通些，司机在驾驶时也会感觉更舒畅些，用较

31、少的行驶时间通过该路段，从而诱使更多的车辆选择在该路段上行驶。当某处的车流量趋向于等于路段容量限制的状态时，会逐渐降低车辆行驶的自由度，导致该路段上的车辆只能以较低的行驶速度移动，增加在该路段上行驶的时间，从而促使部分车辆绕行到其他的路段。当交通量大于道路的路段容量限制时，该路段就会发生交通堵塞，严重的话会引起交通瘫痪。现假设为某一路段的长度（千米），为路段上的最大交通密度（辆/千米）。那么，该路段上的最大车辆数则为。而路段上行驶的车辆数必须不能超过该路段的最大容量限制，即： （2-12）2.3 优化算法最优化算法是从众多可以实现的方案当中选取最合适的一种方案，以达到获得最佳目标的目的。启发式

32、算法属于优化算法中的一种，该算法在状态空间中对每个搜索到的位置都会进行评价，排除掉不合理的位置，得到最好的位置后再对这个位置进行精细的搜索直到满足目标要求。由于其具有误差小、计算时间短、程序简单易于修改等优点，常用于研究动态交通分配模型。常见的最优化算法有：禁忌搜索算法、遗传算法、蚁群算法和粒子群算法等，表2-1简要地对这几种算法进行比较。表2-1 几种优化算法的比较优化算法基本思想优点缺点禁忌搜索算法先求得一初始解，每次只与最优值比较；记录下已经搜索过的局部最优点，在下一次搜索中有目的地搜索这些点，以此来摆脱局部最优点5。在搜索过程中允许存在劣解，具有较强的越过障碍的能力；具有很强的局部搜索

33、能力。对初始值的依赖性较强，不能进行并行搜索。遗传算法用种群来表示一组解，通过对当前群体进行选择、交叉和变异等一系列遗传操作，产生新一代的种群，并逐渐使种群进化到包含近似最优解的状态6。良好的收敛性；较高的鲁棒性；不受函数约束条件的限制。搜索空间范围大，搜索时间较长；易早熟收敛；对初始种群要求高，初始种群的取值常影响解的素质和算法效率。蚁群算法运动方向根据释放的信息素物质的浓度来引导，浓度越高，选择该路径的几率越大。当一批蚂蚁经过同一路径时，后面的蚂蚁选择该路径的可能性也就越大。引入正反馈并行机制，加快了进化过程；优良的分布式机制、易于与其他方法结合；不易陷入局部最优；较强的鲁棒性。每次解算法

34、过程的计算量较大，搜索耗时很大，易于出现迟缓现象；算法收敛性能影响初始取值。粒子群优化算法目标解视为维搜索空间中的一个粒子，所有粒子都有一个由被目标函数决定的适应值，得出自己目前为止发现的最好位置，利用个体和全局最好位置更新位置和速度7。具有很强的鲁棒性和并行分布性；优化过程无需依赖具体问题的数学特性；执行时间短。局部搜索能力差；搜索精度不高；缺少算法设计的指导原则。2.4 本章小结本章主要介绍了动态交通流中的一些相关概念、相关符号和动态交通路网中的约束条件，对几种常用的优化算法进行详细论述，并比较了这几种算法各自的优缺点。第3章 粒子群优化算法3.1 粒子群优化算法简介粒子群算法（parti

35、cle swarm optimization，简称 pso）在1995年由kennedy和eberhart 首先提出，该算法模拟鸟群飞行寻找食物的行为，通过鸟与鸟之间的合作使群体达到最优目的。pso开始是为了形象化地模拟鸟类群体觅食时不可预测的飞行行为，通过对鸟类社会行为的研究，发现在群体中共享社会信息能在演化中获得生存优势，并以此作为开发 pso 算法的根据。通过匹配附近粒子的速度，排除不需要用到的变量，并加入对多维搜索以及根据距离的加速的考虑，初步形成了pso的原始版本8。后来，shi等人通过增加惯性权重，使pso能够更好地用于调整探索（exploration）和开发（exploitati

36、on）的性能，形成了现在的标准版本。3.1.1 算法的基本原理在特定的模型中，每个粒子都象征着求解空间中的一个可行解，粒子本身都有一个由被优化的目标函数所设定的适应值，以及在解空间中当前所处的位置和速度，位置和速度的值决定了它飞翔时跨越的距离和方向。基于群体的行为繁乱多变，在搜索的过程中粒子应遵守以下三个原则：（1）飞离最近的粒子，避免产生相撞；（2）飞向最终目标；（3）飞向群体的中心。接下来具体的表述一下粒子群算法的原理，首先假设在一个维的目标搜索领域中，有个粒子形成一个粒子群，其中：第个粒子表示为一个维的向量，也就是粒子的当前位置：第个粒子的速度也是一个维的向量，每个向量也即是粒子的的当前

37、飞行速度：第个粒子搜索到的最优位置，也即是粒子所发现过的具有最好适应值的位置：整个种群到一定程度时寻优到的最优位置为全局最好：关于最小化求解，目标函数值越小，相应的适应值越优。pso算法同其它进化算法相似，是一种迭代的优化算法，速度和位置的更新公式为：（3-1）（3-2）式中 、第、次迭代、加速因子、0，1内的随机数个体极值全局极值在寻优中粒子的和都要接受最大值，和最小值，的约束。在式（3-1）中，当 时，取= ；当 时，取= ；当时，取= .如公式（3-1）所示，每个粒子的运动行为由三部分决定：第一部分体现粒子当前速度的影响，结合粒子目前的情况，明确了局部搜索能力与全局搜索能力的均衡比重；第

38、二部分为“认知”部分，即与个体极值的距离（），表示粒子本身的权衡；第三部分为“社会”部分，即与全局极值的距离（），表示粒子间的信息传播与合作。对pso 算法的这些心理学假设的争论是没有意义的。在追寻一致的认知过程中，个体通常牢记它们自身的最优位置，并且兼顾到其它个体的最优位置。当个体发现其它个体的最优位置较好时，它将选择灵活性地调整。pso粒子移动搜索的原理图可用图3-1描述。群体的影响微粒自我记忆的影响当前速度的影响图3-1粒子移动搜索原理图3.1.2 算法流程pso的算法步骤如下，流程图如图3-2所示。 step1：初始化粒子群（设定群体规模为），初始化随机位置和速度； step2：由适应

39、度函数计算每个粒子的适应度； step3：对每个粒子，将其目前的适应值与本身发现过的最好位置作对比，如果更好，则将其替换为当前的最好位置； step4：对每个粒子，将其目前的适应值与全局所发现的最好位置作对比，如果较好，则重新更新； step5：根据公式（3-1）和（3-2）更新粒子的速度和位置； step6：满足结束条件(误差足够小或达到最大迭代次数)则退出，否则返回step2。输出结果是否满足结束条件是否根据公式(3-2)对粒子的位置进行更新根据公式(3-1)对粒子的速度进行更新求出整个群体的全局最优值求出每个粒子的个体最优计算每个粒子的适应值初始化每个粒子的速度和位置开 始图3-2 ps

40、o算法流程图3.1.3 算法的特点（1）整个算法更新过程中，惯性权重、加速因子和和最大速度一起保持对全局和局部寻优能力的均衡；（2）在粒子群搜索初始阶段，其解值随迭代具有更明显的随机性，使其产生了下一代解群的较强的随机性，以及后面全部解的“信息”的共享性，改善各个解的“自我素质”等；（3）个体具有“记忆”和“学习”的品质，它们通过“自我”学习和向“他人”学习，使其后来的解有针对性的从“先辈”那里接收到更多的信息，从而能快速找到最优解；（4）在算法中，信息单向传播，只能将信息传给其余的粒子，使整个寻优在更新过程中跟随当前解。3.1.4 参数的意义pso参数有：种群数量，惯性权重，加速因子及和最大

41、速度，最大代数。 （1）最大速度决定了粒子在解空间的搜索精度，同时也决定了粒子在一个更新中能够移动的最大距离，在每一维中，它们的速度都会被限定在中，如果某一维粒子更新后的速度超过了（或），那么这一速度就被设置为（或）。如果太大，粒子可能会错过最好解；如果太小，粒子可能掉进局部最优区域而不能进行全局搜索。 （2）惯性权重因子 惯性权重因子使粒子保持运动惯性，使其有能力搜索新的区域。取值大有利于搜索一个新的空间，而取值小则有利于粒子精确搜索当前区域中的最优值。于是在开始进行全局搜索时需要取较大的值，扩张搜索范围（exploration），使搜索迅速收敛于某一范围，然后取较小的值进行局部精确开发（e

42、xploitation）来获得更加精确的解。 （3）学习因子和学习因子表示粒子的动作来自于自己经验的部分和其它粒子经验的部分。学习因子和代表将每个粒子推向和位置的学习权重，即表征粒子本身的思考的权重，则表示粒子间的信息传播与相互协作的权重。低的取值能够让粒子在被拉回之前在目标范围外来回搜索，而高的值则容易使粒子失控地冲向或超出目标区域，一般情况下取 。3.1.5 算法的优缺点主要的优缺点如下：优点：（1）pso 算法实现方式简单，主要是随粒子的位置和速度来寻优，收敛速度较快； （2）pso 算法拥有高效的局部和全局寻优的平衡能力，可以及时避开早熟； （3）pso 算法存在本质的并行性，利用批量

43、处理粒子群中多个粒子的方式，可以同时对寻优空间中的某个区域进行搜索； （4）pso 算法利用实数编码，可以在问题域上直接进行解值，需设定的变量较少，在工程上应用方便。 缺点： （1）pso 算法易取得局部最优解； （2）pso 算法搜索精度不高； （3）pso 算法高效的信息共享机制可能致使粒子搜索时过度聚集在某一区域，使粒子都飞向某个全局极值点，一般不用于多模态模型的优化研究； 3.2 粒子群优化算法的改进粒子群算法作为一种仿生进化算法，采用建立在群体的全局搜索策略和简单的位移速度模式，避免了类似其他复杂的遗传操作。由于它具有极快的计算速度以及算法具有的易实现性，吸引了社会上大量学者的密切关

44、注和探究。3.2.1 算法的研究方向根据粒子群算法研究的相关文献以及进化算法领域的发展趋势，目前粒子群算法主要有以下几个研究方向9。（1）pso的设计及改进研究兼顾到不同问题的特殊性，应注重加强对高效混合pso的开发，包括pso与神经网络、pid逻辑、模拟退火、生物智能、禁忌搜索以及混沌等方法相结合，充分吸收其他算法的优点，改进目前pso存在的弊端。此外，由于pso对参数具有很强的依赖性，选取参数时需要慎重考虑。（2）pso的理论分析迄今为止，pso的求解方法还不统一，存在许多待解决和未涉及到的问题，pso的理论分析一直是pso研究的难点。如何有效地利用数学模型对pso的运动轨迹、收敛速度、参

45、数选取、鲁棒性及计算复杂性进行分析应成为目前的研究热点，包括pso在多目标、离散以及动态等环境下的相关理论研究。（3）pso与其他进化算法的比较研究当前存在有三种经典的进化算法，遗传算法，进化规划和进化策略，这些算法有共通的特点，各自具有优劣势。粒子群算法与其他进化算法的共同之处在于都是基于“群体”、基于适应度来进行随机搜索，但都无法确保一定能寻到最优解。其他进化算法在进化的过程中只是保留和采用位置的信息，但粒子群算法可以同时保留及提取速度和位置信息，适应值低的粒子在寻优中仍能生存，并且可能搜索到空间中的任何一个领域。相比较之下可以突出pso的优劣。3.2.2 算法的改进（1）增加惯性权重和收

46、敛因子为了能够平衡全局搜索和局部搜索性能，得到质量更好的种群后代，选取合适的算法参数是关键。shi10等人提出了带有惯性权重的pso算法，通过在速度更新公式中加入惯性权重，极大地提高了算法的收敛性能。在文献10中还提出惯性权重线性递减权值（linearly decreasing weight，简称ldw）策略，随着对解空间的迭代，线性减小，算法在初期进行全局搜索而后期能够进行局部精确的搜索。eberhart11等人提出了一种带收敛因子的pso算法，与加入惯性权重的pso算法相比较，带收敛因子的pso算法在运算中具有更好的收敛速度。（2）对粒子的特征量重新赋值粒子的特征量主要由粒子的位置和速度体

47、现，为了减少pso出现早熟收敛和停滞现象，需要对粒子的特征值重新赋值，使算法可持续更新并维持群体的多样性。xiao-feng xie12提出了自适应pso算法，通过采用一种新粒子替换不活泼粒子使群体保持多样性，在pso中引入自然进化过程中的群体消亡现象，该算法在更新粒子位置和速度后，按预先设置的消亡间隔重新初始化每个粒子的状态，实验表明该方法能改善pso算法的性能，但由于本身的限制，该算法会影响消亡间隔的设置。（3）混合方法将pso与其他优化算法混合，综合利用其他优化算法的优势来弥补pso本身容易陷入局部最优和搜索精度低的不足。katare13等人提出基于pso和levenberg-marqu

48、ardt的混合优化算法，结合pso的全局搜索能力与levenberg-marquardt的局部改良能力，极大提高了pso的搜索精度；后来外国研究者在算法中引入量子行为，放弃用牛顿力学而是利用量子测不准原理来确定粒子的行为14，等等。3.2.3 算法的拓扑结构研究粒子群拓扑结构分为全局版本（）和局部版本（）模型。在全局版本模型中，粒子同时追寻本身的历史最优值（）和群体全局最优值（）在搜索领域中更新速度和位置。如果对粒子速度更新公式稍作变化，让所有粒子更新速度时依据下面两个要素进行：a、粒子本身历史最优值；b、粒子邻域内粒子的最优值。其他不变，这个算法就变成局部版本的粒子群算法。在局部版本中，粒子

49、的邻域随着迭代次数的增加而逐渐变大。实验表明，全局版本的粒子群算法具有收敛速度快的优点，但运算的同时易于落入局部最优。局部版本的粒子群算法则与全局版本相反，其收敛速度慢但却很少落入局部最优。两者各自都具有优缺点，在收敛速度和摆脱局部最优这两方面的考虑要很好地权衡运用。按照取邻域方式的区别，存在着不同的方法来描述局部版本的粒子群算法。第一种方法是对粒子编号，然后根据编号来取粒子的邻域，一般取法主要有：a、环形取法；b、随机环形取法；c、轮形取法；d、随机轮形取法。下图3-3、图3-4、图3-5、图3-6为四种取法的表示。21876534 87634521 图3-3 环形 图3-4 随机环形 图3

50、-5 轮形 图3-6 随机轮形第二种方法是根据粒子之间的距离来取粒子的邻域。在上一种方法中，可以通过编号来获得粒子的邻域，但是这种方法可能存在粒子与粒子间的当前位置并不相邻，为了改良这个方法，suganthan15提出基于空间距离的划分方案，即在搜索进行的初期，将邻域定义为每个粒子本身；随着迭代次数的增加，测算出每一个粒子与群中其余粒子的距离，将邻域范围逐渐延伸到整个种群。该办法经过试验，获得良好的应用效果，但由于需要求得群体中所有粒子之间的距离，运算量大，且需要足够的内存空间，所以这个方法一般不常用。3.3 粒子群优化算法的应用 pso最早运用于人工神经网络的训练方法，由kennedy和eb

51、erhart应用在分类xor问题的神经网络训练。随着对pso的深入研究，发现pso又可以用来确定神经网络的结构。pso在医学上也得到很大的应用，目前发现pso可用于医学图像的配准以及人类的帕金森综合症等疾病的研究和治疗；应用pso技术分别对时变系统和非线性系统进行验证和辨析，仿真结果表明了这两种系统辨识的可行性16。用pso解决实际问题已成为优化行业的热点，由于其具有很好的通用性和有效性，使得其广泛应用在化工、电力、机械设计、交通以及通信等领域。在粒子群研究的领域内，无论是理论还是应用效果都需要再进一步的探讨。3.4 本章小结本章首先详细地介绍了粒子群算法的基本思想和算法流程，同时对该算法的参

52、数、特点以及改进方面作出总结，最后简要介绍了粒子群算法的拓扑结构和应用情况。第4章 粒子群算法在动态交通分配问题的应用4.1 带惯性权重因子的改进算法本文取用全局版本的粒子群算法。为了使粒子在空间寻优时避免陷入局部最优值，得到更好的探测和开发能力，本文中采用了带惯性权重因子的改进粒子群算法。更新方程为：（4-1）（4-2）当惯性权重时，式（4-1）和式（3-1）是相等的，由此表明带惯性权重因子的粒子群算法是基本粒子群算法的发展和延伸。惯性权重较大时，全局搜索能力比较强；较小时，局部搜索能力比较强。通过校准权重的大小，可以使运算跳出局部极小值，达到更好的优化效果。现在应用中经常采用的惯性权重是由

53、shi提出的线性递减权值策略，表示为式（4-3）。（4-3）式中 、惯性权重的最大取值和最小取值；当前迭代数；最大迭代数。4.2 研究算例交通行为中，在选择路线时出行者会倾向于挑选当前阻抗最小的道路行驶，阻抗最小可以用路段距离最小、路段车流量最小或者路段上行驶时间最少等来表示。在本文中采用路段上行驶时间最少为阻抗最小原则，模型采用高自友17于2000年提出的经典模型做算例，并用matlab软件来进行仿真测试。 4.2.1 动态交通分配模型模型的网络结构见图4-1。od图4-1 网络结构图各路径的阻抗函数为：（4-4）（4-5）（4-6）采用的目标函数为：（4-7） s.t. （4-8）此模型为

54、单od对模型，研究时间应为连续的时间范围，但在本文中将时间段0，划分为等时间间距的10个时间段，各时间段流入量如表4-1所示。表4-1 各时间段流入量时段tit1t2t3t4t5t6t7t8t9t10流入量ei183020282325191724234.2.2 动态交通分配求解对上述模型用粒子群算法进行动态分配，粒子群参数设定如下：种群规模为10，限定速度范围为-0.1，0.1，每个时间段的流入量为，参数搜索范围为0，学习因子，惯性权重，最大迭代数，各时段粒子群动态配流结果如表4-2所示。表4-2 各时段粒子群动态配流结果时段路径1路径2路径3分配量存在量阻抗分配量存在量阻抗分配量存在量阻抗t118441.51212121.664221.000t2301719168.04161.0001261.107t3204201.512111.00015161.260t4288239.192651.04214231.198t5234231.512541.02014271.198t6253231.162441.00818381.540t7195232.25381.003383811.7