基于蟻群算法的STP系統(tǒng)測試序列優(yōu)化生成

唐匯東，楊華昌，王浩然，任宛星

(1.中國鐵道科學研究院集團有限公司 通信信號研究所，北京 100081；2.北京華鐵信息技術(shù)有限公司，北京 100081)

0 引 言

無線調(diào)車機車信號和監(jiān)控系統(tǒng)(shunting train protection system，STP)是保證鐵路調(diào)車作業(yè)安全的關(guān)鍵設(shè)備，當前已經(jīng)在全路范圍內(nèi)推廣使用。在STP系統(tǒng)投入運營前必須進行嚴格的測試與驗證，以確保系統(tǒng)的安全性與可靠性，而測試案例和測試序列是執(zhí)行功能驗證的基礎(chǔ)，故有必要研究測試序列的優(yōu)化生成方法，以便將測試案例組合成為最有效和最優(yōu)化的測試序列，從而節(jié)約測試時間，提高測試效率。

近些年來，針對鐵路信號系統(tǒng)測試序列的優(yōu)化生成問題，學者們展開了一系列研究工作[1-6]，并提出了一些用于優(yōu)化生成測試序列的算法，如改進Hungray算法[2]、深度學習與遺傳算法[3,4]、動態(tài)規(guī)劃算法[6]等。但還存在一些問題需要進一步研究：①在生成測試序列時未考慮被測功能的優(yōu)先級，而實際測試時往往需要對系統(tǒng)關(guān)鍵功能優(yōu)先執(zhí)行測試；②生成測試序列時以極小化測試序列中包含的測試案例個數(shù)為優(yōu)化目標，而實際測試時由于各個測試案例的執(zhí)行時間長短不一，故測試序列中案例個數(shù)極小化往往并不等價于測試效率極大化。本文在前人研究的基礎(chǔ)上，進一步考慮被測功能的優(yōu)先級，并以最小化測試時間為優(yōu)化目標，提出將STP系統(tǒng)測試序列的優(yōu)化生成問題轉(zhuǎn)換為求解有向圖上的分層中國郵遞員問題，并給出基于改進蟻群算法的測試序列優(yōu)化生成方法。仿真結(jié)果表明，該方法可在不影響測試完備性的前提下大幅度節(jié)約測試時間，提高測試效率。

1 問題描述

1.1 STP測試需求

STP系統(tǒng)是基于計算機的控制系統(tǒng)，由地面設(shè)備和車載設(shè)備組成，其通過無線通信的方式將調(diào)車相關(guān)的信號、道岔、軌道電路區(qū)段等信息傳送到調(diào)車機上，實現(xiàn)調(diào)車信號、調(diào)車進路在機車上的實時顯示，并基于目標距離模式實現(xiàn)對車列的安全防護[7]。

鐵路行業(yè)標準《無線調(diào)車機車信號和監(jiān)控系統(tǒng)技術(shù)條件》[7]描述了STP系統(tǒng)應(yīng)具有的各項功能和對應(yīng)的技術(shù)指標，對STP設(shè)備執(zhí)行測試，就是要檢測STP設(shè)備的功能實現(xiàn)是否符合該技術(shù)條件。

1.2 測試案例

可將STP設(shè)備的運行過程看作是由一系列狀態(tài)以及狀態(tài)之間的轉(zhuǎn)換構(gòu)成，這可以通過測試案例來刻畫。一個測試案例描述被測設(shè)備從某個狀態(tài)到另外一個狀態(tài)的轉(zhuǎn)換，其包括3個基本要素：起始狀態(tài)、相關(guān)輸入/期望輸出、結(jié)束狀態(tài)，如圖1所示。一個測試案例是某個系統(tǒng)功能的部分體現(xiàn)，通過執(zhí)行測試案例，比較被測設(shè)備實際輸出與測試案例期望輸出的一致性，可實現(xiàn)對被測設(shè)備的功能驗證。

圖1 測試案例要素組成

在實際的測試過程中，由于測試案例數(shù)目通常非常龐大，而測試時間和測試資源卻非常有限，在執(zhí)行測試時，應(yīng)優(yōu)先測試與系統(tǒng)關(guān)鍵功能密切相關(guān)的測試案例，然后再測試與輔助功能相關(guān)的測試案例，以便盡早地發(fā)現(xiàn)系統(tǒng)中潛在的關(guān)鍵功能缺陷，從而及時反饋給開發(fā)人員或數(shù)據(jù)制作人員進行修改。所以每個測試案例有一個對應(yīng)的測試優(yōu)先級，該值越高，則測試時應(yīng)優(yōu)先安排測試。

