考慮順序和組合關系的列控車載設備測試序列生成方法

王 碩,崔佳諾,吳培棟,張友兵

(北京全路通信信號研究設計院集團有限公司,北京 100070)

引言

列控車載設備是列控系統(tǒng)的重要組成部分，直接影響列車行車效率和運行安全，在投入使用前應進行嚴格完整的測試[1-2]。其中，測試案例描述了測試輸入和預期結果。在執(zhí)行測試案例時，要求列控車載設備處于規(guī)定的起始狀態(tài)；當測試案例執(zhí)行完成后，會造成系統(tǒng)狀態(tài)的轉移。因此，測試案例不能單獨直接執(zhí)行，需通過一些功能將列控車載設備調整至測試案例指定的初始狀態(tài)，而相關功能又包含在其他測試案例中。由此進行的狀態(tài)調整將導致大量測試案例被重復執(zhí)行，嚴重影響測試效率[3]。

為提高測試效率，需利用測試案例之間的狀態(tài)轉移銜接關系，將測試案例有序串接為測試序列。但由于列控車載設備的測試案例規(guī)模較大，人工串接測試案例工作繁重，容易遺漏測試案例且測試序列中往往包含大量冗余的測試案例，直接增加了測試執(zhí)行的成本。因此，如何充分利用測試案例間的銜接關系構建測試序列并使測試序列的總成本最小，成為列控車載設備測試領域的一個重要問題，即測試序列優(yōu)化生成問題。

近年來，研究多是將測試案例之間的銜接關系描述為有向圖的頂點和弧，并把測試序列優(yōu)化生成問題轉化為有向中國郵路問題(Directed Chinese Postman Problem， DCPP)[4-6]或非對稱旅行商問題(Asymmetric Traveling Salesman Problem， ATSP)[7-8]來生成測試序列。此外，ZHENG，梁茨等[9-10]提出了序列優(yōu)選算法生成測試序列；趙曉宇，唐匯東等[11-12]考慮了測試案例的優(yōu)先級并生成了測試序列；宋爽等[13-14]提出了一種基于時間自動機模型的區(qū)域控制器測試序列生成方法。上述方法的基本假設是測試案例之間完全相互獨立。而在實際測試過程中，為對被測設備的特定流程及其組合進行測試，測試案例之間往往會涉及一些順序和組合關系。這些關系是測試經驗和測試需求的共同體現，在實際測試中具有很強的應用需求?；诖?，ZHANG等[15]利用知識樹和基于模型的推理實現了構建測試序列的專家系統(tǒng)；LI，袁磊等[16-17]則利用了深度學習生成測試序列。但前述研究方法無法確定性地覆蓋測試案例之間指定的順序關系和組合關系。

為使測試序列以最小的成本覆蓋測試案例及其順序關系和組合關系，首先，定義了一種關聯弧路徑問題(Associated Arc Routing Problem， AARP)，用于解決有向圖中弧之間存在關聯關系的路徑問題，并提出了一種求解算法；然后，利用AARP及其求解算法生成測試序列；最后，以CTCS-2級列控車載設備的測試序列生成為例，驗證本文所述方法的有效性。

1 研究基礎

1.1 測試案例與測試序列

定義1(測試案例) 一條測試案例是一個6元組t=(ss，id，o，p，c，se)。

其中，ss是為執(zhí)行該測試案例而要求被測設備所處的起始狀態(tài)；id是測試案例的唯一編號；o是測試案例的操作輸入和期望輸出；p是測試案例的轉移成本，指當測試案例作為狀態(tài)轉移項執(zhí)行時所花費的時間；c是測試案例的測試成本，指當測試案例作為測試項執(zhí)行時所花費的時間；se是被測設備正常執(zhí)行測試案例后所處的終止狀態(tài)。

根據測試案例的起始終止狀態(tài)將測試案例串接為測試序列，使前面的測試案例為后面測試案例創(chuàng)造執(zhí)行條件，能夠有效減少測試案例的重復執(zhí)行。

