考慮順序和組合關(guān)系的列控車載設(shè)備測(cè)試序列生成方法

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

(北京全路通信信號(hào)研究設(shè)計(jì)院集團(tuán)有限公司,北京 100070)

引言

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

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

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

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

1 研究基礎(chǔ)

1.1 測(cè)試案例與測(cè)試序列

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

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

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

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

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

1.2 順序關(guān)系與組合關(guān)系

測(cè)試案例是功能需求的體現(xiàn)，在測(cè)試過程中，測(cè)試人員往往會(huì)根據(jù)以往測(cè)試經(jīng)驗(yàn)和功能需求對(duì)部分測(cè)試案例的特定順序或組合進(jìn)行測(cè)試。將這種特定順序和組合分別稱為測(cè)試案例之間的順序關(guān)系和組合關(guān)系。不同于現(xiàn)有研究方法，本文生成的測(cè)試序列不僅需覆蓋測(cè)試案例集，同時(shí)要覆蓋測(cè)試案例之間的順序關(guān)系和組合關(guān)系。

測(cè)試案例之間的順序關(guān)系是指規(guī)定了若干測(cè)試案例的銜接順序，以對(duì)特定功能流程進(jìn)行驗(yàn)證。例如，圖1所示的9條測(cè)試案例(每條弧表示一條測(cè)試案例，弧上的數(shù)字表示測(cè)試案例編號(hào))，從狀態(tài)s1到s4有27種組合方式。如果(1，4，7)的順序是特定的驗(yàn)證流程，則希望測(cè)試序列中能夠包含(1，4，7)的順序。

圖1 測(cè)試案例之間的關(guān)系示意

測(cè)試案例之間的組合關(guān)系是指某個(gè)測(cè)試案例要與其他相鄰接的測(cè)試案例進(jìn)行組合銜接，以提高交錯(cuò)檢測(cè)能力。

定義3(測(cè)試案例的n-維組合) 測(cè)試案例的n-維組合是指以該測(cè)試案例作為起始測(cè)試案例的n條相鄰接測(cè)試案例構(gòu)成序列的集合。

如圖1中，測(cè)試案例2的2-維組合包括(2，4)、(2，5)、(2，6)；測(cè)試案例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 關(guān)聯(lián)弧路徑問題

在以往研究中，將測(cè)試案例集建立為具有多重弧的強(qiáng)連通有向圖D，通過求解D的DCPP生成測(cè)試序列。DCPP是經(jīng)典的弧路徑問題，其定義為給定一個(gè)強(qiáng)連通有向圖D=(V，A)，其中，V為頂點(diǎn)集，A為弧集，且每條弧帶有一個(gè)非負(fù)的成本，目標(biāo)為尋找一條成本最小且經(jīng)過A中每條弧至少一次的回路[18]。在求解DCPP過程中，由于弧之間是相互獨(dú)立的，因此，測(cè)試序列不會(huì)包含特定的順序關(guān)系或組合關(guān)系。

定義4(弧的關(guān)聯(lián)關(guān)系) 弧的關(guān)聯(lián)關(guān)系是D中的一條鏈，用于描述若干條弧之間的銜接關(guān)系，用h表示，由h構(gòu)成的集合為關(guān)聯(lián)關(guān)系集H。

其中，鏈?zhǔn)侵疙旤c(diǎn)與弧交替出現(xiàn)的序列，與弧相鄰的兩個(gè)頂點(diǎn)恰好是弧的兩個(gè)端點(diǎn)[19]。下文中為便于表示，將鏈W表示為弧的序列，第一條弧的起始頂點(diǎn)為W的起點(diǎn)，最后一條弧的終止頂點(diǎn)為W的終點(diǎn)，相鄰前一條弧的終止頂點(diǎn)與后一條弧的起始頂點(diǎn)相同。如鏈W的起點(diǎn)和終點(diǎn)相同，則被稱為閉鏈。

定義5(弧的通過成本和服務(wù)成本) 經(jīng)過弧a的成本為弧a的通過成本，由p(a)表示，其中p(a)≥0；通過弧a并對(duì)其進(jìn)行某種服務(wù)的成本為弧a的服務(wù)成本，由c(a)表示，其中c(a)≥p(a)≥0。