1.3 測試序列優(yōu)化生成

在執(zhí)行某個測試案例之前，需要先執(zhí)行某些系統(tǒng)功能，以便將被測設(shè)備的狀態(tài)轉(zhuǎn)換到該測試案例的起始狀態(tài)，而這些系統(tǒng)功能又包含在其它測試案例之中，由此可以看出：直接執(zhí)行單個測試案例來驗證系統(tǒng)需求是不可取的[1]，這將導(dǎo)致大量測試案例被重復(fù)執(zhí)行，嚴重影響測試效率。應(yīng)將多個相關(guān)聯(lián)的測試案例按照一定規(guī)則串接起來一同測試，從而使得序列中前面的測試案例可為后面的測試案例創(chuàng)造執(zhí)行條件，這樣可減少測試案例重復(fù)，提高測試效率。如圖2所示，將多個測試案例按照一定規(guī)則串接到一起，就構(gòu)成了測試序列。

圖2 由測試案例串接形成測試序列

測試序列的構(gòu)建原則：①在測試序列中，后一個測試案例的輸入態(tài)(起始狀態(tài))必須能與前一個測試案例的輸出態(tài)(結(jié)束狀態(tài))相匹配；②為使測試覆蓋所有的測試案例，完整的測試序列應(yīng)能對所有的測試案例執(zhí)行測試；③優(yōu)先級高的測試案例應(yīng)在優(yōu)先級低的測試案例之前執(zhí)行測試；④為提高測試效率，應(yīng)盡量減少整個測試序列的測試時間。

不同的測試案例串接順序?qū)?yīng)著不同的測試序列。當前主要由測試人員憑借自身經(jīng)驗從測試案例庫中挑選案例并串接形成測試序列。當測試案例數(shù)目較多時，這種人工串接形成的測試序列往往包含大量的冗余測試項，從而導(dǎo)致測試效率低下；同時也容易因人為疏忽而造成測試案例遺漏，從而影響功能測試的完備性。故有必要研究測試序列的優(yōu)化生成算法，以便利用計算機基于測試案例集自動生成最有效和最優(yōu)化的測試序列。

測試序列優(yōu)化生成的目標是：在滿足上述測試序列構(gòu)建原則的前提下，通過合理安排測試案例，使得整個測試序列的總測試時間最少。

2 模型構(gòu)建

2.1 模型假設(shè)

本文所建模型基于以下假設(shè)：①測試成本只考慮時間成本；②優(yōu)化生成測試序列時，不考慮測試案例執(zhí)行失敗的情形；③當測試案例作為測試項時，其執(zhí)行所需時間是固定的；④當測試案例作為系統(tǒng)狀態(tài)轉(zhuǎn)換項時，其執(zhí)行所需時間也是固定的。

2.2 變量定義

A={a1,a2,…,aN}——測試案例集合；

S={s1,s2,…,sM}——生成的測試序列；

p(ai)——測試案例ai的測試優(yōu)先級；

xij——0-1決策變量，xij=1時，表示sj=ai；xij=0時，表示sj≠ai；

rj——0-1決策變量，rj=1時，表示在測試序列S中sj為測試項；rj=0時，表示在測試序列S中sj為狀態(tài)轉(zhuǎn)換項；

t1(ai)——測試案例ai作為測試項時，其執(zhí)行所需時間；

t2(ai)——測試案例ai作為狀態(tài)轉(zhuǎn)換項時，其執(zhí)行所需時間；

2.3 測試序列優(yōu)化生成問題的數(shù)學模型

測試序列優(yōu)化生成問題的數(shù)學模型可以表達為：基于N個測試案例構(gòu)成的無序集合A={a1,a2,…,aN}，構(gòu)建一個由測試案例組成的序列S={s1,s2,…,sM}，使得在符合約束條件下目標函數(shù)最小化

(1)

(2)

(3)

(4)

p(sj)≥p(sk),ifrj=1,rk=1,j

?j,k∈[1,M]

(5)

式(1)為目標函數(shù)，表示最小化測試時間；式(2)表示測試完備性約束，即測試序列S需能對所有的測試案例執(zhí)行測試；式(3)表示測試序列S中的所有測試案例均來自測試案例集合A；式(4)表示測試序列S中的任意兩個相鄰測試案例sj和sj+1需滿足狀態(tài)一致性；式(5)表示測試優(yōu)先級約束，即優(yōu)先級高的測試案例應(yīng)在優(yōu)先級低的測試案例之前安排測試。

3 算法設(shè)計

