何濤，王婧

基于夢(mèng)境蟻群算法的車載VOBC測(cè)試案例約減策略研究

何濤1, 2，王婧1

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

測(cè)試案例作為CBTC通用測(cè)試平臺(tái)的基礎(chǔ)，研究其約減策略，構(gòu)建高效完備的測(cè)試案例集更加有助于CBTC系統(tǒng)的測(cè)試。提出夢(mèng)境蟻群算法，在傳統(tǒng)蟻群算法的信息素更新方式中引入做夢(mèng)因子，并將其運(yùn)用在車載VOBC的測(cè)試案例約減中，利用CBTC通用測(cè)試平臺(tái)所用的有關(guān)測(cè)試案例集以matlab作為仿真平臺(tái)對(duì)其進(jìn)行驗(yàn)證，結(jié)果表明夢(mèng)境蟻群算法能有效地減少測(cè)試案例數(shù)量，減少測(cè)試時(shí)間，節(jié)約測(cè)試成本，且減少比例比使用蟻群算法提高了10%。該算法為測(cè)試案例約減研究提供了新的方法，同時(shí)該算法擴(kuò)大了解的搜索空間，能很好改善傳統(tǒng)方法易產(chǎn)生局部最優(yōu)的缺點(diǎn)，而且考慮了需求覆蓋度和測(cè)試代價(jià)兩重因素，使最后所得的測(cè)試案例集易行全面。

CBTC通用測(cè)試平臺(tái)；車載VOBC；夢(mèng)境蟻群算法；測(cè)試案例；約減

目前，城市軌道交通發(fā)展迅速，憑借其載客量大、速度快等優(yōu)點(diǎn)，己經(jīng)成為人們出行的優(yōu)先選 擇[1]。CBTC系統(tǒng)目前已廣泛運(yùn)用于城市軌道交通，它與乘客的生命財(cái)產(chǎn)安全有密切聯(lián)系，在實(shí)際線試驗(yàn)之前必須經(jīng)過嚴(yán)格的仿真測(cè)試，因此，有必要建立 CBTC 通用測(cè)試平臺(tái)[2]。測(cè)試案例是測(cè)試平臺(tái)的指導(dǎo)性文件，處于基礎(chǔ)性地位，高效、完備的測(cè)試案例集可以更加科學(xué)地指導(dǎo)測(cè)試工作，節(jié)約測(cè)試成本[3]。本文以CBTC系統(tǒng)中的關(guān)鍵子系統(tǒng)車載VOBC為例，研究其測(cè)試案例約減算法。針對(duì)測(cè)試案例約減算法，國(guó)外提出了貪心算法、HGS算法、GRE算法和整數(shù)規(guī)劃方法等。華麗等[4]提出貪心算法，即不斷選取滿足測(cè)試需求數(shù)最多的測(cè)試案例，同時(shí)劃去需求集中相應(yīng)的需求，直到測(cè)試需求集為空集為止；Harrold等[5]提出HGS算法，它依賴于測(cè)試案例的重要性來選擇測(cè)試案例；CHEN等[6]提出GRE 算法，即先挑選必不可少的測(cè)試案例再剔除1-1冗余案例，再使用貪心算法直到所有需求都滿足為止。有實(shí)驗(yàn)研究指出，在求解結(jié)果精度方面，以上3種方法各有特點(diǎn)，沒有哪一種更優(yōu)越，且約減后的測(cè)試案例集不一定都是優(yōu)化代表集[7]。Lee等[8]提出整數(shù)規(guī)劃法，但其計(jì)算復(fù)雜程度較高，運(yùn)算開銷呈指數(shù)級(jí)增長(zhǎng)。聶長(zhǎng)海等[9]在利用上述算法精簡(jiǎn)測(cè)試案例集時(shí)考慮測(cè)試需求之間的相互關(guān)系，但是沒有考慮測(cè)試案例與測(cè)試需求之間的覆蓋關(guān) 系。華麗[10]提出建立基于變異因子的蟻群算法的測(cè)試案例約減模型，算法中考慮測(cè)試案例的測(cè)試代價(jià)，有效地減少了測(cè)試案例集的數(shù)量，然而該算法容易產(chǎn)生早熟現(xiàn)象，所得到的結(jié)果質(zhì)量仍需進(jìn)一步提高，收斂速度和信息素多樣性之間存在矛盾。為解決上述問題，本文提出一種夢(mèng)境蟻群算法(Dream Ant Colony System, DACS)來約減車載VOBC的測(cè)試案例集，此方法可以擴(kuò)大原有蟻群算法的搜索空間，有效解決算法早熟問題，實(shí)驗(yàn)結(jié)果表明，DACS能在充分考慮測(cè)試需求與測(cè)試案例之間的覆蓋度的前提下有效減少測(cè)試案例集數(shù)目，并且能大幅度降低測(cè)試代價(jià)，節(jié)約測(cè)試時(shí)間。

