多种群分层联合优化的城轨列车ATO研究

徐 凯，吴 磊，赵 梅

(1.重庆交通大学 信息科学与工程学院，重庆 400074；2.重庆市公共交通运营大数据工程技术研究中心，重庆 400074；3.西华大学 电气与电子信息学院，四川 成都 610039)

列车自动驾驶ATO系统是列车自动控制系统的重要组成部分，其运行等级模式曲线计算的精确性将直接影响车载ATO的控制效果[1]。通常利用节能优化算法来获得列车节能驾驶策略，用以指导列车自动运行，减少运行能耗。为达到此目的，文献[2]在列车运行控制模型的优化中，采用遗传算法降低了列车运行的能耗。文献[3-5]分别采用不同形式的粒子群优化算法来获取列车自动驾驶曲线。上述参考文献有一个共同点，即在一定约束条件下采用加权求和的方法，将列车运行控制的多目标优化转换为单目标优化。在列车运行控制系统中，各个目标之间的关系较为复杂，加权求和方法并没有考虑各目标之间的相互作用及影响，无法体现出多目标问题研究的本质。由于多目标优化获得的是所有占优解的集合，而并非只有一个最优解。为体现出多目标优化的本质，采用Pareto原理来解决此问题是一种较佳选择。对于具体的列车以运行时间和能耗为目标问题，需要从Pareto最优解集中选择一个或一些最符合实际需求的解作为最终解使用，由此设计列车ATO运行模式曲线。

近年来研究者采用基于Pareto原理的多目标优化方法来获取列车运行操纵策略。文献[6-7]结合模拟退火思想，对传统差分进化算法的交叉操作进行改进，得到了高速列车运行优化的操纵策略。文献[8-9]分别采用基于模糊参数的NSGA-Ⅱ算法和基于模糊模型的遗传算法，得到相应的列车控制策略。近年来，不少研究者将多目标粒子群优化MOPSO算法应用于列车运行优化的操纵策略中[10-12]。相比遗传算法和动态规划，MOPSO算法可以在收敛性和结果质量之间获得较好的平衡。文献[13]为获得列车最佳控制策略，对MOPSO算法作了相应的改进。文献[14]将MOPSO与NSGA-Ⅱ两种算法进行对比研究，发现MOPSO算法在计算时间、逼近Pareto真实前沿和多样性等方面更为优越。因此，如何进一步改善、提高MOPSO算法的收敛性和多样性，得到一组优越的Pareto前沿解集，从而获得更为合理的ATO速度命令成为当前研究的热点之一。

为进一步提高粒子群优化PSO算法的性能，将PSO与布谷鸟搜索CS算法相结合。文献[15]借鉴PSO算法中全局最优和个体最优的概念，在CS算法lévy飞行随机游动和偏好随机游动之间引入PSO组件。文献[16]将PSO与CS串行，每次迭代过程中先使用PSO算法优化种群，记录全局最优和个体最优，采用CS算法对种群个体最优继续寻优。上述将PSO和CS算法进行组合优化求解，仅针对单目标优化，降低了研究问题的深度，并采用测试函数评价组合算法的性能，没有结合实际工程应用问题来研究。本文采用一种将多种群PSO与布谷鸟搜索CS相结合的分层算法，即多种群分层PSO-CS联合优化算法，针对多目标优化问题，在列车运行控制仿真实验中采用所提出的方法，通过多种群PSO、分层结构以及两种算法的混合策略，提高了Pareto前沿解的收敛性和多样性。

1 列车控制多目标优化模型

参考文献[17]描述列车运动的微分方程为

( 1 )

( 2 )

式中：t为列车运行时间；v和s分别为列车运行速度和距离；c和ε分别为列车单位合力和加速度系数。

列车在运行过程中，其所受的力为

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

( 3 )

式中：m和a分别为列车质量以及运行中合力产生的加速度；f(u，v)为作用于列车上的牵引力或者制动力，当列车处于牵引、制动和惰行状态时，f(u，v)分别为正值、负值和零；g(v)为列车基本阻力；w(x，v)为列车附加阻力，其中x和v分别为线路位置和列车运行速度，附加阻力取决于列车运行的线路条件。