對于測試案例集合，不妨以各個測試案例狀態(tài)為頂點，以測試案例為弧，構(gòu)建帶權(quán)的、具有多重弧的有向圖G=(V，A)，如圖3所示。圖G中每條弧具有權(quán)值和優(yōu)先級，其中權(quán)值為對應(yīng)測試案例的執(zhí)行所需時間，優(yōu)先級值為對應(yīng)測試案例的測試優(yōu)先級。則測試序列S={s1,s2,…,sM}等價于圖G中的一條路徑L，且S中的測試案例sj對應(yīng)于路徑L中的一條弧。對測試案例sj執(zhí)行測試，可視為對路徑L中的對應(yīng)弧執(zhí)行服務(wù)。在測試序列S中，如果sj為測試項，則對應(yīng)弧在路徑L中稱為服務(wù)邊，其服務(wù)費用為t1(sj)；反之如果sj僅作為狀態(tài)轉(zhuǎn)換項，則對應(yīng)弧在路徑L中稱為走行邊，其通過費用為t2(sj)。

圖3 以測試案例為弧構(gòu)建有向圖G

設(shè)測試案例集共有K個測試優(yōu)先級，令弧集合A=A1∪A2∪…∪AK，其中Ai表示優(yōu)先級為i的弧集。為保證按測試優(yōu)先級順序構(gòu)建測試序列，針對測試優(yōu)先級p

經(jīng)過上述變換之后，測試序列的優(yōu)化生成問題等價于：在上述有向圖G中，尋求一條可對圖G中的所有弧按優(yōu)先級順序執(zhí)行服務(wù)的路徑L，且路徑的總費用最小。此問題即為有向圖上的分層中國郵遞員問題(hierarchical chinese postman problem，HCPP)。1992年Gélinas證明[8]：有向圖上的分層中國郵遞員問題是NP-hard問題。當圖的節(jié)點規(guī)模較小時，該問題可以使用窮舉法或傳統(tǒng)的經(jīng)典法求解，但當節(jié)點規(guī)模增大時其計算量將呈現(xiàn)爆炸式增長?？紤]到STP系統(tǒng)的邏輯復(fù)雜性，上述有向圖G將非常龐大，此時只能利用啟發(fā)式搜索算法來尋求較優(yōu)解或滿意解。

3.1 轉(zhuǎn)化為類似旅行商問題

當使用蟻群算法優(yōu)化生成測試序列時，由于其中的某些測試案例可能需要重復(fù)出現(xiàn)多次，這將導(dǎo)致螞蟻搜索過程中的禁忌表無法建立，本文通過構(gòu)建圖G′來避免此問題。具體方法如下：

圖4 由圖G生成圖G′示例

由于STP系統(tǒng)的所有測試案例狀態(tài)均可從未上電狀態(tài)轉(zhuǎn)換得到，也均可回到未上電狀態(tài)，故各個測試案例狀態(tài)之間均可達，所以有向圖G′中任意兩個頂點之間必然存在雙向的有向弧，即有向圖G′是全連通圖。

在圖G′中將路徑的費用定義為：途經(jīng)的各條弧及各頂點的權(quán)值之和。于是測試序列優(yōu)化生成問題再次等價于：在圖G′中尋求一條路徑L′，使該路徑可按頂點優(yōu)先級順序經(jīng)過有向圖中各個頂點至少一次，且路徑的總費用最小。此為一個類似旅行商問題。

3.2 計算測試案例狀態(tài)轉(zhuǎn)換最短路徑

為計算3.1中有向圖G′每兩個頂點(v′i和v′j)之間有向弧(i，j)的權(quán)值，需計算圖G中從測試案例ai的結(jié)束狀態(tài)轉(zhuǎn)換為測試案例aj的起始狀態(tài)所需的最短路徑?？墒褂肍loyd最短路徑算法[9]求取圖G中任意兩個頂點之間的最短路徑。此最短路徑體現(xiàn)的物理意義為：在考慮測試時間成本的前提下，為實現(xiàn)指定的測試案例狀態(tài)轉(zhuǎn)換，應(yīng)依次執(zhí)行哪些測試案例。

3.3 使用改進蟻群算法優(yōu)化測試序列

在3.1中已將測試序列優(yōu)化生成問題轉(zhuǎn)化為一個類似旅行商問題，該問題可通過蟻群算法來尋求一個較優(yōu)解。蟻群算法是一種用來在圖中尋找優(yōu)化路徑的機率型算法。該算法具有分布式計算、正反饋等優(yōu)點，但也存在收斂速度慢、容易陷入局部最優(yōu)解等缺點[10-12]，對此，本文通過動態(tài)調(diào)整信息素揮發(fā)系數(shù)并引入鄰域搜索機制，以期增強算法的全局搜索能力，加快算法收斂速度。

