梁昌征, 張貴陽, 張志清

(1.中國城市規(guī)劃設(shè)計(jì)研究院， 北京 100037； 2.中國電建市政建設(shè)集團(tuán)有限公司， 天津 300384；3.北京工業(yè)大學(xué)交通工程北京市重點(diǎn)實(shí)驗(yàn)室， 北京 100124)

0 引言

遺傳算法在公路工程中的應(yīng)用發(fā)展到今天，已經(jīng)有20多年歷史. 最先將遺傳算法用于公路工程的是美國馬里蘭大學(xué)的Jong博士[1]，他在其博士論文中進(jìn)行了遺傳算法在平面線形優(yōu)化的嘗試，該優(yōu)化模型的主要特點(diǎn)是以起訖點(diǎn)連線為基礎(chǔ)，在選線區(qū)域等距離作起訖點(diǎn)的垂線，假設(shè)公路平面交點(diǎn)在這些垂線上移動(dòng). Jong等[2-3]又提出了一種水平和垂直線形同時(shí)優(yōu)化的路線優(yōu)化模型. 近年來，國內(nèi)外已經(jīng)有很多學(xué)者進(jìn)行自動(dòng)選線研究，從平面線形優(yōu)化、縱斷面線性優(yōu)化到平縱線形組合優(yōu)化，以及三維空間線性優(yōu)化，且取得了相應(yīng)的研究成果[4-9]. 但是，公路自動(dòng)選線表現(xiàn)出的主要局限性是，在選定公路平面交點(diǎn)時(shí)，不能在選線區(qū)域隨機(jī)分布. 本文將主要針對(duì)這個(gè)問題，基于改進(jìn)的遺傳算法，構(gòu)建新的公路路線優(yōu)化模型，以實(shí)現(xiàn)公路智能選線，研究成果具有一定的實(shí)際意義.

1 遺傳算法在公路自動(dòng)選線中的應(yīng)用優(yōu)勢(shì)

1.1 自動(dòng)選線方法介紹

最初的自動(dòng)選線方法是指計(jì)算機(jī)輔助設(shè)計(jì)，由于只能是進(jìn)行一些單一的計(jì)算、輸入輸出數(shù)據(jù)的工作，在詳細(xì)優(yōu)化工作方面仍有待改進(jìn).

自動(dòng)選線方法的核心是智能運(yùn)算方法，智能運(yùn)算是指一系列學(xué)習(xí)和模擬自然界中生物結(jié)構(gòu)和行為，和自然現(xiàn)象、過程及其原理的各種方法[10]，自動(dòng)選線是指在人工確定公路起訖點(diǎn)和控制點(diǎn)的基礎(chǔ)上，借助計(jì)算機(jī)技術(shù)實(shí)現(xiàn)公路路線的自動(dòng)選擇和優(yōu)化.

1.2 遺傳算法的應(yīng)用優(yōu)勢(shì)

遺傳算法是模擬物種進(jìn)化論發(fā)展而來的智能優(yōu)化算法[10]. 遺傳算法不依賴精密的數(shù)學(xué)模型，依靠社會(huì)群體的內(nèi)在準(zhǔn)則實(shí)現(xiàn)方案?jìng)€(gè)體的優(yōu)化，特別適用于復(fù)雜問題的優(yōu)化求解. 主要解決設(shè)計(jì)變量選擇、編碼方法確定、遺傳算子及終止準(zhǔn)則設(shè)計(jì).

遺傳算法主要優(yōu)勢(shì)有3點(diǎn)：操作簡(jiǎn)單，算法實(shí)現(xiàn)比較容易；更符合公路選線的特點(diǎn)，公路自動(dòng)選線的實(shí)現(xiàn)比較容易；屬于隨機(jī)搜索算法，結(jié)合交叉和變異操作更能實(shí)現(xiàn)全局尋優(yōu)的目的.

1.3 遺傳算法步驟

通常情況下，使用遺傳算法進(jìn)行優(yōu)化運(yùn)算的過程可分為5個(gè)步驟：

步驟1編碼：把公路路線表示方式進(jìn)行編碼，每1個(gè)指標(biāo)就表示為1個(gè)基因，每1組基因串就代表1個(gè)路線方案.

步驟2初始種群：隨機(jī)生成n個(gè)基因型，即生成了n個(gè)路線方案，就構(gòu)成了初始種群.

