列控系統(tǒng)RBC 測(cè)試序列優(yōu)化生成方法

齊凡瑞，李 強(qiáng)，2

（1.蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院，蘭州 730070；2.甘肅省工業(yè)交通自動(dòng)化工程技術(shù)研究中心，蘭州 730070）

無(wú)線閉塞中心（Radio Block Center ，RBC）作為CTCS-3（Chinese Train Control System Level 3）級(jí)列控系統(tǒng)的地面核心設(shè)備之一，是基于故障—安全計(jì)算機(jī)平臺(tái)的信號(hào)處理系統(tǒng)，為了保證RBC 的安全性、可靠性和實(shí)用性，必須在開通前進(jìn)行相關(guān)測(cè)試.目前，RBC 系統(tǒng)測(cè)試周期長(zhǎng)，不穩(wěn)定因素多，且測(cè)試序列的生成都是由專家根據(jù)需求規(guī)范和測(cè)試大綱手動(dòng)編寫，容易出現(xiàn)測(cè)試數(shù)據(jù)遺漏、錯(cuò)誤和重復(fù)等問題，并且測(cè)試項(xiàng)的安全性和可用性也不能保證.近年來(lái)，基于模型的測(cè)試方法成為新一代鐵路系統(tǒng)測(cè)試方法，它能在保證系統(tǒng)安全性的同時(shí)有效提高測(cè)試效率、節(jié)約測(cè)試成本.

在測(cè)試案例的生成方面，文獻(xiàn)［1］提出了一種端口標(biāo)記的時(shí)間輸入輸出自動(dòng)機(jī)LpTIOA，應(yīng)用Cover 工具實(shí)現(xiàn)CTCS-3 級(jí)車載系統(tǒng)LpTIOA 模型的測(cè)試套自動(dòng)生成，解決了CTCS-3 級(jí)列控系統(tǒng)測(cè)試中存在的需要多個(gè)端口協(xié)同測(cè)試的問題，但該方法生成的測(cè)試用例抽象層次高，執(zhí)行測(cè)試案例時(shí)還需對(duì)抽象測(cè)試案例中的數(shù)據(jù)進(jìn)行具象化.文獻(xiàn)［2］提出一種領(lǐng)域無(wú)關(guān)覆蓋準(zhǔn)則的測(cè)試用例生成算法，利用Cover 工具生成模式轉(zhuǎn)換測(cè)試用例套，從而實(shí)現(xiàn)自動(dòng)生成覆蓋全部車載模式轉(zhuǎn)換規(guī)則的測(cè)試用例，但該方法無(wú)法描述系統(tǒng)的并發(fā)行為，且不具有時(shí)序性；在測(cè)試序列的優(yōu)化方面，文獻(xiàn)［3］將列控系統(tǒng)車載設(shè)備測(cè)試序列優(yōu)化生成問題轉(zhuǎn)換為求解一個(gè)具有多重弧有向圖的中國(guó)郵路問題，利用Edmons-Johnson 算法和LINGO 建模工具對(duì)中國(guó)郵路問題進(jìn)行求解，但該方法優(yōu)化過程復(fù)雜，往往需要二次優(yōu)化.文獻(xiàn)［4］將車載設(shè)備模式轉(zhuǎn)換轉(zhuǎn)化為一個(gè)旅行商問題（Traveling Salesman Problem，TSP）問題，提出一種基于SA 優(yōu)化IC 算法的測(cè)試序列優(yōu)化算法，實(shí)現(xiàn)了測(cè)試序列優(yōu)化生成.

本文作者依據(jù)CTCS-3 級(jí)列控系統(tǒng)技術(shù)規(guī)范構(gòu)造功能場(chǎng)景模型［5］，從功能場(chǎng)景模型中提取功能特征［6］，利用CPN 對(duì)RBC 單電臺(tái)切換場(chǎng)景進(jìn)行形式化建模，從生成的模型可得到狀態(tài)空間可達(dá)圖和XML 文件，應(yīng)用路徑搜索算法可以得到初始的測(cè)試案例.采用M-ACO 算法對(duì)測(cè)試序列進(jìn)行優(yōu)化生成，以期為高效完成測(cè)試工作，保障列控系統(tǒng)的安全性提供參考.

