考虑顺序和组合关系的列控车载设备测试序列生成方法

王 硕,崔佳诺,吴培栋,张友兵

(北京全路通信信号研究设计院集团有限公司,北京 100070)

引言

列控车载设备是列控系统的重要组成部分，直接影响列车行车效率和运行安全，在投入使用前应进行严格完整的测试[1-2]。其中，测试案例描述了测试输入和预期结果。在执行测试案例时，要求列控车载设备处于规定的起始状态；当测试案例执行完成后，会造成系统状态的转移。因此，测试案例不能单独直接执行，需通过一些功能将列控车载设备调整至测试案例指定的初始状态，而相关功能又包含在其他测试案例中。由此进行的状态调整将导致大量测试案例被重复执行，严重影响测试效率[3]。

为提高测试效率，需利用测试案例之间的状态转移衔接关系，将测试案例有序串接为测试序列。但由于列控车载设备的测试案例规模较大，人工串接测试案例工作繁重，容易遗漏测试案例且测试序列中往往包含大量冗余的测试案例，直接增加了测试执行的成本。因此，如何充分利用测试案例间的衔接关系构建测试序列并使测试序列的总成本最小，成为列控车载设备测试领域的一个重要问题，即测试序列优化生成问题。

近年来，研究多是将测试案例之间的衔接关系描述为有向图的顶点和弧，并把测试序列优化生成问题转化为有向中国邮路问题(Directed Chinese Postman Problem， DCPP)[4-6]或非对称旅行商问题(Asymmetric Traveling Salesman Problem， ATSP)[7-8]来生成测试序列。此外，ZHENG，梁茨等[9-10]提出了序列优选算法生成测试序列；赵晓宇，唐汇东等[11-12]考虑了测试案例的优先级并生成了测试序列；宋爽等[13-14]提出了一种基于时间自动机模型的区域控制器测试序列生成方法。上述方法的基本假设是测试案例之间完全相互独立。而在实际测试过程中，为对被测设备的特定流程及其组合进行测试，测试案例之间往往会涉及一些顺序和组合关系。这些关系是测试经验和测试需求的共同体现，在实际测试中具有很强的应用需求。基于此，ZHANG等[15]利用知识树和基于模型的推理实现了构建测试序列的专家系统；LI，袁磊等[16-17]则利用了深度学习生成测试序列。但前述研究方法无法确定性地覆盖测试案例之间指定的顺序关系和组合关系。

为使测试序列以最小的成本覆盖测试案例及其顺序关系和组合关系，首先，定义了一种关联弧路径问题(Associated Arc Routing Problem， AARP)，用于解决有向图中弧之间存在关联关系的路径问题，并提出了一种求解算法；然后，利用AARP及其求解算法生成测试序列；最后，以CTCS-2级列控车载设备的测试序列生成为例，验证本文所述方法的有效性。

1 研究基础

1.1 测试案例与测试序列

定义1(测试案例) 一条测试案例是一个6元组t=(ss，id，o，p，c，se)。

其中，ss是为执行该测试案例而要求被测设备所处的起始状态；id是测试案例的唯一编号；o是测试案例的操作输入和期望输出；p是测试案例的转移成本，指当测试案例作为状态转移项执行时所花费的时间；c是测试案例的测试成本，指当测试案例作为测试项执行时所花费的时间；se是被测设备正常执行测试案例后所处的终止状态。

根据测试案例的起始终止状态将测试案例串接为测试序列，使前面的测试案例为后面测试案例创造执行条件，能够有效减少测试案例的重复执行。

定义2(测试序列) 一条测试序列S=(t0，t1，…，tm-1)是若干测试案例的有序衔接序列，其中，m为测试序列中测试案例的总数量。

测试序列中的测试案例分为状态转移项和测试项两类：状态转移项是为其他测试案例构造测试条件，只执行相应的输入，花费的时间为p≥0；测试项是为了检验被测设备的功能，既要执行相应的输入，又要记录相应的输出，并与期望输出作比较，其花费时间为c，且c≥p≥0。

