李榮娜 張 喜

（北京交通大學(xué)交通運輸學(xué)院 北京100044）

0 引 言

列車運行調(diào)整是指在列車運行工作中，因各種因素和突發(fā)事件的影響，使得列車運行的實際狀態(tài)偏離預(yù)定值，需要對列車運行方案重新鋪劃，以盡可能小的代價，盡快地恢復(fù)列車的有序運行狀態(tài)［1］。隨著科學(xué)技術(shù)的進步，國內(nèi)外有許多學(xué)者都注重依托先進的系統(tǒng)來研究列車運行調(diào)整問題，以期實現(xiàn)調(diào)度指揮的自動化。

目前，學(xué)者和專家針對列車運行調(diào)整問題提出了數(shù)學(xué)規(guī)劃、模擬仿真和人工智能等多種模型與算法。張翠平等根據(jù)圖論模型的理論建立了列車運行調(diào)整問題的線性規(guī)劃模型，并采用改進的啟發(fā)式算法進行求解［2］。啟發(fā)式算法求解速率較快，但對于求解多目標(biāo)函數(shù)時，效果就不太理想。陳雍君以貨運鐵路為研究對象，建立了以列車旅行平均時間最少為優(yōu)化目標(biāo)函數(shù)的區(qū)間列車沖突調(diào)整模型，在求解時使用了序優(yōu)化方法，減少了計算量［3］。

而在列車運行調(diào)整問題中，遺傳算法是1種可以很好地模擬列車運行調(diào)整過程的算法，一些學(xué)者也進行了研究。但是由于遺傳算法本身存在的問題，如收斂速度較慢、易出現(xiàn)早熟等，有時候不能獲得最優(yōu)的結(jié)果。而免疫遺傳算法是將免疫算法與遺傳算法相結(jié)合產(chǎn)生的1種方法，可在很大程度上避免遺傳算法中的早熟現(xiàn)象，從而快速找到全局最優(yōu)解。

1 列車運行調(diào)整的數(shù)學(xué)模型

選擇了雙線自動閉塞的線路，并以該調(diào)度區(qū)段單方向的運行調(diào)整問題為例進行研究。為了精確地構(gòu)造和描述模型，建立以下的相關(guān)變量：

M－調(diào)度區(qū)段內(nèi)的車站總數(shù)；

N－調(diào)度區(qū)段內(nèi)列車總數(shù)；

Qi，j－列車i在車站j的起車附加時分；

Ti，j－列車i在車站j的停車附加時分；

I－最小追蹤列車間隔時間；

Si，j－列車i在車站j的最小作業(yè)標(biāo)準(zhǔn)時間；

Dj－車站j可供使用的到發(fā)線數(shù)量；

列車運行調(diào)整的模型建立包括2部分：①目標(biāo)函數(shù)的建立；②約束條件的確定。

1.1 列車運行調(diào)整目標(biāo)函數(shù)的建立

列車運行調(diào)整的目的就是使偏離列車運行圖的列車盡快恢復(fù)按圖行車。因此，以與列車運行圖的偏差最小為優(yōu)化目標(biāo)［4］。具體的調(diào)整模型如下

式中：wi為列車i的權(quán)重因子，wi越大，說明列車的等級級別越高。

1.2 列車運行調(diào)整約束條件的模型化

列車運行調(diào)整問題是1個約束條件眾多的組合優(yōu)化問題，所產(chǎn)生的調(diào)整計劃必須滿足一定的約束條件，才可以執(zhí)行最后求解得到的調(diào)整計劃。

列車運行調(diào)整必須滿足的約束條件如下。

1）區(qū)間運行時分約束。根據(jù)列車在區(qū)間的運行時間不得小于區(qū)間規(guī)定的最小運行時這一規(guī)定，有

2）追蹤間隔時間約束。在區(qū)間內(nèi)追蹤運行的2列列車之間需要滿足最小追蹤間隔時間的約束，即

式中：i為k的后行列車。

3）車站停車時分約束。列車i在車站j的作業(yè)時間不得小于規(guī)定的在該車站的最小作業(yè)時間，該約束條件為

式中：ri，j為列車i在車站j的通過和停站情況，可以定義為

4）發(fā)車時間約束。根據(jù)發(fā)車時間不得早于計劃發(fā)車時間，有