1 模型構(gòu)建及驗(yàn)證

1.1 有色Petri 網(wǎng)

有色Petri 網(wǎng)是一種基于Petri 網(wǎng)的高級(jí)網(wǎng)系統(tǒng)，它具有更嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)定義，能夠直觀地描述系統(tǒng)并發(fā)行為，可用于列控系統(tǒng)RBC 系統(tǒng)描述和驗(yàn)證，有色Petri 網(wǎng)的形式化定義如下

1）SSC是測(cè)試案例開始狀態(tài)有限子集、SEC是測(cè)試案例結(jié)束狀態(tài)有限子集；

2）IIC是測(cè)試案例輸入接口有限子集、OOC是測(cè)試案例輸出接口有限子集；

3）IMC是測(cè)試案例輸入消息有限子集、OMC是測(cè)試案例輸出消息有限子集；

注意：SSC，SEC，IIC，OIC，IMC，OMC均不能為空.

定義3 全節(jié)點(diǎn)覆蓋標(biāo)準(zhǔn)：生成的測(cè)試序列執(zhí)行時(shí)保證覆蓋狀態(tài)空間可達(dá)圖中所有節(jié)點(diǎn)至少一次，其中每個(gè)節(jié)點(diǎn)代表一個(gè)測(cè)試案例.

本次建模采用CPN Tools 工具，CPN Tools 工具是一種用于CPN 建模的計(jì)算機(jī)仿真軟件，能夠?qū)ο到y(tǒng)行為進(jìn)行動(dòng)態(tài)仿真，支持可視化的建模方式和層次化的建模方法，適用于構(gòu)建大型復(fù)雜網(wǎng)絡(luò)模型.CPN Tools 還可以對(duì)模型的狀態(tài)特征和性能進(jìn)行分析，檢驗(yàn)?zāi)Ｐ偷恼_性.

1.2 RBC 切換場(chǎng)景建模

由于單套R(shí)BC 處理性能的約束，通常一套R(shí)BC 無(wú)法管理一整條線的所有設(shè)備，所以一般每條線都會(huì)配備多套R(shí)BC.為了保證列車能夠不降速通過RBC 邊界，相鄰的RBC 以接力的方式不間斷地為車載設(shè)備提供行車許可.在RBC 切換過程中，相鄰RBC 范圍內(nèi)的進(jìn)路信息不再由聯(lián)鎖提供，而是由相鄰的RBC 提供.移交RBC 根據(jù)來(lái)自接收RBC 的進(jìn)路授權(quán)信息，采用行車許可生成技術(shù)為車載設(shè)備生成覆蓋接收RBC 管轄范圍的行車許可；接收RBC 根據(jù)來(lái)自移交RBC 的列車信息為車載設(shè)備預(yù)分配進(jìn)路.RBC 移交分為車載兩部GSMR 無(wú)線電臺(tái)都正常和只有一部電臺(tái)正常的兩種情況，本次討論第二種，具體情況如圖1 所示.

圖1 RBC 切換原理示意圖Fig.1 Schematic diagram of RBC switching principle

單電臺(tái)RBC 切換CPN 頂層模型如圖2 所示，該圖主要模擬了移交RBC、車載設(shè)備和接收RBC 之間的信息交互過程，切換過程具體如下：

1）在只有一部車載電臺(tái)正常工作的情況下，列車使用該電臺(tái)與RBC1 通信（“RBC1Normal”）；

2）當(dāng)列車到達(dá)預(yù)告應(yīng)答器時(shí)（“ReachLTA”），車載設(shè)備向RBC1 發(fā)送位置報(bào)告；

3）RBC1 收到位置報(bào)告后，向車載設(shè)備發(fā)送RBC 切換命令（“SendHandoverOrd”）和向RBC2 發(fā)送移交列車參數(shù)信息和進(jìn)路請(qǐng)求信息（“Send-RouteReq”）［9］；

