多種群分層聯(lián)合優(yōu)化的城軌列車ATO研究

徐 凱，吳 磊，趙 梅

(1.重慶交通大學 信息科學與工程學院，重慶 400074；2.重慶市公共交通運營大數(shù)據(jù)工程技術(shù)研究中心，重慶 400074；3.西華大學 電氣與電子信息學院，四川 成都 610039)

列車自動駕駛ATO系統(tǒng)是列車自動控制系統(tǒng)的重要組成部分，其運行等級模式曲線計算的精確性將直接影響車載ATO的控制效果[1]。通常利用節(jié)能優(yōu)化算法來獲得列車節(jié)能駕駛策略，用以指導列車自動運行，減少運行能耗。為達到此目的，文獻[2]在列車運行控制模型的優(yōu)化中，采用遺傳算法降低了列車運行的能耗。文獻[3-5]分別采用不同形式的粒子群優(yōu)化算法來獲取列車自動駕駛曲線。上述參考文獻有一個共同點，即在一定約束條件下采用加權(quán)求和的方法，將列車運行控制的多目標優(yōu)化轉(zhuǎn)換為單目標優(yōu)化。在列車運行控制系統(tǒng)中，各個目標之間的關(guān)系較為復雜，加權(quán)求和方法并沒有考慮各目標之間的相互作用及影響，無法體現(xiàn)出多目標問題研究的本質(zhì)。由于多目標優(yōu)化獲得的是所有占優(yōu)解的集合，而并非只有一個最優(yōu)解。為體現(xiàn)出多目標優(yōu)化的本質(zhì)，采用Pareto原理來解決此問題是一種較佳選擇。對于具體的列車以運行時間和能耗為目標問題，需要從Pareto最優(yōu)解集中選擇一個或一些最符合實際需求的解作為最終解使用，由此設(shè)計列車ATO運行模式曲線。

近年來研究者采用基于Pareto原理的多目標優(yōu)化方法來獲取列車運行操縱策略。文獻[6-7]結(jié)合模擬退火思想，對傳統(tǒng)差分進化算法的交叉操作進行改進，得到了高速列車運行優(yōu)化的操縱策略。文獻[8-9]分別采用基于模糊參數(shù)的NSGA-Ⅱ算法和基于模糊模型的遺傳算法，得到相應的列車控制策略。近年來，不少研究者將多目標粒子群優(yōu)化MOPSO算法應用于列車運行優(yōu)化的操縱策略中[10-12]。相比遺傳算法和動態(tài)規(guī)劃，MOPSO算法可以在收斂性和結(jié)果質(zhì)量之間獲得較好的平衡。文獻[13]為獲得列車最佳控制策略，對MOPSO算法作了相應的改進。文獻[14]將MOPSO與NSGA-Ⅱ兩種算法進行對比研究，發(fā)現(xiàn)MOPSO算法在計算時間、逼近Pareto真實前沿和多樣性等方面更為優(yōu)越。因此，如何進一步改善、提高MOPSO算法的收斂性和多樣性，得到一組優(yōu)越的Pareto前沿解集，從而獲得更為合理的ATO速度命令成為當前研究的熱點之一。

為進一步提高粒子群優(yōu)化PSO算法的性能，將PSO與布谷鳥搜索CS算法相結(jié)合。文獻[15]借鑒PSO算法中全局最優(yōu)和個體最優(yōu)的概念，在CS算法lévy飛行隨機游動和偏好隨機游動之間引入PSO組件。文獻[16]將PSO與CS串行，每次迭代過程中先使用PSO算法優(yōu)化種群，記錄全局最優(yōu)和個體最優(yōu)，采用CS算法對種群個體最優(yōu)繼續(xù)尋優(yōu)。上述將PSO和CS算法進行組合優(yōu)化求解，僅針對單目標優(yōu)化，降低了研究問題的深度，并采用測試函數(shù)評價組合算法的性能，沒有結(jié)合實際工程應用問題來研究。本文采用一種將多種群PSO與布谷鳥搜索CS相結(jié)合的分層算法，即多種群分層PSO-CS聯(lián)合優(yōu)化算法，針對多目標優(yōu)化問題，在列車運行控制仿真實驗中采用所提出的方法，通過多種群PSO、分層結(jié)構(gòu)以及兩種算法的混合策略，提高了Pareto前沿解的收斂性和多樣性。

