英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
计算机辅助土木与基础设施工程 15（2000）261-271
基于遗传算法和地理信息系统的高速公路初步设计
摘要：本文提出了一种将地理信息系统与遗传算法相结合的方法，以优化两端点之间的水平高速公路，也可以用来校准高度不规则的地理空间。结果比对光滑并且满足最小半径限制,符合高速公路的设计标准。所提模型中的目标函数充分考虑了土地征用成本、环境因素如湿地和泛滥平原、相关成本(排列长度成正比)和用户成本。在现实地图上的一个例子证明该模型能够应用于平面线形的初步设计。
1引言
在传统的公路设计过程中，工程师通常会根据地形图确定几个备选的通道，然后具体到详细的线形设计。如果没有数字模型和地理信息系统，这个过程将是非常复杂并且耗时的，工程师不得不尝试各种线形组合，论证分析每种线形的优劣。正由于公路设计是一个潜藏众多可能性的复杂工程问题，所以仅仅依靠手动设计，将很难达到最优解。
数学模型在公路中的应用将大大加快设计过程并产生一个更优的解决方案。过去三十多年来，已开发了三种适用于线形设计的模型，分别是变分法，网络优化和动态规划。三种方法的优缺点详细讨论见参考文献[6]。变分法可以生成一个平滑的曲线，但需要一个连续的可微函数，对于不同的土地形式和地理特征例如河流湖泊，这种函数可能是不存在的。网络优化法可解决最短路径问题，可修改运输问题，以及具备成熟的方案算法，但由此产生的路线不光滑。动态规划可能比网络优化需要更少的计算机内存，但同样不能产生平滑的曲线。这两种方法约束最小半径方面都存在明显不足，而且，它们的解决方案是基于空间搜索，因此可能会完全错过最优解决方案。
除了以上缺点，预处理的成本函数和链路成本也要应用于这三种方法，这是相当困难的，尤其对变分法而言。此外，这些模型都没有明确考虑用户成本。根据经济合作与发展组织，三十多年来，车辆运营成本贴现范围在百分之三百至百分之一千不等。旅行时间成本通常高于车辆运行成本，而这些模型全都忽略了用户成本，可能会导致非常差的结果。
为了优化公路线形，模型应该直接开发GIS数据库，以便较容易的在计算机上获取大部分的地理信息，例如土地的实际形状和土地利用模式。本文旨在建立这样一个模型，利用地理信息系统优化平面线形，使之满足AASHTO规定的最小半径。除了征地、环境影响、施工成本，该模型还考虑了用户的使用成本，包括车辆的运行，出行时间成本，与事故成本。由于模型复杂，缺乏可微性和凸性属性，可能需要搜索大量的局部最优解，具备八个特定问题的遗传算法正是用来解决这个问题。
2表征比对
以，为使用路线的起终点，表示连接Ｓ和Ｅ的直线。Jong证明沿着SE的任何一条垂直于SE直线Ｌ，将相交于所选的平面曲线，如果最优线形没有回溯（即线形更面向终点而不是起点），直线L将相交于一点，我们则称直线为垂直切割线。基于这个“切割”概念定义变量以确定平面线形。假设我们将SE分割成相等的连续n份，如图一所示。这些垂直分割线将与平面线形有n个交点，我们定义这些点为线形交叉点，在线形优化过程中直接搜索，而不是直接寻找交叉点的XY坐标。我们简单的定义沿着垂直分隔线的决策变量为坐标，以减少需要优化的变量数量。
因为方向不明，每一个垂直分割线的坐标系并没有完全定义，大部分情况下，我们定义向上方向为正方向，向下方向为负方向。唯一例外的是当垂直分割线与X轴正交的时候，此时定义向右为正方向，向左为负方向。
对于每一个垂直分隔线，规定原点为分隔线与线段SE的交点，令为任意一条分割线的原点，i=1,hellip;,n,则对任意坐标系，点（）满足下列公式:
= (1)
为坐标系与第i条分隔线的交点，我们需要确定的上限和下限值，因为这个值是优化模型的约束条件。假设目标区域是一个在坐标系下从到的连续矩形，根据分隔线的角度有四种方法确定的边界值。令theta;表示分隔线与X坐标轴的夹角，theta;值从0°到180°之间，有下式计算theta;值
Theta; = () 90° (2)
在大部分的计算机语言中，一般还从-90°变化到90°，故theta;值是从0°变化到180°。同时我们命名和分别为的上限和下限值。那么和可由下列公式确定：
1.当theta;=0°或theta;=180°时，
=
= (3a)
2.当0°﹤theta;﹤90°时，
=
= (3b)
3.当theta;=90°时，
=
= (3c)
4.当90°﹤theta;﹤180°时，
=
= (3d)
校准线形的重要变量和相关的边界已经定义完成，以及在不同坐标系下的一系列的值。为了一致性,我们必须将其转换为XY坐标系。在第i条分隔线上，由决定的交点令为,则的坐标值（,）由下式计算：
= (4)
平面线形即是由一系列的组成，用直线连接每一个连续的交点即形成一段平面线形,使圆曲线与直线相切，起点为切点，Jong在其著作中提出了利用迭代计算机算法操作该程序。为使线形对于任何值都是连续的，对于转角较大的交点，半径可以比AASHTO规定的最小值略小。此种这种情况下，在评估过程中线形必须要经过不断地修正以满足要求。注意由计算机算法生成，只包括切线段和圆曲线的平面线形，尽管缺少缓和曲线但仍是光滑的，并且足以应用于高速公路的初步设计分析。
平面线形的几何特征，例如转角、切点、曲率点、圆点对于线形都是极重要的因素且在后来成本调整中发挥主要作用。在处的转角值取决于，计算如下式（见图2所示）：
= (5)
图2 圆曲线的几何要素
令,分别为转角处的两个切点，则坐标（，）, （，）计算如下：
= = (6)
= = (7)
为与相关的半径值，圆曲线的圆心为（，）计算方法有多种，最简单的是向量法，令（，）为线段的中点，如图3所示，可知同样位于连线上，故延长-向量可以计算圆心的坐标如下：
= = = (8)
= = (9)
图3 、、以及之间的几何关系
3 成本函数
与高速公路相关的成本项目众多，对于数学规划而言，最好将这些项目按照几何特征的相关程度分门别类，以便在优化线形中较为直观的阐述各自作用。Jong and Schonfeld将高速公路成本划分为地理变量、长度变量、行车里程数以及用户成本。接下来分别阐述每种成本的作用。
3.1 地理成本
一个地理区域通常包含私人土地、湿地、河漫滩等，不同于网络优化和动态编程模型上仅由节点和网格组成，真实的地理图形其实是极其不规则的。在计算地理成本时为了与真实地图相一致，往往将现有的地理信息系统应用于目标模型中。最小的土地单位来源于地理信息系统中的私人土地、湿地、河漫滩，每个最小地块关联一项地理成本设计。除了通行成本，地理成本还应考虑环境因素。例如，如果一个地块是一片湿地或冲积平原，则这块是禁止规划线形的，这块土地的地理成本设定值就相当高，因此对于任何经过该区域的参考线形，地理成本值都是难以接受的。
高速公路的地理总成本计算依赖于各部分的地理成本之和，假设一段高速公路经过m个地块，令是第j个地块的单位地理成本值，则总的地理成本为：
(10)
其中是在该地块内公路线形所占的土地面积，上述计算方法并不容易，因为公路的占地面积不易确定。Jong发展了一种计算机算法操作该步骤，但仅限于规则的正方形区域。，幸运的是，这个过程现在可以用GIS软件完成，对于任意给定的线形，我们可以利用该软件创建一个缓冲区代表公路，再将公路边界覆盖在地块上。将公路边界和地块减去，剩下的就是公路占地面积，再应用上述公式计算即可。
3.2长度成本
计算公路的长度成本，只需用总长度乘以单位长度成本，由目标模型生成的任意平面线形都是由切直线和圆曲线组成的，其中和是由一段切直线相连接，而和是由半径为的圆曲线连接。为标记方便，我们令=S，=E，则总长度计算如下：
(11)
单位长度成本可能包括单位工程成本、单位维护成本、单位环境成本，将单位长度的建筑成本分为多种具体的项目，如挡土墙、护栏、桥梁、路面成本，且每项对计算结果都是必要的。其中桥梁成本取决于多种因素，如桥梁的长度、桥型，而这些因素又与土壤类型、周围土地利用率、地形等地理特征相关。尽管桥梁成本不包含在长度成本中，但是如果存在一个具体的地理数据库，就另当别论了。如果交通量是已知的（在规划阶段可以计算），则空气、噪音污染这些与里程数相关的环境因素将进一步转换为长度成本。令AADT（年平均日交通量）为设计的双向交通量值，我们假定年平均增长率为，使用年限为，则单位长度上的环境成本为：
(12)
其中 = 环境影响下的单位长度成本的净现值
= 单位里程的环境成本
= 假定成长率（保留一位小数）
在上述公式中，单位环境成本由不同环境因素叠加而得，如空气污染、噪声污染、水污染、石油开采和分布、土地使用率、化学废弃物处理等。上式计算过程有些麻烦，混合交通增长形式下的计算方法如下：
(13)
则综合单位长度成本为：
(14)
其中 = 总单位长度成本， = 单位长度的建筑成本， = 单位长度的维护成本
最后总的长度成本为：
= (15)
3.3用户成本
用户成本主要包括车辆运营成本、行车时间成本。用户成本不能直接计算，因为它与公路的平面线形关系不明确，一般来说它们之间的关系由统计分析而得。AASHTO提供了一些数据和表格来估算高速公路以及道路运输改进方面的用户成本。该方法已被广泛应用于各种研究和预估用户成本的主要参考依据，但是由于这些数据和网格繁琐的电子化，Jong和Schonfeld随即又推导出代数函数方程计算用户成本，基于曲率、梯度、长度等平面几何下，他们首先开始预估平均速度下的不同时段（高峰和非高峰），不同交通方向（主流和非主流）下的用户成本。平均运行速度可进一步用于估计不同的车辆类型如，中型车、两轴单一机组卡车和3-S2柴油卡车的耗油率和旅行时间成本等。而估算交通事故成本则包括平面几何因素和交通条件，当然，对于那些不满足最小半径的线形，基于违约大小的违约成本也要计入事故成本中。
4求解算法
该模型的决策变量是沿着垂直分割线的坐标，目标函数是各种成本的总和，因此最终的模型计算是这样的：
对于所有最小值有 (16)
并满足 (17)
其中是用户成本，包括燃料耗值、时间成本和事故成本，由于线形是由目标模型在迭代算法基础上生成的，则上述方程不能直接表示为以作为变量的函数。因此，主要问题就是缺乏凸性和可微性，而这在众多研究方法例如牛顿或最陡下降法都是必不可少的。
遗传算法正是用来解决该模型的，它产生于自然定律“自然选择，适者生存”，遗传算法正是用来解决该模型的，它产生于自然定律“自然选择，适者生存”，他们从一些可能的解决方法入手，俗称“原始群体”。群体中的每一个个体被编译成为一个字符称为染色体，在每一代中根据健康状态选择生存的后代（在我们的模型中，健康状况被定义为相应的价值成本），经过几代之后，最适宜的后代生存下来，而差劲的将被淘汰，群体则逐渐收敛于最优解。遗传算法的效能不仅取决于自然选择同时也取决于指定的遗传过程。为了符号的便利，我们用表示染色体，用标记基因所在的位置，由于遗传算法涉及概率性和随机数，故常用来表示连续均匀分布函数在区间上的的一个随机数，其中L和U分别表示上限和下限。同样，表示离散均匀分布函数在相同区间上的一个随机数。
4.1遗传编码
以浮点编码取代二进制方案对遗传算法更有利，染色体将更易被定义为因变量，且每一个在区间内都是连续实数。
(18)
在上述方程中，取值于区间，其中、分别为区间的上限和下限，边界在生成原始群体和发展遗传算子中有着重要作用。
4.2原始群体
为了全面的搜索遗传空间，随机生成原始群体，基因库应尽可能的完整。但是，在优化公路线形中，代表直线的染色体应该囊括在原始群体中，因为线形受制于最小长度和用户成本的要求中。如果一个工程师有更好的想法和解决方案，也应该被纳入原始群体中。不失一般性的前提下，我们假设没有任何经验可以借鉴，则原始群体概括如下：
1.交点位于连接起终点的直线上。则交点的集合就组成了一个直线线形，这也许不是一个好的解决方案，但是这其中可能包含一些有用信息。事实上，除地理成本之外，使用更多的直线和减少线形都将显著削减其他的任何成本。试想在这种情况下，交点精确的位于垂直分隔线的起始位置。则染色体为：
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[150125]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
