基于免疫粒子群算法的閉塞分區(qū)劃分優(yōu)化設(shè)計(jì)

康 寧，陳永剛，林俊亭，曹 巖

(1.蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院，蘭州 730070;2.蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 730070)

目前，我國(guó)鐵路線路里程正在不斷的增加，同時(shí)要保證在自動(dòng)閉塞制式下，不同列車在通過(guò)相隔數(shù)個(gè)閉塞分區(qū)時(shí)，能實(shí)現(xiàn)同一區(qū)間內(nèi)的安全追蹤運(yùn)行。列車相隔分區(qū)數(shù)目越少，追蹤間隔時(shí)間則越短。而根據(jù)列車扣除系數(shù)經(jīng)驗(yàn)公式，追蹤間隔時(shí)間越短，列車通過(guò)能力就越大［1］。因此，為了保證行車安全，提高列車運(yùn)輸能力，需要對(duì)閉塞分區(qū)劃分問題進(jìn)行進(jìn)一步的優(yōu)化。

近年來(lái)，在閉塞分區(qū)劃分問題研究方面，有關(guān)學(xué)者都取得了一定的成果。國(guó)外學(xué)者曾使用梯度搜索算法［3］、DE(differential evolution)算法［4］、遺傳算法［5］、最大-最小蟻群算法［6］等人工智能算法針對(duì)城市軌道交通系統(tǒng)進(jìn)行了閉塞分區(qū)的劃分研究;而在國(guó)內(nèi)方面，2011年劉劍鋒等人對(duì)準(zhǔn)移動(dòng)閉塞方式下列控系統(tǒng)為CTCS2級(jí)的鐵路區(qū)間通過(guò)信號(hào)機(jī)布置設(shè)計(jì)了啟發(fā)式仿真算法［7］;衛(wèi)和君通過(guò)對(duì)人控駕駛模式下列車追蹤間隔時(shí)間的計(jì)算方法，實(shí)現(xiàn)了對(duì)客運(yùn)專線CTCS-3級(jí)列控系統(tǒng)的閉塞分區(qū)劃分［8］。但這些研究都很少將優(yōu)化算法應(yīng)用于干線鐵路自動(dòng)閉塞分區(qū)劃分中，干線鐵路所要考慮的約束條件更多且更為復(fù)雜。而免疫粒子群算法通過(guò)按比例復(fù)制高親和度抗體，添加變異算子，為新個(gè)體產(chǎn)生提供途徑，增加了種群多樣性，可實(shí)現(xiàn)閉塞分區(qū)快速、準(zhǔn)確劃分。

1 閉塞分區(qū)劃分模型

1.1 模型定義

如圖1所示，設(shè)兩站間信號(hào)機(jī)的架數(shù)Nsignal，每架信號(hào)機(jī)的位置為 xi(i=1，2，…，Nsignal);x0、xNsignal+1分別為兩車站間出站信號(hào)機(jī)、進(jìn)站信號(hào)機(jī)的位置坐標(biāo)，則計(jì)算閉塞分區(qū)長(zhǎng)度是

圖1 變量定義描述

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

閉塞分區(qū)劃分問題是在保證行車安全及具體施工要求的約束條件下，找出劃分節(jié)點(diǎn)，求得最短追蹤間隔。它是一個(gè)復(fù)雜的多目標(biāo)多約束問題，為此，本文建立兩種策略下的劃分模型。

“效率”策略是指在列車制動(dòng)距離和閉塞分區(qū)有效長(zhǎng)度滿足的情況下，通過(guò)最小化追蹤列車間隔時(shí)間得到最大的列車通過(guò)能力，進(jìn)而提高自動(dòng)閉塞區(qū)段上的列車運(yùn)行數(shù)目。其目標(biāo)函數(shù)為

其中，Ik為列車追蹤間隔，在四顯示自動(dòng)閉塞制式下前后行列車應(yīng)間隔4個(gè)閉塞分區(qū)追蹤運(yùn)行;v為列車運(yùn)行的速度;i為在閉塞分區(qū)范圍內(nèi)劃分節(jié)點(diǎn)數(shù)目，i=1…n;max(I1，I2，…，Ii，…，Ik)為由出站信號(hào)機(jī)經(jīng) k+2架通過(guò)信號(hào)機(jī)至進(jìn)站信號(hào)機(jī)最長(zhǎng)追蹤間隔。

