基于遺傳算法的鐵路縱斷面優(yōu)化研究

何祥衛(wèi)

(中鐵第四勘察設(shè)計(jì)院集團(tuán)有限公司，湖北武漢 430063)

在解決鐵路縱斷面優(yōu)化問題時(shí)，首先要建立基于優(yōu)化算法的數(shù)學(xué)模型，所以優(yōu)化算法不單單會(huì)對(duì)模型的質(zhì)量產(chǎn)生影響，而且也決定了該模型求解的精度和效率。當(dāng)前國內(nèi)應(yīng)用廣泛的算法主要有蟻群算法、二次規(guī)劃法、梯度投影法等。蟻群算法由 M.Dori于1991年提出［1］，它主要應(yīng)用于離散空間優(yōu)化問題，之后很多研究人員對(duì)該算法進(jìn)行改進(jìn)以適于解決連續(xù)性的鐵路線路優(yōu)化問題，但它還不是真正意義上的連續(xù)空間優(yōu)化。二次規(guī)劃法是一種特殊的非線性規(guī)劃方法，缺點(diǎn)是以二次函數(shù)作為目標(biāo)函數(shù)的海森矩陣很難求得。梯度投影法適用于解決具有線性約束的非線性規(guī)劃問題［2］，它的弊端是當(dāng)優(yōu)化過程接近最優(yōu)解時(shí)，“鋸齒”現(xiàn)象頻繁發(fā)生，從而導(dǎo)致收斂速率下降，最優(yōu)解難以得到。針對(duì)上述方法存在的問題，本文引入遺傳算法，此方法可在一個(gè)可行域中自動(dòng)搜索一個(gè)最優(yōu)解或較優(yōu)解［3，4］，且對(duì)求解問題限制較少，可適用于解決傳統(tǒng)搜索方法難以處理的縱斷面優(yōu)化問題。

1 建立縱斷面優(yōu)化的數(shù)學(xué)模型

1.1 優(yōu)化變量

整個(gè)縱斷面設(shè)計(jì)線可由變坡點(diǎn)里程、變坡點(diǎn)的設(shè)計(jì)高程和相應(yīng)的豎曲線表達(dá)，依照遺傳算法搜索求解過程的全局性，筆者在此選取變坡點(diǎn)里程和變坡點(diǎn)的設(shè)計(jì)高程這兩個(gè)優(yōu)化變量，采用改進(jìn)后的遺傳算法進(jìn)行優(yōu)化研究。

1.2 目標(biāo)函數(shù)

傳統(tǒng)的縱斷面優(yōu)化模型是在縱斷面線路設(shè)計(jì)要素滿足適當(dāng)?shù)募s束條件下，盡可能地節(jié)約人力物力，減少工程造價(jià)成本，所以應(yīng)把線路的總工程費(fèi)用作為目標(biāo)函數(shù)進(jìn)行優(yōu)化。考慮到實(shí)際工程包含路基土石方工程、橋隧工程、支擋工程、涵洞工程等分項(xiàng)工程，將它們分別設(shè)立不同的目標(biāo)函數(shù)，并作表達(dá)式如下

式中，f1(x)為路基土石方工程費(fèi)用;f2(x)為橋隧工程費(fèi)用;f3(x)為支擋工程費(fèi)用;f4(x)為涵洞工程費(fèi)用;f(x)為縱斷面設(shè)計(jì)線的總工程費(fèi)用。

1.3 約束條件

縱斷面設(shè)計(jì)的約束條件包括:坡度約束、坡長約束、起終點(diǎn)高程約束、豎緩曲線重疊約束、平縱組合約束等。

2 基于遺傳算法的縱斷面優(yōu)化設(shè)計(jì)

遺傳算法是一種模擬自然選擇和生物進(jìn)化機(jī)制的優(yōu)化算法。1975年，美國的John Holland教授首次提出該算法，它的基本思想來源于達(dá)爾文的進(jìn)化論和Mendel的遺傳學(xué)說［5］。遺傳算法中核心的兩個(gè)算子是交叉和變異，它們被反復(fù)利用到由可以代表問題的解的染色體上。遺傳算法基于適應(yīng)度函數(shù)選擇合適的染色體，并剔除掉適應(yīng)性較差的染色體，按照適者生存的原則，通過交叉變異的反復(fù)迭代過程產(chǎn)生適應(yīng)環(huán)境的新種群［6，7］。下面對(duì)基于遺傳算法的縱斷面優(yōu)化模型進(jìn)行分析闡述。

2.1 編碼設(shè)計(jì)