5）到發(fā)線約束條件。由于1個車站可以使用的到發(fā)線的數(shù)目都是固定的，因此列車實際的到發(fā)線使用數(shù)目不應(yīng)該大于車站總的到發(fā)線數(shù)量。首先，引用一函數(shù)，在t時刻，令

則到發(fā)線的約束條件為

6）越行約束。如果列車在車站發(fā)生越行，就需要滿足

2 基于免疫遺傳算法的列車運行調(diào)整算法

2.1 算法介紹

遺傳算法是以自然界中的生物進化過程為背景，將生物進化過程中的繁殖、選擇、交叉、變異和競爭等概念引入算法中［5］。它一般包括以下幾個步驟，首先，對問題的解進行編碼，并產(chǎn)生編碼后的初始種群；根據(jù)優(yōu)化問題的目標(biāo)函數(shù)來制定適應(yīng)度函數(shù)；然后，根據(jù)適應(yīng)度函數(shù)值挑選個體參與遺傳操作；最后，按照優(yōu)勝劣汰和適者生存的生物學(xué)原理逐代進行衍化，直至得到問題的最優(yōu)解或近似最優(yōu)解。遺傳算法具有自組織性、自適應(yīng)性、并行性、過程性、不確定性等特點。這些特點使得遺傳算法在優(yōu)化問題中得到了極為成功的應(yīng)用。但是，它也存在一些不足，如遺傳算法的局部搜索能力很差，并極容易出現(xiàn)早熟現(xiàn)象，從而導(dǎo)致算法的收斂性降低［6］。

為克服遺傳算法存在的缺陷，將免疫系統(tǒng)的相關(guān)理論引入到遺傳算法的框架里，提出了1種新的算法——免疫遺傳算法。免疫遺傳算法是在遺傳算法的基礎(chǔ)上，借鑒生物免疫系統(tǒng)自適應(yīng)識別和排除侵入生物體內(nèi)的抗原性異物的功能，將生物免疫系統(tǒng)的學(xué)習(xí)、記憶、抗體多樣性的特點引入遺傳算法而得［7］。在實際問題中，免疫遺傳算法將求解問題的目標(biāo)函數(shù)對應(yīng)于入侵生命體的抗原，問題的解對應(yīng)為免疫系統(tǒng)產(chǎn)生的抗體，并通過一系列遺傳操作及抗體親和度的計算，在保持抗體多樣性的基礎(chǔ)上，找出針對問題的最優(yōu)解［7］。總而言之，免疫遺傳算法既保留了遺傳算法隨機全局并行搜索的特點，又在很大程度上避免過早收斂，確保收斂于全局最優(yōu)解。

相較于遺傳算法，免疫遺傳算法具有以下特點［8］。

1）通過個體濃度評價可以對抗體進行促進和抑制，很好地保持了抗體的多樣性，這樣，能夠增強算法的全局搜索能力，從而使算法收斂更快。

2）具有免疫記憶功能，該功能是免疫遺傳算法的1個重要特色，可以使系統(tǒng)在處理同類問題時，使用記憶庫中的個體作為初始群體，這樣加快搜索速度，迅速收斂到全局最優(yōu)解。

3）具有自我調(diào)節(jié)功能，可以提高局部搜索能力。

2.2 免疫遺傳算法設(shè)計

1）編碼設(shè)計。列車運行調(diào)整問題的解就是列車的運行時刻，因此采用實數(shù)編碼，能夠省去推算的過程，直接求得結(jié)果，簡便可行。定義從午夜零點到某個時刻所經(jīng)過的秒數(shù)代表現(xiàn)實中的相應(yīng)時刻，如，6000代表著01：40：00。

文中的編碼格式為：xk＝（，，…，），其長度為M×N×2。

2）適應(yīng)度函數(shù)設(shè)計。適應(yīng)度函數(shù)是衡量遺傳算法中解的好壞的1種標(biāo)準(zhǔn)，個體的適應(yīng)度值越大，表明解的性能越優(yōu)。在遺傳算法中，適應(yīng)度函數(shù)一般是目標(biāo)函數(shù)，為了便于操作，一般要求適應(yīng)度值非負，而且適應(yīng)度值增大方向必須對應(yīng)目標(biāo)函數(shù)優(yōu)化的方向。因此，筆者設(shè)計的適應(yīng)度函數(shù)如下。

式中：Cmax為事先設(shè)定的一較大正數(shù)。

