王　瑞，陳永剛

(蘭州交通大學(xué)自動化與電氣工程學(xué)院，蘭州　730070)

?

基于捕食搜索策略的粒子群算法求解高鐵閉塞分區(qū)劃分問題

王瑞，陳永剛

(蘭州交通大學(xué)自動化與電氣工程學(xué)院，蘭州730070)

摘要：高鐵閉塞分區(qū)的合理劃分可以保證列車的運行安全、提高運輸效率和減少投資成本。為了更好地解決這個問題，利用基于捕食搜索策略的粒子群算法求解優(yōu)化準(zhǔn)移動閉塞條件下的閉塞分區(qū)劃分模型。捕食搜索策略可以平衡粒子的局域搜索和全局搜索，從而避免陷入局部最優(yōu)，提高算法精度。通過算例仿真，比較基于捕食搜索策略的粒子群算法和標(biāo)準(zhǔn)粒子群算法對模型優(yōu)化的結(jié)果，驗證基于捕食搜索策略的粒子算法對模型的求解是有效的，而且得到的解更精確，運算速度更快。

關(guān)鍵詞：高速鐵路；捕食搜索策略；粒子群算法；閉塞分區(qū)；準(zhǔn)移動閉塞

高速鐵路建設(shè)首先解決的是選線設(shè)計和閉塞分區(qū)的設(shè)計。目前，我國閉塞分區(qū)長度的確定大多以區(qū)間運行時間間隔進(jìn)行劃分，這種劃分方式由于需留有較大的列車追蹤間隔，導(dǎo)致運行密度較低，運輸效率不高[1]。所以，研究鐵路閉塞分區(qū)的劃分問題，尤其是準(zhǔn)移動閉塞制式下閉塞分區(qū)劃分問題，對于保證行車安全、提高線路通過能力和減少投資成本都具有重要意義。

目前，國外學(xué)者已經(jīng)將啟發(fā)式的坡道搜索算法[2]、遺傳算法[3]、差分進(jìn)化算法[4]、最大-最小蟻群算法[5]應(yīng)用于地鐵系統(tǒng)的信號機布局優(yōu)化。國外學(xué)者主要針對城市軌道交通系統(tǒng)的閉塞分區(qū)劃分問題進(jìn)行了研究，沒有涉及干線鐵路。在國內(nèi)，劉海東等人[6]實現(xiàn)了利用計算機建立仿真系統(tǒng)完成干線鐵路三顯示固定閉塞的信號機布置。劉劍峰等人[7]在分析了影響區(qū)間信號機布置因素后，建立了區(qū)間四顯示固定閉塞信號機布置優(yōu)化模型，并用遺傳算法對模型進(jìn)行了求解。國內(nèi)學(xué)者雖然已將智能算法用于求解干線鐵路固定閉塞條件下閉塞分區(qū)劃分問題，但沒有系統(tǒng)地分析閉塞分區(qū)劃分的影響因素及其約束條件，約束條件較簡單。并且較少研究準(zhǔn)移動閉塞條件下的閉塞分區(qū)劃分問題。再者其運用的算法存在編碼過程復(fù)雜、計算量大、極易陷入局部最優(yōu)等問題。現(xiàn)在運用基于捕食搜索策略的粒子群算法實現(xiàn)高速鐵路閉塞分區(qū)的快速合理劃分，提高閉塞分區(qū)劃分的質(zhì)量和速度。

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

主要研究準(zhǔn)移動閉塞制式下、列車運行控制系統(tǒng)為CTCS-2級的高鐵閉塞分區(qū)劃分方法，以閉塞分區(qū)劃分?jǐn)?shù)量最少為優(yōu)化目標(biāo)，在滿足列車追蹤間隔時間和制動距離等因素的條件下進(jìn)行閉塞分區(qū)劃分，最終在保證列車運行安全和一定效率的前提下，實現(xiàn)降低建設(shè)成本和減少線路維修工作量的目的。

本文用到的模型來自參考文獻(xiàn)[13]，為了提高計算精度，對模型中的部分參數(shù)進(jìn)行了調(diào)整，并將文獻(xiàn)[13]模型中的第一接近信號點位置條件去掉，而在區(qū)間信號點位置條件中進(jìn)行重新定義。

1.1　定義變量

假設(shè)Ⅰ站和Ⅱ站相鄰，兩站之間信號點的個數(shù)為N，每個信號點位置的坐標(biāo)為xi(i=1，2，…，N)。I站的反向進(jìn)站信號機坐標(biāo)為x0，Ⅱ站的進(jìn)站信號機坐標(biāo)為xN+1。對應(yīng)的閉塞分區(qū)的長度li(i=1，2，…，N+1)為相鄰兩個信號點坐標(biāo)的差值。

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