1 VOBC功能需求分析

1.1 CBTC通用測(cè)試平臺(tái)介紹

CBTC通用測(cè)試平臺(tái)作為第3方全仿真自動(dòng)化測(cè)試平臺(tái)，可為研發(fā)軌道交通控制系統(tǒng)方面的企業(yè)提供黑盒測(cè)試和檢測(cè)服務(wù)，能帶來良好的經(jīng)濟(jì)效益與社會(huì)效益[2]。其結(jié)構(gòu)如圖1所示，由仿真子系統(tǒng)、適配子系統(tǒng)、DCS系統(tǒng)、測(cè)試子系統(tǒng)以及真實(shí)被測(cè)設(shè)備組成。由圖1可看出測(cè)試案例是整個(gè)測(cè)試平臺(tái)的基礎(chǔ)，因此，研究測(cè)試案例的優(yōu)化方法得到高效完備的測(cè)試案例有重要意義，而要想優(yōu)化測(cè)試案例，前提是清楚系統(tǒng)的功能需求以及其與測(cè)試案例之間的滿足關(guān)系。

圖1 CBTC通用測(cè)試平臺(tái)結(jié)構(gòu)

圖2 車載VOBC功能特征

1.2 VOBC的功能需求分析

車載VOBC是CBTC系統(tǒng)的安全核心子系統(tǒng)之一，是直接實(shí)現(xiàn)列車運(yùn)行控制的關(guān)鍵設(shè)備，處于信息交互和命令傳達(dá)的中樞位置，對(duì)保證城市軌道交通安全起著非常大的作用，故本文以車載VOBC為例分析研究其測(cè)試案例約減策略[3]。

如圖1所示，車載VOBC系統(tǒng)與區(qū)域控制器(ZC)無線通信獲得移動(dòng)授權(quán)，通過應(yīng)答器對(duì)其測(cè)得的位置信息進(jìn)行校正，根據(jù)所獲得的移動(dòng)授權(quán)、列車位置以及從線路數(shù)據(jù)庫(kù)獲得的數(shù)據(jù)控制并防護(hù)列車運(yùn)行?；谖墨I(xiàn)[11?13]總結(jié)其功能特征如圖2所示，每一個(gè)2級(jí)功能還可以被細(xì)化為多個(gè)最小需求，任一最小需求都可被測(cè)試案例集中的某個(gè)測(cè)試案例充分測(cè)試，不存在多個(gè)測(cè)試案例測(cè)試一個(gè)最小需求。本文選取車載VOBC的核心功能超速防護(hù)功能來展示其需求細(xì)分過程。