步驟3適應(yīng)度值計(jì)算：計(jì)算新個(gè)體的適應(yīng)能力，以體現(xiàn)個(gè)體在種群中的優(yōu)劣程度，也是進(jìn)行選擇、交叉及變異操作的依據(jù).

步驟4遺傳操作：主要包括選擇、交叉和變異3種，選擇種群中適應(yīng)能力較好的個(gè)體，進(jìn)行交叉和變異操作，以產(chǎn)生具有新的基因型的個(gè)體，進(jìn)一步提高個(gè)體的適應(yīng)能力.

步驟5終止：遺傳算法的優(yōu)化尋優(yōu)是有盡頭的，為了防止優(yōu)化一直進(jìn)行下去，需要設(shè)定一定的終止條件，當(dāng)優(yōu)化迭代一定的次數(shù)或當(dāng)問題不能進(jìn)一步優(yōu)化時(shí)，就可終止程序的運(yùn)行. 遺傳算法的終止準(zhǔn)則應(yīng)該采用多種終止方式相結(jié)合的模式，以避免遺傳迭代過早結(jié)束或者無休止進(jìn)行下去.

2 公路路線優(yōu)化目標(biāo)函數(shù)模型

公路的自動(dòng)選線可認(rèn)為是：在選線區(qū)域內(nèi)，搜索滿足各種公路約束條件的路線方案，基于優(yōu)化數(shù)學(xué)模型，搜索確定工程費(fèi)用最低、安全條件高的公路路線方案. 想要實(shí)現(xiàn)公路自動(dòng)選線，處理好設(shè)計(jì)變量的選擇、約束條件及目標(biāo)函數(shù)是關(guān)鍵，公路路線方案的優(yōu)化需要綜合考慮多種影響因素，構(gòu)造一個(gè)完善、有效的目標(biāo)函數(shù)模型，避免遺漏優(yōu)秀公路路線方案. 通過對(duì)路線方案安全性評(píng)價(jià)、經(jīng)濟(jì)性評(píng)價(jià)及規(guī)范性約束3個(gè)方面建立路線優(yōu)化目標(biāo)函數(shù)模型，以比較公路路線方案的優(yōu)劣，確定各路線個(gè)體的適應(yīng)度值.

2.1 安全性評(píng)價(jià)

公路路線是公路建設(shè)的骨架，在選線過程中，不僅要滿足基本的規(guī)范要求，也要確保公路路線設(shè)計(jì)的安全性能，以保障人們生命安全. 設(shè)計(jì)速度是公路設(shè)計(jì)中的重要指標(biāo)，對(duì)于公路實(shí)現(xiàn)其安全迅捷、舒適的使用目的具有重要意義. 以公路線形速度一致性作為公路自動(dòng)選線安全性評(píng)價(jià)指標(biāo). 車輛的運(yùn)行速度是公路線形安全評(píng)價(jià)的一項(xiàng)重要指標(biāo)，是評(píng)價(jià)路線的速度協(xié)調(diào)性、平縱橫等技術(shù)指標(biāo)的重要標(biāo)準(zhǔn)，國外諸多學(xué)者都進(jìn)行了考慮運(yùn)行速度的公路安全性評(píng)價(jià)研究[11-13].

參考《公路項(xiàng)目安全性評(píng)價(jià)指南》的評(píng)價(jià)方法，評(píng)價(jià)指標(biāo)采用相鄰路段運(yùn)行速度的差值Δv85，評(píng)價(jià)標(biāo)準(zhǔn)見表1.

表1 運(yùn)行速度的差值標(biāo)準(zhǔn)

2.2 經(jīng)濟(jì)性評(píng)價(jià)

目標(biāo)函數(shù)的經(jīng)濟(jì)性是指公路建設(shè)總費(fèi)用[14]. 詳細(xì)數(shù)學(xué)表達(dá)見式(1)：

C=C1+C2+C3+C4+C5

(1)

式中，C為建設(shè)工程費(fèi)用；C1為征地費(fèi)用；C2為路基土石方工程費(fèi)用；C3為橋梁、涵洞及隧道建設(shè)工程費(fèi)用；C4為房屋拆遷費(fèi)用；C5為路面材料費(fèi)用.

2.3 規(guī)范約束

路線基本規(guī)范約束模型是公路選線過程中首先需要考慮的模型，是公路選線的基礎(chǔ)，即要求公路路線方案要滿足基本規(guī)范要求. 本文以《公路路線設(shè)計(jì)規(guī)范》(JTG D20—2017)作為基本要求，主要考慮公路平面約束、縱斷面約束及平縱組合約束.