4）RBC2 收到信息后將它控制范圍內(nèi)的進(jìn)路信息 發(fā) 送 給RBC1［10］，注意 當(dāng)RBC2 控 制 范 圍 內(nèi)的 進(jìn)路狀態(tài)改變時(shí)，應(yīng)將更新信息及時(shí)發(fā)送給RBC1（“SendRouteInf”）；

5）列車通過預(yù)告應(yīng)答器后（“PassLTATrain-Normal”），車載設(shè)備向RBC1 發(fā)送位置報(bào)告（“Next-State”），RBC1 收到信息后向車載設(shè)備發(fā)送切換命令（“StartHandover”）；

6）列車收到切換命令后車載設(shè)備開始呼叫RBC2，呼叫成功后與RBC2 建立通信會(huì)話［11］；列車?yán)^續(xù)向前行駛，在到達(dá)切換邊界前車載設(shè)備接收來(lái)自RBC1 和RBC2 的 混 合MA（“ReceiveMixMA”）并發(fā)送位置報(bào)告（“Handover”）；

7）當(dāng)列車最大安全端越過切換邊界后（“MaxsafefrondPassBou”），列車向兩個(gè)RBC 發(fā)送位置報(bào)告，RBC2 收到信息后向RBC1 下發(fā)接管命令，此后車載設(shè)備只接收RBC1 的終止會(huì)話消息，其他消息都不接收（“StopReceiveRBC1Inf”）；

8）當(dāng)列車最小安全端越過切換邊界后（“MinsaferearPassBou”），車載設(shè)備向RBC1 發(fā)送請(qǐng)求中斷連接信息；

9）RBC1 中斷與列車的連接并將其從RBC1 的列車清單中刪除（“StopRBC1Link”）；車載設(shè)備收到RBC1 的中斷安全連接命令后切斷與RBC1 的連接，車載設(shè)備根據(jù)RBC1 先前下達(dá)的切換命令呼叫RBC2，呼叫成功后與RBC2 建立安全連接［12］；

10）RBC2 生成行車許可并發(fā)送給車載設(shè)備（“ReceiveRBC2MA”），監(jiān)控列車運(yùn)行，至此完成RBC 單電臺(tái)情況下的切換（“RBC2Normal”）.

由于在RBC 單電臺(tái)切換過程中，為使列車不減速越過移交邊界，RBC1 提供的行車許可至少在RBC2 管轄范圍延長(zhǎng)一個(gè)40 s 正常行駛距離+完整制動(dòng)距離的長(zhǎng)度，CPN Tools 可以通過設(shè)置“delay函數(shù)”來(lái)模擬該延時(shí)，所以在“ReachLTA”中設(shè)置400 個(gè)時(shí)間單位的延時(shí)來(lái)模擬該時(shí)間.

圖2 RBC 切換CPN 頂層模型Fig.2 RBC switching top-level CPN model

1.3 模型驗(yàn)證

對(duì)RBC 切換模型執(zhí)行ASK-CTL 公式后的驗(yàn)證結(jié)果為“There is no loop terminal！”和“No Deadlock Markings！”，根據(jù)以上信息結(jié)合狀態(tài)空間報(bào)告可知該模型是正確的.在CPN 建模后，可生成該模型的狀態(tài)空間可達(dá)圖，具體如圖3 所示，圖3 已刪除冗余節(jié)點(diǎn)，為最精簡(jiǎn)模型.由于RBC 建模原理主要是從系統(tǒng)具體功能處理以及信息交換的角度去建立的，因此將RBC 所處狀態(tài)看作庫(kù)所，RBC 信息處理過程看作變遷，有向弧看作信息流動(dòng)過程，一條變遷發(fā)生則表明完成某項(xiàng)功能的條件觸發(fā)，根據(jù)變遷的代碼段判斷該動(dòng)作是否發(fā)生，若是，則一條測(cè)試案例生成.在CPN 建模完成后，找到具有輸入信息和輸出信息的庫(kù)所SSC、SEC，其對(duì)應(yīng)的開始狀態(tài)節(jié)點(diǎn)和結(jié)束狀態(tài)節(jié)點(diǎn)IIC、IOC，后應(yīng)用路徑搜索算法找到從開始狀態(tài)節(jié)點(diǎn)到結(jié)束狀態(tài)節(jié)點(diǎn)之間的所有路徑，得到該路徑節(jié)點(diǎn)的特征庫(kù)所信息和特征token 信息PSC*，PEC*，TSC*，TEC*，最后找到以始集庫(kù)所為始端的輸出弧的變量名，以變量名為輸入消息ID，根據(jù)輸入消息ID補(bǔ)充該條消息里的相關(guān)變量及變量值得到IMC，同理得到OMC，隨之生成一條測(cè)試案例，由該方法生成的測(cè)試案例必須滿足定義3 中的的覆蓋度標(biāo)準(zhǔn)，路徑搜索算法的軟件實(shí)現(xiàn)如下.