1 列車控制多目標優(yōu)化模型

參考文獻[17]描述列車運動的微分方程為

( 1 )

( 2 )

式中：t為列車運行時間；v和s分別為列車運行速度和距離；c和ε分別為列車單位合力和加速度系數(shù)。

列車在運行過程中，其所受的力為

ma=f(u，v)-g(v)-w(x，v)

( 3 )

式中：m和a分別為列車質(zhì)量以及運行中合力產(chǎn)生的加速度；f(u，v)為作用于列車上的牽引力或者制動力，當列車處于牽引、制動和惰行狀態(tài)時，f(u，v)分別為正值、負值和零；g(v)為列車基本阻力；w(x，v)為列車附加阻力，其中x和v分別為線路位置和列車運行速度，附加阻力取決于列車運行的線路條件。

在充分考慮安全、停車準確及各種約束條件基礎(chǔ)上，將列車運行能耗和時間作為目標求解。根據(jù)列車運動方程，可計算出列車在整個區(qū)間上的運行時間為

( 4 )

式中：i=1，…，N為劃分的若干個小區(qū)間序號；Ti為每個小區(qū)運行時間；T為站間實際運行時間。

列車運行能耗指標計算模型為[6]

( 5 )

式中：E為列車能耗；F和B分別為牽引力和制動力；A為列車輔助功率；ξM為列車牽引時將電能轉(zhuǎn)換成為機械能的轉(zhuǎn)換因子；ξB為列車制動時將機械能轉(zhuǎn)換成電能的轉(zhuǎn)換因子。

從實質(zhì)上來講，列車運行多目標優(yōu)化就是對式( 1 )～式( 3 )所描述的模型，在滿足約束條件下，求出所輸入的一組控制序列{ui}i=1，2，…，k以及k-1個工況轉(zhuǎn)換點位置{xi}i=1，2，…，k-1(xi∈[0，S])，做到讓列車運行時間短且耗能低。由此，以運行時間和能耗為多目標的優(yōu)化問題可表示為

min{T，E}

( 6 )

約束條件為

( 7 )

式中：v(0)為列車初速度；v(S)為列車末速度；v(s)為列車在位置s處的實際速度；vlim(s)為列車的限制速度；Sr為列車實際運行的距離；S為兩站點之間的距離，cm。

2 多種群分層PSO-CS聯(lián)合優(yōu)化算法

2.1 粒子群優(yōu)化算法PSO

PSO算法是受鳥群覓食行為啟發(fā)而提出的群搜索算法，通過粒子間相互作用，發(fā)現(xiàn)復雜搜索空間中的最優(yōu)區(qū)域，具有全局搜索能力強的特點。該算法的粒子速度和位置更新公式分別為[15]

( 8 )

( 9 )

2.2 布谷鳥搜索算法CS

布谷鳥搜索[18]是由劍橋大學Yang等提出的一種群智能優(yōu)化算法，是一種新型元啟發(fā)式搜索算法。主要原理是基于布谷鳥的lévy飛行機制及巢寄生性，使其能夠快速有效地尋找到最優(yōu)解。布谷鳥搜索算法采用lévy飛行進行位置更新，其更新公式為[18]

⊕L(λ)

(10)

(11)

(12)

式中：Г是標準Gamma函數(shù)；λ取值為2.5。

2.3 雙層框架的聯(lián)合優(yōu)化算法

2.3.1 算法思想

一方面，PSO算法局部搜索能力強、收斂速度快，CS算法由于lévy飛行具有高度的隨機性，因而有較強的全局搜索能力和多樣性。因此將PSO和CS兩種算法的優(yōu)點相結(jié)合。另一方面，可將底層的種群劃分為多個小種群，讓多個小種群獨立并行協(xié)同搜索，不僅擴大了粒子在解空間的搜索范圍，也提高了粒子的搜索速度，與此同時，利用高層中的CS算法來搜索全局的最優(yōu)點，以保證算法收斂性。上述算法能夠在搜索可行解的過程中，兼顧效率和精度兩個方面。