3.3.1 螞蟻狀態(tài)轉(zhuǎn)移策略

設(shè)測試案例集共有K個測試優(yōu)先級，令上述有向圖G′中頂點集V′=V′1∪V′2∪…∪V′K，其中V′i表示優(yōu)先級值為i的頂點集。為保證按優(yōu)先級順序生成測試序列，螞蟻總是先遍歷V′K中的頂點，之后再遍歷V′K-1中的頂點，依此類推。

設(shè)蟻群共包含m只螞蟻，在圖G′中螞蟻k(k=1，2,…,m)依據(jù)弧上的信息素濃度以概率的方式選擇步進方向，采用禁忌表tabuk來記錄其已經(jīng)走過的頂點，并使用levelk記錄當前的頂點優(yōu)先級。在t時刻，螞蟻k從頂點i向頂點j移動的概率為

(6)

當螞蟻k遍歷完當前優(yōu)先級的頂點集，此時allowk為空，若levelk>1，則令levelk←levelk-1，并開始遍歷下一個優(yōu)先級頂點集；否則，螞蟻k此輪路徑搜索完畢。

3.3.2 信息素更新策略

在一輪搜索之后，對圖G′中弧(i，j)上的信息素按如下方式進行調(diào)整

(7)

(8)

信息素揮發(fā)系數(shù)ρ影響算法的收斂速度和全局搜索能力，其值過大，則搜索過程接近于隨機搜索，算法收斂速度慢；相反，其值過小，則全局搜索能力偏弱，易陷入局部最優(yōu)解?；鞠伻核惴ú捎霉潭ǖ膿]發(fā)系數(shù)ρ，存在難于平衡收斂速度與全局搜索能力的問題，為此，本文對揮發(fā)系數(shù)ρ引入動態(tài)調(diào)整策略：在算法早期，使用較大的揮發(fā)系數(shù)，以獲得較強的全局搜索能力；在算法后期，使用較小的揮發(fā)系數(shù)，以加快收斂速度。具體調(diào)整方式為

ρ(t)=ρmin+λt(ρmax-ρmin)

(9)

式中：ρmax和ρmin為預(yù)先定義的常數(shù)，分別表示允許的揮發(fā)系數(shù)最大值和最小值；λ為(0,1)范圍內(nèi)的常數(shù)，表示揮發(fā)系數(shù)的變化率。

3.3.3 2-OPT鄰域搜索

從式(6)可知路徑上的信息素濃度越高則后續(xù)螞蟻選擇該路徑的概率越大，但是當某條路徑上的信息素濃度過高時，大量的螞蟻在此路徑上聚集，導(dǎo)致不能及時進行進一步的路徑搜索，從而影響全局搜索速度，甚至陷入局部最優(yōu)解。為了改善此種情況，在蟻群完成一輪路徑搜索后，對該輪迭代得到的最優(yōu)解引入2-OPT鄰域搜索機制[13]：

設(shè)該輪迭代得到的最優(yōu)路徑為L′min，隨機選取一個測試優(yōu)先級值q(q∈[1,K])，然后以遍歷的方式交換路徑L′min中屬于優(yōu)先級q的任意兩個頂點的位置，每次交換后得到一個新的路徑，如果發(fā)現(xiàn)新路徑長度更短，則使用新路徑替換原L′min。

上述2-OPT鄰域搜索機制對于蟻群算法而言實際是引入了一種“突變”機制，使得算法搜索過程可及時從局部極值點中跳出。

3.3.4 算法步驟

步驟1 參數(shù)初始化，設(shè)置蟻群規(guī)模m、信息素揮發(fā)系數(shù)ρmax和ρmin、信息素揮發(fā)系數(shù)變化率λ、信息素相對重要程度α、能見度相對重要程度β、最大迭代次數(shù)itermax，并置初始迭代次數(shù)iter=1，令有向圖G′中每條弧上初始的信息素τij(t)=const；

步驟2 將m只螞蟻隨機放置到圖G′中最高優(yōu)先級頂點集V′K的各個頂點上。然后對每只螞蟻按照3.3.1狀態(tài)轉(zhuǎn)移策略確定下一個要前往的頂點，并移動螞蟻到該頂點中，重復(fù)該過程直到m只螞蟻都訪問完圖G′中的所有頂點；

步驟3 針對每只螞蟻計算路徑長度，并挑出當前迭代次數(shù)下的最短路徑L′min；

步驟4 針對L′min，按3.3.3執(zhí)行鄰域搜索；

步驟5 依據(jù)式(7)～式(9)更新圖G′中各條弧上的信息素；

步驟6 若iter

3.4 測試序列合成

