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

舒 月，張 勇

(北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

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

舒 月，張 勇

(北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

鑒于測試序列生成專家系統(tǒng)知識(shí)獲取困難以及知識(shí)庫維護(hù)不易等問題，本文提出從案例推理技術(shù)的新角度研究CTCS-3級列控系統(tǒng)測試序列的生成。設(shè)計(jì)了測試序列案例推理流程；提取了現(xiàn)場測試序列特征屬性并構(gòu)建了案例的框架表示結(jié)構(gòu)；為實(shí)現(xiàn)案例檢索，設(shè)計(jì)了屬性相似度計(jì)算方法、確定案例屬性權(quán)重的層次分析法、案例間相似度計(jì)算方法和案例檢索過程；給出一個(gè)測試序列生成的具體流程?；诎咐评淼难芯糠椒镃TCS-3級列控系統(tǒng)測試序列的生成提供了一個(gè)新的思路。

案例推理；測試序列生成；框架表示法；相似性度量；層次分析法

CTCS-3級列車控制系統(tǒng)（以下簡稱：列控系統(tǒng)）其安全運(yùn)行關(guān)系到列車運(yùn)行的安全。在系統(tǒng)正式投入運(yùn)營前，必須對其進(jìn)行一系列的系統(tǒng)功能測試工作[1]，驗(yàn)證其是否滿足技術(shù)規(guī)范的要求以及跨線運(yùn)行的需求。列控系統(tǒng)現(xiàn)場測試工作非常復(fù)雜，需要整個(gè)列控系統(tǒng)中每個(gè)設(shè)備以及鐵路各部門的緊密協(xié)同配合，測試序列是用于現(xiàn)場測試工作安全有序進(jìn)行的指導(dǎo)手冊。

目前，各類測試所需的測試序列以鐵路總公司頒布的《CTCS-3級列控系統(tǒng)測試案例（V3.0）》[2]為基礎(chǔ)，人工編制而成，費(fèi)時(shí)費(fèi)力，測試序列的質(zhì)量直接依賴于編制人員水平。為提高測試序列編制效率，國內(nèi)已開發(fā)了測試序列輔助生成工具，為測試序列的編制提供友好圖形操作環(huán)境[3～4]。同時(shí)，在總結(jié)測試序列編制經(jīng)驗(yàn)的基礎(chǔ)上，國內(nèi)對測試序列的計(jì)算機(jī)自動(dòng)生成技術(shù)也進(jìn)行了深入研究，使用人工智能專家系統(tǒng)方法實(shí)現(xiàn)測試序列生成已取得進(jìn)展和成果[5～6]，然而，該方法存在專家經(jīng)驗(yàn)規(guī)則的提取困難、推理過程費(fèi)時(shí)費(fèi)力、推理速度慢等不足。因此，本論文提出從案例推理的新角度研究測試序列的生成，該方法能一定程度上規(guī)避專家系統(tǒng)遇到的問題。

本文采用人工智能框架表示法，以研究出適合測試序列的知識(shí)表示為策略，使之既有相對固定的結(jié)構(gòu)，又可以非常靈活的更改和擴(kuò)充，以滿足各類預(yù)案的存儲(chǔ)搜索要求，并結(jié)合案例推理方法（CBR，Case Based Reasoning）, 探討測試序列的生成過程。

1 案例推理技術(shù)

案例推理是從人工智能領(lǐng)域發(fā)展起來的一項(xiàng)技術(shù)，其基本思想：根據(jù)當(dāng)前問題（目標(biāo)案例）的提示而訪問案例庫中同類案例（源案例）的求解，并由源案例來指導(dǎo)目標(biāo)案例求解的一種策略，是一種重要機(jī)器學(xué)習(xí)方法。在CBR中，把當(dāng)前所面臨的問題或情況稱為目標(biāo)案例，而把過去的問題或情況稱為源案例。

參考Aamodt和Plaza等國外學(xué)者提出的“4R”模型[7]，結(jié)合測試序列實(shí)際情況，圖1給出了測試序列案例推理的流程：

圖1 案例推理流程

（1）案例提取、表示和輸入。抽取測試序列的特征屬性和測試需求，用合適的方法表示案例，將其輸入系統(tǒng)，為推理提供基礎(chǔ)條件。

（2）案例檢索，包括案例索引和案例適配。通過調(diào)用模型庫中的層次分析模型，從案例庫中檢索出與當(dāng)前問題案例最相似的案例，若沒有搜索到相似案例，則使用人工求解的方式，求解案例，并將新案例保持到案例庫中，實(shí)現(xiàn)增量式學(xué)習(xí)，反正進(jìn)入案例修正階段。

（3）案例修正。該階段的目標(biāo)是從上一階段輸出的案例集中選擇最實(shí)用的案例，對其解進(jìn)行修正、優(yōu)化和調(diào)整，以符合新案例的需求。案例修正模塊是CBR系統(tǒng)實(shí)現(xiàn)技術(shù)的難點(diǎn)?？梢圆捎脤I(yè)編制人員人進(jìn)行工參與方式實(shí)現(xiàn)案例的改寫。

（4）方案評價(jià)。對新的求解方案與結(jié)果的實(shí)施效果或滿意度進(jìn)行評價(jià)和檢驗(yàn)，由編制人員完成。

（5）案例維護(hù)。包括新案例的存儲(chǔ)和舊案例

2 案例表示和組織

案例的表示和組織主要是確定測試序列案例表示結(jié)構(gòu)，通過適當(dāng)方法把源案例信息進(jìn)行數(shù)據(jù)庫存儲(chǔ)，并將其案例屬性轉(zhuǎn)換為計(jì)算機(jī)能夠處理的數(shù)據(jù)結(jié)構(gòu)。

本文用三元組的結(jié)構(gòu)描述案例，結(jié)構(gòu)為TS_Case：{Problem, Solution, Description}。

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

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

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

測試序列案例是進(jìn)行案例推理過程的載體，通常在案例庫中案例表示方式會(huì)隨著案例本身特性而有不同的表示方法，是整個(gè)CBR研究的基礎(chǔ)和核心，其表示方法決定了案例推理的效率和正確性。案例表示方法有10余種[8]，結(jié)合測試序列生成特點(diǎn)，通過綜合分析各方法的優(yōu)缺點(diǎn)，本文選用框架表示法對測試序列案例進(jìn)行描述。因?yàn)榘咐齼?nèi)容比較復(fù)雜，必須同時(shí)使用多個(gè)框架，組成一個(gè)框架系統(tǒng)，表示案例?？蚣苡煽蚣苊鸵唤M槽組成，槽由一組側(cè)面組成，框架表示一個(gè)對象，每個(gè)槽則表示對象的屬性，槽的值就是對象的屬性值。槽的側(cè)面值可以由框架組成，即允許嵌套[9]。