圖3 RBC 切換狀態(tài)空間可達(dá)圖Fig.3 Reachability graph of RBC switching state space

按照測(cè)試案例的開始狀態(tài)節(jié)點(diǎn)和結(jié)束狀態(tài)節(jié)點(diǎn)的狀態(tài)信息，將各測(cè)試案例串聯(lián)起來(lái)生成初始測(cè)試序列.但是直接串聯(lián)生成的測(cè)試序列冗余度大，造成測(cè)試時(shí)間過長(zhǎng)，進(jìn)而影響測(cè)試安全，因此還需要對(duì)測(cè)試序列進(jìn)行優(yōu)化.

2 測(cè)試序列優(yōu)化算法

傳統(tǒng)蟻群算法（ACO）是一種啟發(fā)式智能搜索算法，它描述的是一種最優(yōu)路徑尋找方法，具體定義見文獻(xiàn)［13］，列控系統(tǒng)測(cè)試序列優(yōu)化生成問題可以轉(zhuǎn)化為一個(gè)旅行商問題（Traveling Salesman Problem，TSP）求解問題，TSP 問題中每一個(gè)城市可以看作是一個(gè)節(jié)點(diǎn)，則t時(shí)刻螞蟻由節(jié)點(diǎn)i向節(jié)點(diǎn)j轉(zhuǎn)移的概率為

式中：α為信息素啟發(fā)因子，表示螞蟻在移動(dòng)過程中路徑上殘留信息素的濃度［14］；β為期望啟發(fā)因子，表示螞蟻選擇路徑的相對(duì)重要程度；allowedk表示螞蟻k在行走時(shí)允許轉(zhuǎn)移的點(diǎn)；τij(t)表示信息素濃度函數(shù)；s為目標(biāo)節(jié)點(diǎn).啟發(fā)函數(shù)表達(dá)式為

式中：dij（i，j=1，2，3，…，n）表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離［15］，螞蟻在各節(jié)點(diǎn)中移動(dòng)時(shí)，用禁忌表來(lái)放置已被選擇過的城市，當(dāng)螞蟻完成一次遍歷節(jié)點(diǎn)搜索后，對(duì)應(yīng)的禁忌表被清空，為下一次探索做準(zhǔn)備.隨著時(shí)間推移，節(jié)點(diǎn)上的信息素會(huì)隨之改變，經(jīng)過ns 后節(jié)點(diǎn)（i，j）上的信息素濃度更新式為

式中：?τij(t)表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的信息素總量；m為迭代次數(shù)；ρ為信息素?fù)]發(fā)因子，其值在0 到1 之間是為了避免路徑上軌跡量無(wú)限增加.令初始τij(0)=c，?τij(0)=0，由于該模型信息素更新為完成一次遍歷后的全局更新，因此節(jié)點(diǎn)信息素模型的更新式為

