基于粒子群算法的車站列車進路搜索方法研究

方文雄，侯宇婷，蔡 煊

（成都工業學院汽車與交通學院，成都 611730）

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

1 車站站場數據結構分析

如圖1所示以典型車站平面布置為例，結合文獻[7]構建站場型數據結構?？紤]模型的簡潔性，本文只考慮車站列車作業，調車作業進路搜索原理及數學模型參考列車作業。

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

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

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

圖2 數據結構Fig.2 Data structure diagram

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

2.1 粒子群算法引入

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

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

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

第i個粒子搜索到的最優位置為：

整個粒子群搜索到的最優位置為：

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

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

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

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

2.2.1 粒子編碼

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

2.2.2 進路搜索算法實現

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

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

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

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

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

2.3 目標函數

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

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

公式（10）中第一項只要本節點與前一節點相連差值就為0，當第一項中累加為0，表示能夠構成所選節點相連的進路。第二項為K集合中元素的數目，用來區分基本進路與變更進路，所以當F(K)取值最小，對應的粒子為全局最優解，即搜索出能夠滿足約束要求的進路。

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

3 仿真與分析

3.1 實驗仿真

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

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

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

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

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

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

3.2 參數最優取值范圍分析

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

3.2.1 控制慣性參數ω不變

測試參數c1、c2滿足方程c1＋c2=1－ω相對變化時的程序執行效率。結果表明：當ω在0.3～0.5時，整體搜索效果較好。測試結果如圖5所示。

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

3.2.2 控制歷史最優參數c1不變

測試參數c2、ω滿足方程ω＋c2=1－c1相對變化時的程序執行效率。結果表明當c2與ω差值較大時，搜索效率下降。c2在0.3～0.5時，搜索效果較好。測試結果如圖6所示。

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

3.2.3 控制全局最優參數c2不變

測試參數c1、ω滿足方程ω＋c1=1－c2相對變化時的程序執行效率。結果表明：當c2=0.5時，隨c1增大搜索時間顯著增大，c1在0.3～0.6時，整體搜索效果較好。測試結果如圖7所示。

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

3.3 參數最優統計

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

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

4 結束語

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

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

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