“經(jīng)濟(jì)”策略是指在列車追蹤間隔時(shí)間確定的前提下，最小化信號(hào)機(jī)的數(shù)目。其目標(biāo)函數(shù)為

其中，Nsignal表示兩站間信號(hào)機(jī)的架數(shù)即劃分。

1.3 約束條件

閉塞分區(qū)實(shí)際劃分時(shí)要考慮多個(gè)約束條件，如式(3)所示，包括列車緊急制動(dòng)距離、軌道電路長(zhǎng)度、區(qū)間最小分區(qū)數(shù)目等，其中l(wèi)min為工程人員由現(xiàn)場(chǎng)實(shí)際情況確定的閉塞分區(qū)的最短長(zhǎng)度，lcircuit為軌道電路極限長(zhǎng)度，劃分節(jié)點(diǎn)數(shù)n=N+1，H為預(yù)先設(shè)定追蹤間隔時(shí)間。制動(dòng)距離Sb和附加距離S附長(zhǎng)度之和為閉塞分區(qū)長(zhǎng)度 li，max Sb(vi，vi+1，ij)為列車自坡道值 ij處從高速度等級(jí)vi+1降至相鄰低速度等級(jí)vi的最大制動(dòng)距離。

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

構(gòu)造適應(yīng)度時(shí)引入罰函數(shù)法，將一個(gè)足夠反映約束條件的懲罰項(xiàng)包含到適應(yīng)度函數(shù)中，對(duì)復(fù)雜的約束優(yōu)化問題進(jìn)行無(wú)約束處理，通過(guò)懲罰因子大小的選取調(diào)節(jié)適應(yīng)度函數(shù)的懲罰力度，從而影響算法的收斂速度。

效率策略下適應(yīng)度函數(shù)為

在式(4)和(5)中，a為懲罰因子，取值范圍為10～20。公式(5)說(shuō)明閉塞分區(qū)長(zhǎng)度不滿足實(shí)際軌道電路極限長(zhǎng)度和緊急制動(dòng)距離時(shí)，適應(yīng)度值減小。

經(jīng)濟(jì)策略下的適應(yīng)度函數(shù)為

在式(6)和(7)中，λ為懲罰因子，取值范圍為10～20。公式(7)說(shuō)明追蹤間隔大于給定追蹤間隔時(shí)，適應(yīng)度函數(shù)值減小。

2 免疫粒子群算法優(yōu)化過(guò)程

2.1 免疫粒子群算法總流程圖

IA－PSO算法可分為兩部分，如圖2所示，一為基本PSO算法，用于控制基本的優(yōu)化迭代過(guò)程。當(dāng)算法在運(yùn)行過(guò)程中，某一粒子發(fā)現(xiàn)最優(yōu)解，其余粒子就會(huì)聚集，種群多樣性降低，如果發(fā)現(xiàn)其為局部最優(yōu)解，粒子群無(wú)法再在解空間繼續(xù)搜索，陷入早熟收斂。二為引入人工免疫機(jī)理，經(jīng)過(guò)克隆復(fù)制，柯西變異，克隆選擇算子，加大種群多樣性，增強(qiáng)全局搜索能力。

圖2 免疫粒子群算法流程

2.2 算法設(shè)計(jì)

Step1 根據(jù)式(2)確定種群數(shù)目，即信號(hào)機(jī)數(shù)目n，將區(qū)間n等份，線路上第i架信號(hào)機(jī)位置取值下限:XLow(i)=X(i)－300，取值上限:Xup(i)=X(i)+300，個(gè)體極值 Pbest，全局極值 Gbest，維度范圍 j∈(1，p)。

Step2 根據(jù)約束條件對(duì)劃分結(jié)果影響設(shè)計(jì)的不同策略下的適應(yīng)度函數(shù)式(3)、(4)、(5)、(6)，求解各粒子適應(yīng)度值;由極值更新策略Xbest=max(f(1)，f(2)，…，f(n))得到個(gè)體極值 Pbest、全局極值 Gbest。

Step3 根據(jù)t值是否超過(guò)設(shè)定閾值K判斷是否陷入局部最優(yōu)解，若Gbest沒有更新，累加全局最優(yōu)解迭代次數(shù)t=t+1，t未達(dá)到給定閾值K，轉(zhuǎn)向step4，否則，t清零。

Step4 將粒子看做抗體，計(jì)算親和度