如鏈W中連續(xù)被服務(wù)的弧構(gòu)成的鏈與h相同，則稱W包含h；如W包含H中的所有鏈，則稱W滿足關(guān)聯(lián)關(guān)系集H。其中，規(guī)定弧的關(guān)聯(lián)關(guān)系集H中的元素互相不具有包含關(guān)系。

定義6(關(guān)聯(lián)弧路徑問題(Associated Arc Routing Problem， AARP)) 給定一個(gè)具有關(guān)聯(lián)關(guān)系集的多重弧強(qiáng)連通有向圖D=(V，A，H)，其中，每條弧a∈A帶有一個(gè)非負(fù)的通過成本p(a)和一個(gè)非負(fù)的服務(wù)成本c(a)，目標(biāo)為尋找一條起點(diǎn)為v0∈V，總成本最小，服務(wù)A中每條弧至少一次，且滿足關(guān)聯(lián)關(guān)系集H的閉鏈。

AARP是在有向圖中引入了弧的關(guān)聯(lián)關(guān)系集H，同時(shí)每條弧可作為通過項(xiàng)和服務(wù)項(xiàng)，并伴有相應(yīng)的通過成本和服務(wù)成本。AARP為解決具有關(guān)聯(lián)關(guān)系的弧路徑問題提供了理論模型。

2 關(guān)聯(lián)弧路徑問題的求解算法

AARP求解算法共分為3個(gè)階段。

(1)準(zhǔn)備階段。首先，利用Floyd算法計(jì)算D的最短路徑矩陣L和最短路徑費(fèi)用矩陣B；然后，根據(jù)A和H構(gòu)建被服務(wù)的鏈集R，并計(jì)算鏈間的最小成本矩陣M。

(2)生成階段。利用插入優(yōu)化和遺傳算法相結(jié)合方式將R中的鏈進(jìn)行排列，生成鏈的序列O，使得O中相鄰鏈間的成本之和最小。

(3)轉(zhuǎn)換階段。將序列O中的鏈進(jìn)行拼接，同時(shí)轉(zhuǎn)換為由V和A構(gòu)成的閉鏈W，并根據(jù)v0調(diào)整W的起點(diǎn)。

2.1 準(zhǔn)備階段

準(zhǔn)備階段是為計(jì)算D的最短路徑矩陣L和最短路徑費(fèi)用矩陣B，并構(gòu)建被服務(wù)的鏈集R及其鏈間的最小成本矩陣M，如算法1所示。

算法1 準(zhǔn)備階段算法

算法1中1～7行利用Floyd算法計(jì)算最短路徑費(fèi)用矩陣B和最短路徑矩陣L。其中，Bij為在D中從頂點(diǎn)i到頂點(diǎn)j所需的最小通過成本；Lij為以最小的通過成本從頂點(diǎn)i到頂點(diǎn)j，需先從頂點(diǎn)i到達(dá)頂點(diǎn)Lij。第3行表示當(dāng)頂點(diǎn)i到j(luò)之間存在弧時(shí)，Bij為頂點(diǎn)i到j(luò)之間所有同向弧的最小通過成本；第5行為初始化Lij。

第8行是構(gòu)造被服務(wù)的鏈集R，包括兩部分。第一部分將H中每條鏈加入到R中；第二部分對(duì)任意一條弧a∈A，如其未包含在H的任意一條鏈中，則將a作為一條鏈加入到R中。

第9～13行是計(jì)算R中鏈之間的最小成本矩陣M，是準(zhǔn)備階段的核心部分。其中，Mij為從i所表示的鏈到j(luò)所表示鏈的最小成本。Mij的計(jì)算原理根據(jù)鏈i，j之間是否有重疊部分分為兩種情況。當(dāng)鏈i的尾部與鏈j的頭部之間有重疊部分時(shí)計(jì)算原理如圖2所示。如鏈i串接鏈j，只需在鏈i的末尾增加鏈j未重疊的部分。此時(shí)，Mij為j中未重疊部分弧的服務(wù)成本之和，即notOverlapCost(j)。當(dāng)鏈i的尾部與鏈j的頭部之間無重疊部分時(shí)，計(jì)算原理如圖3所示。此時(shí)，Mij由兩部分構(gòu)成。第一部分為鏈i的終點(diǎn)到鏈j起點(diǎn)的最小通過成本，即Bes。第二部分為鏈j中弧的服務(wù)成本之和cost(j)。其中，規(guī)定兩個(gè)相同鏈間的成本Mii=0。

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

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

