基于粒子群算法的車站列車進(jìn)路搜索方法研究

方文雄，侯宇婷，蔡 煊

（成都工業(yè)學(xué)院汽車與交通學(xué)院，成都 611730）

目前，鐵路信號(hào)機(jī)、岔道及軌道電路之間的制約關(guān)系廣泛采用計(jì)算機(jī)聯(lián)鎖進(jìn)行控制[1]，進(jìn)路搜索是計(jì)算機(jī)聯(lián)鎖的重要功能。文獻(xiàn)[2]中提出了結(jié)合二叉樹(shù)、四叉鏈表和高度原則的搜索算法，文獻(xiàn)[3]中采用深度優(yōu)先搜索方式，適用于道岔較少的車站。文獻(xiàn)[4]中采用廣度優(yōu)先搜索方式，適用于股道較少的車站。文獻(xiàn)[5]中基于站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)，提出采用高度搜索方法克服廣度和深度優(yōu)先算法的不足，并在規(guī)模較大站場(chǎng)（16股道、104組道岔）中測(cè)試了深度搜索與優(yōu)化后的搜索方式的搜索耗時(shí)都在5 s左右。其實(shí)驗(yàn)數(shù)據(jù)說(shuō)明當(dāng)站場(chǎng)規(guī)模較大時(shí)，以上搜索算法無(wú)論是否進(jìn)行優(yōu)化，其搜索效率都大大降低，其原因在于，以上算法從搜索策略上均屬于遍歷搜索或是基于改進(jìn)數(shù)據(jù)結(jié)構(gòu)、優(yōu)化約束條件而在局部范圍進(jìn)行的遍歷搜索，一旦站場(chǎng)規(guī)模增大搜索量將呈幾何增長(zhǎng)。文獻(xiàn)[6]依托智能優(yōu)化型算法，提出基于遺傳算法（Genetic Algorithm，GA）的概率型進(jìn)路搜索方法，搜索結(jié)果以大概率朝全局最優(yōu)結(jié)果演化，從而避免了對(duì)全局進(jìn)行搜索，但沒(méi)有解決智能優(yōu)化型算法普遍存在易收斂局部最優(yōu)的問(wèn)題。粒子群算法(Particle Swarm Optimization，PSO）同屬于智能優(yōu)化型算法，各粒子之間通過(guò)信息共享朝向全局最優(yōu)范圍進(jìn)行搜索，避免了對(duì)全局搜索。本文將粒子群算法應(yīng)用于進(jìn)路搜索，與遍歷搜索型算法相比，在站場(chǎng)規(guī)模增大時(shí)對(duì)搜索效率的影響更??；與遺傳算法相比，能夠以更小的搜索種群與更少的迭代次數(shù)完成進(jìn)路搜索，且采用迭代次數(shù)控制與精度控制相結(jié)合的方式解決了搜索過(guò)程中收斂局部最優(yōu)的問(wèn)題。

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

如圖1所示以典型車站平面布置為例，結(jié)合文獻(xiàn)[7]構(gòu)建站場(chǎng)型數(shù)據(jù)結(jié)構(gòu)?？紤]模型的簡(jiǎn)潔性，本文只考慮車站列車作業(yè)，調(diào)車作業(yè)進(jìn)路搜索原理及數(shù)學(xué)模型參考列車作業(yè)。

圖1 車站平面布置Fig.1 Station layout

將選排進(jìn)路中所途經(jīng)信號(hào)機(jī)、道岔、軌道電路視為節(jié)點(diǎn)統(tǒng)一編號(hào)描述，編號(hào)原則為由下向上、由左向右的順序?qū)?jié)點(diǎn)按序編號(hào)。在某一軌道電路上可能同時(shí)存在防護(hù)本軌道區(qū)段的信號(hào)機(jī)與道岔，即在同一軌道區(qū)段中包含3種信號(hào)設(shè)備節(jié)點(diǎn)，為了避免在同一位置冗余定義節(jié)點(diǎn)，在定義過(guò)程中優(yōu)先選擇道岔作為節(jié)點(diǎn)，再選擇軌道電路，最后再考慮信號(hào)機(jī)。為了描述信號(hào)設(shè)備之間的前后位置聯(lián)系，將其他節(jié)點(diǎn)與本節(jié)點(diǎn)的位置聯(lián)系信息存儲(chǔ)于本節(jié)點(diǎn)數(shù)據(jù)中，同時(shí)只考慮單向連接，即只在本節(jié)點(diǎn)存儲(chǔ)與本節(jié)點(diǎn)相連的前一節(jié)點(diǎn)編號(hào)，不存儲(chǔ)與本節(jié)點(diǎn)相連的下一節(jié)點(diǎn)編號(hào)。數(shù)據(jù)結(jié)構(gòu)如圖2所示。

