基于案例推理的测试序列生成方法研究

舒 月，张 勇

(北京交通大学 电子信息工程学院，北京 100044)

基于案例推理的测试序列生成方法研究

舒 月，张 勇

(北京交通大学 电子信息工程学院，北京 100044)

鉴于测试序列生成专家系统知识获取困难以及知识库维护不易等问题，本文提出从案例推理技术的新角度研究CTCS-3级列控系统测试序列的生成。设计了测试序列案例推理流程；提取了现场测试序列特征属性并构建了案例的框架表示结构；为实现案例检索，设计了属性相似度计算方法、确定案例属性权重的层次分析法、案例间相似度计算方法和案例检索过程；给出一个测试序列生成的具体流程。基于案例推理的研究方法为CTCS-3级列控系统测试序列的生成提供了一个新的思路。

案例推理；测试序列生成；框架表示法；相似性度量；层次分析法

CTCS-3级列车控制系统（以下简称：列控系统）其安全运行关系到列车运行的安全。在系统正式投入运营前，必须对其进行一系列的系统功能测试工作[1]，验证其是否满足技术规范的要求以及跨线运行的需求。列控系统现场测试工作非常复杂，需要整个列控系统中每个设备以及铁路各部门的紧密协同配合，测试序列是用于现场测试工作安全有序进行的指导手册。

目前，各类测试所需的测试序列以铁路总公司颁布的《CTCS-3级列控系统测试案例（V3.0）》[2]为基础，人工编制而成，费时费力，测试序列的质量直接依赖于编制人员水平。为提高测试序列编制效率，国内已开发了测试序列辅助生成工具，为测试序列的编制提供友好图形操作环境[3～4]。同时，在总结测试序列编制经验的基础上，国内对测试序列的计算机自动生成技术也进行了深入研究，使用人工智能专家系统方法实现测试序列生成已取得进展和成果[5～6]，然而，该方法存在专家经验规则的提取困难、推理过程费时费力、推理速度慢等不足。因此，本论文提出从案例推理的新角度研究测试序列的生成，该方法能一定程度上规避专家系统遇到的问题。

本文采用人工智能框架表示法，以研究出适合测试序列的知识表示为策略，使之既有相对固定的结构，又可以非常灵活的更改和扩充，以满足各类预案的存储搜索要求，并结合案例推理方法（CBR，Case Based Reasoning）, 探讨测试序列的生成过程。

1 案例推理技术

案例推理是从人工智能领域发展起来的一项技术，其基本思想：根据当前问题（目标案例）的提示而访问案例库中同类案例（源案例）的求解，并由源案例来指导目标案例求解的一种策略，是一种重要机器学习方法。在CBR中，把当前所面临的问题或情况称为目标案例，而把过去的问题或情况称为源案例。

参考Aamodt和Plaza等国外学者提出的“4R”模型[7]，结合测试序列实际情况，图1给出了测试序列案例推理的流程：

图1 案例推理流程

（1）案例提取、表示和输入。抽取测试序列的特征属性和测试需求，用合适的方法表示案例，将其输入系统，为推理提供基础条件。

（2）案例检索，包括案例索引和案例适配。通过调用模型库中的层次分析模型，从案例库中检索出与当前问题案例最相似的案例，若没有搜索到相似案例，则使用人工求解的方式，求解案例，并将新案例保持到案例库中，实现增量式学习，反正进入案例修正阶段。

（3）案例修正。该阶段的目标是从上一阶段输出的案例集中选择最实用的案例，对其解进行修正、优化和调整，以符合新案例的需求。案例修正模块是CBR系统实现技术的难点。可以采用专业编制人员人进行工参与方式实现案例的改写。

（4）方案评价。对新的求解方案与结果的实施效果或满意度进行评价和检验，由编制人员完成。

（5）案例维护。包括新案例的存储和旧案例

2 案例表示和组织

案例的表示和组织主要是确定测试序列案例表示结构，通过适当方法把源案例信息进行数据库存储，并将其案例属性转换为计算机能够处理的数据结构。

本文用三元组的结构描述案例，结构为TS_Case：{Problem, Solution, Description}。

Problem（问题空间）：是对求解的问题特征提取及周围世界或环境相关的所有特征集合，由集合P描述。主要包括了测试序列中对案例推理起决定作用的特征属性及其属性值。

Solution（解空间）：对问题的解决方案的描述，由集合S描述。主要包括了测试序列测试步骤等描述。

Description（效果描述）：解决方案的优劣描述，由集合D描述。