2.2 生成階段

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

(1)

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

算法2 生成階段算法

2.2.1 初始化種群

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

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

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

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

(2)

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

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

2.2.2 交叉算子EAX

交叉算子EAX最早是由Nagata和Kobayashi為求解旅行商問題提出，其通過合并兩個(gè)父代解中的弧，同時(shí)添加少量較短的弧來生成子代解。為加強(qiáng)EAX求解ATSP的效果，NAGATA[20]驗(yàn)證了不同策略下的求解效果。文中crossover(pA，pB)利用其中的EAX-1AB策略作為交叉算子。其中，將序列中的鏈作為EAX-1AB中的點(diǎn)集，將最小成本矩陣M作為任意兩點(diǎn)間弧的成本。由于序列的最后一條鏈和序列的第一條鏈也視為相鄰鏈，因此，可將序列pA，pB作為EAX-1AB中尾首相連的回路。EAX-1AB原理示意如圖5所示，共包含如下5步。

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

(1)根據(jù)父代的pA和pB構(gòu)造有向圖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，一個(gè)AB-cycle定義為分別由EA和EB中方向相反的弧交替構(gòu)成的回路。例如，將圖5中(4)所表示的DAB劃分為3個(gè)AB-cycles，分別如圖5中(5)～(7)所示。

(3)隨機(jī)選取不超過u個(gè)AB-cycles，對(duì)于每個(gè)AB-cycle，在pA中移除AB-cycle中屬于EA的弧，同時(shí)增加屬于EB的弧，得到不超過u個(gè)的中間解。例如，將圖5中(5)～(7)所示的AB-cycle分別生成中間解如圖5中(8)～(10)所示。

(4)將每個(gè)中間解的若干部分連接起來，形成一個(gè)完整回路。其中，連接過程選擇將弧數(shù)量最少的部分與其他部分連接，以便尋找到成本最小的連接方式。例如，圖5中(8)～(10)連接后如圖5中(11)～(13)所示。

(5)在若干完整回路中選擇成本最小的一個(gè)作為子代解。

2.2.3 種群更新策略

為保持種群中的多樣性，同時(shí)保證種群中的序列朝著成本更小的方向收斂。如果通過EAX生成的子代p的成本比父代pA的小且相對(duì)于pB來說與pA更相似，則用p替換種群中的pA；如p的成本比父代pB的小且相對(duì)于pA來說與pB更相似，則用子代p替換種群中的pB。其中，similar用于計(jì)算兩個(gè)序列中相同相鄰鏈的個(gè)數(shù)，相同的數(shù)量越多，表示兩條序列更相似。

2.3 轉(zhuǎn)換階段

序列O是被服務(wù)鏈的有序排列，需將其中相鄰且有重疊的部分進(jìn)行拼接，并轉(zhuǎn)換為D的閉鏈，如算法3所示。其中，第1～2行為按順序遍歷O中每對(duì)相鄰的兩條鏈rA，rB；第3行是當(dāng)rA的尾部與rB的頭部之間有重疊部分時(shí)，把rB中未重疊部分與W串接，即Concatenate(W，rA，rB)；第4～8行是當(dāng)rA的尾部與rB的頭部之間無重疊部分時(shí)，先將rA終點(diǎn)e與rB起點(diǎn)s之間的最小費(fèi)用路徑進(jìn)行串接。第6～7行利用L中保存的e、s之間的最短路徑，不斷將路徑中兩個(gè)頂點(diǎn)間通過費(fèi)用最小的弧串接到W；第8行再將rB與W串接；第9行將閉鏈W進(jìn)行循環(huán)移位，使得W中的起點(diǎn)為v0。