通過3.3可以得到圖G′中按照優(yōu)先級順序經(jīng)過各個頂點且總費用最小的路徑L′，設(shè)路徑L′中的各個頂點(即測試案例)依次為(a1,a2,…,an)。針對L′中相鄰的兩個測試案例ai和ai+1(i∈[1,n-1])，設(shè)測試案例ai的結(jié)束狀態(tài)為vi，測試案例ai+1的起始狀態(tài)為vj。在執(zhí)行完測試案例ai之后系統(tǒng)處于狀態(tài)vi，為了能執(zhí)行測試案例ai+1，需要將系統(tǒng)狀態(tài)從vi轉(zhuǎn)換為vj。而在3.2中，我們已經(jīng)求得此狀態(tài)轉(zhuǎn)換需要依次執(zhí)行哪些測試案例(b1b2…bm)，將這些測試案例插入到上述L′的ai與ai+1之間(圖5)，即可得到最終的、優(yōu)化后的測試序列。

圖5 合成測試序列

4 仿真實驗

為驗證文中算法的有效性，針對包含150個測試案例的STP系統(tǒng)測試案例子集，由測試人員依據(jù)經(jīng)驗劃分為5個測試優(yōu)先級，并基于以往測試過程統(tǒng)計出各個測試案例的執(zhí)行所需時間，然后在Matlab2015a環(huán)境中使用文中的算法優(yōu)化生成測試序列。實驗時使用的參數(shù)見表1。

表1 參數(shù)設(shè)置

為驗證算法性能，分別使用隨機算法、基本蟻群算法和改進蟻群算法生成測試序列，各實驗20次，統(tǒng)計生成的測試序列的總測試時間，實驗結(jié)果如圖6所示。針對各算法，分別統(tǒng)計實驗的最優(yōu)結(jié)果和平均最優(yōu)結(jié)果，并計算標準差，結(jié)果見表2。從實驗結(jié)果可以看出：①相較隨機算法而言，基本蟻群算法和改進蟻群算法均大幅度縮減了測試序列的總測試時間，從各次實驗的平均最優(yōu)結(jié)果來看可分別節(jié)省58%和60%的測試時間，均呈現(xiàn)出良好的優(yōu)化效果；②改進蟻群算法的各次實驗最優(yōu)結(jié)果(947 min)和平均最優(yōu)結(jié)果(976.6 min)均優(yōu)于基本蟻群算法(958 min和1034.7 min)，即改進蟻群算法呈現(xiàn)出更好的全局搜索能力；③相較隨機算法和基本蟻群算法而言，改進蟻群算法的各次實驗結(jié)果標準差更小，即各次實驗的結(jié)果一致性更好，算法整體表現(xiàn)更平穩(wěn)。

圖6 各次實驗結(jié)果

表2 算法對比

圖7展示了基本蟻群算法和改進蟻群算法的迭代對比情況。可以看出，基本蟻群算法在63次迭代后收斂到最終結(jié)果；而改進后的蟻群算法在38次迭代后即收斂到最終結(jié)果，且計算得到的最終結(jié)果要優(yōu)于基本蟻群算法?？梢娢闹行畔⑺負]發(fā)系數(shù)動態(tài)調(diào)整策略和2-OPT鄰域搜索機制的引入，有效增強了算法的全局搜索能力，并且加快了算法的收斂速度。

5 結(jié)束語

針對當前STP系統(tǒng)測試序列主要由測試人員憑借經(jīng)驗人工生成的現(xiàn)狀，本文研究了測試序列的優(yōu)化生成方法。在考慮被測功能優(yōu)先級的前提下，設(shè)計了以最小化測試時間為目標的優(yōu)化模型，并將其轉(zhuǎn)換為求解有向圖上的分層中國郵遞員問題，此為一個NP-hard問題。提出了一種基于改進蟻群算法的測試序列優(yōu)化生成方法，并且針對基本蟻群算法收斂速度慢、容易陷入局部最優(yōu)解等缺陷，通過動態(tài)調(diào)整信息素揮發(fā)系數(shù)并增加2-OPT鄰域搜索機制，有效增強了算法的全局搜索能力，加快了算法收斂速度。最后通過仿真實驗驗證了算法的有效性。

文中提出的測試序列優(yōu)化生成方法具有一定的普適性，可適用于其它鐵路信號系統(tǒng)的測試序列優(yōu)化生成。但也存在一些不足，比如優(yōu)化生成測試序列時只考慮了測試案例的執(zhí)行所需時間，而未考慮測試案例的操作復(fù)雜度，故未來可繼續(xù)探索測試序列的多目標優(yōu)化生成問題。