超速防護(hù)功能是依據(jù)MA，障礙物信息，臨時(shí)限速信息及事先儲(chǔ)存的數(shù)據(jù)綜合計(jì)算得到列車當(dāng)前允許的最大速度，將它與車載測(cè)速模塊實(shí)時(shí)測(cè)得的列車速度相比較以判斷列車是否超速及是否要進(jìn)行緊急制動(dòng)。列車在CM模式下顯示和防護(hù)觸發(fā)速度和推薦速度，在AM和RM模式下只顯示和防護(hù)觸發(fā)速度。依據(jù)不同模式下超速防護(hù)功能的流程對(duì)需求進(jìn)行細(xì)化，分別得到AM模式下12條最小需求，CM模式下14條最小需求，RM模式下10條最小需求，其中AM模式下車載超速防護(hù)功能的最小測(cè)試需求如下：

R_1.6.1 車載ATO設(shè)備正常工作；

R_1.6.2 有效列車位置，顯示緊急制動(dòng)速度；

R_1.6.3 列車位置丟失，輸出緊急制動(dòng)；

R_1.6.4 列車正常運(yùn)行，車載設(shè)備未處于緊急制動(dòng)狀態(tài)；

R_1.6.5 如果列車處于緊急制動(dòng)狀態(tài)，需一直保持直到速度為0；

R_1.6.6 列車可以加速直到超過緊急制動(dòng)觸發(fā)速度；

R_1.6.7 如果列車速度沒有降至0，需一直保持緊急制動(dòng)；

R_1.6.8 列車速度能達(dá)到或超過緊急制動(dòng)觸發(fā)速度；

R_1.6.9 列車速度降至0，列車緊急制動(dòng)緩解；

R_1.6.10列車超過緊急制動(dòng)觸發(fā)速度，輸出緊急制動(dòng)；

R_1.6.11列車緊急制動(dòng)時(shí)，MMI顯示紅色圖標(biāo)，且速度下降；

R_1.6.12如果收到的MA突然回撤，列車速度超越了觸發(fā)速度，輸出緊急制動(dòng)。

下文將針對(duì)AM模式下車載超速防護(hù)功能以及CM模式下退行防護(hù)功能的最小需求，選取CBTC通用測(cè)試平臺(tái)所用的對(duì)應(yīng)測(cè)試案例利用夢(mèng)境蟻群算法進(jìn)行約減研究。CM模式下退行防護(hù)功能的需求分析過程與超速防護(hù)功能類似，本文不再贅述。

2 夢(mèng)境蟻群算法

2.1 蟻群算法

蟻群算法(ACS)是一種模擬螞蟻覓食行為的優(yōu)化算法，1991年由意大利學(xué)者Dorigo M首次提出。ACS的原理是螞蟻在尋找食物的初期會(huì)隨機(jī)選擇路徑同時(shí)釋放濃度與路徑長(zhǎng)度成反比的信息素，之后的螞蟻再選擇路徑時(shí)會(huì)選擇信息素濃度較高的路徑，如此循環(huán)最優(yōu)路徑上的信息素濃度就會(huì)越來越高，最終找到最佳覓食路徑[10]。

信息素更新模式分為蟻周、蟻量和蟻密，其中蟻周模型已被證明優(yōu)于另外2個(gè)，蟻周模型是在一次迭代后更新信息素，信息素與路徑長(zhǎng)度有關(guān)，可讓長(zhǎng)度短的路徑上的信息素濃度增大。信息素更新公式為：

蟻群算法由于其正反饋性能使得蟻群最終找到最優(yōu)解，同時(shí)也因?yàn)槠湫畔⑺馗履芰τ邢?，使它容易陷入局部最?yōu)而過早停滯。針對(duì)這一缺點(diǎn)，本文提出夢(mèng)境蟻群算法。

2.2 夢(mèng)境蟻群算法

有關(guān)研究證明，自然界中的高級(jí)生命遵循白天黑夜的活動(dòng)規(guī)律，白天生理活動(dòng)，夜晚心理活動(dòng)，Hobson等[14]提出了一種2階段模型，并且指出人做夢(mèng)的原因是腦干神經(jīng)釋放信號(hào)刺激大腦皮層區(qū)域，從而激活了人過去的記憶經(jīng)驗(yàn)所致。