测试序列案例是进行案例推理过程的载体，通常在案例库中案例表示方式会随着案例本身特性而有不同的表示方法，是整个CBR研究的基础和核心，其表示方法决定了案例推理的效率和正确性。案例表示方法有10余种[8]，结合测试序列生成特点，通过综合分析各方法的优缺点，本文选用框架表示法对测试序列案例进行描述。因为案例内容比较复杂，必须同时使用多个框架，组成一个框架系统，表示案例。框架由框架名和一组槽组成，槽由一组侧面组成，框架表示一个对象，每个槽则表示对象的属性，槽的值就是对象的属性值。槽的侧面值可以由框架组成，即允许嵌套[9]。

通过分析《CTCS-3级列控系统总体技术方的维护，体现CBR 系统自学习能力。当前问题所求解的过程与结果形成的新案例，根据CBR案例库管理者在实际应用中设定的某个特定阈值，来决定是否将目标案例作为新案例存入案例库。同时对源案例只做描述方式或存储结构上的调整，不做推理过程上的改动。

（6）案例复用。该阶段将已修改的测试序列案例的解，以文档手册等的方式，供司机和测试人员使用，用于指导列车测试过程。案》[10]中运营场景和工作模式以及现场测试序列报告，将提取出的测试序列信息同三元组结构相融合，设计如表1所示的测试序列案例的结构。其中，问题空间被拆分为基本信息、测试需求和测试案例3个部分，案例框架的内容信息将会根据具体的情况，有一定的调整。限于篇幅，框架只列举了部分槽信息。

在该框架中，列车运行路径、试验前提条件、注册与启动等属性包含的内容多，将嵌套框架结构描述这些属性。

表1 案例框架表示

案例组织是CBR系统设计的重要环节，直接影响测试序列案例推理的效率。通过对测试序列案例的分析，本文采用关系数据库结构的设计思想，存储案例，搭建测试序列案例库。图2为测试序列数据库E-R模型。

3 案例检索

案例检索是案例推理方法的核心，其目标是快速高效的地从案例库中查找同问题描述最相似的案例。

3.1 相似度计算

案例间相似性可通过比较两案例的属性值（相似元[11]），综合共有属性或特征比较的结果，作为相似性计算的标准。

3.1.1 案例属性相似度计算

数值型属性的相似度计算，采用基于欧几里德距离公式演化而来的一种计算确定数值型属性的相似度算法。

图2 测试序列案例库E-R模型

式（1）中，sim(xi, yi)表示案例x和y的第i个确定属性的相似度；xi和yi表示案例x和y的第 i个属性值；ri表示属性i的取值范围。

符号型属性的相似度计算，采用以下相似度计算方法。

式（2）中，xi和yi表示案例x和y的第i个属性，该属性是一种简单的枚举法，属性值间不存在实际意义上量的关系。

3.1.2 属性权重的确定

本文采用层次分析法（APH）确定属性的权值[12]：（1）建立目标层、准则层、方案层3层层次分析模型。目标层描述测试序列生成需求；准则层对应进行测试序列案例选择的标准和要求；主要指案例框架中测试需求槽中的内容；方案层对应案例库提供的测试序列案例集。（2）通过相互比较准则层中的指标属性，确定准则对于目标的权值，即构造案例属性判断矩阵；继而计算判断矩阵最大特征值及其对应的特征向量，利用一致性指标做判断矩阵的一致性校验，若通过校验，归一化处理后的特征向量即为对应属性的权重集合。

3.1.3 案例间相似性计算公式，采用改进的TC相似法[13]

式（3）中，MCxy表示案例x和案例y的相似度，表示第i属性在案例x中的权重，表示第i属性在案例k中的权重，sim(xi, yi)表示案例n和案例k第i属性的相似度， m表示属性个数。

3.2 案例检索过程

案例检索的目的是得到一个与新问题最相似的源案例，案例检索过程分两步走：

（1）案例索引；设置索引表，比较案例间对应的槽值或侧面值，缩小目标案例的查找范围，提高案例检索的效率。案例索引表信息从基本信息和测试需求中提取，内容主要包括：基本信息（线路选择类型，列车运行路径等）、测试需求（注册与启动，注销等）以及测试用例等。

（2）案例适配；使用层次分析法确定测试需求槽中每个属性的权重并进行归一化处理，得到初始权重 w1，w2，…，w34，… …，并计算案例属性间相似度，使用改进的TC相似法，得到案例间相似度，选择相似度最好的案例集，作为案例修正阶段的输入。在收集到足够多在属性上都有相应值的案例之后，可以通过神经网络算法采用训练样本案例对权重进行调整。

4 示例

结合案例推理流程，给出一个测试序列生成具体流程。

问题描述：列车从虎门站出发，途经中继站，抵达光明站。需要测试列车注册与启动、RBC切换、临时限速和注销等功能。

思路：将问题描述转换成基本信息和测试需求已知的目标案例，提取满足索引要求的测试序列案例集合，比较目标案例和源案例集间相似度，在编制人员参与下，择优选择案例并对其修正，使其满足需求。案例索引在论文中已详细描述，此处不在讨论。该处将重点讨论案例适配过程。