1.2 顺序关系与组合关系

测试案例是功能需求的体现，在测试过程中，测试人员往往会根据以往测试经验和功能需求对部分测试案例的特定顺序或组合进行测试。将这种特定顺序和组合分别称为测试案例之间的顺序关系和组合关系。不同于现有研究方法，本文生成的测试序列不仅需覆盖测试案例集，同时要覆盖测试案例之间的顺序关系和组合关系。

测试案例之间的顺序关系是指规定了若干测试案例的衔接顺序，以对特定功能流程进行验证。例如，图1所示的9条测试案例(每条弧表示一条测试案例，弧上的数字表示测试案例编号)，从状态s1到s4有27种组合方式。如果(1，4，7)的顺序是特定的验证流程，则希望测试序列中能够包含(1，4，7)的顺序。

图1 测试案例之间的关系示意

测试案例之间的组合关系是指某个测试案例要与其他相邻接的测试案例进行组合衔接，以提高交错检测能力。

定义3(测试案例的n-维组合) 测试案例的n-维组合是指以该测试案例作为起始测试案例的n条相邻接测试案例构成序列的集合。

如图1中，测试案例2的2-维组合包括(2，4)、(2，5)、(2，6)；测试案例2的3-维组合包括(2，4，7)、(2，4，8)、(2，4，9)、(2，5，7)、(2，5，8)、(2，5，9)、(2，6，7)、(2，6，8)、(2，6，9)。

1.3 关联弧路径问题

在以往研究中，将测试案例集建立为具有多重弧的强连通有向图D，通过求解D的DCPP生成测试序列。DCPP是经典的弧路径问题，其定义为给定一个强连通有向图D=(V，A)，其中，V为顶点集，A为弧集，且每条弧带有一个非负的成本，目标为寻找一条成本最小且经过A中每条弧至少一次的回路[18]。在求解DCPP过程中，由于弧之间是相互独立的，因此，测试序列不会包含特定的顺序关系或组合关系。

定义4(弧的关联关系) 弧的关联关系是D中的一条链，用于描述若干条弧之间的衔接关系，用h表示，由h构成的集合为关联关系集H。

其中，链是指顶点与弧交替出现的序列，与弧相邻的两个顶点恰好是弧的两个端点[19]。下文中为便于表示，将链W表示为弧的序列，第一条弧的起始顶点为W的起点，最后一条弧的终止顶点为W的终点，相邻前一条弧的终止顶点与后一条弧的起始顶点相同。如链W的起点和终点相同，则被称为闭链。

定义5(弧的通过成本和服务成本) 经过弧a的成本为弧a的通过成本，由p(a)表示，其中p(a)≥0；通过弧a并对其进行某种服务的成本为弧a的服务成本，由c(a)表示，其中c(a)≥p(a)≥0。

如链W中连续被服务的弧构成的链与h相同，则称W包含h；如W包含H中的所有链，则称W满足关联关系集H。其中，规定弧的关联关系集H中的元素互相不具有包含关系。

定义6(关联弧路径问题(Associated Arc Routing Problem， AARP)) 给定一个具有关联关系集的多重弧强连通有向图D=(V，A，H)，其中，每条弧a∈A带有一个非负的通过成本p(a)和一个非负的服务成本c(a)，目标为寻找一条起点为v0∈V，总成本最小，服务A中每条弧至少一次，且满足关联关系集H的闭链。

AARP是在有向图中引入了弧的关联关系集H，同时每条弧可作为通过项和服务项，并伴有相应的通过成本和服务成本。AARP为解决具有关联关系的弧路径问题提供了理论模型。

2 关联弧路径问题的求解算法

AARP求解算法共分为3个阶段。

(1)准备阶段。首先，利用Floyd算法计算D的最短路径矩阵L和最短路径费用矩阵B；然后，根据A和H构建被服务的链集R，并计算链间的最小成本矩阵M。

(2)生成阶段。利用插入优化和遗传算法相结合方式将R中的链进行排列，生成链的序列O，使得O中相邻链间的成本之和最小。