夢(mèng)境蟻群算法(DACS)將上述夢(mèng)境理論中的做夢(mèng)因子用于蟻群算法的信息素更新中，用以擴(kuò)大蟻群算法的搜索空間，促進(jìn)其找到最優(yōu)解，避免其早熟產(chǎn)生局部最優(yōu)。假設(shè)螞蟻?zhàn)裱滋旃ぷ鳎雇硭X的活動(dòng)規(guī)律，每次迭代螞蟻在分泌信息素時(shí)分成2個(gè)階段，即白天和黑夜，白天螞蟻正常分泌信息素，夜晚螞蟻受其夢(mèng)境的影響，扭曲其分泌在不同路徑的信息素濃度，而且保證距離越短的路徑受夢(mèng)境扭曲的影響越小，如此使其他路徑的信息素濃度與當(dāng)前最優(yōu)路徑上的差距不大，利于擴(kuò)大搜索空間，有機(jī)會(huì)找到更優(yōu)的解。隨著迭代次數(shù)的不斷增加，受夢(mèng)境的影響也會(huì)逐漸減弱，可以保證算法 收斂。

研究表明由于個(gè)體間存在差異，不同個(gè)體的睡眠周期不同，大約符合高斯分布[15]。故結(jié)合高斯分布和文獻(xiàn)[16]中的夢(mèng)境粒子群算法的做夢(mèng)因子重新定義本文做夢(mèng)因子：

其中：是螞蟻編號(hào)；是螞蟻的數(shù)量；是地點(diǎn)的數(shù)量。計(jì)算公式如下：

夢(mèng)境蟻群算法的流程圖如圖3所示。

圖3 夢(mèng)境蟻群算法流程圖

3 車載VOBC測(cè)試案例約減策略及驗(yàn)證

3.1 車載VOBC測(cè)試案例約減策略

d越小，說明測(cè)試案例所滿足的測(cè)試需求數(shù)越多或其測(cè)試代價(jià)越小，由式(1)所算得的轉(zhuǎn)移概率就越大，螞蟻就會(huì)從測(cè)試案例轉(zhuǎn)移到測(cè)試案例處，如此蟻群便開始在解空間內(nèi)移動(dòng)，螞蟻每到達(dá)一個(gè)測(cè)試案例處就會(huì)將其所滿足的需求從測(cè)試需求集中刪除，直到測(cè)試需求集為空時(shí)，螞蟻在本次迭代中任務(wù)結(jié)束，記錄此次迭代螞蟻所到達(dá)過的測(cè)試案例，且計(jì)算螞蟻所走的路程，當(dāng)所有螞蟻都完成任務(wù)時(shí)，迭代結(jié)束，多次迭代之后找到路程最短的測(cè)試案例集，即完全覆蓋需求且所需測(cè)試代價(jià)最低的測(cè)試案例集′。

表1 測(cè)試案例與測(cè)試需求關(guān)系

表1中需求1，2，3，…，12為AM模式下速度防護(hù)功能的需求R_1.6.1至R_1.6.12，案例1，2，3，…，12為CBTC通用測(cè)試平臺(tái)中與其所對(duì)應(yīng)的測(cè)試案例TC-Sys-13-001至TC-Sys-13-012，“1”表示對(duì)應(yīng)測(cè)試案例滿足相應(yīng)測(cè)試需求。

夢(mèng)境蟻群算法解模型如圖4。

圖4 夢(mèng)境蟻群算法解模型

基于以上介紹，現(xiàn)將夢(mèng)境蟻群算法(DACS)解決車載VOBC速度防護(hù)功能的測(cè)試案例約減的算法步驟描述如下：

