基于案例推理的測試序列生成方法研究

舒 月，張 勇

(北京交通大學 電子信息工程學院，北京 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系統實現技術的難點?？梢圆捎脤I編制人員人進行工參與方式實現案例的改寫。

（4）方案評價。對新的求解方案與結果的實施效果或滿意度進行評價和檢驗，由編制人員完成。

（5）案例維護。包括新案例的存儲和舊案例

2 案例表示和組織

案例的表示和組織主要是確定測試序列案例表示結構，通過適當方法把源案例信息進行數據庫存儲，并將其案例屬性轉換為計算機能夠處理的數據結構。

本文用三元組的結構描述案例，結構為TS_Case：{Problem, Solution, Description}。

Problem（問題空間）：是對求解的問題特征提取及周圍世界或環境相關的所有特征集合，由集合P描述。主要包括了測試序列中對案例推理起決定作用的特征屬性及其屬性值。

Solution（解空間）：對問題的解決方案的描述，由集合S描述。主要包括了測試序列測試步驟等描述。

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

測試序列案例是進行案例推理過程的載體，通常在案例庫中案例表示方式會隨著案例本身特性而有不同的表示方法，是整個CBR研究的基礎和核心，其表示方法決定了案例推理的效率和正確性。案例表示方法有10余種[8]，結合測試序列生成特點，通過綜合分析各方法的優缺點，本文選用框架表示法對測試序列案例進行描述。因為案例內容比較復雜，必須同時使用多個框架，組成一個框架系統，表示案例?？蚣苡煽蚣苊鸵唤M槽組成，槽由一組側面組成，框架表示一個對象，每個槽則表示對象的屬性，槽的值就是對象的屬性值。槽的側面值可以由框架組成，即允許嵌套[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）。

舒 月，在讀碩士研究生；張 勇，副教授。