基于蒙特卡洛树搜索算法实现轨道交通车辆多功能车辆总线周期调度表优化

耿 力 耿 强

(1.同济大学铁道与城市轨道交通研究院,201804,上海; 2.电子科技大学自动化工程学院,611731,成都∥第一作者,硕士研究生)

轨道车辆通信总线由WTB(绞线式列车总线)和MVB(多功能车辆总线)构成。其中:WTB主要用于日常作业时经常改变编组数量的列车间连接各车辆的串行数据总线;MVB主要用于固定车厢或具有固定编组列车这一特定范围的轨道车辆的通信网络[1]。MVB将一个车厢内或一个编组内的可编程设备互连,并可直接连接简单的传感器和执行机构,从而为车厢内各设备的诸多功能(如车门控制、列车制动、空调调节、发布旅客信息及预留坐席等)的自动实现、消息的传达、资源的共享,以及各设备间的合理调配提供可靠且顺畅的信息交换通道。在车辆上有众多设备,设备之间对MVB的占用通过MVB周期调度表(以下简称“调度表”)来控制。合理的调度表能提高MVB的带宽利用率,并通过缩短通信周期来提高车辆通信系统的实时性。

调度表的设计主要有两种方案。方案一用经典的RMS(单调速率调度)算法设计调度表,RMS算法的优点是速度快,缺点是其调度表不具有负载均衡特性,易引起带宽浪费,其通信的实时性也较低。方案二借助启发式算法找出合理的调度顺序。因为寻找负载均衡的调度方式是一个NP-Hard(非确定性多项式困难)的组合优化问题,其组合方式随变量的数目呈指数增长,例如针对20个变量的调度表设计,普通的计算机已经难以穷举求解,通常采用启发式算法求解。已提出用于调度表设计的启发式算法包括GA(遗传算法)[2]、混合遗传算法[3]、免疫遗传算法[4]、蚁群算法[5]及改进的差分进化算法[6]等,这些算法的相似度高,很多算法属于对同一算法进行了不同程度的改进,其缺点是搜索过程中可能产生大量效果很差的解,进而造成搜索效率低。部分改进过后的算法将搜索分成两个阶段进行[6],第一阶段为全局搜索,第二阶段为局部搜索,这在一定程度上提高了搜索的效率,但也面临如更多超参数等问题。

基于强化学习的围棋人工智能程序Alpha-Go采用MCTS(蒙特卡洛树搜索)算法进行启发式搜索[7],该算法很好地解决了组合优化问题中搜索空间巨大、难以搜索到优质解这一难题。因此,本文尝试将MCTS算法引入MVB调度表设计中,并针对MVB调度表的特点对该算法进行改进,以提高搜索效率。

1 MVB周期信息通信原理

1.1 MVB调度表及约束条件

MVB上有多个节点,主节点根据调度表的规则将特定的从设备指定为源节点,赋予该源节点发送数据的能力。该调度过程不断循环,将每个循环周期称为宏周期。为了能够传输非周期信息,主节点将时间等分成若干个时间片,并将该时间片称为微周期。每个微周期被划分成两部分,第一部分称为周期相,用于传输周期性数据;第二部分称为偶发相,用于传输非周期性数据。国际电工委员会发布的IEC 61375标准第3-1部分对MVB调度表的宏周期及微周期中的周期相时间占比等条件进行了约束。使用各种算法生成的调度表,需要检查是否满足规定的约束条件。若满足约束条件,则称该调度表是可调度的,否则称该调度表是不可调度的。MVB的约束条件包括约束条件1及约束条件2。

1.1.1 约束条件1

约束条件1为变量首次出现位置必须不超过其周期,可形式化表示为

∀i∈{1,2,…,m},pi≤Ti/Tbp

(1)

式中:

i——变量编号;

m——变量总数;

Tbp——微周期,单位ms;

pi——变量i首次出现的周期位置;

Ti——变量i的周期,单位ms。

1.1.2 约束条件2

约束条件2为根据IEC 61375标准第3-1部分,每个微周期中周期相所占时间最多为微周期的65%,即

∀j∈{1,2,…,z},Uj≤0.65Tbp

(2)

式中:

j——微周期的编号;

z——微周期总数;

Uj——第j个微周期中周期相所占时间,单位ms。

1.2 优化目标

(3)

(4)

算法的优化目标转为找到最佳的组合方式G*,使得σ(G)最小,即:

(5)

2 MCTS算法原理简述

本文首次将强化学习中的MCTS算法引入到MVB调度表的构建过程中。MCTS算法是一种在决策空间进行随机采样并构建出一棵搜索树,通过搜索树来实现寻找最优决策的算法。MCTS算法在序列决策问题、博弈问题及规划问题中均具有重要的影响力,特别是在围棋AI(人工智能)程序中的成功应用,使得该算法备受关注。MCTS算法原理如图1所示。

