基于捕食搜索策略的粒子群算法求解高铁闭塞分区划分问题

王　瑞，陈永刚

(兰州交通大学自动化与电气工程学院，兰州　730070)



基于捕食搜索策略的粒子群算法求解高铁闭塞分区划分问题

王瑞，陈永刚

(兰州交通大学自动化与电气工程学院，兰州730070)

摘要：高铁闭塞分区的合理划分可以保证列车的运行安全、提高运输效率和减少投资成本。为了更好地解决这个问题，利用基于捕食搜索策略的粒子群算法求解优化准移动闭塞条件下的闭塞分区划分模型。捕食搜索策略可以平衡粒子的局域搜索和全局搜索，从而避免陷入局部最优，提高算法精度。通过算例仿真，比较基于捕食搜索策略的粒子群算法和标准粒子群算法对模型优化的结果，验证基于捕食搜索策略的粒子算法对模型的求解是有效的，而且得到的解更精确，运算速度更快。

关键词：高速铁路；捕食搜索策略；粒子群算法；闭塞分区；准移动闭塞

高速铁路建设首先解决的是选线设计和闭塞分区的设计。目前，我国闭塞分区长度的确定大多以区间运行时间间隔进行划分，这种划分方式由于需留有较大的列车追踪间隔，导致运行密度较低，运输效率不高[1]。所以，研究铁路闭塞分区的划分问题，尤其是准移动闭塞制式下闭塞分区划分问题，对于保证行车安全、提高线路通过能力和减少投资成本都具有重要意义。

目前，国外学者已经将启发式的坡道搜索算法[2]、遗传算法[3]、差分进化算法[4]、最大-最小蚁群算法[5]应用于地铁系统的信号机布局优化。国外学者主要针对城市轨道交通系统的闭塞分区划分问题进行了研究，没有涉及干线铁路。在国内，刘海东等人[6]实现了利用计算机建立仿真系统完成干线铁路三显示固定闭塞的信号机布置。刘剑峰等人[7]在分析了影响区间信号机布置因素后，建立了区间四显示固定闭塞信号机布置优化模型，并用遗传算法对模型进行了求解。国内学者虽然已将智能算法用于求解干线铁路固定闭塞条件下闭塞分区划分问题，但没有系统地分析闭塞分区划分的影响因素及其约束条件，约束条件较简单。并且较少研究准移动闭塞条件下的闭塞分区划分问题。再者其运用的算法存在编码过程复杂、计算量大、极易陷入局部最优等问题。现在运用基于捕食搜索策略的粒子群算法实现高速铁路闭塞分区的快速合理划分，提高闭塞分区划分的质量和速度。

1闭塞分区划分模型

主要研究准移动闭塞制式下、列车运行控制系统为CTCS-2级的高铁闭塞分区划分方法，以闭塞分区划分数量最少为优化目标，在满足列车追踪间隔时间和制动距离等因素的条件下进行闭塞分区划分，最终在保证列车运行安全和一定效率的前提下，实现降低建设成本和减少线路维修工作量的目的。

本文用到的模型来自参考文献[13]，为了提高计算精度，对模型中的部分参数进行了调整，并将文献[13]模型中的第一接近信号点位置条件去掉，而在区间信号点位置条件中进行重新定义。

1.1　定义变量

假设Ⅰ站和Ⅱ站相邻，两站之间信号点的个数为N，每个信号点位置的坐标为xi(i=1，2，…，N)。I站的反向进站信号机坐标为x0，Ⅱ站的进站信号机坐标为xN+1。对应的闭塞分区的长度li(i=1，2，…，N+1)为相邻两个信号点坐标的差值。

1.2　目标函数

为了达到降低建设成本和减少维修工作量的目的，闭塞分区划分数量在满足一定效率的条件下要尽可能的少，这里设定列车追踪间隔时间不大于H(3 min)。目标函数为

(1)

1.3　约束条件

约束条件如下所述。