為了達(dá)到降低建設(shè)成本和減少維修工作量的目的，閉塞分區(qū)劃分?jǐn)?shù)量在滿足一定效率的條件下要盡可能的少，這里設(shè)定列車追蹤間隔時間不大于H(3 min)。目標(biāo)函數(shù)為

(1)

1.3　約束條件

約束條件如下所述。

(1)區(qū)間信號點位置

(2)

(3)

(2)閉塞分區(qū)長

(4)

(5)

式中，li為閉塞分區(qū)長度；lmin為閉塞分區(qū)的最小長度；lmax為閉塞分區(qū)最大長度。

(3)閉塞分區(qū)劃分?jǐn)?shù)量

閉塞分區(qū)劃分?jǐn)?shù)量n(n=N+1)，其取值條件如下

(6)

式中，lsection為Ⅰ站和Ⅱ站之間的區(qū)間長度。

(4)第一離去信號點位置

(7)

(5)第二接近信號點位置

(8)

式中，xN-1為第二接近信號點坐標(biāo)；xc為第二接近信號點下限位置(由進(jìn)站間隔時間計算得到)。

(6)CTCS軌道電路正常碼序顯示

(9)

(7)停車起動條件

列車在每個信號點前停車以后再次起動需要滿足以下條件

(10)

式中，F(xiàn)xi為列車在xi位置處的起動牽引力；Gq為列車總重；wq為列車單位基本阻力；iq為xi位置處坡度千分?jǐn)?shù)。

(8)列車追蹤間隔時間

(11)

式中，Ii為列車追蹤間隔時間(閉塞分區(qū)劃分完畢后根據(jù)公式進(jìn)行計算)；H為給定的列車追蹤間隔時間。

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

由于以閉塞分區(qū)劃分?jǐn)?shù)量最少為優(yōu)化目標(biāo)即求目標(biāo)函數(shù)的最小值。因此，適應(yīng)度函數(shù)定義如下

(12)

(13)

式中，P1與信號點限界位置有關(guān)；α為懲罰因子；N1為在給定范圍外的信號點個數(shù)。

(14)

式中，P2與閉塞分區(qū)長度限值有關(guān)；β為懲罰因子；N2為分區(qū)長度在規(guī)定長度以外的個數(shù)。

(15)

式中，P3與軌道電路碼序有關(guān)；γ為懲罰因子；N3為不滿足軌道電路碼序約束條件的閉塞分區(qū)個數(shù)。

(16)

式中，P4與第一離去信號點位置有關(guān)；ε為懲罰因子；當(dāng)滿足第一離去信號點條件時要減小個體適應(yīng)度值。

(17)

式中，P5與第二接近信號點位置有關(guān)；λ為懲罰因子；當(dāng)滿足第二接近信號點條件時要減小個體適應(yīng)度值。

(18)

式中，P6與列車追蹤間隔有關(guān)；δ為懲罰因子；N4為大于給定列車追蹤間隔時間H的閉塞分區(qū)個數(shù)。

(19)

上面各式中的懲罰因子α、β、γ、ε、λ、δ、μ，根據(jù)懲罰強弱程度不同而取值不同，其取值在10～30。

2基于捕食搜索策略的粒子群算法(PSPSO)

2.1　粒子群算法

粒子群算法(Particle Swarm Optimization， PSO)是由Kennedy博士 和 Eberhart教授于1995年提出來的。PSO是一種隨機的、并行的優(yōu)化算法。其算法簡單，容易實現(xiàn)，且不要求被優(yōu)化函數(shù)具有可微、可導(dǎo)、連續(xù)等性質(zhì)，收斂速度快。

假設(shè)在D維空間中求解，群體中有m個粒子，這些粒子在解空間中以一定的速度飛行，每個粒子都是一個可能的解， 都是一個D維向量，記作xi=(xi1，xi2，…，xiD)，即第i(i=1，2，…，m)個粒子在 D維的搜索空間中的位置是xi。將滿足設(shè)定的約束條件的xi帶入預(yù)設(shè)的適應(yīng)度函數(shù)中，可以計算每個粒子的適應(yīng)度值， 然后依據(jù)適應(yīng)度值的大小判定xi的優(yōu)劣。在搜索過程中，每個粒子根據(jù)自己搜索到的歷史最優(yōu)位置和群體內(nèi)或鄰域內(nèi)其他粒子搜索到的歷史最優(yōu)位置進(jìn)行位置的變化。第i個粒子的速度也是一個D維向量，記作vi=(vi1，vi2，…，viD)，第i個粒子搜索到的歷史最好點記作pi=(pi1，pi2， …，piD)，整個群體搜索到的歷史最優(yōu)點記作pg=(pg1，pg2，…，pgD)。粒子的位置和速度都是實數(shù)，其根據(jù)下面的方程進(jìn)行變化