定義2(測試序列) 一條測試序列S=(t0，t1，…，tm-1)是若干測試案例的有序銜接序列，其中，m為測試序列中測試案例的總數量。

測試序列中的測試案例分為狀態(tài)轉移項和測試項兩類：狀態(tài)轉移項是為其他測試案例構造測試條件，只執(zhí)行相應的輸入，花費的時間為p≥0；測試項是為了檢驗被測設備的功能，既要執(zhí)行相應的輸入，又要記錄相應的輸出，并與期望輸出作比較，其花費時間為c，且c≥p≥0。

1.2 順序關系與組合關系

測試案例是功能需求的體現，在測試過程中，測試人員往往會根據以往測試經驗和功能需求對部分測試案例的特定順序或組合進行測試。將這種特定順序和組合分別稱為測試案例之間的順序關系和組合關系。不同于現有研究方法，本文生成的測試序列不僅需覆蓋測試案例集，同時要覆蓋測試案例之間的順序關系和組合關系。

測試案例之間的順序關系是指規(guī)定了若干測試案例的銜接順序，以對特定功能流程進行驗證。例如，圖1所示的9條測試案例(每條弧表示一條測試案例，弧上的數字表示測試案例編號)，從狀態(tài)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中連續(xù)被服務的弧構成的鏈與h相同，則稱W包含h；如W包含H中的所有鏈，則稱W滿足關聯關系集H。其中，規(guī)定弧的關聯關系集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)生成階段。利用插入優(yōu)化和遺傳算法相結合方式將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)。其中，規(guī)定兩個相同鏈間的成本Mii=0。

圖2 有重疊鏈之間最小成本示意

圖3 無重疊鏈之間最小成本示意

2.2 生成階段

經過準備階段，R中包含了所有需要被服務的鏈，M為鏈之間的最小成本。將R中的鏈按照一定順序排列，并使得序列中相鄰鏈(序列的最后一條鏈和序列的第一條鏈也視為相鄰鏈)間的成本之和最小，則該序列即為生成階段的結果O={r0，…，rm-1}。其中，ri為O中的第i條鏈，m為R中鏈的數量，O的總成本如式(1)所示。

(1)

利用插入優(yōu)化和遺傳算法相結合方式求最小成本的O如算法2所示。第1行采用隨機生成與插入優(yōu)化相結合的方式生成n個序列，作為初始種群。第3～9行是迭代進化的過程。其中，第3行對P中元素進行隨機排序。第6行選擇兩個序列進行交叉并產生一個較好的子代，其中交叉算子采用EAX(Edge Assembly Crossover)。7～8行是子代替換父代的策略。第9行表示當連續(xù)g代種群中最優(yōu)序列未得到改善，則終止迭代進化。第10行為返回種群中最優(yōu)序列O。

算法2 生成階段算法

2.2.1 初始化種群

初始化種群的策略為首先隨機生成n條序列，然后根據插入優(yōu)化概率Po隨機選取若干序列進行插入優(yōu)化運算。這種策略既能夠保證種群的多樣性，又能夠保證種群中具有較好的路徑，提高收斂速度。

一次插入優(yōu)化運算是為在序列中尋找一條鏈的一個插入位置，使得序列的成本降低最多。如圖4(a)中，如將ri取出插入到rj之后，就形成了圖4(b)所示的序列，則降低的成本如式(2)所示。

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

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

(2)

圖4 插入操作成本變化示意

對于序列中的每條鏈依次嘗試所有可能的插入位置，記錄成本降低最多的鏈和其插入位置，并進行插入操作，即完成了一次插入優(yōu)化運算。對完成一次插入優(yōu)化運算的序列再次進行插入優(yōu)化運算，直到不存在降低成本的插入為止。

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進行循環(huán)移位，使得W中的起點為v0。

算法3 轉換階段算法

在轉換階段，鏈rA，rB中的弧均為服務項，保證服務D中的每條弧，同時保證關聯關系中涉及的弧均為服務項。而利用L串接的弧均為通過項，是為到達服務項而通過的。轉換階段并未發(fā)生成本的變化，因此，閉鏈W的總成本與序列O的總成本相同。