(1)区间信号点位置

(2)

(3)

(2)闭塞分区长

(4)

(5)

式中，li为闭塞分区长度；lmin为闭塞分区的最小长度；lmax为闭塞分区最大长度。

(3)闭塞分区划分数量

闭塞分区划分数量n(n=N+1)，其取值条件如下

(6)

式中，lsection为Ⅰ站和Ⅱ站之间的区间长度。

(4)第一离去信号点位置

(7)

(5)第二接近信号点位置

(8)

式中，xN-1为第二接近信号点坐标；xc为第二接近信号点下限位置(由进站间隔时间计算得到)。

(6)CTCS轨道电路正常码序显示

(9)

(7)停车起动条件

列车在每个信号点前停车以后再次起动需要满足以下条件

(10)

式中，Fxi为列车在xi位置处的起动牵引力；Gq为列车总重；wq为列车单位基本阻力；iq为xi位置处坡度千分数。

(8)列车追踪间隔时间

(11)

式中，Ii为列车追踪间隔时间(闭塞分区划分完毕后根据公式进行计算)；H为给定的列车追踪间隔时间。

1.4　适应度函数

由于以闭塞分区划分数量最少为优化目标即求目标函数的最小值。因此，适应度函数定义如下

(12)

(13)

式中，P1与信号点限界位置有关；α为惩罚因子；N1为在给定范围外的信号点个数。

(14)

式中，P2与闭塞分区长度限值有关；β为惩罚因子；N2为分区长度在规定长度以外的个数。

(15)

式中，P3与轨道电路码序有关；γ为惩罚因子；N3为不满足轨道电路码序约束条件的闭塞分区个数。

(16)

式中，P4与第一离去信号点位置有关；ε为惩罚因子；当满足第一离去信号点条件时要减小个体适应度值。

(17)

式中，P5与第二接近信号点位置有关；λ为惩罚因子；当满足第二接近信号点条件时要减小个体适应度值。

(18)

式中，P6与列车追踪间隔有关；δ为惩罚因子；N4为大于给定列车追踪间隔时间H的闭塞分区个数。

(19)

上面各式中的惩罚因子α、β、γ、ε、λ、δ、μ，根据惩罚强弱程度不同而取值不同，其取值在10～30。

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

2.1　粒子群算法

粒子群算法(Particle Swarm Optimization， PSO)是由Kennedy博士 和 Eberhart教授于1995年提出来的。PSO是一种随机的、并行的优化算法。其算法简单，容易实现，且不要求被优化函数具有可微、可导、连续等性质，收敛速度快。

假设在D维空间中求解，群体中有m个粒子，这些粒子在解空间中以一定的速度飞行，每个粒子都是一个可能的解， 都是一个D维向量，记作xi=(xi1，xi2，…，xiD)，即第i(i=1，2，…，m)个粒子在 D维的搜索空间中的位置是xi。将满足设定的约束条件的xi带入预设的适应度函数中，可以计算每个粒子的适应度值， 然后依据适应度值的大小判定xi的优劣。在搜索过程中，每个粒子根据自己搜索到的历史最优位置和群体内或邻域内其他粒子搜索到的历史最优位置进行位置的变化。第i个粒子的速度也是一个D维向量，记作vi=(vi1，vi2，…，viD)，第i个粒子搜索到的历史最好点记作pi=(pi1，pi2， …，piD)，整个群体搜索到的历史最优点记作pg=(pg1，pg2，…，pgD)。粒子的位置和速度都是实数，其根据下面的方程进行变化

(20)

(21)

式中，c1和c2称为学习因子或加速系数；ξ，η是在[0，1]区间内的均匀分布的伪随机数；ω称为惯性权重，是一个位于[0，1]区间内的常数；k为迭代次数。

2.2　捕食搜索策略