常見的編碼方式是Holland教授提出的二進(jìn)制編碼。為了更好地結(jié)合縱斷面優(yōu)化的知識(shí)建立模型，本文采用實(shí)數(shù)編碼方式。該編碼適用于較大空間的搜索，能解決變坡點(diǎn)位置組合需要較大空間搜索的問題，并將編碼的基因與變坡點(diǎn)一一對(duì)應(yīng)起來，能有效提高該模型的精度和效率。

實(shí)數(shù)編碼中每個(gè)個(gè)體ρ可表示為

式中，Mi為變坡點(diǎn)里程，Hi為變坡點(diǎn)設(shè)計(jì)高程，i=1，2，3，…，n。

2.2 種群初始化

為了使初始種群具有多樣性，減少算法陷入局部解的可能性，本文將采用崎嶇度的方法對(duì)初始個(gè)體進(jìn)行處理，并挑選最優(yōu)個(gè)體放入初始種群，從而得到適合算法的初始種群［8］。這種方法能使模型在預(yù)期內(nèi)得到最優(yōu)解，并且能縮減搜索時(shí)間。

縱斷面方案的初始種群是一系列由崎嶇度生成的個(gè)體的集合，每個(gè)個(gè)體分別代表一組解，即一條完整的經(jīng)連續(xù)處理后的縱斷面曲線。

2.3 適應(yīng)度函數(shù)的構(gòu)建

遺傳算法進(jìn)化過程以每個(gè)個(gè)體的適應(yīng)度值作為選擇依據(jù)。縱斷面優(yōu)化的目標(biāo)是減少線路運(yùn)營維護(hù)費(fèi)用以及增強(qiáng)機(jī)車行駛安全性，并且改良與周邊環(huán)境的協(xié)調(diào)性(平面線型已經(jīng)擬定的情況)。但是現(xiàn)階段研究尚未明確揭示線路運(yùn)營維護(hù)費(fèi)用與縱斷面線形之間的關(guān)系，而且線路與周邊環(huán)境的協(xié)調(diào)性也不好量化。在此選取土石方工程費(fèi)用作為適應(yīng)度函數(shù)變量，基于此目標(biāo)函數(shù)求得個(gè)體的適應(yīng)度值。

要選取遺傳進(jìn)化過程中最優(yōu)的個(gè)體，則需根據(jù)土石方費(fèi)用函數(shù)建立適應(yīng)度函數(shù)，計(jì)算個(gè)體的適應(yīng)度值，然后將個(gè)體的適應(yīng)度值進(jìn)行排列選擇。該適應(yīng)度函數(shù)如下

式中，n為方案中橫斷面的個(gè)數(shù);Vf(i)、Vc(i)分別為i路段的填、挖體積;Cf(i)、Cc(i)分別為i路段的單位填方及挖方費(fèi)用。

2.4 遺傳操作數(shù)

標(biāo)準(zhǔn)遺傳算法操作數(shù)包含選擇、交叉和變異。這3個(gè)操作數(shù)分別模擬了自然界中生物進(jìn)化的3個(gè)不同階段，同時(shí)這3個(gè)階段也是相互結(jié)合相互滲透的。因此，選擇合適的或者改變每個(gè)算子的排列組合和操作方式，都能極大程度地影響該算法的優(yōu)化計(jì)算結(jié)果。

2.4.1 選擇策略

在保持種群多樣性的前提下為使得算法收斂速度加快，本文采用排序輪盤法選擇算子。第一步計(jì)算每個(gè)個(gè)體的適應(yīng)度值 E(ρi)，其中 i=1，2，…，n，然后對(duì)種群中的個(gè)體按照其適應(yīng)度值E(ρi)由小到大排列。選擇每個(gè)個(gè)體ρ的概率pi為

計(jì)算個(gè)體ρ的累積概率qi為

旋轉(zhuǎn)n次輪盤后，獲得新的種群。輪盤方法中放回取樣的選擇策略容易使新種群產(chǎn)生重復(fù)的方案，所以在該過程中，要對(duì)重復(fù)的新方案進(jìn)行剔除。選擇策略設(shè)計(jì)流程如圖1所示。

圖1 選擇操作流程

2.4.2 交叉操作

交叉算子是遺傳算法中最核心的部分，即把2個(gè)配對(duì)的染色體在同一位置被切斷，基因重組后形成2個(gè)新個(gè)體。通過交叉操作產(chǎn)生的個(gè)體具有離散性強(qiáng)的特征，該特征能夠大大增強(qiáng)算法的全局尋優(yōu)能力。本文采用啟發(fā)式交叉，將適應(yīng)度較大的個(gè)體向著較優(yōu)的個(gè)體增大的方向移動(dòng)，交叉后得到更優(yōu)個(gè)體。該交叉方法有利于生成較優(yōu)個(gè)體，能在全局范圍內(nèi)搜索變坡點(diǎn)。

