一種基于遺傳算法的進路搜索算法

張文泉 余立建

在鐵路車站作業(yè)中，進路選排對接發(fā)車作業(yè)的效率和車站通過能力有著直接影響，如何高速有效地選排接發(fā)列車和調(diào)車作業(yè)進路，是保證行車安全和提高行車效率的重要內(nèi)容。

在計算機聯(lián)鎖的進路選排中，進路搜索的方法有很多種。最常見的有鏈表法、二叉樹搜索法等。近年來智能優(yōu)化算法在求解路徑優(yōu)化等問題方面顯示了較強的優(yōu)勢，所以也可以采用智能算法來進行進路搜索。本文就提出了一種基于遺 傳 算 法 （genetic algorithm，簡稱GA）的進路搜索算法，這種方法以遺傳算法為核心，具有快速、準確的特點，能夠有效地進行進路搜索。

1 站場數(shù)據(jù)結(jié)構(gòu)分析

為了簡化建模過程，本文只考慮列車進路選排，暫不考慮調(diào)車進路選排，下面以 《6502電氣集中電路》中的一個典型站場簡化圖為例進行分析和建模。如圖1所示。

圖1 站場平面圖

首先需要簡化站場圖，將站場圖以節(jié)點的形式進行描述。因進路選排過程中，主要需要考慮信號機、軌道區(qū)段和道岔，將信號機、軌道區(qū)段以及道岔都作為站場圖節(jié)點，并進行統(tǒng)一定義。對于圖1所示站場，按照由下向上、由左向右的順序?qū)?jié)點依次進行奇數(shù)編號。由于信號機、道岔以及軌道區(qū)段在位置上可能重復(fù)，所以為了避免重復(fù)定義節(jié)點，在定義過程中先選擇道岔作為節(jié)點，再選擇軌道區(qū)段，最后再考慮信號機。對于一條進路，各個節(jié)點的前后連接關(guān)系十分重要，所以采用數(shù)據(jù)結(jié)構(gòu)圖表示整個站場，圖1站場的數(shù)據(jù)結(jié)構(gòu)圖如圖2所示。

圖2中，k1，k3…均表示當前節(jié)點的編號；pf1表示水平方向上所連接的前一節(jié)點的編號，pf2表示渡線方向上所連接的前一節(jié)點的編號，若不存在則賦值為0。

圖2 數(shù)據(jù)結(jié)構(gòu)圖

2 進路搜索的遺傳算法建模

2．1 編碼與染色體

根據(jù)節(jié)點取值特點，選取二進制編碼。在遺傳算法中，一條特定的進路可以表示成一條染色體，將一組染色體放入到問題環(huán)境中，通過適者生存的規(guī)則選擇出適合環(huán)境的個體進行遺傳。Ki表示一條特定的進路，即是一條染色體，Ki＝ ｛ki1，ki2，…kin｝。

當站場數(shù)據(jù)結(jié)構(gòu)圖確定后，節(jié)點數(shù)也就隨之確定。在進路選排過程中，如果讓節(jié)點ki為1表示選中、為0表示未選中，則 ｛k1，k2，…kn｝就可以表示一條搜索出的進路。于是進路搜索的問題就可以抽象成在眾多的解Ki＝｛ki1，ki2，…kin｝中選擇最優(yōu)解的問題。

2．2 進路搜索的遺傳操作

設(shè)K為進路搜索的集合，算法初始狀態(tài)的進路搜索集合作為初始種群，在大小為m的初始種群中，Ki表示第i個染色體。遺傳算法的基本流程見圖3。

在整個遺傳算法過程中，主要進行三個遺傳操作，分別是復(fù)制操作 （選擇）、交叉操作和變異操作。復(fù)制操作是根據(jù)每個個體的適應(yīng)度大小進行優(yōu)勝劣汰，將適應(yīng)度更高的遺傳到下一代。本文采用輪盤賭的方法，即將所有個體的適應(yīng)度求和作為分母，每個個體自身的適應(yīng)度作為分子，按比例進行選擇。因此，每個個體被選擇的概率為

圖3 遺傳算法流程圖

交叉操作是選擇父代中2個個體，將這2個個體的某一段進行交換得到新的2個個體，本文采用單點交叉。變異操作是對單個個體進行的操作，在單個個體的某個基因上按照某個較小的概率進行取反操作，使之產(chǎn)生新的個體，從而改善進路搜索能力。

2．3 適應(yīng)度函數(shù)

一個個體若能夠構(gòu)成一條合理的進路，則從始端節(jié)點到終端節(jié)點需依次相連。即一個個體中去除為0的信息后組成新的子集，該子集所包含的節(jié)點應(yīng)連續(xù)。此時，各個節(jié)點的節(jié)點編號并不發(fā)生變化，用一個新的數(shù)組n表示。例如，某個個體K為 ｛0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0｝，對應(yīng)的節(jié)點編號為 ｛1，3，5，…41，43｝，個體K去除0信息后組成新的子集 K′ 為 ｛1 1 1 1 1 1 1 1｝，對應(yīng)的節(jié)點編號為 ｛3，7，9，15，21，23，29，35｝，記作數(shù)組n。