圖2中每一節(jié)點(diǎn)數(shù)據(jù)定義為（pf1,pf2,i），其中pf1為水平方向上所連接的前一節(jié)點(diǎn)的編號(hào)，pf2為渡線方向上所連接的前一節(jié)點(diǎn)的編號(hào)，若不存在則為0；i為本節(jié)點(diǎn)編號(hào)（i=1、2、3...）。在辦理接車進(jìn)路時(shí)，按搜索結(jié)果順序輸出途經(jīng)節(jié)點(diǎn)。辦理發(fā)車進(jìn)路時(shí)，按照進(jìn)站方向搜索，逆序輸出途經(jīng)節(jié)點(diǎn)。

圖2 數(shù)據(jù)結(jié)構(gòu)Fig.2 Data structure diagram

2 粒子群進(jìn)路搜索算法建模

2.1 粒子群算法引入

粒子群算法是一種隨機(jī)全局優(yōu)化算法，通過(guò)粒子間的相互作用發(fā)現(xiàn)復(fù)雜搜索空間中的最優(yōu)區(qū)域。算法描述為[8]在D維區(qū)域里存在m個(gè)粒子，如公式（1）～（6）所示。

第i個(gè)粒子的位置為一個(gè)矢量：

第i個(gè)粒子的速度為一個(gè)矢量：

第i個(gè)粒子搜索到的最優(yōu)位置為：

整個(gè)粒子群搜索到的最優(yōu)位置為：

第i個(gè)粒子在k次迭代時(shí)的速度為：

第i個(gè)粒子位置更新公式：

其中i=1, 2, 3…m；d=1, 2, 3…D；ω稱為慣性參數(shù)；c1、c2稱為學(xué)習(xí)因子；r1、r2為隨機(jī)數(shù)；公式（5）中等號(hào)右邊， 為歷史速度的記憶、為個(gè)體認(rèn)知部分、為社會(huì)認(rèn)知部分。

2.2 改造粒子群算法建立模型

2.2.1 粒子編碼

在標(biāo)準(zhǔn)的粒子群算法中，粒子的位置與速度是可以連續(xù)取值的，以單個(gè)粒子的移動(dòng)在解空間進(jìn)行搜索。而在進(jìn)路搜索中由于節(jié)點(diǎn)位置是離散的，如果粒子位置離散取值，帶來(lái)一定的困難，并且一個(gè)粒子的位置無(wú)法記錄下一條進(jìn)路中多個(gè)節(jié)點(diǎn)的位置。鑒于此，根據(jù)節(jié)點(diǎn)取值特點(diǎn)，使用二進(jìn)制對(duì)節(jié)點(diǎn)選取進(jìn)行表示。當(dāng)一個(gè)節(jié)點(diǎn)取值為1，表示搜索的進(jìn)路包含此節(jié)點(diǎn)，為0反之?，F(xiàn)對(duì)搜索粒子做出新的定義：一個(gè)粒子代表一條可能滿足要求的進(jìn)路，表示為：x={x1,x2,x3...xD}，其中xd（d=1...D）的取值表示第d個(gè)節(jié)點(diǎn)是否選中，D表示站場(chǎng)中節(jié)點(diǎn)的個(gè)數(shù)。如x20=1，表示編號(hào)為20的節(jié)點(diǎn)被選中。這樣一來(lái)，一個(gè)粒子就是長(zhǎng)度為D的0、1序列，就可以表示一條進(jìn)路。進(jìn)路搜索也就是在眾多粒子中選擇最優(yōu)解問(wèn)題。

2.2.2 進(jìn)路搜索算法實(shí)現(xiàn)

設(shè)粒子種群為集合X，包含m個(gè)粒子xi={xi1,xi2,xi3...xiD}，其中i=1, 2, 3…m。 表示一條可能滿足要求的進(jìn)路，通過(guò)不斷改變粒子中的節(jié)點(diǎn)取值，搜索出滿足要求的進(jìn)路?；诹Ｗ尤核惴ǖ倪M(jìn)路搜索算法流程如圖3所示。

圖3 算法流程Fig.3 Algorithm flow chart

由于進(jìn)路搜索中粒子具有新的含義，所以要重新定義迭代公式，第i個(gè)粒子在第k次迭代如公式（7）～(9)所示。

其中i=1, 2, 3…m，xi為第i個(gè)粒子的序列；Pi為第i個(gè)粒子的歷史最優(yōu)解序列；Pgbest為截止到第k代所有粒子中最優(yōu)序列又稱全局最優(yōu)序列。ω為慣性參數(shù)；c1為歷史最優(yōu)參數(shù)；c2為全局最優(yōu)參數(shù)，rand(a%,b)表示隨機(jī)在b的0、1序列中，抽取占b中a%的序列。rand_rever(b)表示隨機(jī)對(duì)b序列中某一位取反操作。