3 遺傳算法在公路自動(dòng)選線中的應(yīng)用

3.1 設(shè)計(jì)變量選擇

設(shè)計(jì)變量是公路路線優(yōu)化過程中需要控制的變量. 在公路平縱線形設(shè)計(jì)中，需要確定平面交點(diǎn)位置、圓曲線半徑、豎曲線半徑、變坡點(diǎn)位置及變坡點(diǎn)高程5個(gè)指標(biāo). 為了便于研究，假設(shè)變坡點(diǎn)位置與平面交點(diǎn)位置重合，通過改變平面交點(diǎn)位置、圓曲線半徑、豎曲線半徑和變坡點(diǎn)高程來實(shí)現(xiàn)公路路線的自動(dòng)搜索與優(yōu)化.

3.2 遺傳編碼

根據(jù)公路自動(dòng)選線的問題和特點(diǎn)，選擇實(shí)數(shù)編碼方法. 對(duì)線路三維空間基因編碼進(jìn)行改進(jìn)，平面交點(diǎn)采取隨機(jī)分布，先生成平、縱斷面基因片段，再組合形成整體公路路線表達(dá)基因，以完成公路路線基因編碼的全過程.

圖1 遺傳編碼程序示意圖

3.3 生成初始種群

路線方案初始種群是指一系列滿足規(guī)范要求和安全要求的路線方案組合，是路線優(yōu)化的初始狀態(tài). 首先根據(jù)基因編碼方法生成一串基因序列構(gòu)成一個(gè)路線方案?jìng)€(gè)體；再生成一定數(shù)量的方案?jìng)€(gè)體構(gòu)成初始種群. 生成流程見圖2：

圖2 初始種群生成流程圖

3.4 適應(yīng)度函數(shù)

遺傳算法的適應(yīng)度值是表示某一個(gè)體對(duì)環(huán)境的適應(yīng)能力，也表示該個(gè)體優(yōu)秀性能被選擇的能力. 由于公路路線方案之間的目標(biāo)函數(shù)值差異有限，適應(yīng)度值計(jì)算采用公式f(x)=cmax-g(x)計(jì)算，公路路線方案的適應(yīng)度值越大，則該方案被選擇的概率就越大. 適應(yīng)度值計(jì)算程序示意如圖3：

圖3 適應(yīng)度值計(jì)算

3.5 遺傳操作

遺傳操作主要包括選擇、交叉和變異3種操作，是實(shí)現(xiàn)尋優(yōu)的主要手段. 選擇的目的是把父代的優(yōu)秀基因傳遞給子代個(gè)體，可通過輪盤賭模型實(shí)現(xiàn)選擇操作. 基于遺傳算法的交叉運(yùn)算，交換2個(gè)父代個(gè)體的部分基因片段，在整個(gè)選線區(qū)域內(nèi)，不斷產(chǎn)生新的路線方案. 變異是一種基本的遺傳操作，通過隨機(jī)改變父代個(gè)體的某一基因片段，以產(chǎn)生新的路線方案，可提高遺傳算法對(duì)整個(gè)空間的搜索能力.

圖4 遺傳操作流程圖

在遺傳操作的過程中，需要特別注意的是遺傳操作點(diǎn)位的選取，雖然理論上講，遺傳算法的操作點(diǎn)位是可在任意位置的，結(jié)合公路選線的實(shí)際情況，在公路自動(dòng)選線過程中，路線的起訖點(diǎn)是已定的，要求在優(yōu)化的時(shí)候不能改變起訖點(diǎn)位置，因此在交叉操作是需要把起訖點(diǎn)的位置基因片段及高程基因片段除外. 本文采用的方法是把所有的基因片段進(jìn)行排序，在進(jìn)行遺傳操作點(diǎn)位選擇的時(shí)候，首先判斷選擇的是否為起訖點(diǎn)相關(guān)基因片段，只有選擇非起訖點(diǎn)相關(guān)基因片段才可進(jìn)行交叉、變異操作.

4 算例分析

通過公路選線方法與遺傳算法相結(jié)合，實(shí)現(xiàn)公路自動(dòng)選線，為了提高研究成果的可信度，更好地為我國公路自動(dòng)選線工程服務(wù)，本文進(jìn)行實(shí)際工程案例分析，實(shí)現(xiàn)基于遺傳算法的公路自動(dòng)選線. 選線區(qū)域等高線圖如圖5所示，路線起訖點(diǎn)坐標(biāo)分別為：(477 772.985，320 625.085 6)、(478 204.230 4，321 791.855 7).

