方文雄，侯宇婷，蔡 煊

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

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

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

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

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

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

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

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

2 粒子群進路搜索算法建模

2.1 粒子群算法引入

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

第i個粒子的位置為一個矢量：

第i個粒子的速度為一個矢量：

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

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

第i個粒子在k次迭代時的速度為：

第i個粒子位置更新公式：

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

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

2.2.1 粒子編碼

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

2.2.2 進路搜索算法實現(xiàn)

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

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

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

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

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

2.3 目標函數(shù)

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

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

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

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

3 仿真與分析

3.1 實驗仿真

以圖1站場為例，選排北京方向下行至4G接車進路進行仿真分析。

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

2）輸入搜索進路的始端、終端按鈕編號2和21。

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

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

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

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

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

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

測試參數(shù)c1、c2滿足方程c1＋c2=1－ω相對變化時的程序執(zhí)行效率。結(jié)果表明：當ω在0.3～0.5時，整體搜索效果較好。測試結(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不變

測試參數(shù)c2、ω滿足方程ω＋c2=1－c1相對變化時的程序執(zhí)行效率。結(jié)果表明當c2與ω差值較大時，搜索效率下降。c2在0.3～0.5時，搜索效果較好。測試結(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不變

測試參數(shù)c1、ω滿足方程ω＋c1=1－c2相對變化時的程序執(zhí)行效率。結(jié)果表明：當c2=0.5時，隨c1增大搜索時間顯著增大，c1在0.3～0.6時，整體搜索效果較好。測試結(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)計

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

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

4 結(jié)束語

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

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

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