在充分考虑安全、停车准确及各种约束条件基础上，将列车运行能耗和时间作为目标求解。根据列车运动方程，可计算出列车在整个区间上的运行时间为

( 4 )

式中：i=1，…，N为划分的若干个小区间序号；Ti为每个小区运行时间；T为站间实际运行时间。

列车运行能耗指标计算模型为[6]

( 5 )

式中：E为列车能耗；F和B分别为牵引力和制动力；A为列车辅助功率；ξM为列车牵引时将电能转换成为机械能的转换因子；ξB为列车制动时将机械能转换成电能的转换因子。

从实质上来讲，列车运行多目标优化就是对式( 1 )～式( 3 )所描述的模型，在满足约束条件下，求出所输入的一组控制序列{ui}i=1，2，…，k以及k-1个工况转换点位置{xi}i=1，2，…，k-1(xi∈[0，S])，做到让列车运行时间短且耗能低。由此，以运行时间和能耗为多目标的优化问题可表示为

min{T，E}

( 6 )

约束条件为

( 7 )

式中：v(0)为列车初速度；v(S)为列车末速度；v(s)为列车在位置s处的实际速度；vlim(s)为列车的限制速度；Sr为列车实际运行的距离；S为两站点之间的距离，cm。

2 多种群分层PSO-CS联合优化算法

2.1 粒子群优化算法PSO

PSO算法是受鸟群觅食行为启发而提出的群搜索算法，通过粒子间相互作用，发现复杂搜索空间中的最优区域，具有全局搜索能力强的特点。该算法的粒子速度和位置更新公式分别为[15]

( 8 )

( 9 )

2.2 布谷鸟搜索算法CS

布谷鸟搜索[18]是由剑桥大学Yang等提出的一种群智能优化算法，是一种新型元启发式搜索算法。主要原理是基于布谷鸟的lévy飞行机制及巢寄生性，使其能够快速有效地寻找到最优解。布谷鸟搜索算法采用lévy飞行进行位置更新，其更新公式为[18]

⊕L(λ)

(10)

(11)

(12)

式中：Г是标准Gamma函数；λ取值为2.5。

2.3 双层框架的联合优化算法

2.3.1 算法思想

一方面，PSO算法局部搜索能力强、收敛速度快，CS算法由于lévy飞行具有高度的随机性，因而有较强的全局搜索能力和多样性。因此将PSO和CS两种算法的优点相结合。另一方面，可将底层的种群划分为多个小种群，让多个小种群独立并行协同搜索，不仅扩大了粒子在解空间的搜索范围，也提高了粒子的搜索速度，与此同时，利用高层中的CS算法来搜索全局的最优点，以保证算法收敛性。上述算法能够在搜索可行解的过程中，兼顾效率和精度两个方面。

结合图1，多种群分层PSO-CS联合优化算法的思路为：在底层中，将种群平均划分为k个小种群，使用PSO算法优化每个小种群，进行局部并行搜索；将每个小种群中的精英粒子si(i=1，…，k)送到高层，使用CS算法进行深度优化，优化后的较优解分别返回到各自的小种群中；底层和高层的粒子若有可行解，则找出可行解的Pareto前沿解集，将解集放入外部档案中，并对外部档案更新。这种多种群分层联合优化结构提高了算法收敛性和全局搜索能力。

图1 多种群分层PSO-CS联合优化框架图

该算法在底层小种群之间，通过整个种群的最优值进行间接交流，增强了粒子的多样性。每个小种群不仅根据该种群个体最优和全局最优来修正本种群内粒子的速度和位置，还要考虑整个种群全局最优值来修正粒子速度和位置。标准粒子群的迭代公式修正为

(13)

(14)

不同于单目标优化，在解决列车多目标优化问题时，如何选择合适的小种群全局最优值Besti和整个种群的全局最优值gBest，用于指导各小种群中粒子的“飞行”显得十分重要。

小种群全局最优值Besti选择策略为：若小种群中所有粒子均为不可行解，选择违反约束程度最小的粒子作为Besti；若小种群中只有一个粒子是可行解，则该粒子作为Besti；若小种群中有多个可行解，找出可行解的Pareto前沿解，从Pareto前沿解中随机选取一个粒子作为Besti。