1) 初始化VOBC速度防護(hù)功能的需求矩陣、車載VOBC速度防護(hù)功能的測(cè)試案例坐標(biāo)矩陣，需求與測(cè)試案例滿足關(guān)系矩陣以及各參數(shù)包括：迭代次數(shù)，最大迭代次數(shù)NC_max，螞蟻個(gè)數(shù)，協(xié)調(diào)因子和，揮發(fā)系數(shù)，常量，信息素矩陣Tau以及做夢(mèng)參數(shù)；

2) 將只螞蟻隨機(jī)放到不同的測(cè)試案例上準(zhǔn)備出發(fā)；

3) 第只螞蟻由于做夢(mèng)因子影響根據(jù)公式(6)扭曲測(cè)試案例到其他測(cè)試案例之間的路徑上的信息素濃度；

4) 第只螞蟻從測(cè)試案例出發(fā)，計(jì)算螞蟻從測(cè)試案例到其余各測(cè)試案例的轉(zhuǎn)移概率，它將向概率最大的測(cè)試案例移動(dòng)，將它所到達(dá)的測(cè)試案例所滿足的需求從需求矩陣中清零；

5) 若需求矩陣中還有不為0的元素，則返回步驟4)，否則記錄第只螞蟻所經(jīng)過的測(cè)試案例編號(hào)和它所走過的路程，，若不大于，返回步驟3)；

5) 比較所有螞蟻所找到的解，記錄當(dāng)前最優(yōu)解，利用式(7)進(jìn)行信息素更新；

6) 若還沒到達(dá)NC_max，且解還在變化，則+1，=1返回步驟2)，否則輸出最優(yōu)解，程序結(jié)束。

7) 步驟2)和3)屬于夜晚的夢(mèng)境信息素更新過程，而步驟4)到6)屬于白天蟻群正常工作過程。

3.2 DACS算法的驗(yàn)證與結(jié)果分析

在matlab環(huán)境下參考中鐵檢驗(yàn)認(rèn)證中心城軌事業(yè)部開發(fā)的CBTC通用測(cè)試平臺(tái)中有關(guān)AM模式下，速度防護(hù)功能的測(cè)試案例集TC-Sys-13-001至TC-Sys-13-012和CM模式下退行防護(hù)功能的測(cè)試案例集TC-Sys-14-001至TC-Sys-14-013，利用DACS和ACS分別進(jìn)行多次仿真實(shí)驗(yàn)，以驗(yàn)證DACS算法的有效性和可靠性。

圖5 速度防護(hù)ACS算法測(cè)試案例優(yōu)化結(jié)果

圖6 速度防護(hù)DACS算法測(cè)試案例優(yōu)化結(jié)果

圖5~6為AM模式下速度防護(hù)功能的蟻群算法和夢(mèng)境蟻群算法的優(yōu)化結(jié)果。共有原始測(cè)試案例數(shù)12個(gè)，由于有2個(gè)測(cè)試案例4和8坐標(biāo)相同，所以圖中原始測(cè)試案例集個(gè)數(shù)僅顯出11個(gè)測(cè)試案例。由圖5可知，用ACS算法約減后速度防護(hù)功能的測(cè)試案例數(shù)減少了5個(gè)，約減比例為41.7%，所得到的最短距離為66.25，由圖6可知，運(yùn)用DACS算法約減后測(cè)試案例數(shù)減少了6個(gè)，約減比例為50.0%，所得到的最短距離為56.25。

圖7 退行防護(hù)ACS算法測(cè)試案例優(yōu)化結(jié)果

圖7~8為CM模式下退行防護(hù)功能的蟻群算法和夢(mèng)境蟻群算法的優(yōu)化結(jié)果。共有原始測(cè)試案例數(shù)13個(gè)，運(yùn)用ACS算法約減后測(cè)試案例數(shù)減少了8個(gè)，約減比例為61.5%，所得到的最短距離為39.666 7，運(yùn)用DACS算法約減后測(cè)試案例數(shù)減少了9個(gè)，約減比例為69.2%，所得到的最短距離為30.5。