算法3 轉(zhuǎn)換階段算法

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

3 實(shí)例驗(yàn)證

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

3.1 建立模型

將所有測(cè)試案例的起始終止?fàn)顟B(tài)集作為有向圖的頂點(diǎn)集；將每條測(cè)試案例作為有向圖的一條弧，弧的起點(diǎn)為測(cè)試案例起始狀態(tài)對(duì)應(yīng)的頂點(diǎn)，弧的終點(diǎn)為測(cè)試案例終止?fàn)顟B(tài)對(duì)應(yīng)的頂點(diǎn)，弧的通過成本為測(cè)試案例的轉(zhuǎn)移成本，弧的服務(wù)成本為測(cè)試案例的測(cè)試成本，弧的編號(hào)為測(cè)試案例的編號(hào)。為展示測(cè)試案例之間的狀態(tài)轉(zhuǎn)移銜接關(guān)系，人工建立的有向圖如圖6所示，每條弧上的三元組分別表示唯一編號(hào)、通過成本和服務(wù)成本。

圖6 模式轉(zhuǎn)換場(chǎng)景的有向圖

根據(jù)測(cè)試需求，制定了一個(gè)順序關(guān)系(0，2，8，9，17，16，6)，該順序關(guān)系的實(shí)際意義為：列車上電(NP到SB)-啟機(jī)過程(SB到PS)-PS模式行車(維持PS)-獲取完整線路數(shù)據(jù)(PS-FS)-FS模式自動(dòng)過分相(維持FS)-線路數(shù)據(jù)耗盡(FS到PS)-停車下電(PS-NP)。同時(shí)，根據(jù)以往測(cè)試經(jīng)驗(yàn)，車載設(shè)備上電的組合情況容易出現(xiàn)異常，對(duì)此構(gòu)造了測(cè)試案例0的2-維組合關(guān)系((0，1)，(0，2)，(0，3)，(0，4)，(0，5))。其中，(0，1)，(0，2)，(0，3)，(0，4)，(0，5)的實(shí)際意義分別為上電再下電，上電啟機(jī)進(jìn)入PS模式，上電啟機(jī)進(jìn)入OS模式，上電啟機(jī)進(jìn)入SH模式，上電啟機(jī)進(jìn)入IS模式。

根據(jù)上述順序關(guān)系和組合關(guān)系組建了4個(gè)弧的關(guān)聯(lián)關(guān)系集如表1所示。其中，4個(gè)關(guān)聯(lián)關(guān)系集分別表示無關(guān)聯(lián)關(guān)系，包含了順序關(guān)系、組合關(guān)系、順序關(guān)系和組合關(guān)系。

表1 模式轉(zhuǎn)換場(chǎng)景的關(guān)聯(lián)關(guān)系集

3.2 方法有效性分析

利用Java實(shí)現(xiàn)了第2節(jié)中的算法，并在電腦內(nèi)存為8G，CPU為i5-6200U、2.30GHz的環(huán)境下，對(duì)圖6的有向圖與表1中的4個(gè)關(guān)聯(lián)關(guān)系集分別進(jìn)行運(yùn)算。其中，算法中涉及的參數(shù)取值如表2所示；生成的測(cè)試序列如表3所示。表3中測(cè)試序列中帶“( )”的編號(hào)表示該條測(cè)試案例只用于狀態(tài)轉(zhuǎn)換，為非測(cè)試項(xiàng)；加粗部分表示覆蓋的順序關(guān)系和組合關(guān)系。

表2 算法參數(shù)取值

表3 生成的測(cè)試序列

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

分別將關(guān)聯(lián)關(guān)系集2、3、4中的關(guān)聯(lián)關(guān)系人工串接成相應(yīng)的弧添加到有向圖中，再利用DCPP生成包含相應(yīng)順序關(guān)系和組合關(guān)系的測(cè)試序列，將其總成本與本文方法進(jìn)行對(duì)比，如表4所示。

表4 測(cè)試序列總成本對(duì)比分析

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

3.3 方法性能分析

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

圖7 對(duì)比分析折線

4 結(jié)語

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