3 實例驗證

為便于展示分析，選取CTCS-2級列控車載設備模式轉換場景的45條測試案例作為測試案例集生成測試序列。其中，測試案例中涉及的起始終止狀態(tài)包括未上電狀態(tài)(NP)、待機模式(SB)、部分監(jiān)控模式(PS)、完全監(jiān)控模式(FS)、引導模式(CO)、目視行車模式(OS)、調車模式(SH)及隔離模式(IS)。測試案例的轉移成本和測試成本是在某仿真測試平臺上用于狀態(tài)轉移和測試執(zhí)行時所花費的最小時間。

3.1 建立模型

將所有測試案例的起始終止狀態(tài)集作為有向圖的頂點集；將每條測試案例作為有向圖的一條弧，弧的起點為測試案例起始狀態(tài)對應的頂點，弧的終點為測試案例終止狀態(tài)對應的頂點，弧的通過成本為測試案例的轉移成本，弧的服務成本為測試案例的測試成本，弧的編號為測試案例的編號。為展示測試案例之間的狀態(tài)轉移銜接關系，人工建立的有向圖如圖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節(jié)中的算法，并在電腦內存為8G，CPU為i5-6200U、2.30GHz的環(huán)境下，對圖6的有向圖與表1中的4個關聯關系集分別進行運算。其中，算法中涉及的參數取值如表2所示；生成的測試序列如表3所示。表3中測試序列中帶“( )”的編號表示該條測試案例只用于狀態(tài)轉換，為非測試項；加粗部分表示覆蓋的順序關系和組合關系。

表2 算法參數取值

表3 生成的測試序列

從4條測試序列可以看出，每條測試序列均覆蓋了作為測試項的所有測試案例。對于不包含順序關系和組合關系的測試序列a，總成本是最小的。而測試序列b、c、d分別覆蓋了相應的順序關系和組合關系，總成本不低于測試序列a的成本。

分別將關聯關系集2、3、4中的關聯關系人工串接成相應的弧添加到有向圖中，再利用DCPP生成包含相應順序關系和組合關系的測試序列，將其總成本與本文方法進行對比，如表4所示。

表4 測試序列總成本對比分析

當關聯關系集為空時，兩種方法生成的測試序列總成本均為4 510 s，均為最優(yōu)解。當關聯關系集為2，3，4時，本文所述方法生成的測試序列總成本分別減少了10.5%，9.8%，16.3%。

3.3 方法性能分析

通過分析發(fā)現，影響本文算法性能的因素是被服務鏈集R中元素的數量。為驗證本文算法的性能，在圖6所示模型基礎上，通過分別增加編號0～25測試案例的2-維組合關系、所有測試案例的2-維組合關系、編號0～11測試案例的3-維組合關系、編號0～16測試案例的3-維組合關系，使得R中元素的數量分別為140，234，352，443。在每種情況下，分別運算20次，并與遺傳算法(第3節(jié)中不采用插入優(yōu)化的遺傳算法)的運算結果進行對比。其中，本文算法與遺傳算法生成測試序列的平均總成本相同，但在平均運算時間(圖7(a))及迭代次數(圖7(b))方面，由于本文算法引入了插入優(yōu)化，有效提高了運算效率。當R集中元素數量為443時，平均運算時間和平均迭代次數分別降低了58.0%和74.3%。

圖7 對比分析折線

4 結語

為解決測試案例之間帶有順序關系和組合關系的測試序列生成問題，抽象出一種新的弧路徑問題——關聯弧路徑問題，并給出一種求解算法。關聯弧路徑問題能夠解決有向圖中弧之間存在關聯關系的路徑問題，將其應用在列控車載設備的測試序列生成中，生成的測試序列能夠同時覆蓋測試案例集、順序關系集和組合關系集。測試序列的總成本與人工+DCPP方法相比有很大程度降低。此外，通過實驗驗證了本文算法在求解性能上的優(yōu)勢。