結(jié)合圖1，多種群分層PSO-CS聯(lián)合優(yōu)化算法的思路為：在底層中，將種群平均劃分為k個小種群，使用PSO算法優(yōu)化每個小種群，進行局部并行搜索；將每個小種群中的精英粒子si(i=1，…，k)送到高層，使用CS算法進行深度優(yōu)化，優(yōu)化后的較優(yōu)解分別返回到各自的小種群中；底層和高層的粒子若有可行解，則找出可行解的Pareto前沿解集，將解集放入外部檔案中，并對外部檔案更新。這種多種群分層聯(lián)合優(yōu)化結(jié)構(gòu)提高了算法收斂性和全局搜索能力。

圖1 多種群分層PSO-CS聯(lián)合優(yōu)化框架圖

該算法在底層小種群之間，通過整個種群的最優(yōu)值進行間接交流，增強了粒子的多樣性。每個小種群不僅根據(jù)該種群個體最優(yōu)和全局最優(yōu)來修正本種群內(nèi)粒子的速度和位置，還要考慮整個種群全局最優(yōu)值來修正粒子速度和位置。標準粒子群的迭代公式修正為

(13)

(14)

不同于單目標優(yōu)化，在解決列車多目標優(yōu)化問題時，如何選擇合適的小種群全局最優(yōu)值Besti和整個種群的全局最優(yōu)值gBest，用于指導各小種群中粒子的“飛行”顯得十分重要。

小種群全局最優(yōu)值Besti選擇策略為：若小種群中所有粒子均為不可行解，選擇違反約束程度最小的粒子作為Besti；若小種群中只有一個粒子是可行解，則該粒子作為Besti；若小種群中有多個可行解，找出可行解的Pareto前沿解，從Pareto前沿解中隨機選取一個粒子作為Besti。

整個種群中的所有粒子單獨選擇gBest，其策略為：若外部檔案沒有解，選擇整個種群違反約束程度最小的粒子作為gBest；若外部檔案存在解，每個粒子隨機地從外部檔案中選擇一個粒子作為gBest。

圖1中小種群精英粒子si的選擇策略為：若小種群中所有粒子均為不可行解，選擇違反約束程度最小的粒子作為小種群精英粒子；若小種群中的粒子有可行解，將可行解中所有Pareto前沿解作為小種群的精英粒子。

2.3.2 算法步驟和流程

算法底層：

步驟1初始化PSO相關(guān)參數(shù)，隨機生成N個粒子作為初始種群，將整個初始種群均分成k個小種群。

步驟2計算每個粒子的目標向量{T，E}，存儲每個粒子的個體歷史最優(yōu)值pBest，找出每個小種群的全局最優(yōu)值Besti和整個種群的全局最優(yōu)值gBest。

步驟3利用式(13)和式(14)分別更新粒子的速度和位置。

步驟4計算每個粒子的目標向量{T，E}，若存在Pareto前沿解集，則更新外部檔案。

算法高層：

步驟5計算每個小種群的精英解，并將精英解送往高層作為布谷鳥的初始位置，精英解的個數(shù)作為鳥巢的個數(shù)，初始化CS算法的參數(shù)。

步驟6用式(10)更新鳥巢位置，對更新后的鳥巢位置進行相應測試，與上一代鳥巢位置比較，將測試值好的保留，并轉(zhuǎn)入下一步。

步驟7產(chǎn)生[0，1]之間的隨機數(shù)rand，設(shè)定鳥巢被發(fā)現(xiàn)的概率pa，并與rand比較。若pa≤rand，則隨機改變鳥巢的位置，否則保持不變。進一步測試鳥巢改變后位置，將它與上一步獲得的鳥巢位置對比，把適應度好的鳥巢位置保留下來。

步驟8計算高層每個粒子目標向量{T，E}，若存在Pareto前沿解集，則更新外部檔案，將上層更新后的粒子分別返回各自所在的小種群。

步驟9判斷是否達到終止條件，若達到，輸出外部檔案Pareto最優(yōu)解集；否則，返回步驟2。

算法的具體流程如圖2所示。

圖2 算法流程圖

3 仿真實驗及分析

3.1 仿真參數(shù)設(shè)置