其中，disi為第i個(gè)粒子與全局最優(yōu)粒子gbest在第j維度上的距離，即待優(yōu)化長(zhǎng)度與全局極值的距離。

Step5 第i個(gè)粒子被克隆復(fù)制的數(shù)目

通過(guò)抗體抑制原理，親和度值越小，被克隆數(shù)目越少，基因優(yōu)良性越保持。

Step6 進(jìn)行柯西變異，對(duì)于每個(gè)克隆個(gè)體，根據(jù)父代個(gè)體親和度變化采用變異操作?？挛髯儺惖姆秶S著t值的減小而縮小，當(dāng)t值確定，父代種群的親和度連續(xù)δ代不發(fā)生變化時(shí)，選取t(k+1)=0.8*t(k)，為抗體x的父代變異體，參數(shù)η控制柯西隨機(jī)變量ijcauchy(t)的衰減。

Step7 進(jìn)行克隆選擇，采用輪盤賭(Roulette wheel)方法將父代適應(yīng)度函數(shù)進(jìn)行排序，從父代個(gè)體中選出適應(yīng)度最高的粒子作為下一代個(gè)體，淘汰適應(yīng)度較低個(gè)體。

Step8 對(duì)粒子位置坐標(biāo)xij和速度vij(即追蹤間隔時(shí)間)進(jìn)行更新。其中，學(xué)習(xí)因子c1、c2為固定值，r1，r2∈[0，1]，Pij為當(dāng)前信號(hào)機(jī)位置坐標(biāo)最優(yōu)解，Pgj信號(hào)機(jī)位置坐標(biāo)經(jīng)親和度值升序排列后選出的最優(yōu)位置。

Step9 若滿足迭代次數(shù)，算法停止，輸出xij，vij值，否則轉(zhuǎn)向step2。

3 閉塞分區(qū)劃分檢驗(yàn)

閉塞分區(qū)劃分檢驗(yàn)分為列車追蹤間隔檢驗(yàn)、列車起動(dòng)檢驗(yàn)，列車停車檢驗(yàn)，特殊線路條件檢查。主要通過(guò)對(duì)信號(hào)機(jī)位置調(diào)整，使信號(hào)機(jī)間的列車追蹤間隔小于給定的間隔時(shí)間，并通過(guò)對(duì)速度參數(shù)控制，不斷計(jì)算列車牽引和制動(dòng)性能并設(shè)定制動(dòng)觸發(fā)點(diǎn)，根據(jù)動(dòng)能公式、動(dòng)量定理，牽引時(shí)保證列車能夠在坡段起動(dòng)需使列車起動(dòng)牽引力滿足:Fq≥ [Gq(+iq)+P(+iq)]g×103;制動(dòng)時(shí)，在列車達(dá)到最大速度前提下，制動(dòng)距離在閉塞分區(qū)劃分的范圍內(nèi)，滿足:L閉≥(Sb+la)/(M－2)，并考慮特殊線路的限制因素，如坡道、曲線半徑等，檢驗(yàn)?zāi)Ｐ腿鐖D3所示。

圖3 劃分檢驗(yàn)?zāi)Ｐ?/p>

4 案例分析

選取A站—B站為待布置通過(guò)信號(hào)機(jī)的區(qū)間，A站出站信號(hào)機(jī)位置為270.746 km，B站進(jìn)站信號(hào)機(jī)位置為284.026 km，則區(qū)間全長(zhǎng)13.28 km，設(shè)列車在區(qū)間平均運(yùn)行速度為100 km/h，列車長(zhǎng)度為800 m，按四顯示自動(dòng)閉塞布置，設(shè)閉塞分區(qū)最小長(zhǎng)度為1 000 m，最大閉塞分區(qū)長(zhǎng)度為1 400 m，初始種群20個(gè)，優(yōu)化10次，每次最大迭代次數(shù)250次，取最優(yōu)的優(yōu)化結(jié)果輸出。圖4所示為兩種策略下，算法的各代群體平均適應(yīng)度與最大適應(yīng)度的變化趨勢(shì)。