整个种群中的所有粒子单独选择gBest，其策略为：若外部档案没有解，选择整个种群违反约束程度最小的粒子作为gBest；若外部档案存在解，每个粒子随机地从外部档案中选择一个粒子作为gBest。

图1中小种群精英粒子si的选择策略为：若小种群中所有粒子均为不可行解，选择违反约束程度最小的粒子作为小种群精英粒子；若小种群中的粒子有可行解，将可行解中所有Pareto前沿解作为小种群的精英粒子。

2.3.2 算法步骤和流程

算法底层：

步骤1初始化PSO相关参数，随机生成N个粒子作为初始种群，将整个初始种群均分成k个小种群。

步骤2计算每个粒子的目标向量{T，E}，存储每个粒子的个体历史最优值pBest，找出每个小种群的全局最优值Besti和整个种群的全局最优值gBest。

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

步骤4计算每个粒子的目标向量{T，E}，若存在Pareto前沿解集，则更新外部档案。

算法高层：

步骤5计算每个小种群的精英解，并将精英解送往高层作为布谷鸟的初始位置，精英解的个数作为鸟巢的个数，初始化CS算法的参数。

步骤6用式(10)更新鸟巢位置，对更新后的鸟巢位置进行相应测试，与上一代鸟巢位置比较，将测试值好的保留，并转入下一步。

步骤7产生[0，1]之间的随机数rand，设定鸟巢被发现的概率pa，并与rand比较。若pa≤rand，则随机改变鸟巢的位置，否则保持不变。进一步测试鸟巢改变后位置，将它与上一步获得的鸟巢位置对比，把适应度好的鸟巢位置保留下来。

步骤8计算高层每个粒子目标向量{T，E}，若存在Pareto前沿解集，则更新外部档案，将上层更新后的粒子分别返回各自所在的小种群。

步骤9判断是否达到终止条件，若达到，输出外部档案Pareto最优解集；否则，返回步骤2。

算法的具体流程如图2所示。

图2 算法流程图

3 仿真实验及分析

3.1 仿真参数设置

为验证所提方法的有效性，以重庆轨道三号线郑家院子到唐家院线路为例，在Matlab环境下进行仿真。

(1)线路参数：线路的参数见表1。

表1 线路参数

(2)列车参数：采用6节编组，总重量162 t，长度120 m。从大到小依次将牵引、惰行和制动所产生的加速度值进行编码，编码采用实数方式。先将最大的3级牵引加速度编码设置为1，然后该编码依次递增，直到4级制动减速度的编码值为8结束。表2列出了列车在不同运行工况下的参数取值及所对应的编码。

表2 列车运行工况参数取值

(3)运行参数：列车运行区间目标时间85～95 s。

(4)参数设置：MOPSO种群数100，迭代次数250，其他参数按照参考文献[14]设置。多种群分层PSO-CS联合优化算法的参数设置：惯性权重w=1，学习因子c1=c2=c3=2，步长因子α=1，鸟窝被发现概率pα=0.25，种群粒子总数50，小种群个数5，迭代次数500，两种算法函数评价次数均为25 000次。

根据种群粒子总数为50，将小种群个数取为5，既保证小种群数量恰当，又保证了每个小种群中粒子数适中，这样本文所提算法的收敛性和多样性均达到最佳。

3.2 算法性能评价指标

在多目标优化问题中，为了验证所提出算法的优越性，首先需要明确以下几个指标，对算法的收敛性和多样性进行度量。

(1)收敛性指标GD

(15)

式中：n为算法得到的Pareto前沿解个数；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 实验结果及分析

将所提出的多种群分层PSO-CS联合优化算法和MOPSO算法分别用于列车自动驾驶曲线的优化。上述两种算法分别独立运行30次，从收敛性指标GD、γ和多样性指标SP、Δ以及Pareto前沿解的个数等方面，分别对两种算法的结果进行统计比较，以此衡量算法的优劣性。算法的性能比较统计结果见表3。

表3 性能评价指标统计结果

