交通规划

遗传算法在均衡交通分配模型中的应用在城市及区域交通规划中交通分配是一个很重要的环节。交通分配也是在交通规划的诸多问题中被国内外学者研究得最深入、取得研究成果最多的内容。现有的交通分配方法通常划分为非均衡模型和均衡模型两种,划分依据为Wardrop原理。如果交通分配模型满足Wardrop第一、第二原理,则该模型为B-L(Beckmann-Leblanc)均衡分配模型,简称为均衡分配模型；如果分配模型不使用Wardrop原理,则该模型为非均衡模型。就目前国内外的研究形势来看,均衡交通分配理论发展最为迅速。从理论上讲,这类模型较非均衡交通分配模型具有结构严谨、思路明确、结果合理、适用于宏观研究等优点.但这类模型往往由于变量较多、维数太大、约束条件太多而局限了其在交通分配中的应用。经过近几年有关专家学者的研究,人们提出了许多算法来求解均衡分配问题,如增量分配法、凸组合法等。尽管这些算法在一定程度上降低了运算复杂性,然而却不能有效地处理实际应用中大规模复杂的交通网络问题。因此,要将这些方法用于城市及区域交通规划上还有一定的困难。这都迫切需要引入一种新的算法,建立一种计算速度快、易于编程而且更符合实际交通状况的预测模型,以便对路网交通量进行更准确的分配预测。为了提高交通分配预测的准确性,解决均衡交通分配的求解问题，将遗传算法（GA）应用到其中。1遗传算法的一般理论1.1基本概念遗传算法是一种模拟生物在自然环境中遗传和进化过程而形成的一种自适应全局化概率搜索算法,它从任一初始的群体出发,通过随机选择、交叉和变异等遗传算子,使群体一代一代地进行，直到得到空间中最好的区域,直至达到最优点.遗传算法中的术语如下：(1)染色体：算法中的编码串，表示问题的解。(2)基因：编码串中的元素，解的最小构成单位。(3)基因位：基因在染色体中的位置。(4)等位基因：同一基因位可能有的全部基因。(5)基因型：生物个体所特有的基因及其构成形式。(6)表现型：生物个体所表现出来的性状。(7)群体：个体的集合。(9)适应度：适应度表示个体对生存环境的适应程度。将自然界的选择过程应用于工程和数学领域，经过逐渐演化和改进，就产生了遗传算法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的外部表现型。初代种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将使种群像自然进化一样，后生代群体将比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似的最优解。2遗传算法基本流程遗传算法求解问题的过程类似于自然界生物进化的过程，即适者生存、优胜劣汰，其具体步骤如下:步骤1：选择编码方案。步骤2：根据初始解，生成一定规模的初始种群。步骤3：计算个体的适应度，并评价个体适应度值。步骤4：按照选择策略选择出用于产生子代种群的染色体。步骤5：子代个体按一定的交叉进行交叉操作。步骤6：子代个体按一定变异概率进行变异操作，产生新的子代种群。步骤7：判断是否满足最优解的标准，满足则终止，不满足则返回步骤3。3算法详细设计3.1编码设计问题的有效解称为解数据，遗传算法不直接处理解数据，因此必须通过编码将解数据表示成为“染色体”，算法通过复制、交叉、变异等操作染色体进行搜索优化解，然后再通过解码的方式，将最佳的染色体还原为解数据。因此，选择编码方案是遗传算法的首要工作。常见的编码方案有二进制编码、符号编码和浮点数编码等。在交通分配时，最小的信息单元基因被定义为一个分配方案(TO，TransportOperation)。一个TO包含以下内容：出行起点，出行人员类型，目的地，出行车辆类型，出行车辆位置。一条染色体就是一个TO序列。考虑一个有3个出行起点、4个目的地，两类出行人员的情景，则出行的OD表如下表所示：出行OD表一个有效的染色体可以是：可以简写为：生成新的种群时，可根据问题要求对每一个TO内容进行填充。在进行选择、交叉、变异等操作时，直接对TO序列进行操作即可。这样在解码时，根据出行目的地与出行起点对应的距离，即可求出每辆车出行所消耗的时间，整个路网的出行时间即可得知。该编码方案不仅简单方便，而且包含了丰富的数据信息，可以得出最优的分配方案。3.2适应度函数设计适应度函数值定量地反映了每个个体对于整个进化过程的适应能力，它选取的好坏直接影响到是否能够尽快达到最优解。出行方案所用的时间，为所有出行车辆到达目的地所用时间的最大值，设为Tmax，则Tmax越小，对应的个体适应性越强。为了简化计算，可以将Tmax的倒数作为其适应值。则适应度函数可设置为：3.3遗传算子设计（1）存活选择策略遗传算法中选择父代染色体的方法有很多，但是都坚持一个原则，就是适应度高的个体被选择的概率较大。本文采用精英保留法和轮盘赌相结合的选择策略。首先计算出当前种群中适应度最大的个体，直接保留至下一代，剩余的按照轮盘的方式进行选择。它的过程是这样的：将每个个体的适应度值与该种群的总适应度值（也就是种群所有个体的适应度值之和）相比，得到该个体的相对适应度，所有个体的相对适应度之和应为1。把每个个体的相对适应度当作其在选择操作中被选中的概率，每一轮选择会产生一个[0,1]均匀随即数，并将该随机数作为选择指针来确定被选个体，适应度大的个体被选中的概率就大。具体算法设计是：先计算种群总的适应度s,然后从区间[0,s]中随机一个数r，从某个染色体的适应度开始累加直到大于r时，返回当前染色体，即选择该个体。该方法可以保证适应度大的个体被选择的概率大于适应度小的个体。为避免在进化初期，有可能适应度很高的个体，被选择的概率很大，从而复制出很多后代，个体单一而无法继续进化使搜索陷入局部最优解，以及在进化后期，当各个个体的适应度差距不大时，该方法已经不再具有选择能力，体现不出个体的优势，所以在选择父代染色体时，适当保留一些适应度低的个体，可以在一定程度上避免算法陷入局部最优解。（2）交叉算子设计遗传算法的交叉概率的大小直接影响算法的收敛性,交叉概率越大,新个体产生的速度就越快。然而交叉概率过大遗传模式被破坏的可能性也越大,使得具有高适应度的个体结构很快就会被破坏。但是如果交叉概率过小,会使搜索的过程缓慢，以至停滞不前。而且,优秀的个体与较差的个体都具有相同的交叉概率,不利于优秀基因的保留和差的基因的淘汰。对此，本文采取了自适应交叉概率的方法，个体交叉概率计算公式如下：式中，'f表示当前个体适应度，maxf表示当前群体最大适应度，Pc表示交叉概率初始值，'Pc表示当前个体交叉概率。采用自适应的交叉概率,不同的个体用不同的交叉概率,对于适应度值高的个体,对应于较低的交叉概率,使它得以保护进入下一代;而适应度低的个体,给予较高的交叉概率,使之被淘汰。（3）变异算子设计变异在前期可以扩大算法的搜索空间，不至于落入局域的最优解，后期变异可以寻找隐藏的优秀基因，但是变异率过高会导致算法波动性较大。同交叉概率设置方法一样，本文变异概率的设置也采用自适应变异概率的方法。个体变异概率计算公式如下：式中，'f表示当前个体适应度，maxf表示当前群体最大适应度，Pi表示变异概率初始值，'Pi表示当前个体变异概率。采用自适应的变异概率,不同的个体采用不同的变异概率。在进化初期，各个体适应度差异较大，适应度低的个体有较高的变异率，以加快算法搜索效率。在进化后期，各个体适应度大小相差不大，这时变异概率较低，可以保持算法的稳定性。3.4检测机制应该注意的是，交叉和变异操作后可能会出现不满足约束条件(2)的情况，此时的染色体称为非有效染色体，所生成的方案也是无效的方案。因此，本算法中加入了染色体的有效性检测机制，每当产生新的染色体时，都会检查该染色体是否符合约束条件(2)。当出现非有效染色体时，解决方法有两种，第一种是在其适应度函数加上一个惩罚函数M(x)，来极大程度地降低其适应度，以便在后面进化中逐渐淘汰。这样做的好处是符合遗传算法的优胜劣汰的思想，也会保留一些父代的优秀基因段，但是缺点是会增加运算代数，降低运算效率。第二方法是直接修改非有效染色体。这样可能会改变父代的优秀基因，也可以看成是一种特殊的变异。在编码长度较大的情况下，该方法的运算效率优势很明显。因此本文选择第二种解决办法来处理非有效染色体的问题。3.5参数设置遗传算法中一共有四个重要的设置参数，即种群数、进化代数、变异概率和交叉概率。经研究证实，一般情况下种群数与编码长度大小相当即可，因此种群数的设置往往与具体问题的编码长度有关。进化代数越多，结果就越接近最佳结果。但是当算法执行到一定程度时，结果就基本稳定，变化很小。因此进化代数的设置可以是指定具体数目，也可以指定两代之间的一个阈值，当结果变化小于该阈值后，即可认为是达到了终止条件。交叉概率的推荐设置范围[0.25，1.0]，变异概率的经验值范围[0.005，0.1]。变异率的设置对进化结果影响较大，可以在实际应用中通过实验比较确定。4结语本文将遗传算法应用于用户最优的均衡交通分配模型的求解中,,建立了行之有效的算法。首先介绍了遗传算法的相关术语和一般过程，然后对算法进行了详细的设计，包括编码方案的设计、适应度函数的设计以及遗传算子的设计等，最后设计了一种复合式编码方案，从而适应交通分配问题中的变量多，维数大，约束条件多等特点。可以用于解决交通规划中交通分配的问题。