在公式(7)中通過(guò)rand(a%,b)的隨機(jī)抽取操作，模擬標(biāo)準(zhǔn)粒子群算法中r1、r2隨機(jī)數(shù)。3個(gè)參數(shù)與標(biāo)準(zhǔn)粒子群算法中類似，代表歷史記憶、個(gè)體認(rèn)知部分、社會(huì)認(rèn)知部分所占權(quán)重，下一代粒子的序列來(lái)自于上一代粒子序列與該粒子歷史最優(yōu)序列和全局最優(yōu)序列，并且這3部分所占比例分別為ω、c1、c2。因此這3個(gè)系數(shù)要受到公式（8）的約束。粒子群算法可能在搜索過(guò)程中陷入局部最優(yōu)解，為提高粒子的搜索能力，在每次迭代過(guò)程中通過(guò)公式（9）隨機(jī)對(duì)序列中某1位取反，產(chǎn)生突變，從而跳出局部最優(yōu)解，改善進(jìn)路搜索能力。

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

一條合理的進(jìn)路，應(yīng)該是被選中的節(jié)點(diǎn)從始端到終端在站場(chǎng)位置上是相連的，即由一個(gè)粒子中值為1的節(jié)點(diǎn)所組成的子集，該子集的節(jié)點(diǎn)從始端到終端依次連接。在站場(chǎng)中還存在變更進(jìn)路滿足上述約束，為了能夠選出基本進(jìn)路，按照基本進(jìn)路對(duì)車站作業(yè)影響最小的含義，約定所途經(jīng)節(jié)點(diǎn)數(shù)目最小的為基本進(jìn)路。所以做出約束為：在多個(gè)粒子同時(shí)滿足其全為1子集的節(jié)點(diǎn)是相連的條件下，子集元素?cái)?shù)目小的為基本進(jìn)路。按照以上約束條件，結(jié)合適應(yīng)度函數(shù)做出改進(jìn)，提出目標(biāo)函數(shù)如公式（10）所示。

K為該粒子中取值為1的節(jié)點(diǎn)所構(gòu)成的子集，n是K中節(jié)點(diǎn)對(duì)應(yīng)的粒子編號(hào)集合，例如某粒子x={0, 1, 0…, 1, 0}，對(duì)應(yīng)的K={1, 1, 1, 1, 1}、n={2, 5,8, 9, 12}。m為K中元素的個(gè)數(shù)；ni表示n中第i個(gè)編號(hào)；pf1ni表示節(jié)點(diǎn)編號(hào)為ni的pf1值；pf2ni表示節(jié)點(diǎn)編號(hào)為ni的pf2值。

公式（10）中第一項(xiàng)只要本節(jié)點(diǎn)與前一節(jié)點(diǎn)相連差值就為0，當(dāng)?shù)谝豁?xiàng)中累加為0，表示能夠構(gòu)成所選節(jié)點(diǎn)相連的進(jìn)路。第二項(xiàng)為K集合中元素的數(shù)目，用來(lái)區(qū)分基本進(jìn)路與變更進(jìn)路，所以當(dāng)F(K)取值最小，對(duì)應(yīng)的粒子為全局最優(yōu)解，即搜索出能夠滿足約束要求的進(jìn)路。

由于智能優(yōu)化算法可能陷入局部最優(yōu)解的普遍共性，為了確保進(jìn)路搜索的準(zhǔn)確性，必須要有精度控制的環(huán)節(jié)，即保證F(K)－m=0。單純采用精度控制搜索結(jié)束喪失了一定的高效性，因?yàn)橐坏┫萑刖植孔顑?yōu)解時(shí)，需要一定時(shí)間等待跳出局部最優(yōu)，再尋找到全局最優(yōu)后結(jié)束搜索。為了兼顧安全性與高效性，采用迭代次數(shù)控制與精度控制相結(jié)合的方法結(jié)束搜索。先進(jìn)行迭代控制，迭代N次后結(jié)束搜索，再檢查搜索精度是否滿足要求，如不滿足要求重新執(zhí)行搜索程序，重復(fù)上述過(guò)程。這樣一來(lái)，一旦陷入局部最優(yōu)，滿足迭代次數(shù)時(shí)結(jié)束程序，重新搜索，避免長(zhǎng)時(shí)間等待。

3 仿真與分析

3.1 實(shí)驗(yàn)仿真

以圖1站場(chǎng)為例，選排北京方向下行至4G接車進(jìn)路進(jìn)行仿真分析。

1）初始化粒子種群數(shù)目為20個(gè)，并隨機(jī)賦值粒子0、1序列，設(shè)置迭代數(shù)目30代。