式中：Q為螞蟻完成一次搜尋后留下的信息素濃度大小之和；Lk表示螞蟻在遍歷完所有節(jié)點(diǎn)后的路徑長(zhǎng)度，傳統(tǒng)蟻群算法作為一種啟發(fā)式優(yōu)化搜索算法，具有很強(qiáng)的穩(wěn)定性和可擴(kuò)展性，由于自身的正反饋原理機(jī)制使得算法能很快地尋找出最優(yōu)解，它的全局搜索、正反饋、魯棒性、分布式計(jì)算等特點(diǎn)體現(xiàn)出了求解復(fù)雜問題的優(yōu)越性，然而它的缺點(diǎn)也很明顯，一是容易陷入局部最優(yōu)，二是易發(fā)生停滯［16］.

為了克服以上兩個(gè)缺點(diǎn)，實(shí)現(xiàn)測(cè)試序列優(yōu)化生成，對(duì)傳統(tǒng)蟻群算法中的信息素?fù)]發(fā)因子ρ和節(jié)點(diǎn)信息素模型?τij進(jìn)行改進(jìn)，ρ的大小在一定程度上反映了所走路徑的信息素含量，ρ值不能設(shè)置的太大或是太小，因?yàn)樵O(shè)置太大雖然能夠加快算法的收斂程度，但會(huì)使得螞蟻還未走過的節(jié)點(diǎn)上信息素?fù)]發(fā)過快；設(shè)置太小易陷入當(dāng)前局部最優(yōu)，使得螞蟻不能尋找更多的點(diǎn)；此外，如果將ρ設(shè)置成一個(gè)固定的值就會(huì)導(dǎo)致該算法搜索度降低.基于以上考量，對(duì)ρ值進(jìn)行更改使其符合高斯分布，這是因?yàn)樵谇捌谖浵佒饕鶕?jù)信息素的含量選擇節(jié)點(diǎn)路徑，這時(shí)將ρ設(shè)置的小一點(diǎn)有助于提高模型的全局搜索能力；中期時(shí)各個(gè)節(jié)點(diǎn)上的信息素含量逐漸變成一個(gè)定值，將ρ設(shè)置的大一點(diǎn)可以增大解空間、提高搜索程度；后期節(jié)點(diǎn)相對(duì)較少，將ρ設(shè)置的小一點(diǎn)以便加快信息素的導(dǎo)向功能.改進(jìn)后的信息素?fù)]發(fā)因子公式如下

式中：μ為迭代完成后螞蟻的搜索期望；σ為一次迭代完成后，遍歷路徑的最優(yōu)路徑與最差路徑信息素的方差.

所有螞蟻在一次迭代完成后將更新節(jié)點(diǎn)上留下的信息素含量，然而螞蟻在走過的各個(gè)節(jié)點(diǎn)上留下的信息素權(quán)重不同，有些節(jié)點(diǎn)權(quán)重占比大.基于此，對(duì)節(jié)點(diǎn)信息素模型引入路段權(quán)重因子vij，從而克服傳統(tǒng)蟻群算法易發(fā)生停滯，加快算法收斂，改進(jìn)后的公式如下

3 測(cè)試序列優(yōu)化生成與合理性驗(yàn)證

3.1 測(cè)試序列優(yōu)化生成

基于M-ACO 的列控系統(tǒng)RBC 測(cè)試序列優(yōu)化生成方法總體框架如圖5 所示，主要包括以下3 部分：

1）根據(jù)《CTCS-3 級(jí)列控系統(tǒng)技術(shù)規(guī)范》提取功能特征，構(gòu)建基于CPN 的單電臺(tái)RBC 切換模型，并采用ASK-CTL 公式對(duì)CPN 建模進(jìn)行驗(yàn)證，得到狀態(tài)空間可達(dá)圖和XML 文件，再應(yīng)用路徑搜索算法生成滿足全節(jié)點(diǎn)覆蓋的測(cè)試案例［17］；

2）測(cè)試案例生成后，根據(jù)測(cè)試案例的開始條件和結(jié)束條件將測(cè)試案例串聯(lián)成測(cè)試序列，采用MACO 生成優(yōu)化后的測(cè)試序列；

3）生成XML 格式的優(yōu)化測(cè)試序列文檔.