2.4.3 變異操作

變異運(yùn)算是對(duì)個(gè)體串的某些基因值做等位替換后形成一個(gè)新個(gè)體。根據(jù)已有經(jīng)驗(yàn)，優(yōu)化設(shè)計(jì)中交叉采用多種變異算子。變異概率Pm通常取0.000 1～0.1。通過變異操作，計(jì)算種群中的最優(yōu)的縱斷面方案(即最優(yōu)個(gè)體)與當(dāng)前個(gè)體的差異值，將該值乘以變異概率來調(diào)整當(dāng)前縱斷面方案。

2.5 約束條件的處理

上文已經(jīng)介紹了縱斷面設(shè)計(jì)的約束條件，經(jīng)過每次迭代后產(chǎn)生新的個(gè)體，若個(gè)體符合約束條件，則保留用于下一次迭代，若不符合，則剔除并重新迭代。

2.6 停止規(guī)則

利用遺傳算法進(jìn)行縱斷面優(yōu)化的目標(biāo)是為了尋得可行解中的最優(yōu)方案，并且該方案能滿足事先設(shè)定的所有約束條件。上述過程已經(jīng)完成了一次完整的迭代，是否繼續(xù)取決于算法的停止規(guī)則。一種是指定一個(gè)最大的遺傳代數(shù)G，當(dāng)進(jìn)化迭代次數(shù)達(dá)到G時(shí)即停止;另一種是對(duì)各代的最佳解進(jìn)行監(jiān)控的方法，動(dòng)態(tài)確定停止規(guī)則。即當(dāng)前的最好解在連續(xù)20代沒有變化時(shí)即停止計(jì)算。否則，將繼續(xù)迭代。在本文中采用后一種方法。

3 算法實(shí)現(xiàn)過程

基于遺傳算法與動(dòng)態(tài)監(jiān)測(cè)最優(yōu)解的方法需要通過許多次的迭代才能不斷地接近最優(yōu)解，該過程用人工計(jì)算幾乎不可能實(shí)現(xiàn)。本文為解決該算法繁瑣冗長的計(jì)算過程，在VS.NET下利用AutoCAD二次開發(fā)平臺(tái)和遺傳算法方法編制了縱斷面優(yōu)化程序，以期提高程序的執(zhí)行效率?？v斷面優(yōu)化程序流程如圖2所示。

4 結(jié)語

本文引進(jìn)了模擬生物進(jìn)化過程和遺傳機(jī)理的遺傳算法，該算法具有全局優(yōu)化和對(duì)問題提供啟發(fā)式等特點(diǎn)，將遺傳算法應(yīng)用于縱斷面優(yōu)化模型，能更便捷地解決多峰函數(shù)優(yōu)化問題以及無解析表達(dá)式的目標(biāo)函數(shù)優(yōu)化問題，提高優(yōu)化模型的計(jì)算效率，減少設(shè)計(jì)人員的工作任務(wù)量，具有很好的適用價(jià)值。但是，遺傳算法的應(yīng)用依然存在一些適應(yīng)度函數(shù)及有效約束處理上的問題，在接下來的研究中，應(yīng)重點(diǎn)考慮改進(jìn)遺傳算法的構(gòu)造方式。

圖2 縱斷面優(yōu)化程序流程

［1］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社，2005.

［2］詹振炎.梯度投影法及其在鐵路縱斷面設(shè)計(jì)中的應(yīng)用［J］.長沙鐵道學(xué)院學(xué)報(bào)，1979，26(4):32-37.

［3］Eungcheol Kim，Manoj K.Jha，Bongsoo Son.Improving the computational efficiency of highway alignment optimization models through a stepwise genetic algorithms approach［J］.Transportation research part B，2005，17(39):339-360.

［4］Goldberg，D.E.Genetic Algorithms in Search，Optimization，and Machine Learning［M］.Massachusetts，Addison-Welsey Publishing Company Inc，1989.

［5］楊獻(xiàn)波.基于遺傳算法的公路縱斷面優(yōu)化研究［D］.南京:東南大學(xué)，2006.

［6］陳國良.遺傳算法及其應(yīng)用［M］.北京:人民郵電出版社，1996.

［7］李敏強(qiáng).遺傳算法的基本理論與應(yīng)用［M］.北京:科學(xué)出版社，2002.

［8］許金良.集成化公路CAD系統(tǒng)研究與開發(fā)［D］.西安:長安大學(xué)，2002.