粒子群算法计算简单、容易实现、收敛速度快，但是由于粒子交流信息量过大和信息流动的单一性，粒子就会加速聚集。随着迭代的进行，粒子种群多样性就会下降，迭代后期很难找到更好的解，容易陷入局优。使得算法对复杂问题的开发能力减弱。为了解决这个问题将捕食搜索策略引入到标准粒子群算法中。

捕食搜索(Predatory Search， PS)是由巴西学者Alexandre Linhares在1998年提出来的一种用于解决组合优化问题的模拟动物捕食行为的空间搜索策略。捕食搜索策略的思想：在整个解空间内进行全局搜索，找到一个较优解，然后在找到的较优解的周围进行局域搜索，在进行多次搜索后，未发现更好的解，放弃局域搜索，转到全局搜索。经过这样多次循环最终找到最优解。由于大部分搜索时间都在较优解附近的较小区域进行搜索，所以搜索高效且速度快。将其引入到标准粒子群算法中，第一可以提高算法前期的迭代搜索能力，抑制早熟；第二可以提高算法的后期搜索能力找到更精确的解。

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

在把捕食搜索策略引入到标准粒子群算法过程中，首先将限制定义为多维解空间内的两点间的距离。粒子在某限制下的邻域定义为与粒子的距离小于该限制的多维空间。在解空间内设置NL级限制：R(1)，R(2)，…，R(NL)。

在最小限制R(1)规定的邻域内随机初始化m个粒子，根据标准PSO公式迭代若干次，试图找到更优解，当PSO进行Cs次还不能找到，则增加限制到R(2)，在其邻域内初始化粒子群，根据公式迭代，若能找到则替换历史最优解，并重新计算限制，若不能则继续增加限制等级，随着限制等级的增加搜索空间也在增大。当限制等级达到某一个值Ls时，而无法找到更优解时，就需放弃区域搜索，将搜索限制增加到一个较高的等级Lh，也就跳出了局部最优，如此循环，直到设定的限制等级NL规定的邻域也搜索完成。

重新计算限制方法如下：

(1)在初始解空间利用标准粒子群算法搜索NL次，得到NL个解；

(2)把这NL个解按照到发现的历史最优解的距离从小到大排列，组成NL级限制。

算法主要步骤如下：

步骤1在解空间内随机选择一个解x，令其为历史最优解pg，pg=x，PSO进行次数k=0，限制等级L=1；

步骤2若L≤NL，在x的R(L)限制内初始化m个粒子，粒子的最大速度为当前限制，按照公式(19)、公式(20)迭代若干次，找到其历史最优解p，然后转到步骤3，否则结束；

步骤3令x=p，解x的适应值与历史最优解pg的适应值进行比较，若f(x)

步骤4令k=k+1，若k≤Cs，则转步骤2，否则令L=L+1，转步骤5；

步骤5若L=Ls，则令L=Lh，转步骤2，否则直接转步骤2。

3算例分析

3.1　数据准备

以Ⅰ站—Ⅱ站区间为待划分区间，Ⅰ站中心公里标为0 km，反向进站信号机公里标为1 km，Ⅱ站中心公里标为34.500 km，进站信号机公里标为33.500 km，区间全长33.5 km。参数条件如表1所示。

表1　闭塞分区划分参数

轨道电路传输极限长度如表2所示。

表2　轨道电路传输极限长度

所选用的动车组类型及其参数如表3所示。

表3　区间运行动车组类型及参数

3.2　算法参数设置

在PSPSO中，通过限制L来实现全局搜索和局部搜索的平衡，学习因子和惯性权重只在内循环中起作用，对全局和局域搜索影响不大。因此，学习因子和惯性权重可以采用固定值，本文令c1=c2=1，ω=0.5。另外，粒子数取10，在Matlab中经过多次仿真后将一些参数做如下设置：NL=N，Cs=N，Ls=[NL/4]，Lh=NL-Ls。

3.3 计算结果及分析