根據(jù)1.2 節(jié)中的RBC 的CPN 頂層模型，可以將RBC 切換分為4 個(gè)場(chǎng)景，對(duì)應(yīng)到狀態(tài)空間可達(dá)圖中即得到4 個(gè)變遷場(chǎng)景的輸入、輸出節(jié)點(diǎn)，具體如表1所示，由于節(jié)點(diǎn)1、2、3、4 是4 個(gè)必須經(jīng)過的節(jié)點(diǎn)，所以合并為一個(gè)節(jié)點(diǎn)A，為了滿足全節(jié)點(diǎn)覆蓋，相鄰場(chǎng)景的兩個(gè)節(jié)點(diǎn)之間會(huì)有重疊.在表1 中，由狀態(tài)空間可達(dá)圖可知場(chǎng)景1 有2 條路徑，即場(chǎng)景1 生成了2 個(gè)測(cè)試案例，分別是：/12345/12346/，不同路徑用“//”隔 開，以此 類推，場(chǎng)景2 有4 條路徑，場(chǎng)景3 有3 條 路徑，場(chǎng)景4 有10 條路徑，可以按照測(cè)試案例開始條件與結(jié)束條件直接將測(cè)試案例串聯(lián)成測(cè)試序列，但是這些測(cè)試序列中包含大量冗余測(cè)試案例，造成了測(cè)試效率低下.基于此，在C++平臺(tái)上開發(fā)基于MACO 算法的測(cè)試序列自動(dòng)生成軟件，得到各場(chǎng)景的測(cè)試案例數(shù)如表2 所示，由此可知應(yīng)用M-ACO算法共生成8 條測(cè)試序列，在此基礎(chǔ)上滿足重復(fù)測(cè)試案例數(shù)最少，實(shí)現(xiàn)了測(cè)試序列的優(yōu)化生成.最終利用CPN Tools 自帶的XML 保存功能得到測(cè)試序列XML 文檔，如下

圖5 測(cè)試序列生成方法總體框架Fig.5 Overall framework diagram of test sequence generation method

表1 輸入輸出節(jié)點(diǎn)表Tab.1 Input and output nodes

表2 優(yōu)化路徑表Tab.2 Optimized paths

3.2 對(duì)比分析

本文應(yīng)用M-ACO 算法共生成了8 條測(cè)試序列，涵蓋了《CTCS-3 級(jí)列控系統(tǒng)測(cè)試案例》［18］中與RBC 單電臺(tái)切換的所有測(cè)試案例以及車載設(shè)備測(cè)試案例中與RBC 相關(guān)的測(cè)試案例，《TB/T 3535—2018 無(wú)線閉塞中心測(cè)試規(guī)范》中RBC 單電臺(tái)切換測(cè)試內(nèi)容為單電臺(tái)移交，測(cè)試方法及預(yù)期結(jié)果如下：

車載設(shè)備行車許可延伸至移交邊界；

移交RBC 發(fā)送移交預(yù)告，啟動(dòng)與接收RBC 移交流程；

移交RBC 收到接收RBC 對(duì)移交預(yù)告的應(yīng)答后，發(fā)送授權(quán)相關(guān)信息請(qǐng)求；

接收RBC 根據(jù)授權(quán)相關(guān)信息請(qǐng)求，發(fā)送授權(quán)相關(guān)信息；

移交RBC 根據(jù)進(jìn)路授權(quán)信息向車載設(shè)備發(fā)送信息包【3】（配置參數(shù)），并要求車載設(shè)備確認(rèn)（M_ASK=1）；

車載設(shè)備最大安全前端越過移交邊界；

車載設(shè)備向RBC 發(fā)送消息【ETCS-136】（位置報(bào)告）；

移交RBC 向接收RBC 發(fā)送移交通告；接收RBC 向移交RBC 發(fā)送接管職責(zé)；

車載設(shè)備最小安全末端越過移交邊界；

車載設(shè)備向RBC 發(fā)送消息【ETCS-136】（位置報(bào)告）；

移交RBC 收到位置報(bào)告后，向車載設(shè)備發(fā)送包 含 信 息 包【ETCS-42】（Q_RBC=0）的 消 息【ETCS-24】；