图1 MCTS算法原理示意图

如图1所示,MCTS是一个不断迭代的过程,每次迭代可分为4个步骤:

1) 步骤1:选择。从根节点开始,按照一定的策略递归向下伸展,直到抵达最需要扩展的节点处。如果一个节点没有到达终止状态,并且还有未访问的子节点,则该节点是可扩展的。如图1中的A节点。

2) 步骤2:扩展。根据每个状态可选择的动作,对选择出的叶节点新增一个或多个子节点,从而实现树的扩展。如图1中的A节点,可将其扩展得到B节点。

3) 步骤3:模拟。将步骤2扩展得到的新节点按照预定的方式进行演算,进而产生一个输出结果,直至游戏结束。如对B节点进行快速模拟时,其每个动作通常为随机选择。在游戏结束时,根据游戏规则可获得对应的奖励。

4) 步骤4:回传。将步骤3模拟后获得的奖励回传,更新执行模拟节点及它的所有祖先节点的统计值。

在上述迭代过程中,步骤1中如何选择合适的子节点是一个关键问题,这也正是强化学习必须要面对的探索-利用困境。MCTS算法中使用了UCT(针对树的置信上界)方法,以平衡探索和利用。通常选择在UCT值最大的节点上进行扩展,其表达式为:

(6)

式中:

Q(v)——节点v的UCT值;

R(v)——节点v获得的累计奖励;

N(v)——节点v的总访问次数;

pv——v的父节点;

N(pv)——pv被访问的总次数;

Cp——平衡探索与利用的常数,本文取0.1。

式(6)等式的右边为2项之和,其中:第1项表征了节点v平均获得的奖励;第2项中,在父节点pv多次被访问而某个子节点长期未被访问时,其对应的N(v)较小,此时Q(v)较大,则节点v应被访问。

3 MCTS算法在MVB调度表中的优化

上文介绍了MCTS算法的通用框架,将其应用于MVB调度表时需要进行优化设计。

3.1 状态空间与动作空间

MVB调度表的状态为当前变量的排布情况,其状态采用各个变量首次出现的微周期序号形成的整数数组来表示,所有状态的可能集合构成状态空间。不同的状态可以执行不同的动作,即选出某个未安排的变量,将其排布在某一个微周期内,其所有可执行的动作将构成动作空间。所有变量均排布完毕后,动作空间变为空集,算法结束。

3.2 奖励规则设计

在强化学习中,智能体的目标是获得尽可能多的奖励。根据MVB变量调度的过程,提出将当前调度表的均衡程度与历史数据进行对比,根据“进步”程度给出奖励。其奖励规则如表1所示。

表1 MVB调度表中MTCS算法的奖励规则

3.3 对搜索树进行预剪枝优化

在变量排布过程中,应遵循上文所述的MVB调度表约束条件。通常情况下,约束条件2很容易满足,因此在算法实现中应先考虑约束条件1,待得到一个较好的解时,再检查是否满足约束条件2。约束条件1能过滤掉大量不满足要求的劣质解。例如,仿真时选取20个变量及32个微周期工况,在无任何约束时调度表的组合数为2032(即4.3×1041),而满足约束条件1的组合数约为5.8×1017,即只有大约1/1024的组合能够满足约束条件1。

因此,针对MCTS算法和约束条件1,本文设计的预剪枝规则为:如果某个状态对应的调度表不可调度,则将其标记为不合法节点,以后不再对该不合法节点进行任何的扩展或模拟,以避免大量不必要的搜索。

3.4 设置变量优先级

变量优先级的设计对提高MVB的均衡度有一定的影响。如果最后安排的变量传输时间很长,则该变量的排布很可能导致整个调度表不均衡,试验中也验证了此结论的正确性。因此,优先级规则设定为:变量传输时间越长,此变量的优先级越高。

4 仿真试验及结果分析

选取RMS算法、MCTS算法和GA三种算法进行仿真试验,并对各算法的结果进行对比分析。其中GA的形式随具体应用场景的改变而略有差异,因此先简要介绍一下本文使用的GA形式,再进行算法对比。

4.1 用于MVB调度表的GA

GA是一种经典的启发式搜索算法,其流程如图2所示。该算法对个体的编码方法和上文所述MCTS算法的编码方法一致,即一个编码中包含了各个变量首次出现的位置,编码长度等于变量总数m。初始化种群中个体数量为记作Np,每轮更新中将每个个体变异。变异方式为取随机编码中的一个变量,将其随机放到一个微周期内。如果变异后的新个体适应度大于其父亲的适应度,则新个体代替父亲,否则保留父亲不变,丢弃新个体。