另外，同一組始端和終端節(jié)點之間可能存在著多條進路，因此還需要處理多余的變更進路。根據(jù)如上分析，確定了優(yōu)化目標為

其中，fni表示節(jié)點kni的pf1值，f′ni表示節(jié)點kni的pf2值，ni表示個體去除0信息后組成子集的節(jié)點編號；m表示子集長度；kj表示節(jié)點取值，j表示節(jié)點編號；s表示始端節(jié)點編號；e表示終端節(jié)點編號。上式中的第一項表示能否構(gòu)成合理進路，第二項表示去除多余變更進路。

3 進路搜索模型改進

雖然建立了基于遺傳算法的進路搜索模型，但是要將這種模型應(yīng)用到實際的進路選排過程中，還需要考慮信號燈的變化以及道岔的轉(zhuǎn)動。因此，必須對上述的基本模型進行改進。

首先在一個站場中，每一架列車信號燈均對應(yīng)一個股道區(qū)段，以圖1站場圖為例就有如表1所示的對應(yīng)關(guān)系。

因此，當該股道區(qū)段所對應(yīng)節(jié)點為始端節(jié)點時，則該股道區(qū)段所對應(yīng)的列車信號機由紅燈狀態(tài)變?yōu)榫G燈狀態(tài)，即信號開放。其次，當選定節(jié)點時，相應(yīng)節(jié)點所對應(yīng)的道岔需要進行動作。為了便于道岔動作的判斷，對前面的數(shù)據(jù)結(jié)構(gòu)進行改進，加入一項新的數(shù)據(jù)L，即節(jié)點所在的股道編號，如圖4所示。

圖4 改進的單節(jié)點數(shù)據(jù)結(jié)構(gòu)

其中，L（k3）＝0，即節(jié)點k3所在的股道編號為0。在整個站場中，L（i）表示節(jié)點ki所在股道的編號。在搜索到一條進路以后，進路中所有節(jié)點的前后節(jié)點隨之確定。此時，若L（i）≠L（i－1）或者L（i）≠L（i＋1），則節(jié)點ki所對應(yīng)的道岔需要轉(zhuǎn)動。

表1 股道與信號燈對應(yīng)關(guān)系

4 實例仿真分析

以圖1站場為例，可以選擇任意一條列車進路進行選排。下面以北京方向下行至5G接車進路的選排為例進行仿真分析。

步驟1：依次按下始端按鈕 （XJA）和終端按鈕 （S5LA）。此時，對應(yīng)的進路搜索起始節(jié)點和終止節(jié)點被確定，分別是k3和k43，參見圖2。

步驟2：利用遺傳算法搜索列車進路。遺傳算法參數(shù)分別為，群體規(guī)模取80，交叉概率pc取0．6，突變概率pm取0．1。仿真結(jié)果如圖5所示。

顯然，在迭代32次以后適應(yīng)度F達到最大值且不再變化，此時F＝1．0149。得到的最優(yōu)個體為 ｛0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1｝，對應(yīng)的最優(yōu)進路節(jié)點為k3－k7－k11－k17－k19－k27－k43。經(jīng)多次試驗表明，遺傳算法的初始種群均隨機產(chǎn)生，收斂速度也隨之變化，但均能在一定的迭代次數(shù)后收斂。

步驟3：相應(yīng)道岔的轉(zhuǎn)動。根據(jù)數(shù)據(jù)結(jié)構(gòu)可知，搜索到的節(jié)點確定以后，相對應(yīng)道岔關(guān)系也隨之確定，如表2所示。

步驟4：開放信號燈。信號燈的開放和始端按鈕 （或起始節(jié)點）所在股道區(qū)段相關(guān)，由于此時的搜索起始節(jié)點k3所對應(yīng)的股道區(qū)段是IAG，由表1可知，需開放信號燈X。

至此，整個進路選排完畢，X信號機開放。

值得注意的是在遺傳算法的計算過程中，有時會陷入局部最優(yōu)從而影響最終結(jié)果，為了避免這種情況的發(fā)生，可以對遺傳算法進行改進。同時也可以采用冗余計算的方法，比較選取最優(yōu)結(jié)果，防止局部最優(yōu)解的出現(xiàn)。

圖5 遺傳算法仿真結(jié)果

5 總結(jié)

通過對站場圖進行數(shù)據(jù)結(jié)構(gòu)分析，在此基礎(chǔ)上提出了一種基于遺傳算法模型的進路選排算法。通過仿真證明，這種進路選排算法可以簡單便捷的搜索出一條合理的進路，是一種具有可行性的進路選排算法。

表2 道岔轉(zhuǎn)動關(guān)系

［1］ 何文卿．6502電氣集中電路［M］．北京：中國鐵道出版社，2011．

［2］ 陳志穎，董昱，楊柳，李亮．計算機聯(lián)鎖進路搜索算法的分析與研究［J］．鐵路通信信號，2007．4，43（4）：4．

［3］ 陳榮武，劉莉，郭進．基于遺傳算法的列車運行能耗優(yōu)化算法［J］．交通運輸工程學(xué)報，2012．2，12（1）：111－112．