（通信會(huì)話管理），斷開與列車的通信；車載設(shè)備呼叫接收RBC 建立通信連接；

車載設(shè)備獲得接收RBC 內(nèi)的行車許可，以完全監(jiān)控模式運(yùn)行.

測(cè)試目的：RBC 應(yīng)能處理單電臺(tái)車載設(shè)備移交.測(cè)試前提：RBC 狀態(tài)正常并且已被TSRS 初始化，單電臺(tái)已完全監(jiān)控模式在移交RBC 中運(yùn)行.應(yīng)用本文算法生成的測(cè)試序列包含了該規(guī)范中提到的所有步驟，證明了本文算法的正確性.令場(chǎng)景1的測(cè)試案例一/1 2 3 4 6/為a1，測(cè)試案例二/1 2 3 4 5/為a2；場(chǎng)景2 的測(cè)試案例一/8 9 11 13 15/為b1，場(chǎng)景2 的測(cè)試案例二/8 9 11 14 15/為b2，場(chǎng)景2 的測(cè)試案例三/8 10 12 14 15/為b3，場(chǎng)景2 的測(cè)試案例四/8 10 11 13 15/為b4；場(chǎng)景3 的測(cè)試案例一/16 17 20 21 23/為c1；場(chǎng)景4 的測(cè)試案例一/24 27 30 33 34/為d1，生成的測(cè)試序列見表3.

表3 生成的測(cè)試序列Tab.3 Generated test sequence

表4 將本文算法與傳統(tǒng)蟻群算法（ACO）算法和序列優(yōu)選算法（SPS）算法進(jìn)行對(duì)比，由于SPS 算法與啟發(fā)式算法不同，沒有迭代次數(shù)的概念，因此這里只進(jìn)行測(cè)試效果（測(cè)試?yán)寐?、測(cè)試時(shí)間和消耗內(nèi)存）的對(duì)比，結(jié)果顯示基于M-ACO 算法的測(cè)試序列優(yōu)化方法生成的測(cè)試序列總數(shù)和測(cè)試項(xiàng)數(shù)相對(duì)較少，且其測(cè)試?yán)寐剩y(cè)試?yán)寐蕿閷?shí)際用到的測(cè)試項(xiàng)數(shù)占總測(cè)試項(xiàng)數(shù)的百分比）明顯高于其他兩種算法，在較短的時(shí)間內(nèi)生成滿足要求的測(cè)試序列，但消耗的內(nèi)存反而更低，能夠有效提高測(cè)試效率，減少冗余項(xiàng).

表4 不同算法的結(jié)果對(duì)比Tab.4 Comparison of the results of different algorithms

4 結(jié)論

1）提出了一種基于M-ACO 算法的測(cè)試序列優(yōu)化生成方法，首先對(duì)RBC 切換場(chǎng)景進(jìn)行CPN 形式化建模，并采用ASK-CTL 邏輯公式對(duì)模型進(jìn)行驗(yàn)證，之后生成該模型的狀態(tài)空間可達(dá)圖，應(yīng)用路徑搜索算法生成測(cè)試案例，各測(cè)試案例串聯(lián)生成測(cè)試序列.

2）由于列控系統(tǒng)測(cè)試序列優(yōu)化問題可以轉(zhuǎn)換為一個(gè)TSP 問題，可以應(yīng)用M-ACO 算法進(jìn)行求解，直至找出最優(yōu)序列，最終生成XML 格式的測(cè)試序列.

3）本文算法生成的測(cè)試案例與《CTCS-3 級(jí)列控系統(tǒng)測(cè)試案例》中與單電臺(tái)RBC 切換相關(guān)的測(cè)試案例進(jìn)行比較，結(jié)果證明應(yīng)用本算法生成的測(cè)試序列都包含在規(guī)范中，驗(yàn)證了該算法的正確性和完備性，同時(shí)又將該算法和SPS 算法及ACO 算法相比，證明了該算法能夠有效提高測(cè)試效率，簡(jiǎn)化測(cè)試步驟，實(shí)現(xiàn)測(cè)試過程自動(dòng)化.