算法必須考慮對約束條件的處理，筆者采用罰函數(shù)法進行處理，即對解空間中無對應(yīng)可行解的個體在計算適應(yīng)度值時增加一個罰函數(shù)，降低該個體遺傳到下一代的概率。第1個約束條件進行罰函數(shù)處理的過程如下

式中：P為一正數(shù)。

剩余的約束條件可依次進行，則經(jīng)過罰函數(shù)方法處理得到的新的適應(yīng)度函數(shù)為

3）抗體濃度。抗體和抗體之間的親和力反映了抗體之間的相似程度，此處借鑒由Forrest等提出的R位連續(xù)方法計算抗體與抗體之間的親和力［9］。即

式中：ki，j為抗體i和j中相同的位數(shù)；L為抗體的長度。

親和力越大，表明2個抗體之間的相似程度越高，當(dāng)種群進入下一代時，親和力大的抗體將會大肆繁殖，但是如果相似抗體太多，為了防止算法在小范圍內(nèi)進行復(fù)制，使得算法收斂于局部解，就要抑制它們的再繁殖，從而保證算法求解的范圍比較廣。選用濃度來決定抗體的促進和抑制。設(shè)Ci為抗體i的濃度，則濃度定義為

其中：τ為預(yù)先設(shè)定的閾值，一般取值范圍為［0.9，1］.

4）抗體的抑制和促進。免疫遺傳算法的選擇概率不僅與個體的適應(yīng)度有關(guān)，而且與抗體的濃度有關(guān)［6］。這是免疫遺傳算法區(qū)別于遺傳算法的1個重要特色。設(shè)抗體i的期望繁殖率為P，則其選擇復(fù)制的概率為

式中：α為常數(shù)。由上式可見，個體適應(yīng)度越高，則期望繁殖概率越大；個體濃度越大，則期望繁殖概率越小。這樣既鼓勵了適應(yīng)度高的個體，同時抑制了濃度高的個體，從而確保了個體多樣性［9］。

5）選擇操作。選擇：按照輪盤賭選擇機制和精英保留策略相結(jié)合的方式進行選擇操作。精英保留策略是指群體中適應(yīng)度最高的個體不進行交叉操作與變異操作，直接遺傳到下1代種群中，目的是為了保證群體收斂到最優(yōu)解。

輪盤賭選擇是基于適者生存這一思想，按照期望繁殖概率進行選擇。

6）交叉操作。是指從種群中選取2個個體，通過2個染色體的交換組合，從而產(chǎn)生下1代的新的個體。由于采用的是實數(shù)編碼，因此采用實數(shù)交叉法，即染色體xi和染色體xj在隨機選取的k基因位上進行基因交換，用數(shù)學(xué)公式可以描述為

式中：b為隨機數(shù)。

7）變異操作。變異操作是算法中很重要的一步，筆者采用混合變異算法，即采用基于實數(shù)編碼的非均勻變異與邊界變異法進行變異操作。將進化代數(shù)T分為2個階段，當(dāng)進化到當(dāng)前代數(shù)t時，若0＜t＜T／2，時，采用非均勻變異算法，否則采用邊界變異法。這樣混合的變異方式可以提高算法的收斂速度，使算法盡快收斂于全局最優(yōu)解。

2.3 免疫遺傳算法的基本步驟

在上述內(nèi)容的基礎(chǔ)上，得到基于免疫遺傳算法（調(diào)整算法）的步驟如下。

1）輸入抗原。輸入目標(biāo)函數(shù)和各種約束條件，作為抗原。

2）產(chǎn)生初始抗體群。把抗體定義為列車運行調(diào)整問題的可行解，在解空間上，隨機生成一定數(shù)目的個體。

3）計算適應(yīng)度和濃度。計算抗體群中的適應(yīng)度和濃度。

4）記憶細胞。先將適應(yīng)度最高的若干個體放入記憶庫中，再按照期望繁殖率將剩余的抗體選入記憶庫，這些記憶庫中的個體可以直接傳遞到下1代中。

5）抗體的抑制和促進。在免疫遺傳算法中，適當(dāng)?shù)夭捎靡种撇呗砸员３址N群中抗體的多樣性，在構(gòu)造選擇概率時，綜合考慮適應(yīng)度和濃度來實現(xiàn)。

