基于遺傳算法的公路平面線形優(yōu)化方法

基于遺傳算法的公路平面線形優(yōu)化方法

0路線平面優(yōu)化設(shè)計算法公路選擇線在整個道路設(shè)計中發(fā)揮著非常重要的作用。通過公路定線所確定的路線方案,不僅在很大程度上決定著新建公路的工程費用和營運費用,而且與交通安全有很大的聯(lián)系,因此所采用的路線方案,應(yīng)當保證工程量與路線工程費用、營運費用以及安全費用間具有最優(yōu)關(guān)系。現(xiàn)代數(shù)學方案和計算機技術(shù)的發(fā)展,為路線方案優(yōu)化提供了保證。進行公路平面優(yōu)化,首先需要建立公路平面優(yōu)化設(shè)計的數(shù)學模型,但是要真正實現(xiàn)利用計算機自動完成平面優(yōu)化設(shè)計,還必須選擇合適的優(yōu)化算法,這是優(yōu)化設(shè)計至關(guān)重要的一步。路線平面優(yōu)化設(shè)計由于涉及諸多因素,如社會、環(huán)境、地形、地質(zhì)等,遠比縱斷面優(yōu)化設(shè)計復雜,目前各國對此問題基本上是處于方法的研究試用階段。目前應(yīng)用較多的方法有變分法、網(wǎng)絡(luò)優(yōu)化法、動態(tài)規(guī)劃法和梯度投影法。變分法得到的優(yōu)化結(jié)果具有連續(xù)和全局優(yōu)化的特點,但由于組成目標函數(shù)的各項費用具有不連續(xù)性(如占地費用),因此目標函數(shù)連續(xù)的假設(shè)并不符合實際情況。網(wǎng)絡(luò)優(yōu)化法由于要計算網(wǎng)格間的連通費用,而且缺乏地理信息系統(tǒng)(GIS)的支持,因此其成本區(qū)劃分以及網(wǎng)格連通費用計算量非常大。動態(tài)規(guī)劃法具有不適合于連續(xù)搜索空間,而且要求目標函數(shù)為顯函數(shù)、要求子問題獨立等缺點。梯度投影法目標函數(shù)是以各計算點的設(shè)計高程與地面高程之差為基礎(chǔ)的,計算中往往假定地形變化規(guī)律不變,而這種假定只有在很小范圍內(nèi)才接近實際,因此在優(yōu)化的迭代過程中每次迭代的步長不能太大;另外,該方法在接近最優(yōu)解時收斂速度較慢。筆者針對上述方法存在的問題,提出一種基于遺傳算法的平面優(yōu)化的新方法,這種方法可以在一個可行域中自動搜索一個最優(yōu)或較優(yōu)解。1平面優(yōu)化數(shù)學模型1.1路線優(yōu)化設(shè)計的實踐路線優(yōu)化設(shè)計不僅需要建立路線優(yōu)化模型和選擇優(yōu)化算法,而且需要GIS的支持,以保證路線方案能夠滿足路網(wǎng)規(guī)劃、環(huán)保、工程地質(zhì)等各方面要求。正是由于公路選線涉及自然、社會、經(jīng)濟等諸多因素,盡管路線優(yōu)化技術(shù)經(jīng)過幾十年的研究,仍然難以得到能夠達到公路設(shè)計目標的路線方案。通常路線優(yōu)化多是對縱斷面進行優(yōu)化,優(yōu)化的目標是使工程費用最少,但這種優(yōu)化往往是以較低的技術(shù)指標為代價的,得到的優(yōu)化結(jié)果與實際差別較大,因此在目前難以實現(xiàn)設(shè)計智能化的情況下,路線優(yōu)化設(shè)計的定位應(yīng)該是能夠為路線設(shè)計提供參考方案,從而在設(shè)計過程中給設(shè)計人員提供更多的幫助,而不是通過優(yōu)化設(shè)計產(chǎn)生路線的最終方案。由此確定平面優(yōu)化的任務(wù)和作用:(1)在滿足路網(wǎng)規(guī)劃、環(huán)境保護、避讓不利地質(zhì)條件等前提下,由計算機自動定出技術(shù)合理、滿足規(guī)范要求、綜合費用(占地費用、工程費用、安全費用等)最小的平面設(shè)計方案。(2)為平面交互設(shè)計提供參考方案。1.2半徑的確定按照對平面優(yōu)化設(shè)計的定位及計算機自動處理的要求,在平面優(yōu)化設(shè)計中約定:(1)不考慮緩和曲線。(2)平面線形的確定是以滿足路線的連續(xù)性為前提的,即在確定半徑過程中,允許半徑小于極限最小半徑,但不允許出現(xiàn)不連續(xù)情況。(3)當出現(xiàn)不連續(xù)情況時,半徑由式(1)確定(圖1)Ri=Ri+1=‖Pi+1-Pi‖/[tan(Δi/2)+tan(Δi+1/2)](1)根據(jù)上述約定,確定以平面交點坐標作為平面優(yōu)化的設(shè)計變量。1.3優(yōu)化模型中缺乏對養(yǎng)護、營運等費用的考慮一般來說,在公路網(wǎng)規(guī)劃確定以后,影響路線方案選擇的費用有建設(shè)費用、養(yǎng)護費用、營運費用和環(huán)境費用。目前大多數(shù)的平面優(yōu)化模型往往只考慮建設(shè)費用,有的甚至僅考慮土石方工程量的費用,之所以這樣做的原因在于:一方面缺乏對養(yǎng)護、營運等費用與公路設(shè)計要素關(guān)系的研究;另一方面目標函數(shù)涉及的因素越多,求解的難度會越大。在確定目標函數(shù)時,不僅要考慮建設(shè)費用,還要考慮環(huán)境費用和營運費用。按照它們的性質(zhì),將其分為位置相關(guān)費用、使用者費用。1.3.1cb+cs式位置相關(guān)費用可以用式(2)表示CN=CR+CI+CE+CB+CG(2)式中:CN為位置相關(guān)費用;CR為占地費用;CI為土石方費用;CE為對環(huán)境影響的費用;CB為修建橋涵的費用;CG為與長度有關(guān)的交通安全設(shè)施(護欄等)費用。(1)回填苗木和土方費用占地費用與占地寬度、土地的性質(zhì)有關(guān),土地的性質(zhì)可以通過GIS查詢得到,從而得到不同土地性質(zhì)下的單位面積土地費用;占地寬度則與填挖高度和邊坡的形式有關(guān)。土石方費用與土石方的體積直接相關(guān),然而在未作縱斷面設(shè)計之前,土石方體積是無法精確計算的,因此占地費用、土石方費用是和縱斷面設(shè)計路線密切相關(guān)的,因此在計算這兩項費用時,通過兩步法計算。首先用優(yōu)化算法產(chǎn)生平面方案,然后利用數(shù)字高程模型(DEM)自動產(chǎn)生縱斷面地面線,用縱斷面優(yōu)化算法進行縱斷面優(yōu)化,從而計算得到占地費用和土石方費用。(2)允許穿越的治療在公路選線的過程中,對環(huán)境敏感區(qū)的考慮可以分為兩種情況:①絕對不允許穿越環(huán)境敏感區(qū);②允許穿越,但必須采取措施對周圍環(huán)境進行恢復。在費用計算時,結(jié)合GIS,建立環(huán)境影響費用柵格圖層,通過地圖代數(shù)方法,將環(huán)境影響費用柵格與路線長度相乘即可得到環(huán)境影響費用。對于第一種情況,通常需要賦給柵格以足夠大的值,以保證優(yōu)化時,路線不穿過環(huán)境敏感區(qū)。(3)橋墩的長度和寬度通過GIS,可以查詢出路線跨越河流的寬度,由此可以估計出橋涵的長度,再根據(jù)橋涵的規(guī)模,將橋涵長度與橋涵每延米單價相乘即可得到修建橋涵的費用。(4)運營安全設(shè)施的成本交通安全設(shè)施費用主要是護欄費用,是與路線長度直接相關(guān)的。每延米的護欄費用與設(shè)置護欄的路段長度相乘就是交通安全設(shè)施費用。1.3.2燃油消耗費用使用者費用主要包括汽車營運費(燃油消耗)、時間消耗費和交通事故費,用式(3)表示CU=CF+CT+CC(3)式中:CU為使用者費用;CF為燃油消耗費;CT為時間消耗費;CC為交通事故費。要計算使用者費用,必須找出燃油消耗、時間消耗、交通事故與公路線形要素的關(guān)系,另外還必須確定汽車的平均行駛速度及其與使用者費用之間的關(guān)系。國外通常采用回歸分析的方法建立它們之間的聯(lián)系,而在中國則缺乏這方面的研究,因此本文中直接引用國外的研究成果計算使用者費用CU。1.4brib轉(zhuǎn)化為目標函數(shù)筆者考慮平面優(yōu)化約束條件時,除限制坐標的取值范圍外,僅考慮最小半徑約束。為了求解方便,通過罰函數(shù)的方法將約束條件轉(zhuǎn)化為目標函數(shù)的一部分,見式(4)Cc(i)={b(Ri?Rmin)2?Ri<Rmin0?Ri≥Rmin(4)Cc(i)={b(Ri-Rmin)2?Ri<Rmin0?Ri≥Rmin(4)式中:b為罰函數(shù)系數(shù)。當然,在平面優(yōu)化時還存在路線位置約束,如穿越城鎮(zhèn)、橋位等約束,但這些約束都可以反映在目標函數(shù)中,通過費用約束來避免路線穿越高費用區(qū)。1.5x大合一,4e,4e,5e,5e,5e,5e,5e,5平面優(yōu)化設(shè)計模型可表示為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基于遺傳理論的平面優(yōu)化算法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群體的第一次創(chuàng)造初始種群按2種方式產(chǎn)生。(1)縱向切割線2nΛ=(λ1,λ2,λ3,λ4,…,λ2n-1,λ2n)=(xO1,yO1,xO2,yO2,…,xOn,yOn)(7)式中:(xOi,yOi)為第i個縱向切割線的原點。(2)初始種群染色體數(shù)目λ2i-1=rc[xO,xmax]?i=1,2,…,n(8)λ2i=rc[yO,ymax]?i=1,2,…,n(9)初始種群染色體的數(shù)目建議為交點個數(shù)的5倍,即np=10n。2.2遺傳處理設(shè)計的遺傳算子共有4個變異算子和4個交叉算子,本文中僅介紹有代表性的幾種算子。2.2.1i1基因值計算設(shè)Λ=(λ1,λ2,…,λ2n-1,λ2n)為擬變異的染色體,隨機產(chǎn)生兩個獨立基因位置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)為擬交叉的父個體,二者將在隨機產(chǎn)生的k位置交叉,k=rd[1,n]。則交叉后的子個體為Λ′i=(λi1,λi2,…,λik,λj(k+1),…,λjn)(12)Λ′j=(λj1,λj2,…,λjk,λi(k+1),…,λin)(13)通過簡單交叉,新產(chǎn)生的子個體將可能從父個體中繼承更好的基因,如圖3所示。2.2.3凸集的線性組合算術(shù)交叉算子借鑒了凸集的概念,即凸集內(nèi)兩點的線性組合仍然落在凸集內(nèi)。Λi=(λi1,λi2,…,λin)和Λj=(λj1,λj2,…,λjn)為擬交叉的父個體,基于凸集的概念,算術(shù)交叉的子個體就是父個體的線性組合,如圖4所示。交叉得到的子個體為Λ′i=ωΛi+(1-ω)Λj(14)Λ′j=ωΛj+(1-ω)Λi(15)式中:ω為(0,1)之間的隨機數(shù)。2.3性能進化的復迭代公路平面優(yōu)化停止規(guī)則是事先確定一個最大的遺傳代數(shù),算法迭代達到該數(shù)值時停止。也可采用反復迭代,直到得到的解在性能進化過程中無法改進或改進甚微時,停止計算。由于非均勻變異需要用到最大迭代次數(shù),因此可采用二者結(jié)合方式,以加快收斂速度,即事先確定一個最大遺傳代數(shù),如果最后幾代迭代結(jié)果仍然具有較大差異,則增加迭代20次,直到迭代結(jié)果差異不大時停止迭代。3群數(shù)、迭代次數(shù)以及綜合費用選擇某三級公路的一段作為該算法的驗證對象。設(shè)計速度為30km·h-1,最小半徑為30m,研究區(qū)域如圖5所示。種群數(shù)為50個,初始交點數(shù)為20個,迭代次數(shù)為300。從而得到迭代次數(shù)為100和迭代次數(shù)為300的路線方案。由圖5可以看出:圖5(a)線形很好,但計算得到的目標函數(shù)值很大,土石方量較大,工程費用較高。經(jīng)過300次迭代后,路線避開了高費用區(qū),雖然線形不如圖5(a),但綜合費用最低;雖然圖5(b)還不能滿足最終定線的需要,但已經(jīng)可以為交互定線提供參考。4公