利用Matlab对算法进行仿真验证。根据公式(6)得到可划分的闭塞分区数量范围，进而得到区间布置的信号点数量N的范围，根据N由小到大依次进行寻优。经过仿真求解，当N=13时，得到最优布置结果。图1为N=13时的历史最优解的适应度函数值随循环次数变化而变化的关系曲线，得到一次历史最优解pg为一次循环，粒子的迭代次数取10。

图1　算法适应度随迭代次数变化曲线

从图1可知，PSPSO算法在循环到第104次左右收敛，总循环次数为10×104=1 040代左右收敛，并找到了比较优良的结果。

为了进一步说明算法的优越性，本文将标准PSO算法和PSPSO算法分别运行30次，结果对比如表4所示。

表4　PSPSO和标准PSO优化比较

由于标准PSO算法在粒子数为10时，很难找到最优解，因此，将粒子数增大到100。从表4可知，虽然标准PSO算法收敛速度比较快，但是不能保证每次都收敛到最优，可能收敛到局优。实际上标准PSO算法随着迭代的进行，认识部分和学习部分在减小， 粒子的种群多样性下降，容易陷入局优。而PSPSO算法搜索时每次都会重新初始化粒子，由于不会受历史信息的影响，用较少的粒子也不会陷入局优。而在计算时间上，虽然PSPSO算法的迭代次数要多一些，但是由于粒子数量少，搜索所用的时间反而更短。

PSPSO算法优化最终得到的信号点布置结果如表5所示。从表5的优化结果得知，闭塞分区的最大长度为2 830 m，符合最大长度要求。区间的最大列车追踪间隔为2.14 min，符合给定的追踪间隔(3 min)要求，经检验，车站追踪间隔也符合要求。最大码序为U，符合码序检验要求。综上说明，算法是有效的。

表5　基于捕食搜索策略粒子群算法的优化结果

布置同样长度的区间，最终得到的结果与文献[13]相比，划分的闭塞分区个数都为13个，区间的最大列车追踪间隔时间2.14 min，优于文献[13]得到的2.2 min，在闭塞分区个数相同的情况下，本文的划分结果在效率方面优于文献[13]。

4结语

利用基于捕食搜索策略的粒子群算法求解优化高铁闭塞分区划分模型。基于捕食搜索策略的粒子群算法利用较少的粒子，通过限制等级的调节，实现快速收敛到全局最优。通过实例仿真验证了基于捕食搜索策略的粒子群算法求解高铁闭塞分区划分问题是有效的。算法在重新计算限制时，是通过随机初始化粒子群实现的，这样可能会出现较差的解，减慢算法的收敛速度，有待改进。

参考文献：

[1]王瑞峰，高继祥.铁路信号运营基础[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]刘海东，毛保华，刘剑锋，等.铁路信号机布置及其计算机实施系统研究[J].系统仿真学报，2006，18(1):62-66.

[7]刘剑锋，毛保华，侯忠生，等.基于遗传算法的区间自动闭塞信号机布局优化方法[J].铁道学报，2006，28(4):54-59.

[8]卫和君.铁路自动闭塞分区划分技术展望[J].长沙铁道学院学报，2003，21(4):99-102.

[9]王俊伟.粒子群优化算法的改进及应用[D].东北大学，2006.

[10]刘冬华，甘若迅，樊锁海，等.基于捕食策略的粒子群算法求解投资组合问题[J].计算机工程与应用，2013，49(6):253-256.

[11]张济民，吴汶麒.准移动闭塞列车安全间隔时间的计算[J].铁道学报，1999，21(3):6-10.

[12]潘峰，李位星，高琪，等.粒子群优化算法与多目标优化[M].北京:北京理工大学出版社，2013.

[13]刘海东，毛保华，王保山，等.基于差分进化算法的高速铁路区间信号布置优化方法研究[J].铁道学报，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。

基金项目：国家自然科学基金地区项目(61164101)

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

中图分类号：U238； U284

文献标识码：ADOI:10.13238/j.issn.1004-2954.2016.01.029

文章编号：1004-2954(2016)01-0131-05