圖5 選線區(qū)域等高線圖

4.1 參數(shù)設(shè)定

基礎(chǔ)參數(shù)是與公路等級(jí)要求、程序運(yùn)行狀態(tài)直接相關(guān)的公路選線技術(shù)指標(biāo)，需要在公路自動(dòng)選線程序運(yùn)行之前就確定. 根據(jù)公路等級(jí)不同，參考公路設(shè)計(jì)相關(guān)標(biāo)準(zhǔn)，路線平縱橫斷面設(shè)計(jì)參數(shù)見表2.

表2 公路基本參數(shù)表

4.2 選線結(jié)果分析

通過基于遺傳算法的公路自動(dòng)選線程序的運(yùn)行，實(shí)現(xiàn)了公路路線方案的搜索與優(yōu)化. 主要體現(xiàn)在路線長度變化和工程總費(fèi)用變化上. 公路自動(dòng)選線過程中的每一代最優(yōu)路線方案相關(guān)技術(shù)指標(biāo)輸出見表3.

表3 公路逐代優(yōu)化技術(shù)指標(biāo)表

通過運(yùn)行程序，輸出路線優(yōu)化圖見圖6，路線長度變化圖見圖7，工程總費(fèi)用圖見圖8.

圖8 建設(shè)總費(fèi)用迭代圖

從圖6可看出：經(jīng)過100代的迭代優(yōu)化，公路路線方案有了明顯的優(yōu)化. 從圖7可看出，公路路線長度呈逐代下降趨勢(shì)，說明遺傳算法在公路自動(dòng)選線中的應(yīng)用是基本成功的. 公路路線優(yōu)化過程可分為3個(gè)階段：快速優(yōu)化期(1～20代)，緩慢優(yōu)化期(20～60代)，穩(wěn)定優(yōu)化期(60代以后). 說明迭代

圖6 路線優(yōu)化示意圖

圖7 路線長度迭代圖

初期公路路線迅速優(yōu)化，迭代中期優(yōu)化速度減緩，迭代末期優(yōu)化速度趨于平緩，最后保持不變，實(shí)現(xiàn)路線最優(yōu)化選擇. 從圖8可看出，公路路線的工程總費(fèi)用變化趨勢(shì)與路線長度變化基本相似，工程總費(fèi)用的變化更能體現(xiàn)遺傳算法應(yīng)用于公路自動(dòng)選線中的優(yōu)勢(shì).

5 結(jié)束語

在分析國內(nèi)外遺傳算法在公路自動(dòng)選線應(yīng)用理論方法的基礎(chǔ)上，重點(diǎn)改進(jìn)了交點(diǎn)在整個(gè)選線區(qū)域的自動(dòng)尋優(yōu)，并且增加了安全性指標(biāo)的約束條件，提出了一種基于遺傳算法的公路自動(dòng)選線新方法. 以MATLAB為實(shí)驗(yàn)平臺(tái)，模擬公路路線自動(dòng)尋優(yōu)，可優(yōu)化選出公路路線方案，說明該方法可行. 論文提出的自動(dòng)選線方法較以往研究成果具有3個(gè)方面的優(yōu)勢(shì)：

1)基于遺傳算法的公路自動(dòng)選線方法，克服了以往公路自動(dòng)選線過程中平面交點(diǎn)只能在某一剖切面上變化的局限，實(shí)現(xiàn)了對(duì)整個(gè)選線區(qū)域內(nèi)的公路路線方案的自動(dòng)尋優(yōu).

2)在滿足基本公路路線設(shè)計(jì)規(guī)范的基礎(chǔ)上，將公路線形一致性的安全性評(píng)價(jià)指標(biāo)，引入公路自動(dòng)選線過程中，提高了公路自動(dòng)選線的安全性.

3)以公路工程造價(jià)作為評(píng)價(jià)標(biāo)準(zhǔn)，把公路路線優(yōu)化問題轉(zhuǎn)化為以公路工程造價(jià)為導(dǎo)向的優(yōu)化問題. 建立了以經(jīng)濟(jì)評(píng)價(jià)指標(biāo)為基礎(chǔ)的公路自動(dòng)選線優(yōu)化模型，保證了自動(dòng)選擇方案的經(jīng)濟(jì)性.