圖8 退行防護(hù)DACS算法測(cè)試案例優(yōu)化結(jié)果

根據(jù)以上分析可以得出蟻群算法和夢(mèng)境蟻群算法均能有效減少測(cè)試案例數(shù)量。雖然對(duì)于不同功能的測(cè)試案例約減的比例不同，但是運(yùn)用夢(mèng)境蟻群算法得到的最短距離均比運(yùn)用蟻群算法得到的最短距離低，且約減比例均提高了10%左右。由此證明使用引入做夢(mèng)因子的DACS算法所得到的結(jié)果質(zhì)量更優(yōu)。

另外本文運(yùn)用DACS算法分別對(duì)2個(gè)功能特征的測(cè)試案例集進(jìn)行5次約減，發(fā)現(xiàn)每組的約減比例和最短距離都基本一致，速度防護(hù)功能約減比例為50%，最短距離為56.25，退行防護(hù)功能的約減比例為69.2%，最短距離為30.5，充分證明DACS算法能保證需求的前提條件下有效縮減測(cè)試案例數(shù)量，且一定程度地反映了其可靠性。

圖9為使用ACS算法和DACS算法約減AM模式下速度防護(hù)功能測(cè)試案例迭代100次每次迭代之后的平均值，可以看出ACS算法每次迭代的平均值大約在132.086上下波動(dòng)，DACS算法每次迭代的平均值大約在135.138上下波動(dòng)，據(jù)此分析可知ACS算法每次迭代的平均值比DACS算法的低的數(shù)量居多，側(cè)面證明由ACS算法所得到的結(jié)果有可能由于過早收斂使得其后面的數(shù)據(jù)都停留在局部最優(yōu)解上，同時(shí)也可以說明DACS算法確實(shí)擴(kuò)大了解的搜索空間。

圖9 2種算法平均距離比較結(jié)果

圖10 2種算法效果對(duì)比圖

圖10為2種算法約減AM模式下速度防護(hù)功能測(cè)試案例最終結(jié)果的效果對(duì)比，可以看到迭代100次由ACS算法得到的結(jié)果從第10次迭代就已經(jīng)收斂了，產(chǎn)生過早停滯現(xiàn)象，而DACS算法從75才開始收斂，且得到的最短路徑比前者低，因此引入做夢(mèng)因子使得信息素更新更為隨機(jī)，一定程度上減少了最優(yōu)路徑上信息素的更新，擴(kuò)大了搜索空間，改善了算法的早熟缺陷。

3.3 DACS算法參數(shù)影響

DACS算法主要是在ACS算法中引入做夢(mèng)因子使ACS算法的搜索空間增大的改進(jìn)ACS算法，因此本節(jié)僅討論有關(guān)做夢(mèng)因子的參數(shù)影響。當(dāng)測(cè)試案例集給定，蟻群編號(hào)給定時(shí)權(quán)重因子和螞蟻編號(hào)c就確定，而′又受蟻群數(shù)量的影響，所以只有蟻群數(shù)量和迭代次數(shù)NC_max會(huì)對(duì)優(yōu)化結(jié)果產(chǎn)生影響，表2為不同參數(shù)取值利用DACS算法約減CM模式下退行防護(hù)功能的測(cè)試案例所得到的結(jié)果對(duì)比。

表2 參數(shù)m和NC_max取不同值所獲最優(yōu)解的比較

表2中括號(hào)中的數(shù)字代表約減后測(cè)試案例集個(gè)數(shù)，如第5行第4列的值為29.8(4)代表迭代120次，蟻群數(shù)量為15時(shí)得到的最短路徑為29.8，約減后的測(cè)試案例集數(shù)量為4。當(dāng)?shù)螖?shù)和蟻群數(shù)量都比較小時(shí)，得到的結(jié)果不是很好，而當(dāng)蟻群數(shù)量m為13，即當(dāng)蟻群數(shù)量等于原始測(cè)試案例集數(shù)量，且迭代次數(shù)為80次時(shí)，利用DACS算法所得到的測(cè)試案例約減集的數(shù)量最小，此時(shí)再增加蟻群數(shù)量和迭代次數(shù)所影響的是最短路徑的大小，即約減后的測(cè)試案例集的測(cè)試代價(jià)。由于考慮算法的時(shí)間性能，建議m取與原始測(cè)試案例集數(shù)量相同，迭代次數(shù)NC_max取[80,100]即可。