提取该案例的问题空间信息P：{P1：＜注册与启动＞，P2：＜RBC切换＞，P3：＜临时限速＞，P4＜注销＞}。＜注册与启动＞框架属性信息P1：{A1：启动位置，车站；A2：运行等级，CTCS-3；A3：运行模式，FS }；＜RBC切换＞框架属性信息P2：{B1：电台个数，双电台；B2：RBC切换点位置，位置1[公里标23561G，23579G]}；＜临时限速＞框架属性信息P3：{C1：临时限速个数，1；C2：临时限速起点，K2359+701 ；C3：临时限速终点，K2361+635 }；＜注销＞框架属性信息P4：{D1：运行等级，CTCS -3}。目标案例和源案例关键参数的计算结果如表2所示。

表2 计算实例

案例检索结果表明，目标案例与案例2的相似度最高，因此案例2的测试具体方案可供目标案例参考，经案例修正后，可生成适合目标案例的解方案。此处给出的只是一个简单的案例，目的在于透过案例分析，表明案例推理方法在测试序列生成过程中的可用性和实用性，在实际中，系统的案例表示、提取更为详细全面，提取出的案例方案具有更高的实用价值。

5 结束语

本文阐述了基于案例推理的测试序列生成方法的设计和实现流程。该方法从类比推理的崭新角度，探讨测试序列的生成流程，实现了案例推理的思想和测试序列生成过程的结合，克服了测试序列生成专家系统在知识规则获取上的瓶颈，为人工智能技术在铁路行业中的应用提供了新思路。

[1]中国铁路总公司．铁技委函[2009]773号：CTCS-3级列控系统综合试验试验大纲[S]. 北京：中国铁路总公司，2009，7.

[2]中国铁路总公司科学技术司，铁路总公司运输局.科技运[2009]59：CTCS-3级列控系统测试案例.v3.0[S].北京：铁路总公司科学技术司，铁路总公司运输局，2009.

[3]张 勇，王超琦. CTCS-3级列控系统车载设备测试序列优化生成方法[J].中国铁道科学，2011，32（3）: 100-106.

[4]ZHANG Yong, TANG Huidong, CHEN Yan, ZHOU Rong. Research and Implementation of Test Case Management System for CTCS-3 Train Control System [Z]. 2011 International Conference on Information, Services and Management Engineering. Beijing, China, 2011.

[5]Zhang Yong, Wang Shu, Zhang Xiaokun, Sha Shuo, XuGaozhen, A Computer-aided Tool for Generating Test Sequences for CTCS-3 Train Control System, AISS:Advances in Information Sciences and Service Sciences, 4/11/311-319, 2012-6.

[6]Zhang Yong, Sha Shuo, Wang Shu, An Expert System Approach for Generating Test Sequence for CTCS-3 Train Control System, 2013 Fourth International Conference on Intelligent Control and Information Processing (ICICIP), pp271-276, 2013-6.

[7]A.Aamodt, E.Plaza. Case-based reasoning：foundational issues, methodological variations, and system approaches, Artif i cial Intelligence Communications. 1994:39-59.

[8]李建洋,陈雪云,刘慧婷,谢秀珍.基于案例推理中案例表示的研究[J].合肥学院学报，2007（3）：26-29.

[9]Shiu, S.C.K.. Case-Based Reasoning: Concepts, Features and Soft Computing[J].Applied Intelligence,2004,20(2): 92-99.

[10]张曙光. CTCS-3级列控系统技术创新总体方案[M].北京：中国铁道出版社，2008.

[11]周美立.相似工程学[M].北京：机械工业出版杜1998.

[12]许树柏. 层次分析法原理[M]. 天津：天津大学出版社，1988.

[13]魏元风,骆洪青,辛崇渡.属性相似案例的检索模型比较研究[J].华东船舶工业学院学报，1999，13（4）：41-44.

责任编辑 徐侃春

Test sequence generation based on case-based reasoning

SHU Yue, ZHANG Yong
( School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing 100044, China )

New case-based reasoning method was used to generate test sequence for the reason that it was diff i culty to test sequence generation expert system in acquiring knowledge and maintaining the knowledge base. The paper designed the process of case based reasoning for test sequence generation, extracted the features of test sequence and constructed the framework for cases. To implement the case retrieval, it was designed the method of attribute similarity measurement, the analytic hierarchy process which was used to determine the attribute weight, method of case similarity measurement and the process of case retrieval. An example to show detailed process of test sequence generation was provided. Case-based reasoning opened up a new way to generate the test sequence.

case-based reasoning; test sequence generation; frame representation; similarity measurement; analytic hierarchy process(AHP)

U284.482∶TP39

：A

1005-8451（2014）06-0016-05

2013-12-15

中国铁路总公司科技开发计划项目（2013X001-F）。

舒 月，在读硕士研究生；张 勇，副教授。