為驗證所提方法的有效性，以重慶軌道三號線鄭家院子到唐家院線路為例，在Matlab環(huán)境下進行仿真。

(1)線路參數(shù)：線路的參數(shù)見表1。

表1 線路參數(shù)

(2)列車參數(shù)：采用6節(jié)編組，總重量162 t，長度120 m。從大到小依次將牽引、惰行和制動所產(chǎn)生的加速度值進行編碼，編碼采用實數(shù)方式。先將最大的3級牽引加速度編碼設(shè)置為1，然后該編碼依次遞增，直到4級制動減速度的編碼值為8結(jié)束。表2列出了列車在不同運行工況下的參數(shù)取值及所對應的編碼。

表2 列車運行工況參數(shù)取值

(3)運行參數(shù)：列車運行區(qū)間目標時間85～95 s。

(4)參數(shù)設(shè)置：MOPSO種群數(shù)100，迭代次數(shù)250，其他參數(shù)按照參考文獻[14]設(shè)置。多種群分層PSO-CS聯(lián)合優(yōu)化算法的參數(shù)設(shè)置：慣性權(quán)重w=1，學習因子c1=c2=c3=2，步長因子α=1，鳥窩被發(fā)現(xiàn)概率pα=0.25，種群粒子總數(shù)50，小種群個數(shù)5，迭代次數(shù)500，兩種算法函數(shù)評價次數(shù)均為25 000次。

根據(jù)種群粒子總數(shù)為50，將小種群個數(shù)取為5，既保證小種群數(shù)量恰當，又保證了每個小種群中粒子數(shù)適中，這樣本文所提算法的收斂性和多樣性均達到最佳。

3.2 算法性能評價指標

在多目標優(yōu)化問題中，為了驗證所提出算法的優(yōu)越性，首先需要明確以下幾個指標，對算法的收斂性和多樣性進行度量。

(1)收斂性指標GD

(15)

式中：n為算法得到的Pareto前沿解個數(shù)；di為第i個解與真實Pareto前端之間的最短距離。該值越小，表明算法的收斂性越好。

(2)收斂性指標γ

(16)

式中：p*=(p1，p2，…，p|p*|)為真實Pareto前沿解集，A=(a1，a2，…，a|A|)為算法得到Pareto前沿解集。γ越小則算法逼近真實Pareto前沿解集的程度越好。

(3)多樣性指標SP

(17)

(4)多樣性指標Δ

(18)

3.3 實驗結(jié)果及分析

將所提出的多種群分層PSO-CS聯(lián)合優(yōu)化算法和MOPSO算法分別用于列車自動駕駛曲線的優(yōu)化。上述兩種算法分別獨立運行30次，從收斂性指標GD、γ和多樣性指標SP、Δ以及Pareto前沿解的個數(shù)等方面，分別對兩種算法的結(jié)果進行統(tǒng)計比較，以此衡量算法的優(yōu)劣性。算法的性能比較統(tǒng)計結(jié)果見表3。

表3 性能評價指標統(tǒng)計結(jié)果

從表3統(tǒng)計結(jié)果可以看出：根據(jù)Pareto前沿解的收斂性、多樣性和數(shù)量的比較，多種群分層PSO-CS聯(lián)合優(yōu)化算法性能指標均優(yōu)于MOPSO算法。從各指標的平均值可以看出，所提出的算法不僅收斂速度快，還能增加解的多樣性，同時解的個數(shù)也較多。

圖3和圖4分別是MOPSO算法和多種群分層PSO-CS聯(lián)合優(yōu)化算法的解空間分布情況。從圖3、圖4可以看出，在兩種算法得到的可行解中，Pareto前沿解都處于解空間內(nèi)側(cè)，滿足運行時間較短和能耗小的目標。采用MOPSO算法得到的可行解數(shù)量少且分布稀疏。而多種群分層PSO-CS聯(lián)合優(yōu)化算法得到的可行解數(shù)量較多且分布均勻，大量可行解都集中靠近Pareto前沿。

圖3 MOPSO算法的解空間

圖4 PSO-CS算法的解空間