從圖4中可以看出，隨著迭代次數(shù)的增加，群體的平均適應(yīng)度和最優(yōu)適應(yīng)度波動(dòng)減小，表明算法可以維持種群的多樣性，避免早熟收斂發(fā)生。在效率策略和經(jīng)濟(jì)策略下，算法運(yùn)行到接近200代群體的平均適應(yīng)度和最優(yōu)適應(yīng)度的減小趨勢(shì)已較為緩慢，可將算法250代時(shí)的計(jì)算結(jié)果作為最終的布局方案。運(yùn)行結(jié)果見表1，經(jīng)濟(jì)策略下追蹤間隔為min max(I1，I2，…，Ik)=3.96 min，效率策略下追蹤間隔為3.25 min，預(yù)先設(shè)定的列車追蹤間隔為5 min，并且經(jīng)檢驗(yàn)所有信號(hào)機(jī)滿足制動(dòng)距離要求，說(shuō)明算法是有效的。

圖4 群體適應(yīng)度變化曲線

表1 基于免疫粒子群算法的優(yōu)化結(jié)果

評(píng)價(jià)算法性能時(shí)，Ef為波動(dòng)率，反映了初始條件下逼近最優(yōu)解的程度，如圖5所示，其值越小，說(shuō)明算法的魯棒性越好。

式中，C*為問題的期望最優(yōu)值;Ca為算法多次運(yùn)行所得的平均值。

圖5 波動(dòng)率曲線

Ef1、Ef2分別為“經(jīng)濟(jì)”和“效率”下的波動(dòng)率。試驗(yàn)結(jié)果表明，IM-PSO法運(yùn)行到250次得到最優(yōu)解，波動(dòng)率小，算法魯棒性好。

5 結(jié)語(yǔ)

使用免疫粒子群算法對(duì)信號(hào)機(jī)的數(shù)目和位置進(jìn)行初始化，并對(duì)種群進(jìn)行克隆、變異、選擇等操作，完成列車追蹤間隔檢驗(yàn)和列車起停車檢驗(yàn)，實(shí)現(xiàn)閉塞分區(qū)的快速、準(zhǔn)確劃分。最后通過(guò)實(shí)際案例，考慮“經(jīng)濟(jì)”、“效率”等因素對(duì)該算法進(jìn)行驗(yàn)證，結(jié)果表明該算法確實(shí)能改善閉塞分區(qū)的優(yōu)化劃分。

［1］董昱.區(qū)間信號(hào)與列車運(yùn)行控制系統(tǒng)［M］.中國(guó)鐵道出版社，2008.

［2］Gill D C，Goodman C J.Computer-based optimization techniques for mass transit railway signaling design［J］.IEE Proc-B，1992，139(3):261-275.

［3］Chang CS，Du D.Improved optimization method using genetic algorithms for mass transit signaling block-layout design［J］.IEE Proc-Electr.Power Appl.，1998，145(3):266-272.

［4］Ke B.R，Chen M C，Lin C L.Block-layout design using MAX-MIN ant system for saving energy on mass rapid transit systems［J］.IEEE Transactions on Intelligent Transportation System，2009，10(2):226-235.

［5］衛(wèi)和君.客運(yùn)專線CTCS-3級(jí)列控系統(tǒng)牽引計(jì)算與閉塞分區(qū)劃分技術(shù)［J］.鐵路技術(shù)創(chuàng)新，2010(5):24-28.

［6］于宗艷，韓連濤.免疫粒子群優(yōu)化算法及應(yīng)用［J］.計(jì)算機(jī)仿真，2008(12):208-211.

［7］雷德明，嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用［M］.北京:科學(xué)出版社，2009.

［8］劉瀾，杜文.多信息自動(dòng)閉塞列車速度——間隔控制模型及算法［J］.鐵道學(xué)報(bào)，2000(6):8-12.

［9］毛保華.列車運(yùn)行計(jì)算與設(shè)計(jì)［M］.北京:人民交通出版社，2008.

［10］衛(wèi)和君.鐵路自動(dòng)閉塞分區(qū)劃分技術(shù)展望［J］.長(zhǎng)沙鐵道學(xué)院學(xué)報(bào)，2003，21(4):99-102.

［11］薛長(zhǎng)虹.青藏鐵路關(guān)角特長(zhǎng)隧道內(nèi)自動(dòng)閉塞設(shè)計(jì)探討［J］.鐵道標(biāo)準(zhǔn)設(shè)計(jì)，2012(4):127-130.

［12］傅世善.自動(dòng)閉塞設(shè)計(jì)的新理念［J］.鐵道通信信號(hào)，2004，40(5):16-18.