通過分析《CTCS-3級列控系統(tǒng)總體技術(shù)方的維護(hù)，體現(xiàn)CBR 系統(tǒng)自學(xué)習(xí)能力。當(dāng)前問題所求解的過程與結(jié)果形成的新案例，根據(jù)CBR案例庫管理者在實(shí)際應(yīng)用中設(shè)定的某個(gè)特定閾值，來決定是否將目標(biāo)案例作為新案例存入案例庫。同時(shí)對源案例只做描述方式或存儲(chǔ)結(jié)構(gòu)上的調(diào)整，不做推理過程上的改動(dòng)。

（6）案例復(fù)用。該階段將已修改的測試序列案例的解，以文檔手冊等的方式，供司機(jī)和測試人員使用，用于指導(dǎo)列車測試過程。案》[10]中運(yùn)營場景和工作模式以及現(xiàn)場測試序列報(bào)告，將提取出的測試序列信息同三元組結(jié)構(gòu)相融合，設(shè)計(jì)如表1所示的測試序列案例的結(jié)構(gòu)。其中，問題空間被拆分為基本信息、測試需求和測試案例3個(gè)部分，案例框架的內(nèi)容信息將會(huì)根據(jù)具體的情況，有一定的調(diào)整。限于篇幅，框架只列舉了部分槽信息。

在該框架中，列車運(yùn)行路徑、試驗(yàn)前提條件、注冊與啟動(dòng)等屬性包含的內(nèi)容多，將嵌套框架結(jié)構(gòu)描述這些屬性。

表1 案例框架表示