从表3统计结果可以看出：根据Pareto前沿解的收敛性、多样性和数量的比较，多种群分层PSO-CS联合优化算法性能指标均优于MOPSO算法。从各指标的平均值可以看出，所提出的算法不仅收敛速度快，还能增加解的多样性，同时解的个数也较多。

图3和图4分别是MOPSO算法和多种群分层PSO-CS联合优化算法的解空间分布情况。从图3、图4可以看出，在两种算法得到的可行解中，Pareto前沿解都处于解空间内侧，满足运行时间较短和能耗小的目标。采用MOPSO算法得到的可行解数量少且分布稀疏。而多种群分层PSO-CS联合优化算法得到的可行解数量较多且分布均匀，大量可行解都集中靠近Pareto前沿。

图3 MOPSO算法的解空间

图4 PSO-CS算法的解空间

图5是两种算法的Pareto前沿解比较。从图5可知，采用所提出算法获得Pareto前沿解更加靠近内侧，收敛性更好。在相同运行时间下，用该算法得到的解，能耗更低；采用所提出算法得到的解集向左端拓展，分布范围更广，意味着可获得更短的列车运行时间；所提出算法获得的解分布更均匀，相邻解之间间隙小。而MOPSO算法获得的相邻解之间的间隙较大，需要进行填充才能增加解的多样性。

图5 两种算法的Pareto前沿解比较

从Pareto前沿解可知，列车运行时间和能耗之间相互矛盾，即列车运行时间越短所需能耗越高，列车运行时间越长能耗越低。可以通过选择恰当的控制策略来满足列车实际运行的要求。采用本文提出算法得到Pareto前沿最优解集后，可以获得最省时、最节能和两个目标折衷的列车运行速度-距离曲线，如图6所示。

图6 三种不同要求的速度-距离曲线

结合图5和图6，当时间最优时，所对应的时间和能耗分别是86.02 s和48 151.82 kJ；当能耗最优时，所对应的时间和能耗分别为94.82 s和36 598.49 kJ；若性能折衷，则所需的时间和能耗分别为90.31s和40 197.05 kJ。

当列车输入控制序列数设置为7，在上述3种不同要求下，图6中速度-距离曲线所对应控制序列下的加速度和距离值见表4。从表4可知，当时间最优时，惰行的距离最短，为176 m；而当能耗最优时，惰行的距离最长，为380 m。

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

4 结论

针对城轨列车在满足安全、精确停车及各种约束条件下，以时间和能耗为优化目标，建立列车运行操纵的多目标优化数学模型。提出一种多种群分层联合优化的多目标算法，将它用于城轨列车ATO中，通过仿真实验得到如下结论：

(1)针对将多目标加权转化为单目标问题而存在的缺点，提出的算法能够避免由于各目标间的相互影响而不能得到需要的解集。

(2)将多种群PSO算法与CS算法的优点相结合，采用分层联合优化的策略，与MOPSO算法相比较，提高了Pareto前沿解的收敛性。由此得到的列车控制策略，可以让列车在相同运行时间下降低能耗。

(3)与MOPSO算法相比，本文所提算法获得Pareto前沿解的多样性更为优越。这为设计者提供了更多、更灵活的选择方案，在设计列车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]丁勇,刘海东,栢赟,等.地铁列车节能运行的两阶段优化模型算法研究[J].交通运输系统工程与信息,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]余进,何正友,钱清泉.基于混合微粒群优化的多目标列车控制研究[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]黄友能,宫少丰,曹源,等.基于粒子群算法的城轨列车节能驾驶优化模型[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]孙其升,胡文斌,陈磊,等.基于粒子群优化算法的地铁列车节能运行研究[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]严细辉,蔡伯根,宁滨,等.基于差分进化的高速列车运行操纵的多目标优化研究[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]荀径,杨欣,宁滨,等.列车节能操纵优化求解方法综述[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]余进,何正友,钱清泉.基于微粒群算法的多目标列车运行过程优化[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]毛保华,李夏苗.列车运行计算与设计[M].2版.北京:人民交通出版社,2013:72-75.

[18]兰少峰,刘升.布谷鸟搜索算法研究综述[J].计算机工程与设计,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.