圖5是兩種算法的Pareto前沿解比較。從圖5可知，采用所提出算法獲得Pareto前沿解更加靠近內(nèi)側(cè)，收斂性更好。在相同運行時間下，用該算法得到的解，能耗更低；采用所提出算法得到的解集向左端拓展，分布范圍更廣，意味著可獲得更短的列車運行時間；所提出算法獲得的解分布更均勻，相鄰解之間間隙小。而MOPSO算法獲得的相鄰解之間的間隙較大，需要進行填充才能增加解的多樣性。

圖5 兩種算法的Pareto前沿解比較

從Pareto前沿解可知，列車運行時間和能耗之間相互矛盾，即列車運行時間越短所需能耗越高，列車運行時間越長能耗越低。可以通過選擇恰當?shù)目刂撇呗詠頋M足列車實際運行的要求。采用本文提出算法得到Pareto前沿最優(yōu)解集后，可以獲得最省時、最節(jié)能和兩個目標折衷的列車運行速度-距離曲線，如圖6所示。

圖6 三種不同要求的速度-距離曲線

結(jié)合圖5和圖6，當時間最優(yōu)時，所對應的時間和能耗分別是86.02 s和48 151.82 kJ；當能耗最優(yōu)時，所對應的時間和能耗分別為94.82 s和36 598.49 kJ；若性能折衷，則所需的時間和能耗分別為90.31s和40 197.05 kJ。

當列車輸入控制序列數(shù)設(shè)置為7，在上述3種不同要求下，圖6中速度-距離曲線所對應控制序列下的加速度和距離值見表4。從表4可知，當時間最優(yōu)時，惰行的距離最短，為176 m；而當能耗最優(yōu)時，惰行的距離最長，為380 m。

表4 三種不同要求下的控制策略

4 結(jié)論

針對城軌列車在滿足安全、精確停車及各種約束條件下，以時間和能耗為優(yōu)化目標，建立列車運行操縱的多目標優(yōu)化數(shù)學模型。提出一種多種群分層聯(lián)合優(yōu)化的多目標算法，將它用于城軌列車ATO中，通過仿真實驗得到如下結(jié)論：

(1)針對將多目標加權(quán)轉(zhuǎn)化為單目標問題而存在的缺點，提出的算法能夠避免由于各目標間的相互影響而不能得到需要的解集。

(2)將多種群PSO算法與CS算法的優(yōu)點相結(jié)合，采用分層聯(lián)合優(yōu)化的策略，與MOPSO算法相比較，提高了Pareto前沿解的收斂性。由此得到的列車控制策略，可以讓列車在相同運行時間下降低能耗。

(3)與MOPSO算法相比，本文所提算法獲得Pareto前沿解的多樣性更為優(yōu)越。這為設(shè)計者提供了更多、更靈活的選擇方案，在設(shè)計列車ATO運行模式曲線時，具有更大的選擇空間。

參考文獻：

[1]林穎,王長林.車載ATO運行等級模式曲線的計算模型研究[J].鐵道學報,2013,35(7):50-55.

LIN Ying,WANG Changlin.Computational Model of Operation Level Type Profile of Onboard ATO[J].Journal of the China Railway Society,2013,35(7):50-55.

[2]丁勇,劉海東,栢赟,等.地鐵列車節(jié)能運行的兩階段優(yōu)化模型算法研究[J].交通運輸系統(tǒng)工程與信息,2011,11(1):96-101.

DING Yong,LIU Haidong,BAI Yun,et al.A Two-level Optimization Model and Algorithm for Energy-Efficient Urban Train Operation[J].Journal of Transportation Systrms Engineering and Information Technology,2011,11(1):96-101.

[3]余進,何正友,錢清泉.基于混合微粒群優(yōu)化的多目標列車控制研究[J].鐵道學報,2010,32(1):38-42.

YU Jin,HE Zhengyou,QIAN Qingquan.Study on Multi-objective Train Control Based on Hybrid Particle Swarm Optimization[J].Journal of the China Railway Society,2010,32(1):38-42.

[4]黃友能,宮少豐,曹源,等.基于粒子群算法的城軌列車節(jié)能駕駛優(yōu)化模型[J].交通運輸工程學報,2016,16(2):118-124.