(20)

(21)

式中，c1和c2稱為學(xué)習(xí)因子或加速系數(shù)；ξ，η是在[0，1]區(qū)間內(nèi)的均勻分布的偽隨機數(shù)；ω稱為慣性權(quán)重，是一個位于[0，1]區(qū)間內(nèi)的常數(shù)；k為迭代次數(shù)。

2.2　捕食搜索策略

粒子群算法計算簡單、容易實現(xiàn)、收斂速度快，但是由于粒子交流信息量過大和信息流動的單一性，粒子就會加速聚集。隨著迭代的進(jìn)行，粒子種群多樣性就會下降，迭代后期很難找到更好的解，容易陷入局優(yōu)。使得算法對復(fù)雜問題的開發(fā)能力減弱。為了解決這個問題將捕食搜索策略引入到標(biāo)準(zhǔn)粒子群算法中。

捕食搜索(Predatory Search， PS)是由巴西學(xué)者Alexandre Linhares在1998年提出來的一種用于解決組合優(yōu)化問題的模擬動物捕食行為的空間搜索策略。捕食搜索策略的思想：在整個解空間內(nèi)進(jìn)行全局搜索，找到一個較優(yōu)解，然后在找到的較優(yōu)解的周圍進(jìn)行局域搜索，在進(jìn)行多次搜索后，未發(fā)現(xiàn)更好的解，放棄局域搜索，轉(zhuǎn)到全局搜索。經(jīng)過這樣多次循環(huán)最終找到最優(yōu)解。由于大部分搜索時間都在較優(yōu)解附近的較小區(qū)域進(jìn)行搜索，所以搜索高效且速度快。將其引入到標(biāo)準(zhǔn)粒子群算法中，第一可以提高算法前期的迭代搜索能力，抑制早熟；第二可以提高算法的后期搜索能力找到更精確的解。

2.3　基于捕食搜索策略的粒子群算法

在把捕食搜索策略引入到標(biāo)準(zhǔn)粒子群算法過程中，首先將限制定義為多維解空間內(nèi)的兩點間的距離。粒子在某限制下的鄰域定義為與粒子的距離小于該限制的多維空間。在解空間內(nèi)設(shè)置NL級限制：R(1)，R(2)，…，R(NL)。

在最小限制R(1)規(guī)定的鄰域內(nèi)隨機初始化m個粒子，根據(jù)標(biāo)準(zhǔn)PSO公式迭代若干次，試圖找到更優(yōu)解，當(dāng)PSO進(jìn)行Cs次還不能找到，則增加限制到R(2)，在其鄰域內(nèi)初始化粒子群，根據(jù)公式迭代，若能找到則替換歷史最優(yōu)解，并重新計算限制，若不能則繼續(xù)增加限制等級，隨著限制等級的增加搜索空間也在增大。當(dāng)限制等級達(dá)到某一個值Ls時，而無法找到更優(yōu)解時，就需放棄區(qū)域搜索，將搜索限制增加到一個較高的等級Lh，也就跳出了局部最優(yōu)，如此循環(huán)，直到設(shè)定的限制等級NL規(guī)定的鄰域也搜索完成。

重新計算限制方法如下：

(1)在初始解空間利用標(biāo)準(zhǔn)粒子群算法搜索NL次，得到NL個解；

(2)把這NL個解按照到發(fā)現(xiàn)的歷史最優(yōu)解的距離從小到大排列，組成NL級限制。

算法主要步驟如下：

步驟1在解空間內(nèi)隨機選擇一個解x，令其為歷史最優(yōu)解pg，pg=x，PSO進(jìn)行次數(shù)k=0，限制等級L=1；

步驟2若L≤NL，在x的R(L)限制內(nèi)初始化m個粒子，粒子的最大速度為當(dāng)前限制，按照公式(19)、公式(20)迭代若干次，找到其歷史最優(yōu)解p，然后轉(zhuǎn)到步驟3，否則結(jié)束；

步驟3令x=p，解x的適應(yīng)值與歷史最優(yōu)解pg的適應(yīng)值進(jìn)行比較，若f(x)

步驟4令k=k+1，若k≤Cs，則轉(zhuǎn)步驟2，否則令L=L+1，轉(zhuǎn)步驟5；