6）新群體的產(chǎn)生。通過遺傳操作，產(chǎn)生新1代的抗體。

7）終止條件判斷。若滿足終止條件，則輸出結(jié)果，否則返回到步驟3）。

3 實例分析

以某雙線自動閉塞鐵路12：00～16：00時的10輛列車為例。在算法運行中，比較重要的參數(shù)有：交叉概率，變異概率，迭代次數(shù)，種群規(guī)模最大迭代次數(shù)等［10］。經(jīng)過反復(fù)試驗，本例參數(shù)設(shè)置為：迭代次數(shù)maxgen＝200，種群規(guī)模sizepop＝30，記憶庫容量overbest＝10，交叉概率pcross＝0.8，變異概率pmutation＝0.1，多樣性評價參數(shù)α＝0.9，濃度閾值τ＝0.9。應(yīng)用免疫遺傳算法進行計算，并將其與遺傳算法的運行過程進行對比，結(jié)果見圖1和圖2。

由此可以看出，免疫遺傳算法在40多代進行收斂，而遺傳算法在60多代后曲線才收斂，顯然，免疫遺傳算法收斂速度較快。此外，免疫遺傳算法收斂到最優(yōu)解，而遺傳算法只收斂到次優(yōu)解，這說明免疫遺傳算法能搜索到更優(yōu)結(jié)果。

在進行試驗時，同時對2種算法試驗20次，發(fā)現(xiàn)遺傳算法試驗成功率僅為70%，而免疫遺傳算法能達到100%。

綜上所述，免疫遺傳算法在收斂速度，最優(yōu)值以及試驗成功率方面都具有更為優(yōu)越的特性。

圖1 免疫遺傳算法收斂曲線Fig.1 The convergence curve of the immune genetic algorithm

圖2 遺傳算法收斂曲線Fig.2 The convergence curve of the genetic algorithm

4 結(jié)束語

針對遺傳算法在運用中存在的不足，選用1種免疫遺傳算法進行列車運行調(diào)整問題的求解。列車運行調(diào)整模型的建立，突出了以偏離運行圖最小為目標(biāo)函數(shù)的特點，并充分考慮了區(qū)間運行時分、車站停車時分約束、越行約束等條件，在此基礎(chǔ)上設(shè)計了免疫遺傳算法的各個步驟。其中，適應(yīng)度函數(shù)進行了罰函數(shù)方法處理，親和度采用了不同于信息熵的R位連續(xù)方法進行計算，選擇操作則是綜合了輪盤賭選擇機制和精英保留策略的方式，變異操作采用了混合的變異方式進行操作。仿真結(jié)果表明，免疫遺傳算法在收斂速度，最優(yōu)值甚至試驗成功率方面都具有更好的性能。

［1］ 李志宏.列車運行智能調(diào)整系統(tǒng)相關(guān)問題研究［D］.成都：西南交通大學(xué)，2006.

［2］ 張翠平，曹成鉉.列車運行調(diào)整的圖論模型與啟發(fā)式算法［J］.科學(xué)技術(shù)與工程，2010，10（10）：2560－2564.

［3］ 陳雍君.基于序優(yōu)化方法的列車運行調(diào)整算法研究［J］.鐵道學(xué)報，2010，32（3）：1－8.

［4］ 梁 旭，黃 明.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用［M］.北京：電子工業(yè)出版社，2011.

［5］ 豆雯雯.基于免疫蟻群算法列車運行調(diào)整模型的優(yōu)化與研究［D］.蘭州：蘭州交通大學(xué)，2012.

［6］ 劉泉叮.基于免疫遺傳算法的OD矩陣反推模型與算法［D］.重慶：重慶大學(xué)，2010.

［7］ 莫 軍.基于免疫遺傳算法的水下無人平臺航路規(guī)劃［J］.艦船科學(xué)技術(shù)，2012，34（9）：76－78.

［8］ 王宏剛，張 琦等.基于遺傳算法的高速鐵路行車調(diào)整模型［J］.中國鐵道科學(xué)，2006，27（3）：96－100.

［9］ 史 峰.Matlab智能算法30個案例分析［M］.北京：北京航空航天大學(xué)出版社，2011.

［10］ 趙勝武，趙建武，林 楊.基于免疫遺傳算法的公交線網(wǎng)優(yōu)化研究［J］.交通信息與安全，2009，27（6）：43－47.