(3)转换阶段。将序列O中的链进行拼接，同时转换为由V和A构成的闭链W，并根据v0调整W的起点。

2.1 准备阶段

准备阶段是为计算D的最短路径矩阵L和最短路径费用矩阵B，并构建被服务的链集R及其链间的最小成本矩阵M，如算法1所示。

算法1 准备阶段算法

算法1中1～7行利用Floyd算法计算最短路径费用矩阵B和最短路径矩阵L。其中，Bij为在D中从顶点i到顶点j所需的最小通过成本；Lij为以最小的通过成本从顶点i到顶点j，需先从顶点i到达顶点Lij。第3行表示当顶点i到j之间存在弧时，Bij为顶点i到j之间所有同向弧的最小通过成本；第5行为初始化Lij。

第8行是构造被服务的链集R，包括两部分。第一部分将H中每条链加入到R中；第二部分对任意一条弧a∈A，如其未包含在H的任意一条链中，则将a作为一条链加入到R中。

第9～13行是计算R中链之间的最小成本矩阵M，是准备阶段的核心部分。其中，Mij为从i所表示的链到j所表示链的最小成本。Mij的计算原理根据链i，j之间是否有重叠部分分为两种情况。当链i的尾部与链j的头部之间有重叠部分时计算原理如图2所示。如链i串接链j，只需在链i的末尾增加链j未重叠的部分。此时，Mij为j中未重叠部分弧的服务成本之和，即notOverlapCost(j)。当链i的尾部与链j的头部之间无重叠部分时，计算原理如图3所示。此时，Mij由两部分构成。第一部分为链i的终点到链j起点的最小通过成本，即Bes。第二部分为链j中弧的服务成本之和cost(j)。其中，规定两个相同链间的成本Mii=0。

图2 有重叠链之间最小成本示意

图3 无重叠链之间最小成本示意

2.2 生成阶段

经过准备阶段，R中包含了所有需要被服务的链，M为链之间的最小成本。将R中的链按照一定顺序排列，并使得序列中相邻链(序列的最后一条链和序列的第一条链也视为相邻链)间的成本之和最小，则该序列即为生成阶段的结果O={r0，…，rm-1}。其中，ri为O中的第i条链，m为R中链的数量，O的总成本如式(1)所示。

(1)

利用插入优化和遗传算法相结合方式求最小成本的O如算法2所示。第1行采用随机生成与插入优化相结合的方式生成n个序列，作为初始种群。第3～9行是迭代进化的过程。其中，第3行对P中元素进行随机排序。第6行选择两个序列进行交叉并产生一个较好的子代，其中交叉算子采用EAX(Edge Assembly Crossover)。7～8行是子代替换父代的策略。第9行表示当连续g代种群中最优序列未得到改善，则终止迭代进化。第10行为返回种群中最优序列O。

算法2 生成阶段算法

2.2.1 初始化种群

初始化种群的策略为首先随机生成n条序列，然后根据插入优化概率Po随机选取若干序列进行插入优化运算。这种策略既能够保证种群的多样性，又能够保证种群中具有较好的路径，提高收敛速度。

一次插入优化运算是为在序列中寻找一条链的一个插入位置，使得序列的成本降低最多。如图4(a)中，如将ri取出插入到rj之后，就形成了图4(b)所示的序列，则降低的成本如式(2)所示。

(Mri-1ri+Mriri+1+Mrjrj+1)-

(Mri-1ri+1+Mrjri+Mrirj+1)

(2)

图4 插入操作成本变化示意

对于序列中的每条链依次尝试所有可能的插入位置，记录成本降低最多的链和其插入位置，并进行插入操作，即完成了一次插入优化运算。对完成一次插入优化运算的序列再次进行插入优化运算，直到不存在降低成本的插入为止。

2.2.2 交叉算子EAX

