基于遗传算法的动态交通分配问题研究毕业设计Word文档下载推荐.docx
《基于遗传算法的动态交通分配问题研究毕业设计Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《基于遗传算法的动态交通分配问题研究毕业设计Word文档下载推荐.docx（35页珍藏版）》请在冰点文库上搜索。
经过多年的实践，改扩或新建道路是能暂时解决城市路网系统的交通问题，但并不能从根本上解决问题。
我国地少人多，在城市化进程中，土地资源越来越稀少，只有大力发展我国在交通规划领域的研究，充分利用现有交通资源，才能最大限度地解决目前的交通问题。
科学的规划和管理，如改进交叉口信号控制，动态地调整交叉口信号时间，可以有效舒缓交通堵塞。
据了解，北京，广州等一线城市都已建立了交通控制试点，可以监控城市路网系统的实时交通状况，对路段状况进行实时反应和实时处理，提高了城市路网系统的服务质量。
城市道路网络优化和动态交通分配算法的研究，不仅可以用数学模型优化交通系统的规划和管理，也可以从交通预测时间的角度为诱导提供理论支持。
因此，城市动态交通分配模型能极大地影响智能交通系统的建设，提供更多的理论和应用方面的技术支持。
1.3交通流分配的研究现状
交通流分配是指把已知交通流量的起讫点按照不同的要求有效地分配到路网系统中,并求出各条道路的交通量。
交通流分配是城市路网系统规划的重要组成部分。
我国关于交通流分配的研究工作从上世纪80年代开始，经过20余年的发展，动态其研究已经成形并日趋成熟。
我国关于动态交通流分配的研究与国外的相比，在理论，方法和实际应用等方面都较滞后，国内外都是注重理论方面的研究。
动态交通流分配研究在实际应用中还有待探索开发，目前并没有很好地把理论应用于实际建设当中，相关的研究工作仍然处于发展阶段。
虽然我国关于动态交通流分配的研究工作较晚才开展，但发展比较迅速。
我国的交通政策、结构、环境、运行特性等都有自己的特点，特别需要注意的是，我国现有的交通设施与发达国家相比是比较落后，对于国外的先进理念、管理技术我们不能生搬硬套，要结合我国实际情况稳步发展智能交通方面的技术,除了尽快完善交通硬件的建设，还应该多应用先进的技术来建设，以求尽快提高我国智能交通管理方面的水平和效率。
我国关于动态交通流的研究才刚刚起步，应该投入更多的资源，在理论和应用方面做更多的探索。
1.4本文主要内容
本论文主要围绕交通流分配问题展开。
全文共分四章，其主要内容和章节如下：
第1章绪论。
本章说明了课题的背景、研究目的和意义，最后详细说明了当前国内外关于城市交通流分配的研究工作。
第2章遗传算法概述。
本章主要介绍遗传算法，从其模型，分类进行介绍
第3章交通流分配模型。
本章对交通流分配进行了综述，描述了交通流分配模型。
第4章用遗传算法进行交通配流。
介绍了算法步骤，参数设置以及仿真结果。
第2章遗传算法理论及方法
2.1基本概念
1975年，美国密歇根大学的Holland教授首先提出了遗传算法的概念。
遗传算法是一种基于自然选择和进化论的发展，随机自适应搜索算法。
其主要特点是直接对结构对象进行操作，没有限制的推导和函数的连续性，并具有内在的并行性和良好的全局搜索能力，可以自动获取和指导优化搜索空间，没有明确的规定。
由于遗传算法具有的性质，它已被人们广泛应用。
遗传算法主要借鉴了一些诸如选择、交叉、变异等物种进化过程中所出现的特征。
遗传算法首先要对种群中的所有个体做初始化处理，把所有待优化问题的参数编码成若干个二进制位串，再把这些二进制位串组成待优化问题候选解的初始种群。
每个个体可以看作是与实体特征不相同的染色体，每个个体根据适应度函数再生个体适应度的第一代，交叉和变异产生比迭代操作的父母的后代，基因重组和突变的后代必须按照一定的规律；
但如果后代不能满足优化准则，那么下一代种群继续迭代计算，直到你找到最优解或执行迭代的最大数量。
遗传算法在许多领域中都有成功的应用，由于其具有多项优点，各国研究者一直在探索如何更好地应用其于更多领域的实际问题的解决中。
2.2遗传算法的特点
遗传算法借鉴了进化论的相关理论，它的特点如下：
（a）自适应、自组织和智能性。
对于要解决的问题，算法本身不用提前针对它的特点进行设计；
不但能够帮助解决复杂的大型化的非结构化问题，而且针对不同问题，算法本身都有不同的处理方法。
（b）直接对对象的参数编码集进行处理。
（c）整个算法的搜索只依赖于对目标函数的评价，在算法实行搜索的时候，无论即将优化的函数是否可微，或者函数本身连续性与否都不会对整个搜索过程造成影响。
（d）基本的想法比较简单，运作模式还有整个算法操作起来比较方便，节省时间。
2.3遗传算法的理论研究
2.3.1编码表示
在我们要运用遗传算法去解决问题时，我们首先想要解决的第一个问题，同时也是对遗传算法最终性能影响比较大的一个问题，那就是如何编码。
作为在遗传算法中使用最多的一种编码——二进制编码，它本身有着不少好处。
第一，它在遗传算法的分叉和变异操作上比较容易实现；
其二，使用该编码时，我们对于算法的理论分析可以采用模式定理去做；
最后，二进制编码作为我们最熟悉、最基本的编码，操作起来比较简便，减少我们的工作量和时间。
当然对于二进制编码，我们也应该看到它的不足之处，对于处理高精度且多维的数值优化问题上，它要占用的内存比较大，能达到的精度也不能令人满意，并且对于固有的结构性问题，它并无法直接反映，对于误差的处理能力也不足。
2.3.2适应度函数
在遗传算法的使用过程中，个体的选择是由它的适应度好坏来确定的，因为个体体能的一个重要的表现方面就是适应度。
在我们处理有约束条件的优化问题的时候，重中之重就是找到合适的适应度函数，它来源于基于罚函数法建立的目标函数以及约束条件。
要把目标函数转变成适应度函数，我们需要注意两点：
①最后转换结果要为非负，②两个函数的变化方向要保持一致[2]。
适应度函数对于遗传算法的影响较大，具体体现在收敛性以及收敛速度这两个方面。
对于要解决的不同问题，我们要结合好相应的参数区调整，找到最优的适应度函数。
2.3.3遗传算子
遗传算子是用来保持内部的多样性的遗传算法的重要部分，在我们要遗传的群体成员中，其基因的突变性很大程度受到算子的影响。
（a）选择算子，它体现的是自然界中的“适者生存，不适者淘汰”的原则，根据适应度进行优存劣汰。
常用的选择操作主要有：
轮盘赌选择、排序选择。
（b）交叉算子，它作为一个产生新个体的主要方法。
形成的方式DNA相互是交换部分基因，造就新的基因，最后造出新的个体。
常用的交叉算子主要有：
均匀交叉、算术交叉、单点交叉和两点交叉。
（c）变异算子。
基因突变是指基因在染色体上的一些基因编码一个人代替另一等位基因的位点值，产生一个新的个体。
遗传算法的搜索能力来自于变异的新个体，变异量的多少决定搜索能力的大小。
在遗传算法搜索工程中，各类算子都有自己的任务，选择算子对数据进行优化，交叉算子决定全局搜索，变异算子决定局部搜索，最终完成算法的搜索功能。
在应用遗传算法解决问题时，变异算子是不可缺少的，它决定了遗传算法的局部搜索，影响了算法的全局搜索。
主要的变异操作有:
（1）基本位变异。
（2）均匀变异。
（3）二次变异。
参与其中的两个染色体的变异操作，在每个基因分别对应值的两个新的个体形成与原来的染色体基因或/异或。
2.3.4参数选择
遗传算法参数包括群体规模，收敛准则，交叉概率和变异概率这四个。
遗传算法的系统性能会受到以上四个参数影响，参数是否准确，是否可靠，需要的时间长短等等因素都有关联。
一般我们在做遗传算法的研究时，是用经验来估计参数的，这种行为会影响遗传算法的最优性等系统性能。
事实上，参数的选择应该是变化着的，这种变化跟随着适应度函数的变化，也就是遗传本身的变化。
自适应算子的概率方法作为反映这种变化的方法，能有效地应用与遗传算法的研究中。
（1）种群规模
种群多样性、模式生成、计算量都会受到种群规模的影响。
种群的过大过小都会造成各种各样的影响。
当规模太小时，我们得不到足够的先天基因，从而无法造就竞争能力强的高阶模式。
为了拥有多样性我们也要足够的种群规模，但是不能够超出计算量的范围。
种群规模过大时，遗传算法的计算量会增大，这样一来又会降低收敛速度。
所以我们必须通过不断的实验区寻找最优的种群数量。
根据以往的经验，我们得到的规模大小一般在[20,160]这个范围内，至于具体的数值就要靠我们不断的实验缩小。
（2）交叉率和变异率
交叉率和变异率分别决定了交叉算子的使用频率和种群的多样性。
交叉率可以提高模式的生存和重组的概率，它的常用经验值是0.25。
变异率决定种群中新加入的新基因量的多少，它常用的范围在[0.005,0.1]之间。
以上两种因素的不断变大，会致使误差转向单调下降，但是这个下降并不明显，同时算法的收敛时间也会跟着变大。
这就造成进化过程中的代数变化规律变得较为的复杂。
交叉率的变化影响交叉算子的使用，进而影响种群模式，这种影响有好有坏，它的值越大时，种群产生新模式的机会会等多，但是当它过大时，种群原有的模式也会存在被破坏的风险。
它的值过小时又会令算法造成搜索阻滞，使得算法发本身的搜索速度降低。
变异率表明一个种群变异程度，变异率越高，越能提高种群的多样性，反之则降低种群的多样性。
变异率的大小并不是随意设定，过大、多小都不好。
过大的情况会使得遗传算法的搜索方式发生改变，由原来的定向搜索，变成随机方向去搜索；
过小的情况会导致算法陷入局部最小值，无法寻找全局最优。
交叉率与变异率这两个变化在整个遗传算法中是相互交错，相互影响的而且两者之间同样会发生相互牵制的情况。
因此怎样去确定这两个变化的值，至关重要，合理的值能够使我们的遗传算法发挥最好的效果达到我们分配动态交通流的目的。
目前，解决并找到变异率和交叉率最优值的方法是设计一些合理的具有科学性质的策略，让这些策略在遗传算法的进化中可以有效的动态自适应地调整这两个值的变化[10]。
2.4遗传算法的应用
遗传算法有很多优点，它能为我们提供一个通用性的框架，使用这个框架我们可以很好的解决一些复杂的优化问题，也正是因为此，它被广泛应用在各个科学领域。
2.4.1函数优化
遗传算法常应用于函数优化，对此，研究者经常使用函数优化逆推来这种形式研究它性能好坏。
在我们平时使用的函数中，凸函数和凹函数，离散函数，低维、高维函数，连续函数等函数在评价遗传算法的时候，都能得到很客观、很全面的结果。
在其他一些复杂的函数中，比如函数的非线性的、多目标的，函数还可能是多模型组合的，这类函数的优化问题比较困难，但是运用遗传算法却能得到很好的结果[4]。
2.4.2自动控制
遗传算法目前已经证明了它的使用价值，它能为我们解决多类型问题，创造更多的经济利益。
就目前而言，它在自动控制领域中的应用是最广泛的。
比如，自控系统的模型建设、航空航天的控制系统优化、机器人自动控制系统的优化、数控机床工作方式优化等。
2.5本章小结
本章介绍了遗传算法的基本概念、执行过程，对遗传算法的研究以及应用做了详细说明。
第3章交通流分配模型
3.1交通流分配综述
3.1.1交通流分配
交通流分配作为城市智能交通系统建设中的主要部分，在很大程度上影响着整个路网系统的建设。
交通流分配是指将测量出流量的的OD交通流根据实际城市路网建设要求，为实现系统有效率运行，按照实际情况分配在各条道路上，然后计算出各条路段的交通流量以及所产生的出行费用，最后得出的结果可以用来分析和评价该城市交通系统的运行效率。
交通需求每天都在变化，城市路网系统中的交通流每时每刻也在变化，这就是所谓的动态性。
3.1.2动态交通流分配
动态交通流分配是指在已知交通供给和交通需求的情况下，分析出最适合实际应用的交通分布模式，重新合理规划出行者的需求，使得城市路网系统能够效率地运行。
动态交通分配的特点有主要有：
（a）动态交通流分配可以对在时间、空间上都具有非定长特性的交通流作出描述。
（b）路网系统中的交通流可以用交通量守恒准则和连续平衡方程来阐述。
（c）动态交通分配可以同时应用于自由流和拥挤流这两种交通状态。
从上世纪中期开始，国内外的学者对动态交通流分配的研究一直从未停止。
在国外研究发展较优的情况下，我国的研究人员对这一领域一直保持热忱，多年来有许多学者致力于动态交通流分配的研究上。
随着各种理论及模型的建立，如何更好地将动态交通流分配的相关理论应用于实际建设中，是未来动态交通流分配发展的重要研究方向。
3.1.3平衡分配与非平衡分配
1952年著名学者Wardrop平衡定义的第一原理和第二原理，奠定了交通流分配的基础。
Wardrop提出的第一原理是指在道路的利用者都确切知道网络的交通状态时，自主走行于最短径路，城市路网系统将达到平衡状态。
在考虑拥挤对出行时间的影响，当网络达到平衡状态时，每个OD路径中被使用的径路行驶时间最短；
没有被使用的径路的出行时间较前者大。
在交通流的实际分布中，第一个原则也被称为用户均衡或用户最优。
Wardrop提出的第二原理：
在平衡系统的条件，在拥挤的道路网络交通流应按照平均或出行总成本最小作为分配的依据。
在交通流的实际分布中，原则二也称为系统最优原理。
完全满足Wardrop平衡原则的定义的，称为平衡分配方法，分配模型是启发式方法或其他近似方法的，称为非平衡分配方法。
非平衡分布的常用方法是：
变化路阻和固定路阻，单径路和多径路等非平衡分配方法。
非平衡分配方法主要有以下方法：
（a）全有全无分配方法。
（b）增量分配法。
（c）增量加载分配方法
（d）迭代平衡分配
（e）迭代平均法
满足第二原理的交通网络流状态成为系统最优，在这种状态下，交通网络资源得到最优利用，交通网络效益得到最大限度的发挥[7]。
3.1.4最优配流问题讨论
静态交通分配模型是以路网系统规划为目标的模型，因为不考虑时间的变化，所以称为“静态”；
动态交通分配模型是以城市路网中的交通流为对象，需要充分考虑时间的影响，合理配置出行者的需求。
关于城市路网动态交通流分配模型的研究，从分配过程中路径选择的角度，可以分为动态系统最优模型和动态用户最优模型。
简单来说，动态系统最优模型是为路网系统服务的，动态系统最优模型是要求在一定时间段内，按照路网系统管理者的管理思想，将动态的交通需求分配到路网系统的各个路段，该模型是为了实现对整个路网系统的交通管理和控制而设定的，它的期望作用使能是减少系统总体出行时间、减少系统总体延误时间和降低城市路网管理系统的管理费用。
而动态用户最优模型的直接对象是出行者，在一定时间段内，把用户的交通需求按照用户的出行意愿分配到路网系统中的各个路段。
动态用户最优模型可以对用户路径选择进行分析，再现交通流的实时分布状态，由于其比动态系统最优模型更接近城市路网系统的实际运行，交通规划部门常用动态用户最优模型对交通决策进行分析和评价。
动态用户最优模型的种类较多，主要有：
反应型用户最优、预测型用户最优、理想动态用户最优和瞬时动态用户最优等模型。
3.2交通分配模型的分类
在动态交通流分配模型中，首先需要正确掌握每时每刻的出行需求，在已知交通供给和交通需求的条件下，动态交通流分配模型可以为交通管理、诱导等提供依据。
从不同角度出发，动态交通分配模型主要有：
（1）根据描述交通流方法的不同，可将动态交通分配模型分为仿真模型和分析模型。
仿真模型，城市路网系统中的动态交通流过程是应用仿真软件进行交通流分布重现的，它的出行费用、出行时间等是应用计算机模拟得出的。
基于分析的仿真模型通过几何函数来描述城市路网系统的动态特性。
仿真模型是从分析、模拟出行者的出行选择行为出发，由于是应用仿真网络进行模拟，该模型不需要求出城市路网中各个路段的具体函数，也不需要辨识模型的参数。
但是由于仿真模型分析能力较差，精度和灵敏度不高，目前是比较适用于工程应用领域。
分析模型，与仿真模型相比，它的结构严谨、逻辑较严密。
但目前情况来看，分析模型没有系统的、有效的算法，无法精确描述城市路网中动态交通流的动态特性，而且在建立模型是需要附加过多的理解化条件，它并不适合应用于实际，目前是处于学术讨论的阶段。
（2）根据描述模型的数学手段的不同，可将动态交通分配模型分为数学规划模型和变分不等式模型。
数学规划模型，是静态交通分配向动态交通分配转化的过渡模型，现阶段的智能交通发展已经大大超过该模型的理论研究，而且它只适用于单讫点网络，现在已经很少应用。
变分不等式模型，这种基于线路的模型，是比较适用于小型网络的模型，由于实际中路线与路段流之间是多对一的关系，变分不等式模型难以应用于实践建设中。
（3）根据模型是否满足均衡原理，动态交通分配模型分为均衡模型和非均衡模型。
3.3本章小结
本章首先介绍了交通流理论，对交通流特性进行了分析；
然后介绍了动态交通分配模型的研究，对各种模型进行了概述。
第4章基于遗传算法的交通配流
4.1算例
路网结构如图4-1所示。
图4-1路网结构图
该模型共有8个路段，3个OD对，分别是1～5、1～3和4～3。
各OD对之间的流量依次为18、12和8。
路段阻抗函数采用如式4-1所示：
（4-1）
其中，xa表示t时刻路段a上流向终点的交通流量;
ta表示路段的路段a的阻抗;
c表示路段走行时间。
路段阻抗函数系数表如表4-2所示。
表4-2路段阻抗函数系数表
路段a
1
2
3
4
5
6
7
8
15
10
4.2模型建立
本文用有向图G（N,A）表示一个交通网络,N是网络节点集,A为有向弧集,即路段集。
节点集N包括3个子集:
起点集、终点集和中间节点集,这3个子集是相交的,因为有些节点可能同时是起点、终点或中间点。
本文用k表示起点或中间点,n表示终点。
A（k）表示有向路段起点是k的路段集合,B（k）则表示有向路段终点是k的路段集合。
在连续时间的动态交通分配模型中,用
表示t时刻节点k产生的流向终点n的出行率,本文假设其是已知确定的。
表示路段a上t时刻流向终点n的路段流入率,而
是流出率。
为简单起见,考虑一个固定时段[0,T]的最优控制问题。
以
表示t时刻路段a上存在的车辆数,即交通负荷,而
则表示t时刻路段a上流向终点n的交通负荷。
设上述路段走行时间函数
设
为t时刻进入路段a,流向终点n的累积车辆数,而
则表示t时刻流出路段a,流向终点n的累积车辆数。
综上所述,本文给出的动态系统最优分配模型为:
（4-2）
约束条件为：
（4-3）
定义约束：
（4-4）
路网的数学规划模型如下，其中x1～x8表示8个路段的交通量。
（4-5）
4.3应用遗传算法配流
4.3.1算法步骤
（1）参数的确定及编码
首先确定参数的范围，然后选择编码方式。
把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。
为了减少组合数量，在图像中进行分块，然后再把每一块看成一个基因进行组合优化的计算。
每个解的基因数量是要通过实验确定的。
（2）随机产生初始种群，种群的个体数目一定。
随机产生N1个初始串结构数据，每个串结构数据称为一个个体，构成基本可行解，记为B1。
同时计算出B1相对应的运行指标值，记为集合J1。
（3）复制，定义适应度函数。
（4-6）
0≤fi≤1,以fi为概率,从Ji中复制出N1个可行解行解，记为B2，与B1相比，复制后的可行解集合中具有较小目标值的可行解较多，与B2对应的运行指标值集合记为J2。
（4）交叉
对B2进行随机排序,相邻的2组可行解按随机选定的位置交换部分元素,形成新的可行解集B3。
并采用与
（1）中相同的公式计算运行指标值,记为集合J3。
在B2与B3中取N1组可行解构成解集B4,使其具有较小的运行指标值,记为J4。
（5）变异。
为了加快进化速度,本文不仅提高了交叉概率P,而且设计了快速变异方法。
对B4中的任一组可行解:
（1）随机选择其中一个元素,按预先设定的步长Pd分别进行增加和减少运算,形成2个新的可行解,按1）中相同的公式计算其运行指标值;
（2）在2个新的运行指标值和变异前的运行指标值中取较小者,用其对应的可行解更新本次变异前的可行解,并将其作为下步变异的对象;
（3）对
（2）中得到的可行解,再随机选择其它位置的元素进行相同的变异与更
升级会员 