案例組織是CBR系統(tǒng)設(shè)計(jì)的重要環(huán)節(jié)，直接影響測試序列案例推理的效率。通過對測試序列案例的分析，本文采用關(guān)系數(shù)據(jù)庫結(jié)構(gòu)的設(shè)計(jì)思想，存儲(chǔ)案例，搭建測試序列案例庫。圖2為測試序列數(shù)據(jù)庫E-R模型。

3 案例檢索

案例檢索是案例推理方法的核心，其目標(biāo)是快速高效的地從案例庫中查找同問題描述最相似的案例。

3.1 相似度計(jì)算

案例間相似性可通過比較兩案例的屬性值（相似元[11]），綜合共有屬性或特征比較的結(jié)果，作為相似性計(jì)算的標(biāo)準(zhǔn)。

3.1.1 案例屬性相似度計(jì)算

數(shù)值型屬性的相似度計(jì)算，采用基于歐幾里德距離公式演化而來的一種計(jì)算確定數(shù)值型屬性的相似度算法。

圖2 測試序列案例庫E-R模型

式（1）中，sim(xi, yi)表示案例x和y的第i個(gè)確定屬性的相似度；xi和yi表示案例x和y的第 i個(gè)屬性值；ri表示屬性i的取值范圍。

符號型屬性的相似度計(jì)算，采用以下相似度計(jì)算方法。

式（2）中，xi和yi表示案例x和y的第i個(gè)屬性，該屬性是一種簡單的枚舉法，屬性值間不存在實(shí)際意義上量的關(guān)系。

3.1.2 屬性權(quán)重的確定

本文采用層次分析法（APH）確定屬性的權(quán)值[12]：（1）建立目標(biāo)層、準(zhǔn)則層、方案層3層層次分析模型。目標(biāo)層描述測試序列生成需求；準(zhǔn)則層對應(yīng)進(jìn)行測試序列案例選擇的標(biāo)準(zhǔn)和要求；主要指案例框架中測試需求槽中的內(nèi)容；方案層對應(yīng)案例庫提供的測試序列案例集。（2）通過相互比較準(zhǔn)則層中的指標(biāo)屬性，確定準(zhǔn)則對于目標(biāo)的權(quán)值，即構(gòu)造案例屬性判斷矩陣；繼而計(jì)算判斷矩陣最大特征值及其對應(yīng)的特征向量，利用一致性指標(biāo)做判斷矩陣的一致性校驗(yàn)，若通過校驗(yàn)，歸一化處理后的特征向量即為對應(yīng)屬性的權(quán)重集合。

3.1.3 案例間相似性計(jì)算公式，采用改進(jìn)的TC相似法[13]

式（3）中，MCxy表示案例x和案例y的相似度，表示第i屬性在案例x中的權(quán)重，表示第i屬性在案例k中的權(quán)重，sim(xi, yi)表示案例n和案例k第i屬性的相似度， m表示屬性個(gè)數(shù)。

3.2 案例檢索過程

案例檢索的目的是得到一個(gè)與新問題最相似的源案例，案例檢索過程分兩步走：

（1）案例索引；設(shè)置索引表，比較案例間對應(yīng)的槽值或側(cè)面值，縮小目標(biāo)案例的查找范圍，提高案例檢索的效率。案例索引表信息從基本信息和測試需求中提取，內(nèi)容主要包括：基本信息（線路選擇類型，列車運(yùn)行路徑等）、測試需求（注冊與啟動(dòng)，注銷等）以及測試用例等。

（2）案例適配；使用層次分析法確定測試需求槽中每個(gè)屬性的權(quán)重并進(jìn)行歸一化處理，得到初始權(quán)重 w1，w2，…，w34，… …，并計(jì)算案例屬性間相似度，使用改進(jìn)的TC相似法，得到案例間相似度，選擇相似度最好的案例集，作為案例修正階段的輸入。在收集到足夠多在屬性上都有相應(yīng)值的案例之后，可以通過神經(jīng)網(wǎng)絡(luò)算法采用訓(xùn)練樣本案例對權(quán)重進(jìn)行調(diào)整。

4 示例

結(jié)合案例推理流程，給出一個(gè)測試序列生成具體流程。