交叉算子EAX最早是由Nagata和Kobayashi为求解旅行商问题提出，其通过合并两个父代解中的弧，同时添加少量较短的弧来生成子代解。为加强EAX求解ATSP的效果，NAGATA[20]验证了不同策略下的求解效果。文中crossover(pA，pB)利用其中的EAX-1AB策略作为交叉算子。其中，将序列中的链作为EAX-1AB中的点集，将最小成本矩阵M作为任意两点间弧的成本。由于序列的最后一条链和序列的第一条链也视为相邻链，因此，可将序列pA，pB作为EAX-1AB中尾首相连的回路。EAX-1AB原理示意如图5所示，共包含如下5步。

图5 EAX-1AB策略原理示意

(1)根据父代的pA和pB构造有向图DAB=(V，EA∪EBEA∩EB)，EA和EB分别为pA和pB中弧集。例如，pA和pB如图5中(1)和(2)所示，那么EA∪EB示意如图5(3)所示，去掉相同的弧之后便得到DAB如图5(4)所示。

(2)在DAB中搜索AB-cycles，一个AB-cycle定义为分别由EA和EB中方向相反的弧交替构成的回路。例如，将图5中(4)所表示的DAB划分为3个AB-cycles，分别如图5中(5)～(7)所示。

(3)随机选取不超过u个AB-cycles，对于每个AB-cycle，在pA中移除AB-cycle中属于EA的弧，同时增加属于EB的弧，得到不超过u个的中间解。例如，将图5中(5)～(7)所示的AB-cycle分别生成中间解如图5中(8)～(10)所示。

(4)将每个中间解的若干部分连接起来，形成一个完整回路。其中，连接过程选择将弧数量最少的部分与其他部分连接，以便寻找到成本最小的连接方式。例如，图5中(8)～(10)连接后如图5中(11)～(13)所示。

(5)在若干完整回路中选择成本最小的一个作为子代解。

2.2.3 种群更新策略

为保持种群中的多样性，同时保证种群中的序列朝着成本更小的方向收敛。如果通过EAX生成的子代p的成本比父代pA的小且相对于pB来说与pA更相似，则用p替换种群中的pA；如p的成本比父代pB的小且相对于pA来说与pB更相似，则用子代p替换种群中的pB。其中，similar用于计算两个序列中相同相邻链的个数，相同的数量越多，表示两条序列更相似。

2.3 转换阶段

序列O是被服务链的有序排列，需将其中相邻且有重叠的部分进行拼接，并转换为D的闭链，如算法3所示。其中，第1～2行为按顺序遍历O中每对相邻的两条链rA，rB；第3行是当rA的尾部与rB的头部之间有重叠部分时，把rB中未重叠部分与W串接，即Concatenate(W，rA，rB)；第4～8行是当rA的尾部与rB的头部之间无重叠部分时，先将rA终点e与rB起点s之间的最小费用路径进行串接。第6～7行利用L中保存的e、s之间的最短路径，不断将路径中两个顶点间通过费用最小的弧串接到W；第8行再将rB与W串接；第9行将闭链W进行循环移位，使得W中的起点为v0。

算法3 转换阶段算法

在转换阶段，链rA，rB中的弧均为服务项，保证服务D中的每条弧，同时保证关联关系中涉及的弧均为服务项。而利用L串接的弧均为通过项，是为到达服务项而通过的。转换阶段并未发生成本的变化，因此，闭链W的总成本与序列O的总成本相同。

3 实例验证

为便于展示分析，选取CTCS-2级列控车载设备模式转换场景的45条测试案例作为测试案例集生成测试序列。其中，测试案例中涉及的起始终止状态包括未上电状态(NP)、待机模式(SB)、部分监控模式(PS)、完全监控模式(FS)、引导模式(CO)、目视行车模式(OS)、调车模式(SH)及隔离模式(IS)。测试案例的转移成本和测试成本是在某仿真测试平台上用于状态转移和测试执行时所花费的最小时间。

3.1 建立模型