2）輸入搜索進(jìn)路的始端、終端按鈕編號(hào)2和21。

3）得出途經(jīng)節(jié)點(diǎn)編號(hào)為{2, 4, 5, 8, 11, 12, 13，17, 21}，搜索時(shí)間t=0.565 509 s，繪制目標(biāo)函數(shù)收斂曲線如圖4所示。

圖4 目標(biāo)函數(shù)收斂過(guò)程Fig.4 Objective function convergence process

4）實(shí)驗(yàn)結(jié)果表明：搜索算法能夠正確、安全、高效地完成進(jìn)路搜索，在第6代時(shí)找到全局最優(yōu)解F(K)=9，且滿足F(K)－m=0的精度要求。

3.2 參數(shù)最優(yōu)取值范圍分析

目前對(duì)于粒子群算法中，ω、c1、c23個(gè)參數(shù)合適的取值還沒(méi)有科學(xué)的依據(jù)，大多憑借經(jīng)驗(yàn)設(shè)置或動(dòng)態(tài)改變?nèi)≈礫9]。為了確定使搜索效率最高的取值，采用控制變量法，將一個(gè)參數(shù)取定值等于0.1、0.3、0.5、0.7的情況下，改變另外兩個(gè)參數(shù)取值，重復(fù)執(zhí)行5次取平均搜索時(shí)間，進(jìn)行參數(shù)最優(yōu)范圍測(cè)定。

3.2.1 控制慣性參數(shù)ω不變

測(cè)試參數(shù)c1、c2滿足方程c1＋c2=1－ω相對(duì)變化時(shí)的程序執(zhí)行效率。結(jié)果表明：當(dāng)ω在0.3～0.5時(shí)，整體搜索效果較好。測(cè)試結(jié)果如圖5所示。

圖5 ω不變，t隨c1、c2取值變化Fig.5 ω does not change, and t changes with the values of c1 and c2

3.2.2 控制歷史最優(yōu)參數(shù)c1不變

測(cè)試參數(shù)c2、ω滿足方程ω＋c2=1－c1相對(duì)變化時(shí)的程序執(zhí)行效率。結(jié)果表明當(dāng)c2與ω差值較大時(shí)，搜索效率下降。c2在0.3～0.5時(shí)，搜索效果較好。測(cè)試結(jié)果如圖6所示。

圖6 c1不變，t隨c2、ω取值變化Fig.6 c1 does not change, and t changes with the values of c2 and ω

3.2.3 控制全局最優(yōu)參數(shù)c2不變

測(cè)試參數(shù)c1、ω滿足方程ω＋c1=1－c2相對(duì)變化時(shí)的程序執(zhí)行效率。結(jié)果表明：當(dāng)c2=0.5時(shí)，隨c1增大搜索時(shí)間顯著增大，c1在0.3～0.6時(shí)，整體搜索效果較好。測(cè)試結(jié)果如圖7所示。

圖7 c2不變，t隨c1、ω取值變化Fig.7 c2 does not change, and t changes with the values of c1 and ω

3.3 參數(shù)最優(yōu)統(tǒng)計(jì)

將被控制的參數(shù)在每一定值情況下的最短搜索時(shí)間進(jìn)行統(tǒng)計(jì)，如表1所示。在任意被控制的參數(shù)取0.3，另外兩參數(shù)之比為0.75時(shí)，具有較好的搜索效率。以表1中最少的搜索時(shí)間，給出參數(shù)最優(yōu)取值為ω=0.3、c1=0.3、c2=0.4。

表 1 平均最低搜索時(shí)間t隨兩個(gè)參數(shù)比值變化情況Tab. 1 Average minimum search time t changes with the ratio of the two parameters

4 結(jié)束語(yǔ)

通過(guò)引入粒子群算法，并對(duì)粒子的含義與核心公式重新進(jìn)行定義，實(shí)現(xiàn)了一種基于粒子群算法的新的進(jìn)路搜索方法，為計(jì)算機(jī)聯(lián)鎖的進(jìn)路搜索方法提供了新的思路。

通過(guò)精度控制與迭代次數(shù)控制相結(jié)合的方式，確保了進(jìn)路搜索的準(zhǔn)確性、安全性和高效性。進(jìn)行實(shí)驗(yàn)統(tǒng)計(jì)分析，得到參數(shù)最優(yōu)取值為ω=0.3、c1=0.3、c2=0.4，為基于粒子群算法的進(jìn)路搜索方法工程應(yīng)用提供了數(shù)據(jù)指導(dǎo)。

需進(jìn)一步研究在其他進(jìn)路鎖閉情況下，進(jìn)路的搜索方式，改進(jìn)搜索模型，考慮在進(jìn)路搜索完成后驅(qū)動(dòng)信號(hào)燈、道岔狀態(tài)變化。