步驟5若L=Ls，則令L=Lh，轉(zhuǎn)步驟2，否則直接轉(zhuǎn)步驟2。

3算例分析

3.1　數(shù)據(jù)準(zhǔn)備

以Ⅰ站—Ⅱ站區(qū)間為待劃分區(qū)間，Ⅰ站中心公里標(biāo)為0 km，反向進(jìn)站信號機公里標(biāo)為1 km，Ⅱ站中心公里標(biāo)為34.500 km，進(jìn)站信號機公里標(biāo)為33.500 km，區(qū)間全長33.5 km。參數(shù)條件如表1所示。

表1　閉塞分區(qū)劃分參數(shù)

軌道電路傳輸極限長度如表2所示。

表2　軌道電路傳輸極限長度

所選用的動車組類型及其參數(shù)如表3所示。

表3　區(qū)間運行動車組類型及參數(shù)

3.2　算法參數(shù)設(shè)置

在PSPSO中，通過限制L來實現(xiàn)全局搜索和局部搜索的平衡，學(xué)習(xí)因子和慣性權(quán)重只在內(nèi)循環(huán)中起作用，對全局和局域搜索影響不大。因此，學(xué)習(xí)因子和慣性權(quán)重可以采用固定值，本文令c1=c2=1，ω=0.5。另外，粒子數(shù)取10，在Matlab中經(jīng)過多次仿真后將一些參數(shù)做如下設(shè)置：NL=N，Cs=N，Ls=[NL/4]，Lh=NL-Ls。

3.3 計算結(jié)果及分析

利用Matlab對算法進(jìn)行仿真驗證。根據(jù)公式(6)得到可劃分的閉塞分區(qū)數(shù)量范圍，進(jìn)而得到區(qū)間布置的信號點數(shù)量N的范圍，根據(jù)N由小到大依次進(jìn)行尋優(yōu)。經(jīng)過仿真求解，當(dāng)N=13時，得到最優(yōu)布置結(jié)果。圖1為N=13時的歷史最優(yōu)解的適應(yīng)度函數(shù)值隨循環(huán)次數(shù)變化而變化的關(guān)系曲線，得到一次歷史最優(yōu)解pg為一次循環(huán)，粒子的迭代次數(shù)取10。

圖1　算法適應(yīng)度隨迭代次數(shù)變化曲線

從圖1可知，PSPSO算法在循環(huán)到第104次左右收斂，總循環(huán)次數(shù)為10×104=1 040代左右收斂，并找到了比較優(yōu)良的結(jié)果。

為了進(jìn)一步說明算法的優(yōu)越性，本文將標(biāo)準(zhǔn)PSO算法和PSPSO算法分別運行30次，結(jié)果對比如表4所示。

表4　PSPSO和標(biāo)準(zhǔn)PSO優(yōu)化比較

由于標(biāo)準(zhǔn)PSO算法在粒子數(shù)為10時，很難找到最優(yōu)解，因此，將粒子數(shù)增大到100。從表4可知，雖然標(biāo)準(zhǔn)PSO算法收斂速度比較快，但是不能保證每次都收斂到最優(yōu)，可能收斂到局優(yōu)。實際上標(biāo)準(zhǔn)PSO算法隨著迭代的進(jìn)行，認(rèn)識部分和學(xué)習(xí)部分在減小， 粒子的種群多樣性下降，容易陷入局優(yōu)。而PSPSO算法搜索時每次都會重新初始化粒子，由于不會受歷史信息的影響，用較少的粒子也不會陷入局優(yōu)。而在計算時間上，雖然PSPSO算法的迭代次數(shù)要多一些，但是由于粒子數(shù)量少，搜索所用的時間反而更短。

PSPSO算法優(yōu)化最終得到的信號點布置結(jié)果如表5所示。從表5的優(yōu)化結(jié)果得知，閉塞分區(qū)的最大長度為2 830 m，符合最大長度要求。區(qū)間的最大列車追蹤間隔為2.14 min，符合給定的追蹤間隔(3 min)要求，經(jīng)檢驗，車站追蹤間隔也符合要求。最大碼序為U，符合碼序檢驗要求。綜上說明，算法是有效的。

表5　基于捕食搜索策略粒子群算法的優(yōu)化結(jié)果

布置同樣長度的區(qū)間，最終得到的結(jié)果與文獻(xiàn)[13]相比，劃分的閉塞分區(qū)個數(shù)都為13個，區(qū)間的最大列車追蹤間隔時間2.14 min，優(yōu)于文獻(xiàn)[13]得到的2.2 min，在閉塞分區(qū)個數(shù)相同的情況下，本文的劃分結(jié)果在效率方面優(yōu)于文獻(xiàn)[13]。