問題描述：列車從虎門站出發(fā)，途經(jīng)中繼站，抵達(dá)光明站。需要測試列車注冊與啟動(dòng)、RBC切換、臨時(shí)限速和注銷等功能。

思路：將問題描述轉(zhuǎn)換成基本信息和測試需求已知的目標(biāo)案例，提取滿足索引要求的測試序列案例集合，比較目標(biāo)案例和源案例集間相似度，在編制人員參與下，擇優(yōu)選擇案例并對其修正，使其滿足需求。案例索引在論文中已詳細(xì)描述，此處不在討論。該處將重點(diǎn)討論案例適配過程。

提取該案例的問題空間信息P：{P1：＜注冊與啟動(dòng)＞，P2：＜RBC切換＞，P3：＜臨時(shí)限速＞，P4＜注銷＞}。＜注冊與啟動(dòng)＞框架屬性信息P1：{A1：啟動(dòng)位置，車站；A2：運(yùn)行等級，CTCS-3；A3：運(yùn)行模式，F(xiàn)S }；＜RBC切換＞框架屬性信息P2：{B1：電臺(tái)個(gè)數(shù)，雙電臺(tái)；B2：RBC切換點(diǎn)位置，位置1[公里標(biāo)23561G，23579G]}；＜臨時(shí)限速＞框架屬性信息P3：{C1：臨時(shí)限速個(gè)數(shù)，1；C2：臨時(shí)限速起點(diǎn)，K2359+701 ；C3：臨時(shí)限速終點(diǎn)，K2361+635 }；＜注銷＞框架屬性信息P4：{D1：運(yùn)行等級，CTCS -3}。目標(biāo)案例和源案例關(guān)鍵參數(shù)的計(jì)算結(jié)果如表2所示。

表2 計(jì)算實(shí)例

案例檢索結(jié)果表明，目標(biāo)案例與案例2的相似度最高，因此案例2的測試具體方案可供目標(biāo)案例參考，經(jīng)案例修正后，可生成適合目標(biāo)案例的解方案。此處給出的只是一個(gè)簡單的案例，目的在于透過案例分析，表明案例推理方法在測試序列生成過程中的可用性和實(shí)用性，在實(shí)際中，系統(tǒng)的案例表示、提取更為詳細(xì)全面，提取出的案例方案具有更高的實(shí)用價(jià)值。

5 結(jié)束語

本文闡述了基于案例推理的測試序列生成方法的設(shè)計(jì)和實(shí)現(xiàn)流程。該方法從類比推理的嶄新角度，探討測試序列的生成流程，實(shí)現(xiàn)了案例推理的思想和測試序列生成過程的結(jié)合，克服了測試序列生成專家系統(tǒng)在知識(shí)規(guī)則獲取上的瓶頸，為人工智能技術(shù)在鐵路行業(yè)中的應(yīng)用提供了新思路。

[1]中國鐵路總公司．鐵技委函[2009]773號：CTCS-3級列控系統(tǒng)綜合試驗(yàn)試驗(yàn)大綱[S]. 北京：中國鐵路總公司，2009，7.

[2]中國鐵路總公司科學(xué)技術(shù)司，鐵路總公司運(yùn)輸局.科技運(yùn)[2009]59：CTCS-3級列控系統(tǒng)測試案例.v3.0[S].北京：鐵路總公司科學(xué)技術(shù)司，鐵路總公司運(yùn)輸局，2009.

[3]張 勇，王超琦. CTCS-3級列控系統(tǒng)車載設(shè)備測試序列優(yōu)化生成方法[J].中國鐵道科學(xué)，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].合肥學(xué)院學(xué)報(bào)，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級列控系統(tǒng)技術(shù)創(chuàng)新總體方案[M].北京：中國鐵道出版社，2008.

[11]周美立.相似工程學(xué)[M].北京：機(jī)械工業(yè)出版杜1998.

[12]許樹柏. 層次分析法原理[M]. 天津：天津大學(xué)出版社，1988.

[13]魏元風(fēng),駱洪青,辛崇渡.屬性相似案例的檢索模型比較研究[J].華東船舶工業(yè)學(xué)院學(xué)報(bào)，1999，13（4）：41-44.

責(zé)任編輯 徐侃春

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

中國鐵路總公司科技開發(fā)計(jì)劃項(xiàng)目（2013X001-F）。

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