4 結(jié)論

1) 介紹CBTC通用測(cè)試平臺(tái)的結(jié)構(gòu)，并且分析了其核心子系統(tǒng)VOBC的功能特征。

2) 改進(jìn)傳統(tǒng)蟻群算法，將做夢(mèng)因子引入其中，提出夢(mèng)境蟻群算法(DACS)，將其運(yùn)用于測(cè)試案例的約減方面，并且利用CBTC通用測(cè)試平臺(tái)中的車載VOBC的速度防護(hù)功能的測(cè)試案例集驗(yàn)證其正確性。結(jié)果表明DACS能很好地約減測(cè)試案例數(shù)量，比傳統(tǒng)方法約減效果更好，特別在數(shù)據(jù)規(guī)模較大時(shí)更顯其優(yōu)勢(shì)，而且同時(shí)考慮測(cè)試代價(jià)和需求覆蓋程度，使得所得到的最優(yōu)測(cè)試案例集既百分百覆蓋需求又沒有執(zhí)行困難的案例。

3) 針對(duì)蟻群算法的不足之處，提出引入做夢(mèng)因子，增加搜索選擇，有助于解決蟻群算法過早停滯問題，避免了局部最優(yōu)。

[1] 劉曉娟, 張雁鵬, 湯自安. 城市軌道交通智能控制系統(tǒng)[M]. 北京: 中國(guó)鐵道出版社, 2008. LIU Xiaojuan, ZHANG Yanpeng, TANG Zian. Urban rail transit intelligent control system[M]. Beijing: China Railway Press, 2008.

[2] 黨佳, 王瑋琦. CBTC系統(tǒng)測(cè)試平臺(tái)進(jìn)入全面調(diào)試階段[J]. 鐵道技術(shù)監(jiān)督, 2018, 46(7): 17. DANG Jia, WANG Weiqi. CBTC system test platform enters the full debugging stage[J]. Railway Quality Control, 2018, 46(7): 17.

[3] 胡巍巍. CBTC車載系統(tǒng)測(cè)試案例設(shè)計(jì)及優(yōu)化方法研究[D]. 北京: 北京交通大學(xué), 2010. HU Weiwei. Research on the method of test cases generation and optimization for CBTC on-board system[D]. Beijing: Beijing Jiaotong University, 2010.

[4] 華麗, 李曉月, 王成勇, 等. 能提高錯(cuò)誤檢測(cè)能力的回歸測(cè)試用例集約簡(jiǎn)[J]. 湖南科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 30(2): 99?103. HUA Li, LI Xiaoyue, WANG Chengyong, et al. Regression test suite reduction on improving fault detection capability[J]. Journal of Hunan University of Science &Technology (Natural Science Edition), 2015, 30(2): 99?103.

[5] Harrold M J, Gupta R, Soffa M L. A methodology for controlling the size of a test suite. ACM Trans[J]. Software Engineering and Methodology, 1993, 2(3): 270?285.

[6] CHEN T Y, Lau M F. On the divide-and-conquer approach towards test suite reduction[J]. Information Science, 2003, 42(1): 17?25.

[7] CHEN T Y, Lau M F. A simulation study on some heuristics for test suite reduction[J]. Information and Software Technology, 1998, 40: 777?787.

[8] Lee J G, Chung C G. An optimal representaive set selection method[J]. Information and Software Technology, 2000, 42(1): 17?25.

