《路线优化技术》PPT课件.ppt

路线优化技术长安大学公路学院杨宏志内容n n路线优化问题的提出n n问题的定义与描述n n遗传算法与工程优化n n路线平面优化n n路线纵断面优化路线优化问题的提出n n选线设计实际上是一个在满足一定约束条件下，逐步缩小路线可行区选线设计实际上是一个在满足一定约束条件下，逐步缩小路线可行区域并逐步提高设计精度的过程。现有的技术手段难以直接在空间找出域并逐步提高设计精度的过程。现有的技术手段难以直接在空间找出满足约束条件的路线位置，因此通常把选线设计分为两个彼此紧密联满足约束条件的路线位置，因此通常把选线设计分为两个彼此紧密联系的过程：路线平面设计和纵断面设计。系的过程：路线平面设计和纵断面设计。n n按照现行的技术作业程序，寻求路线最优方案的问题，分为三个阶段按照现行的技术作业程序，寻求路线最优方案的问题，分为三个阶段进行：进行：（1 1）提出满足技术要求和约束条件的几个可能方案；）提出满足技术要求和约束条件的几个可能方案；（2 2）把方案的意图变为具体的设计，也就是进行平面、纵断面和横断面）把方案的意图变为具体的设计，也就是进行平面、纵断面和横断面设计；设计；（3 3）进行方案的评价和修正。从安全、环保、经济等各方面对路线方案）进行方案的评价和修正。从安全、环保、经济等各方面对路线方案进行评价，在此基础上，修正路线平面和纵断面，并重复上述过程，直进行评价，在此基础上，修正路线平面和纵断面，并重复上述过程，直至找出满足设计目标的方案。至找出满足设计目标的方案。n n现代数学方案和计算机技术的发展，为路线方案优化提供了保证。第一，可现代数学方案和计算机技术的发展，为路线方案优化提供了保证。第一，可增加研究方案的数目，保证在计算机上能完成评价方案有关的复杂而繁重的增加研究方案的数目，保证在计算机上能完成评价方案有关的复杂而繁重的单纯计算工作；第二，用数学方法来优化所得方案，能保证评价所得方案接单纯计算工作；第二，用数学方法来优化所得方案，能保证评价所得方案接近最优值的程度。近最优值的程度。路线优化设计的定义n n从确定路线最优方案的角度出发，进行路线最优化设计的方法可分为从确定路线最优方案的角度出发，进行路线最优化设计的方法可分为两大类：两大类：对于平面或纵断面各种比较方案，利用数字高程模型和路线计算机辅助对于平面或纵断面各种比较方案，利用数字高程模型和路线计算机辅助设计软件，快速准确地完成路线设计，并计算出各方案的总费用和各项设计软件，快速准确地完成路线设计，并计算出各方案的总费用和各项比较指标，由设计者根据自己的经验选出最佳方案。比较指标，由设计者根据自己的经验选出最佳方案。根据某一路线的初始方案，利用最优化理论的数学方法，由计算机自动根据某一路线的初始方案，利用最优化理论的数学方法，由计算机自动寻找最优设计方案。即输入一个可行方案，通过数学迭代方法来完成最寻找最优设计方案。即输入一个可行方案，通过数学迭代方法来完成最优方案的求解。优方案的求解。n n前前者者属属于于传传统统设设计计模模式式，在在实实际际工工程程中中采采用用较较多多，实实质质上上是是计计算算机机辅辅助方案比选的过程，而后者则是现代意义的工程优化设计方法。助方案比选的过程，而后者则是现代意义的工程优化设计方法。n n路路线线优优化化设设计计就就是是在在满满足足路路线线设设计计技技术术标标准准、控控制制点点等等约约束束条条件件的的前前提提下下，通通过过优优化化技技术术确确定定路路线线方方案案的的最最优优位位置置，从从而而达达到到公公路路路路线线设设计的目标，即安全、环保、经济、舒适、美观。计的目标，即安全、环保、经济、舒适、美观。路线优化设计的步骤与定位n n路线优化设计属于非线性规划问题，基本优化步路线优化设计属于非线性规划问题，基本优化步骤如下：骤如下：（1 1）建立目标函数和约束条件；）建立目标函数和约束条件；（2 2）通过）通过GISGIS或其它手段得到优化的相关信息（如地或其它手段得到优化的相关信息（如地质、地形、环境等）；质、地形、环境等）；（3 3）建立用于路线优化的优化算法；）建立用于路线优化的优化算法；（4 4）评价得到的优化结果，反复迭代，得到满意结果。）评价得到的优化结果，反复迭代，得到满意结果。n n路线优化设计的定位应该是能够为路线设计提供路线优化设计的定位应该是能够为路线设计提供参考方案，从而在设计过程中给设计人员提供更参考方案，从而在设计过程中给设计人员提供更多的帮助，而不是通过优化设计产生路线的最终多的帮助，而不是通过优化设计产生路线的最终方案。方案。n n平面优化设计的任务和作用：平面优化设计的任务和作用：（1 1）在满足路网规划、环境保护、避让不利地质条件）在满足路网规划、环境保护、避让不利地质条件等前提下，由计算机自动定出技术合理、满足规范要等前提下，由计算机自动定出技术合理、满足规范要求、综合费用（占地费、工程费用、安全费用等）最求、综合费用（占地费、工程费用、安全费用等）最小的平面设计方案。小的平面设计方案。（2 2）为平面交互设计提供参考方案。）为平面交互设计提供参考方案。n n纵断面优化设计的任务和作用：纵断面优化设计的任务和作用：（1 1）在平面位置一定的条件下，在技术合理、符合设）在平面位置一定的条件下，在技术合理、符合设计规范要求的前提下，由计算机自动定出工程费用计规范要求的前提下，由计算机自动定出工程费用（工程数量）最小的纵断面设计方案。（工程数量）最小的纵断面设计方案。（2 2）为纵断面交互设计提供参考方案。）为纵断面交互设计提供参考方案。（3 3）根据设计的纵断面方案评判路线平面位置的优劣，）根据设计的纵断面方案评判路线平面位置的优劣，为改善平面位置提供依据。为改善平面位置提供依据。路线优化的层次n n路线方案优化：路线总体走向和起伏模型的建立与路线方案优化：路线总体走向和起伏模型的建立与优化。优化。初始方案的给定，比较困难，以前多借助专家系统给定。初始方案的给定，比较困难，以前多借助专家系统给定。目前多采用目前多采用GISGIS系统产生初始方案。系统产生初始方案。n n路线设计参数优化：是在路线初始方案给定情况下，路线设计参数优化：是在路线初始方案给定情况下，优化设计参数。优化设计参数。设计参数优化相对比较简单，理论也比较成熟。设计参数优化相对比较简单，理论也比较成熟。主要包括两方面内容：一是建立优化数学模型，这是优化主要包括两方面内容：一是建立优化数学模型，这是优化设计关键。二是利用优化方法求解这个数学模型。设计关键。二是利用优化方法求解这个数学模型。路线优化设计的阶段n n优化技术在公路设计过程中应当由粗到细，逐步深入。优化技术在公路设计过程中应当由粗到细，逐步深入。n n在各个设计阶段，宜于采用不同的优化技术，大体上在各个设计阶段，宜于采用不同的优化技术，大体上可以有：可以有：在可行性研究阶段采用宽带范围内的选线优化技术在可行性研究阶段采用宽带范围内的选线优化技术 在初步设计阶段采用平面优化或空间线优化技术在初步设计阶段采用平面优化或空间线优化技术 在技术设计阶段采用详细纵断面优化、局部移线和透视图在技术设计阶段采用详细纵断面优化、局部移线和透视图检查。检查。n n以上三个阶段，技术设计阶段优化目标易于数量化，以上三个阶段，技术设计阶段优化目标易于数量化，影响因素少，易于实现；而可行性研究阶段，涉及复影响因素少，易于实现；而可行性研究阶段，涉及复杂的经济社会因素，难度较大。杂的经济社会因素，难度较大。相关研究与分析n n一、优化的目标函数一、优化的目标函数 1 1）建立多目标优化系统）建立多目标优化系统n n多目标优化设计系统缺点在于，其一随着目标数的增加，计算多目标优化设计系统缺点在于，其一随着目标数的增加，计算工作量将成倍增加；其二在系统中多个评价目标往往难以用一工作量将成倍增加；其二在系统中多个评价目标往往难以用一种合适的尺度加以统一种合适的尺度加以统一 2 2）折合为工程费用，进行单目标优化）折合为工程费用，进行单目标优化n n目前的研究成果大多是以工程造价或土石方工程量为依据建立目前的研究成果大多是以工程造价或土石方工程量为依据建立目标函数的目标函数的“单目标单目标”优化方案，这样得到的成果是工程造价优化方案，这样得到的成果是工程造价最低或工程量最小的方案。这个方案对于路线设计具有指导作最低或工程量最小的方案。这个方案对于路线设计具有指导作用，但随着公路等级的提高，仅以工程造价或工程量的单项指用，但随着公路等级的提高，仅以工程造价或工程量的单项指标值作为方案比选的依据已无法反映路线的设计目标，对平面标值作为方案比选的依据已无法反映路线的设计目标，对平面设计更是如此。设计更是如此。n n二、平面优化设计 国外研究现状国外研究现状n n国外的路线平面优化方法主要有四种即：变分法国外的路线平面优化方法主要有四种即：变分法(calculus of variations)(calculus of variations)、网络优化法、网络优化法(network(network optimization)optimization)、动态规划法、动态规划法(dynamic(dynamic programming)programming)以及遗传算法以及遗传算法(genetic(genetic algorithms)algorithms)国内的研究现状国内的研究现状 n n19921992年长沙铁道学院完成了平纵联合优化的课题，年长沙铁道学院完成了平纵联合优化的课题，提出了提出了RDBRDB方法，即随机搜索动态规划方法，即随机搜索动态规划B B样条样条函数综合方法。函数综合方法。n n19961996年西南交通大学邓域才教授提出用梯度投影法年西南交通大学邓域才教授提出用梯度投影法进行平面优化的思路进行平面优化的思路 n n同济大学朱照宏教授等基于动态规划法平面优化同济大学朱照宏教授等基于动态规划法平面优化 n n三、纵断面优化设计国内外的路线纵断面优化方法主要有五种即：国内外的路线纵断面优化方法主要有五种即：随机搜索法随机搜索法,动态规划法动态规划法,梯度投影法、降维法梯度投影法、降维法和遗传算法。和遗传算法。前联邦德国的前联邦德国的EPOS-1EPOS-1程序以及程序以及EasaEasa采用的就采用的就是随机搜索法进行纵断面优化。是随机搜索法进行纵断面优化。动态规划法以及改进的动态规划法是国内外使动态规划法以及改进的动态规划法是国内外使用较多的一种方法用较多的一种方法 。前苏联铁路部门最早提出将梯度投影法应用于前苏联铁路部门最早提出将梯度投影法应用于纵断面优化中。邓域才等人在此基础上，建立纵断面优化中。邓域才等人在此基础上，建立了梯度投影法对变坡点优化的程序系统了梯度投影法对变坡点优化的程序系统 。英国英国HOPSHOPS系统采用的优化方法就是降维法。系统采用的优化方法就是降维法。遗传算法是近些年来比较流行的算法。遗传算法是近些年来比较流行的算法。遗传算法与工程优化n n遗传算法（遗传算法（Genetic AlgorithmsGenetic Algorithms，简称，简称GAGA）是基于）是基于“适者生存适者生存”的的一种高度并行、随机和自适应的优化算法。这种方法适合于具有很大一种高度并行、随机和自适应的优化算法。这种方法适合于具有很大搜索空间的优化问题。搜索空间的优化问题。n n在遗传算法中，有一个包含个体的群体，个体代表问题的一个解，群在遗传算法中，有一个包含个体的群体，个体代表问题的一个解，群体就是问题的一些解的集合。某一评价函数被用来对这些候选解进行体就是问题的一些解的集合。某一评价函数被用来对这些候选解进行评价，目标是优化该评价函数，即搜索该函数的最大值或最小值，以评价，目标是优化该评价函数，即搜索该函数的最大值或最小值，以解决给定的问题。这些候选解通常用位串（解决给定的问题。这些候选解通常用位串（bit stringbit string）的形式表示，）的形式表示，借用生物学的术语称之为染色体（借用生物学的术语称之为染色体（chromosomechromosome）。把解表示为位）。把解表示为位串的过程称为编码，编码后的每个位串就表示一个个体，即问题的一串的过程称为编码，编码后的每个位串就表示一个个体，即问题的一个解。评价函数用以评价群体中每个个体的适应度（个解。评价函数用以评价群体中每个个体的适应度（fitnessfitness）。在算）。在算法的每次迭代（借用生物学术语称作一代）中，评价函数按照优化标法的每次迭代（借用生物学术语称作一代）中，评价函数按照优化标准对每个个体进行度量，计算其适应度，适应度最高的个体被选择允准对每个个体进行度量，计算其适应度，适应度最高的个体被选择允许再生，以产生新的一代。许再生，以产生新的一代。n n遗传算法中的再生过程主要包括三个遗传算子：（遗传算法中的再生过程主要包括三个遗传算子：（1 1）选择；（）选择；（2 2）交）交叉；（叉；（3 3）变异。在选择过程中，适应度高的个体被直接复制到下一）变异。在选择过程中，适应度高的个体被直接复制到下一代群体中。适应度越高的串，产生后代的概率就越高。在交叉过程中，代群体中。适应度越高的串，产生后代的概率就越高。在交叉过程中，两个串的部分位（称为基因）进行变换从而产生一个新串作为下一代两个串的部分位（称为基因）进行变换从而产生一个新串作为下一代的个体。变异用来随机地改变染色体的部分基因。交叉和变异的使用的个体。变异用来随机地改变染色体的部分基因。交叉和变异的使用都有一定的概率，分别称为交叉概率和变异概率。都有一定的概率，分别称为交叉概率和变异概率。简单的函数优化实例（遗传算法）n n求函数求函数f(x)=xsin(10*x)+2.0 -1x2f(x)=xsin(10*x)+2.0 -1x2的最大值。的最大值。n n求解步骤求解步骤（1 1）编码，采用二进制的编码方式，将某个变量值代表的个体表）编码，采用二进制的编码方式，将某个变量值代表的个体表示为二进制串，串长取决于求解精度，若精确到示为二进制串，串长取决于求解精度，若精确到6 6位小数，由于区位小数，由于区间长度为间长度为3 3，必须将区间分为，必须将区间分为3103106 6等份。等份。由于由于2 22121 310 3106 6222222，则二进制串，则二进制串和和 就表示区间的两个端点值就表示区间的两个端点值1 1和和2 2。（2 2）产生初始种群，一个个体是由串长为）产生初始种群，一个个体是由串长为2222的随机产生的二进制的随机产生的二进制串组成染色体的基因码。我们可以产生一定数目的个体组成种群。串组成染色体的基因码。我们可以产生一定数目的个体组成种群。（3 3）计算适应度，本例直接引用目标函数作为适应度函数，即）计算适应度，本例直接引用目标函数作为适应度函数，即f(s)=f(x),f(s)=f(x),这里二进制串这里二进制串s s对应变量对应变量x x的值。的值。例如，有二个二进制串为例如，有二个二进制串为s1s1分别对应于变量值分别对应于变量值x1=0.637197,x2=x1=0.637197,x2=0.9589730.958973。则。则f f（s1s1）2.586345 f(s2)=1.0788782.586345 f(s2)=1.078878。续上页n n（4 4）选择）选择n n采用轮盘赌的选择方法采用轮盘赌的选择方法续上页n n（5 5）交叉和变异）交叉和变异续上页n n（6 6）模拟结果）模拟结果遗传算法的流程及进化进程公路线形模型 n n公路线形的基本定义公路线形的基本定义 公路平面线形模型的表示 公路平面线形的确定 基于遗传算法的平面优化n n一一.不考虑回头的优化模型不考虑回头的优化模型 1.1.设计变量设计变量n n平面优化模型的设计变量为纵向切割线坐标平面优化模型的设计变量为纵向切割线坐标didi，设计变量为，设计变量为n n个。个。n n设计变量采用交点坐标（设计变量采用交点坐标（x x，y y），若初始优化的交点数为），若初始优化的交点数为n n个，则设个，则设计变量为计变量为2n2n个。个。目标函数目标函数n n位置相关费用，包括占地费用（元）；土石方费用（元）；表示对位置相关费用，包括占地费用（元）；土石方费用（元）；表示对环境影响的费用（元）；修建桥涵的费用（元）；对交通安全设施环境影响的费用（元）；修建桥涵的费用（元）；对交通安全设施（护栏等）与长度有关的费用（元）。（护栏等）与长度有关的费用（元）。n n使用者费用，燃油消耗费（元）；时间消耗费（元）；交通事故费使用者费用，燃油消耗费（元）；时间消耗费（元）；交通事故费（元）。（元）。约束条件约束条件n n考虑交点考虑交点x x，y y坐标的取值范围坐标的取值范围n n考虑最小半径约束（转化为罚函数）考虑最小半径约束（转化为罚函数）平面优化的数学模型遗传算法选择算法变异算子n n均匀变异均匀变异直线变异n n直线变异用于将两任直线变异用于将两任意选择的交点之间的意选择的交点之间的线形取直。线形取直。交叉算子n n简单交叉简单交叉两点交叉其它交叉方式