对GA而言,适应度越大说明其对应的MVB负载越均衡,因此采用式(3)标准差的相反数(即-σ(G))作为该算法的适应度。将种群中每个个体都变异一次叫做一次种群变异,试验中种群变异次数记为NGA。

4.2 算法对比分析

定义ti为第i个变量在1个微周期中占用MVB时间。使用文献[6]中使用的算例数据,其调度表包含20个变量及32个微周期,各变量对应的周期数据如表2所示。

表2 试验用的变量及其周期

本文使用Python编程实现RMS算法、GA和MCTS算法,硬件采用普通的笔记本电脑,其参数分别为: CPU(中央处理器)的型号为i5-8265U,1.60 GHz主频,RAM(随机存取存储器)的容量为12 GiB。为便于比较GA和MCTS算法,试验中将这两种算法的一次试验运行时间均设定为180 min(即10 800 s)。GA一次试验的Np=100个,NGA=5 000万次。MCTS算法一次试验的最大采样次数NMCTS=1 500万次。RMS算法具有确定性,但GA和MCTS算法具有一定的随机性。为了避免单次试验引起的误差,将三种算法均重复运行10次。试验中发现GA和MCTS算法难以收敛,随着时间的推移,这两种算法可能以一定概率获得一个更优的解。因此,不通过最终的收敛而通过一段较长时间内的搜索结果来评估GA和MCTS算法的好坏。表3给出了三种算法10次试验后的试验平均运行时间、平均均衡度及最优解。最优解用一个向量表达,其元素数等于m,向量的第i个值(记作pi)表示第i个变量首次出现安排在第pi个微周期。

表3 三种算法的最优搜索结果对比

试验验证可知:表3中各个算法给出的最优解均满足约束条件1和约束条件2,即获得的调度方式是可调度的。由表3中还可以看出:RMS算法下一次试验的平均运行时间最小,但均衡度最差。在长时间搜索下,MCTS算法的搜索效率较GA高,其均衡度在三个算法中最小。

图3直观展示了RMS算法、GA和MCTS算法三种算法生成的最优调度表每个微周期内周期相占用时间分布情况。由图3可知:RMS算法生成的调度表负载严重不均衡;GA算法生成的调度表均衡度较好;MCTS生成的调度表负载最均衡。

图3 三种算法生成的最优调度表周期相占用时间分布

图4展示了GA和MCTS算法下均衡度随试验运行时间的变化规律,带方块的黑色虚线和带三角的黑色实线分别对应运行10次后GA和MCTS算法的平均均衡度,对应的填充区域为10次运行中以最大值和最小值为边界围成的区域,边界线的阶梯下降表明找到了均衡度更小的解。随着试验运行时间的增加,均衡度均值曲线趋于平缓,这是因为要找更优的解已变得困难。相较于GA,MCTS算法生成的调度表对应的均衡度曲线下降速率更快,即在相同的试验运行时间内MCTS算法能找到更好的解。

无论是GA还是MCTS算法,均会使用式(3)衡量生成的每个解的优劣程度。MCTS算法能统计产生各个解是否比历史解更优等信息,并将这些信息通过回传(步骤4)存储于祖先节点内,用以指导后续解的生成。也就是说,MCTS算法中每个新解的生成都参考了历史所有解的信息。相较之下,GA尽管不断通过优胜劣汰机制来清除劣质解,但每个解的生成仅参考了一个父节点的信息进行变异,而不是全局信息。这也许是GA搜索效率不如MCTS算法的原因。此外,MCTS算法还可以通过设置变量优先级来提高算法效果,而GA只能随机变异。MCTS算法的缺点是需要较大内存,用以记录树生成过程中的大量节点。

5 结语

设计负载均衡的MVB调度表可减少带宽浪费,并可提高网络通信的实时性。本文首次利用强化学习中的MCTS算法实现MVB调度表的优化设计,通过设计奖励方式及博弈规则,将MVB周期数据调度问题转换成可以用MCTS算法解决的组合优化问题。

另外,本文根据MVB调度表的特征实现了预剪枝策略,当MVB变量总数为20个时,可将搜索空间减少数十个数量级,使其搜索效率优于GA。仿真结果表明:本文优化后的MCTS算法能在相同的搜索时间内获得更均衡的解。如果车辆通信设备增加,需要生成包含更多变量的调度表时,MCTS算法更能凸显其搜索优势。未来可进一步设计出不同的探索-利用平衡方案,进一步提高MCTS算法的搜索效果,以期更快设计出负载均衡的MVB调度表。本文给出的设计思路可为通过MCTS算法求解其他领域的组合优化问题提供参考。