[9] 聶長(zhǎng)海, 徐寶文. 一種最小測(cè)試用例集生成方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(12): 1690?1695. NIE Changhai, XU Baowen. A minimal test suite generation method[J]. Chinese Journal of Computers, 2003, 26(12): 1690?1695.

[10] 華麗. 基于蟻群算法的測(cè)試用例集約簡(jiǎn)技術(shù)研究[D].重慶: 西南大學(xué), 2009. HUA Li. The research of test-suite reduction technology based on ant colony algorithm[D]. Chongqing: Southwest University, 2009.

[11] 中交協(xié)10號(hào), 城市軌道交通CBTC信號(hào)系統(tǒng)行業(yè)技術(shù)規(guī)范?需求規(guī)范[S]. China Transportation Association No.10, Technical specification of communication based train control system for urban rail transit requirements specification[S].

[12] CZJS/T 0028—2015, 城市軌道交通CBTC信號(hào)系統(tǒng)-ATP子系統(tǒng)規(guī)范[S]. CZIS/T 0028—2015, Technical specification of communication based train control system for urban rail transit-ATP subsystem specification[S].

[13] Fitzmaurice M. Wayside communications: CBTC data communications subsystems[J]. Vehicular Technology Magazine, IEEE, 2013, 8(3): 73?80.

[14] Hobson J A, Pace-schott E F. The cognitive neuroscience of sleep: Neuronal systems, consciousness and learning[J]. Nature Reviews Neuroscience, 2002, 3(9): 579?693.

[15] ErinJ Wamsley, Matthew Tucker, Jessica D Payne, et al. Dreaming of a learning task is associated with enhanced sleep-dependent memory consolidation[J]. Current Biology, 2010, 20(9): 850?855.

[16] 陳漠. 用于最優(yōu)化問題的改進(jìn)粒子群優(yōu)化算法研究[D].吉林: 吉林大學(xué), 2015. CHEN Mo. Research on improved particle swarm optimization algorithms for optimization problems[D]. Jilin: Jinlin University, 2015.

Research on the reduction strategy of vehicle VOBC test cases based on DACS

HE Tao1, 2, WANG Jing1

(1. School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China;2. Gansu Research Center of Automation Engineering Technology for Industry &Transportation, Lanzhou 730070, China)

As the basis of the CBTC Universal Test Platform, test cases were studied to reduce its reduction strategy. It is important to study reduction strategy of test cases and building efficient and complete test cases is more conductive to the testing of the CBTC system. Dream Ant Colony System (DACS) was proposed in this paper, which introduced the dream factor in the pheromone update method of the traditional ant colony algorithm, applied it to reducing test cases of the Vehicle on-board Controller and verified its effectiveness using the matlab platform and the relevant test case set used by the universal test platform of CBTC. The results show that the dream ant colony algorithm can effectively reduce the number of test cases, reduce test time and save test costs and its reduction ratio is 10% higher than the ant colony algorithm. The algorithm expands the search space of the solution, which can effectively improve the shortcomings called local optimum of the traditional method. Moreover, the algorithm considers the two factors of demand coverage and test cost, so that the final test case set has 100% coverage and is easy to execute.

CBTC universal test platform; VOBC; DACS; test case; reduction

TP206

A

1672 ? 7029(2020)04 ? 0832 ? 09

10.19713/j.cnki.43?1423/u.T20190549

2019?06?20

中國(guó)國(guó)家鐵路集團(tuán)有限公司科技研究開發(fā)計(jì)劃項(xiàng)目(N2019G017)；蘭州市人才創(chuàng)新創(chuàng)業(yè)項(xiàng)目(2019-RC-107)；甘肅省工業(yè)交通自動(dòng)化工程技術(shù)研究中心2019年開放基金項(xiàng)目(GSITA201902)

何濤(1977?)，男，內(nèi)蒙古商都人，教授，從事軌道交通測(cè)試研究；E?mail：34876758@qq.com

(編輯 陽(yáng)麗霞)