4結(jié)語

利用基于捕食搜索策略的粒子群算法求解優(yōu)化高鐵閉塞分區(qū)劃分模型。基于捕食搜索策略的粒子群算法利用較少的粒子，通過限制等級的調(diào)節(jié)，實現(xiàn)快速收斂到全局最優(yōu)。通過實例仿真驗證了基于捕食搜索策略的粒子群算法求解高鐵閉塞分區(qū)劃分問題是有效的。算法在重新計算限制時，是通過隨機初始化粒子群實現(xiàn)的，這樣可能會出現(xiàn)較差的解，減慢算法的收斂速度，有待改進(jìn)。

參考文獻(xiàn)：

[1]王瑞峰，高繼祥.鐵路信號運營基礎(chǔ)[M].北京:中國鐵道出版社，2008.

[2]Gill D C， Goodman C J. Computer-based optimisation techniques for mass transit railway signalling design[C]. IEE Proceedings B (Electric Power Applications). IET Digital Library， 1992，139(3):261-275.

[3]Chang C S， Du D. Improved optimisation method using genetic algorithms for mass transit signalling block-layout design[C]. Electric Power Applications， IEE Proceedings-IET， 1998，145(3):266-272.

[4]Chang C S， Du D. Further improvement of optimisation method for mass transit signalling block-layout design using differential evolution[C].Electric Power Applications， IEE Proceedings-IET， 1999，146(5):559-569.

[5]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]. Intelligent Transportation Systems， IEEE Transactions on， 2009，10(2):226-235.

[6]劉海東，毛保華，劉劍鋒，等.鐵路信號機布置及其計算機實施系統(tǒng)研究[J].系統(tǒng)仿真學(xué)報，2006，18(1):62-66.

[7]劉劍鋒，毛保華，侯忠生，等.基于遺傳算法的區(qū)間自動閉塞信號機布局優(yōu)化方法[J].鐵道學(xué)報，2006，28(4):54-59.

[8]衛(wèi)和君.鐵路自動閉塞分區(qū)劃分技術(shù)展望[J].長沙鐵道學(xué)院學(xué)報，2003，21(4):99-102.

[9]王俊偉.粒子群優(yōu)化算法的改進(jìn)及應(yīng)用[D].東北大學(xué)，2006.

[10]劉冬華，甘若迅，樊鎖海，等.基于捕食策略的粒子群算法求解投資組合問題[J].計算機工程與應(yīng)用，2013，49(6):253-256.

[11]張濟(jì)民，吳汶麒.準(zhǔn)移動閉塞列車安全間隔時間的計算[J].鐵道學(xué)報，1999，21(3):6-10.

[12]潘峰，李位星，高琪，等.粒子群優(yōu)化算法與多目標(biāo)優(yōu)化[M].北京:北京理工大學(xué)出版社，2013.

[13]劉海東，毛保華，王保山，等.基于差分進(jìn)化算法的高速鐵路區(qū)間信號布置優(yōu)化方法研究[J].鐵道學(xué)報，2013，35(5):40-46.

Particle Swarm Algorithm Based on Predatory Search Strategy for Partitioning of High-speed Railway Block Section

WANG Rui， CHEN Yong-gang

(School of Automation and Electrical Engineering， Lanzhou Jiaotong University， Lanzhou 730070， China)

Abstract：The rational division of the high-speed railway block section serves to ensure safe traffic， improve transport efficiency and reduce investment. In this regard， the new optimization model of block section in the quasi-moving block is solved with particle swarm optimization algorithm based on predatory search strategy. The predatory search strategy balances local search and global search of the particles， so as to avoid local optimum and improve algorithm accuracy. By numerical example and comparing the optimization results of the particle swarm algorithm， the effectiveness of the particle swarm algorithm is validated based on the predatory search strategy for solving the model with more precise solutions are and faster operation speed.

Key words：High-speed railway; Predatory search strategy; Particle swarm algorithm; Block section; Quasi-moving block

作者簡介：王瑞(1989—)，男，碩士研究生，E-mail:393556335@qq.com。

基金項目：國家自然科學(xué)基金地區(qū)項目(61164101)

收稿日期：2015-05-08； 修回日期：2015-06-14

中圖分類號：U238； U284

文獻(xiàn)標(biāo)識碼：ADOI:10.13238/j.issn.1004-2954.2016.01.029

文章編號：1004-2954(2016)01-0131-05