基于遗传算法的公路平面线形优化方法

基于遗传算法的公路平面线形优化方法

0路线平面优化设计算法公路选择线在整个道路设计中发挥着非常重要的作用。通过公路定线所确定的路线方案,不仅在很大程度上决定着新建公路的工程费用和营运费用,而且与交通安全有很大的联系,因此所采用的路线方案,应当保证工程量与路线工程费用、营运费用以及安全费用间具有最优关系。现代数学方案和计算机技术的发展,为路线方案优化提供了保证。进行公路平面优化,首先需要建立公路平面优化设计的数学模型,但是要真正实现利用计算机自动完成平面优化设计,还必须选择合适的优化算法,这是优化设计至关重要的一步。路线平面优化设计由于涉及诸多因素,如社会、环境、地形、地质等,远比纵断面优化设计复杂,目前各国对此问题基本上是处于方法的研究试用阶段。目前应用较多的方法有变分法、网络优化法、动态规划法和梯度投影法。变分法得到的优化结果具有连续和全局优化的特点,但由于组成目标函数的各项费用具有不连续性(如占地费用),因此目标函数连续的假设并不符合实际情况。网络优化法由于要计算网格间的连通费用,而且缺乏地理信息系统(GIS)的支持,因此其成本区划分以及网格连通费用计算量非常大。动态规划法具有不适合于连续搜索空间,而且要求目标函数为显函数、要求子问题独立等缺点。梯度投影法目标函数是以各计算点的设计高程与地面高程之差为基础的,计算中往往假定地形变化规律不变,而这种假定只有在很小范围内才接近实际,因此在优化的迭代过程中每次迭代的步长不能太大;另外,该方法在接近最优解时收敛速度较慢。笔者针对上述方法存在的问题,提出一种基于遗传算法的平面优化的新方法,这种方法可以在一个可行域中自动搜索一个最优或较优解。1平面优化数学模型1.1路线优化设计的实践路线优化设计不仅需要建立路线优化模型和选择优化算法,而且需要GIS的支持,以保证路线方案能够满足路网规划、环保、工程地质等各方面要求。正是由于公路选线涉及自然、社会、经济等诸多因素,尽管路线优化技术经过几十年的研究,仍然难以得到能够达到公路设计目标的路线方案。通常路线优化多是对纵断面进行优化,优化的目标是使工程费用最少,但这种优化往往是以较低的技术指标为代价的,得到的优化结果与实际差别较大,因此在目前难以实现设计智能化的情况下,路线优化设计的定位应该是能够为路线设计提供参考方案,从而在设计过程中给设计人员提供更多的帮助,而不是通过优化设计产生路线的最终方案。由此确定平面优化的任务和作用:(1)在满足路网规划、环境保护、避让不利地质条件等前提下,由计算机自动定出技术合理、满足规范要求、综合费用(占地费用、工程费用、安全费用等)最小的平面设计方案。(2)为平面交互设计提供参考方案。1.2半径的确定按照对平面优化设计的定位及计算机自动处理的要求,在平面优化设计中约定:(1)不考虑缓和曲线。(2)平面线形的确定是以满足路线的连续性为前提的,即在确定半径过程中,允许半径小于极限最小半径,但不允许出现不连续情况。(3)当出现不连续情况时,半径由式(1)确定(图1)Ri=Ri+1=‖Pi+1-Pi‖/[tan(Δi/2)+tan(Δi+1/2)](1)根据上述约定,确定以平面交点坐标作为平面优化的设计变量。1.3优化模型中缺乏对养护、营运等费用的考虑一般来说,在公路网规划确定以后,影响路线方案选择的费用有建设费用、养护费用、营运费用和环境费用。目前大多数的平面优化模型往往只考虑建设费用,有的甚至仅考虑土石方工程量的费用,之所以这样做的原因在于:一方面缺乏对养护、营运等费用与公路设计要素关系的研究;另一方面目标函数涉及的因素越多,求解的难度会越大。在确定目标函数时,不仅要考虑建设费用,还要考虑环境费用和营运费用。按照它们的性质,将其分为位置相关费用、使用者费用。1.3.1cb+cs式位置相关费用可以用式(2)表示CN=CR+CI+CE+CB+CG(2)式中:CN为位置相关费用;CR为占地费用;CI为土石方费用;CE为对环境影响的费用;CB为修建桥涵的费用;CG为与长度有关的交通安全设施(护栏等)费用。(1)回填苗木和土方费用占地费用与占地宽度、土地的性质有关,土地的性质可以通过GIS查询得到,从而得到不同土地性质下的单位面积土地费用;占地宽度则与填挖高度和边坡的形式有关。土石方费用与土石方的体积直接相关,然而在未作纵断面设计之前,土石方体积是无法精确计算的,因此占地费用、土石方费用是和纵断面设计路线密切相关的,因此在计算这两项费用时,通过两步法计算。首先用优化算法产生平面方案,然后利用数字高程模型(DEM)自动产生纵断面地面线,用纵断面优化算法进行纵断面优化,从而计算得到占地费用和土石方费用。(2)允许穿越的治疗在公路选线的过程中,对环境敏感区的考虑可以分为两种情况:①绝对不允许穿越环境敏感区;②允许穿越,但必须采取措施对周围环境进行恢复。在费用计算时,结合GIS,建立环境影响费用栅格图层,通过地图代数方法,将环境影响费用栅格与路线长度相乘即可得到环境影响费用。对于第一种情况,通常需要赋给栅格以足够大的值,以保证优化时,路线不穿过环境敏感区。(3)桥墩的长度和宽度通过GIS,可以查询出路线跨越河流的宽度,由此可以估计出桥涵的长度,再根据桥涵的规模,将桥涵长度与桥涵每延米单价相乘即可得到修建桥涵的费用。(4)运营安全设施的成本交通安全设施费用主要是护栏费用,是与路线长度直接相关的。每延米的护栏费用与设置护栏的路段长度相乘就是交通安全设施费用。1.3.2燃油消耗费用使用者费用主要包括汽车营运费(燃油消耗)、时间消耗费和交通事故费,用式(3)表示CU=CF+CT+CC(3)式中:CU为使用者费用;CF为燃油消耗费;CT为时间消耗费;CC为交通事故费。要计算使用者费用,必须找出燃油消耗、时间消耗、交通事故与公路线形要素的关系,另外还必须确定汽车的平均行驶速度及其与使用者费用之间的关系。国外通常采用回归分析的方法建立它们之间的联系,而在中国则缺乏这方面的研究,因此本文中直接引用国外的研究成果计算使用者费用CU。1.4brib转化为目标函数笔者考虑平面优化约束条件时,除限制坐标的取值范围外,仅考虑最小半径约束。为了求解方便,通过罚函数的方法将约束条件转化为目标函数的一部分,见式(4)Cc(i)={b(Ri−Rmin)2∀Ri<Rmin0∀Ri≥Rmin(4)Cc(i)={b(Ri-Rmin)2∀Ri<Rmin0∀Ri≥Rmin(4)式中:b为罚函数系数。当然,在平面优化时还存在路线位置约束,如穿越城镇、桥位等约束,但这些约束都可以反映在目标函数中,通过费用约束来避免路线穿越高费用区。1.5x大合一,4e,4e,5e,5e,5e,5e,5e,5平面优化设计模型可表示为minxp1,yp1,xp2,yp2,⋯,xpn,ypnCT=CN+CUs.t.xO≤xpi≤xmax∀i=1,2,⋯,nyO≤ypi≤ymax∀i=1,2,⋯,n⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪(5)minxp1,yp1,xp2,yp2,⋯,xpn,ypnCΤ=CΝ+CUs.t.xΟ≤xpi≤xmax∀i=1,2,⋯,nyΟ≤ypi≤ymax∀i=1,2,⋯,n}(5)2基于遗传理论的平面优化算法2.1基因编码与初始群体生成2.1.1染色体外光谱采用浮点编码的形式,即Λ=(λ1,λ2,λ3,λ4,…,λ2n-1,λ2n)=(xp1,yp1,xp2,yp2,…,xpn,ypn)(6)式中:Λ为染色体;λj为基因,j=1,2,…,2n-1,2n;xpi、ypi分别为第i个交点的横、纵坐标,i=1,2,…,n,且有xO≤λ2i-1≤xmax,yO≤λ2i≤ymax。2.1.2群体的第一次创造初始种群按2种方式产生。(1)纵向切割线2nΛ=(λ1,λ2,λ3,λ4,…,λ2n-1,λ2n)=(xO1,yO1,xO2,yO2,…,xOn,yOn)(7)式中:(xOi,yOi)为第i个纵向切割线的原点。(2)初始种群染色体数目λ2i-1=rc[xO,xmax]∀i=1,2,…,n(8)λ2i=rc[yO,ymax]∀i=1,2,…,n(9)初始种群染色体的数目建议为交点个数的5倍,即np=10n。2.2遗传处理设计的遗传算子共有4个变异算子和4个交叉算子,本文中仅介绍有代表性的几种算子。2.2.1i1基因值计算设Λ=(λ1,λ2,…,λ2n-1,λ2n)为拟变异的染色体,随机产生两个独立基因位置i和j,其中i=rd[0,n+1],j=rd[0,n+1],i≠j,且i<j,则2i和2j-1之间的基因值为λ′2l−1=λ2i−1+(l−i)λ2j−1−λ2i−1j−i(10)λ2l-1´=λ2i-1+(l-i)λ2j-1-λ2i-1j-i(10)λ′2l=λ2i+(l−i)λ2j−λ2ij−i(11)λ2l´=λ2i+(l-i)λ2j-λ2ij-i(11)式中:l=i+1,i+2,…,j-1。式(10)、(11)中,若i=0,则λ-1=xS,λ0=yS。同样若j=0,则λ2n+1=xE,λ2n+2=yE。直线变异前后的情况见图2。2.2.2拟交叉的父个体该算子与二进制编码中的单点交叉类似。Λi=(λi1,λi2,…,λin)和Λj=(λj1,λj2,…,λjn)为拟交叉的父个体,二者将在随机产生的k位置交叉,k=rd[1,n]。则交叉后的子个体为Λ′i=(λi1,λi2,…,λik,λj(k+1),…,λjn)(12)Λ′j=(λj1,λj2,…,λjk,λi(k+1),…,λin)(13)通过简单交叉,新产生的子个体将可能从父个体中继承更好的基因,如图3所示。2.2.3凸集的线性组合算术交叉算子借鉴了凸集的概念,即凸集内两点的线性组合仍然落在凸集内。Λi=(λi1,λi2,…,λin)和Λj=(λj1,λj2,…,λjn)为拟交叉的父个体,基于凸集的概念,算术交叉的子个体就是父个体的线性组合,如图4所示。交叉得到的子个体为Λ′i=ωΛi+(1-ω)Λj(14)Λ′j=ωΛj+(1-ω)Λi(15)式中:ω为(0,1)之间的随机数。2.3性能进化的复迭代公路平面优化停止规则是事先确定一个最大的遗传代数,算法迭代达到该数值时停止。也可采用反复迭代,直到得到的解在性能进化过程中无法改进或改进甚微时,停止计算。由于非均匀变异需要用到最大迭代次数,因此可采用二者结合方式,以加快收敛速度,即事先确定一个最大遗传代数,如果最后几代迭代结果仍然具有较大差异,则增加迭代20次,直到迭代结果差异不大时停止迭代。3群数、迭代次数以及综合费用选择某三级公路的一段作为该算法的验证对象。设计速度为30km·h-1,最小半径为30m,研究区域如图5所示。种群数为50个,初始交点数为20个,迭代次数为300。从而得到迭代次数为100和迭代次数为300的路线方案。由图5可以看出:图5(a)线形很好,但计算得到的目标函数值很大,土石方量较大,工程费用较高。经过300次迭代后,路线避开了高费用区,虽然线形不如图5(a),但综合费用最低;虽然图5(b)还不能满足最终定线的需要,但已经可以为交互定线提供参考。4公