将所有测试案例的起始终止状态集作为有向图的顶点集；将每条测试案例作为有向图的一条弧，弧的起点为测试案例起始状态对应的顶点，弧的终点为测试案例终止状态对应的顶点，弧的通过成本为测试案例的转移成本，弧的服务成本为测试案例的测试成本，弧的编号为测试案例的编号。为展示测试案例之间的状态转移衔接关系，人工建立的有向图如图6所示，每条弧上的三元组分别表示唯一编号、通过成本和服务成本。

图6 模式转换场景的有向图

根据测试需求，制定了一个顺序关系(0，2，8，9，17，16，6)，该顺序关系的实际意义为：列车上电(NP到SB)-启机过程(SB到PS)-PS模式行车(维持PS)-获取完整线路数据(PS-FS)-FS模式自动过分相(维持FS)-线路数据耗尽(FS到PS)-停车下电(PS-NP)。同时，根据以往测试经验，车载设备上电的组合情况容易出现异常，对此构造了测试案例0的2-维组合关系((0，1)，(0，2)，(0，3)，(0，4)，(0，5))。其中，(0，1)，(0，2)，(0，3)，(0，4)，(0，5)的实际意义分别为上电再下电，上电启机进入PS模式，上电启机进入OS模式，上电启机进入SH模式，上电启机进入IS模式。

根据上述顺序关系和组合关系组建了4个弧的关联关系集如表1所示。其中，4个关联关系集分别表示无关联关系，包含了顺序关系、组合关系、顺序关系和组合关系。

表1 模式转换场景的关联关系集

3.2 方法有效性分析

利用Java实现了第2节中的算法，并在电脑内存为8G，CPU为i5-6200U、2.30GHz的环境下，对图6的有向图与表1中的4个关联关系集分别进行运算。其中，算法中涉及的参数取值如表2所示；生成的测试序列如表3所示。表3中测试序列中带“( )”的编号表示该条测试案例只用于状态转换，为非测试项；加粗部分表示覆盖的顺序关系和组合关系。

表2 算法参数取值

表3 生成的测试序列

从4条测试序列可以看出，每条测试序列均覆盖了作为测试项的所有测试案例。对于不包含顺序关系和组合关系的测试序列a，总成本是最小的。而测试序列b、c、d分别覆盖了相应的顺序关系和组合关系，总成本不低于测试序列a的成本。

分别将关联关系集2、3、4中的关联关系人工串接成相应的弧添加到有向图中，再利用DCPP生成包含相应顺序关系和组合关系的测试序列，将其总成本与本文方法进行对比，如表4所示。

表4 测试序列总成本对比分析

当关联关系集为空时，两种方法生成的测试序列总成本均为4 510 s，均为最优解。当关联关系集为2，3，4时，本文所述方法生成的测试序列总成本分别减少了10.5%，9.8%，16.3%。

3.3 方法性能分析

通过分析发现，影响本文算法性能的因素是被服务链集R中元素的数量。为验证本文算法的性能，在图6所示模型基础上，通过分别增加编号0～25测试案例的2-维组合关系、所有测试案例的2-维组合关系、编号0～11测试案例的3-维组合关系、编号0～16测试案例的3-维组合关系，使得R中元素的数量分别为140，234，352，443。在每种情况下，分别运算20次，并与遗传算法(第3节中不采用插入优化的遗传算法)的运算结果进行对比。其中，本文算法与遗传算法生成测试序列的平均总成本相同，但在平均运算时间(图7(a))及迭代次数(图7(b))方面，由于本文算法引入了插入优化，有效提高了运算效率。当R集中元素数量为443时，平均运算时间和平均迭代次数分别降低了58.0%和74.3%。

图7 对比分析折线

4 结语

为解决测试案例之间带有顺序关系和组合关系的测试序列生成问题，抽象出一种新的弧路径问题——关联弧路径问题，并给出一种求解算法。关联弧路径问题能够解决有向图中弧之间存在关联关系的路径问题，将其应用在列控车载设备的测试序列生成中，生成的测试序列能够同时覆盖测试案例集、顺序关系集和组合关系集。测试序列的总成本与人工+DCPP方法相比有很大程度降低。此外，通过实验验证了本文算法在求解性能上的优势。