HUANG Youneng,GONG Shaofeng,CAO Yuan,et al.Optimization Model of Energy-efficient Driving for Train in Rail Transit Based on Particle Swarm Algorithm[J].Journal of Traffic and Transportation Engineering,2016,16(2):118-124.

[5]孫其升,胡文斌,陳磊,等.基于粒子群優(yōu)化算法的地鐵列車節(jié)能運行研究[J].城市軌道交通研究,2015,18(10):84-88.

SUN Qisheng,HU Wenbin,CHEN Lei,et al.On Subway Trains’ Energy Saving Operation Based on PSO[J].Urban Mass Transit,2015,18(10):84-88.

[6]嚴細輝,蔡伯根,寧濱,等.基于差分進化的高速列車運行操縱的多目標優(yōu)化研究[J].鐵道學報,2013,35(9):65-71.

YAN Xihui,CAI Baigen,NING Bin,et al.Research on Multi-objective High-speed Train Operation Optimization Based on Differential Evolution[J].Journal of the China Railway Society,2013,35(9):65-71.

[7]WEI S G,YAN X H,CAI B G,et al.Multiobjective Optimization for Train Speed Trajectory in CTCS High-speed Railway with Hybrid Evolutionary Algorithm[J].IEEE Transactions on Intelligent Transportation Systems,2015,16(4):2215-2225.

[8]CARVAJAL-CARRENO W,CUCALA A P,FERNANDEZ-CARDADOR A.Optimal Design of Energy-efficient ATO CBTC Driving for Metro Lines Based on NSGA-Ⅱ with Fuzzy Parameters[J].Engineering Applications of Artificial Intelligence,2014(36):164-177.

[9]SICRE C,CUCALA A P,FERNANDEZ-CARDADOR A.Real Time Regulation of Efficient Driving of High Speed Trains Based on a Genetic Algorithm and a Fuzzy Model of Manual Driving[J].Engineering Applications of Artificial Intelligence,2014(29):79-92.

[10]荀徑,楊欣,寧濱,等.列車節(jié)能操縱優(yōu)化求解方法綜述[J].鐵道學報,2014,36(4):14-19.

XUN Jing,YANG Xin,NING Bin,et al.Survey on Trajectory Optimization for Train Operation[J].Journal of the China Railway Society,2014,36(4):14-19.

[11]YANG H,LIU H E,FU Y T.Multi-objective Operation Optimization for Electric Multiple Unit-based on Speed Restriction Mutation[J].Neurocomputing,2015,169:383-391.

[12]LU S F,HILLMANSEN S,HO T K,et al.Single-train Trajectory Optimization[J].IEEE Transactions on Intelligent Transportation Systems,2013,14(2):743-750.

[13]余進,何正友,錢清泉.基于微粒群算法的多目標列車運行過程優(yōu)化[J].西南交通大學學報,2010,45(1):70-75.

YU Jin,HE Zhengyou,QIAN Qingquan.Multi-objective Train Operation Optimization Based on Particle Swarm Algorithm[J].Journal of Southwest Jiaotong University,2010,45(1):70-75.

[14]DOMINGUEZ M,FERNANDEZ-CARDADOR A,CUCALA A P,et al.Multi Objective Particle Swarm Optimization Algorithm for the Design of Efficient ATO Speed Profiles in Metro Lines[J].Engineering Applications of Artificial Intelligence,2014(29):43-53.

[15]GHODRATI A,LOTFI S.A Hybrid CS/PSO Algorithm for Global Optimization[C]//Asian Conference on Intelligent Information & Database Systems,2012:89-98.

[16]WANG F,HE X S,LUO L,et al.Hybrid Optimization Algorithm of PSO and Cuckoo[C]//International Conference on Artificial Intelligence.New York:IEEE,2011:1172-1175.

[17]毛保華,李夏苗.列車運行計算與設(shè)計[M].2版.北京:人民交通出版社,2013:72-75.

[18]蘭少峰,劉升.布谷鳥搜索算法研究綜述[J].計算機工程與設(shè)計,2015,36(4):1064-1067.

LAN Shaofeng,LIU Sheng.Overview of Research on Cuckoo Search Algorithm[J].Computer Engineering and Design,2015,36(4):1064-1067.