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

(1.中國(guó)鐵道科學(xué)研究院集團(tuán)有限公司 通信信號(hào)研究所，北京 100081；2.北京華鐵信息技術(shù)有限公司，北京 100081)

0 引 言

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

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

1 問(wèn)題描述

1.1 STP測(cè)試需求

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

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

1.2 測(cè)試案例

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

圖1 測(cè)試案例要素組成

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

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

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

圖2 由測(cè)試案例串接形成測(cè)試序列

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

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

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

2 模型構(gòu)建

2.1 模型假設(shè)

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

2.2 變量定義

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

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

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

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

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

t1(ai)——測(cè)試案例ai作為測(cè)試項(xiàng)時(shí)，其執(zhí)行所需時(shí)間；

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

2.3 測(cè)試序列優(yōu)化生成問(wèn)題的數(shù)學(xué)模型

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

(1)

(2)

(3)

(4)

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

?j,k∈[1,M]

(5)

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

3 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(6)

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

3.3.2 信息素更新策略

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

(7)

(8)

信息素?fù)]發(fā)系數(shù)ρ影響算法的收斂速度和全局搜索能力，其值過(guò)大，則搜索過(guò)程接近于隨機(jī)搜索，算法收斂速度慢；相反，其值過(guò)小，則全局搜索能力偏弱，易陷入局部最優(yōu)解?；鞠伻核惴ú捎霉潭ǖ膿]發(fā)系數(shù)ρ，存在難于平衡收斂速度與全局搜索能力的問(wèn)題，為此，本文對(duì)揮發(fā)系數(shù)ρ引入動(dòng)態(tài)調(diào)整策略：在算法早期，使用較大的揮發(fā)系數(shù)，以獲得較強(qiáng)的全局搜索能力；在算法后期，使用較小的揮發(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āng)某條路徑上的信息素濃度過(guò)高時(shí)，大量的螞蟻在此路徑上聚集，導(dǎo)致不能及時(shí)進(jìn)行進(jìn)一步的路徑搜索，從而影響全局搜索速度，甚至陷入局部最優(yōu)解。為了改善此種情況，在蟻群完成一輪路徑搜索后，對(duì)該輪迭代得到的最優(yōu)解引入2-OPT鄰域搜索機(jī)制[13]：

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

上述2-OPT鄰域搜索機(jī)制對(duì)于蟻群算法而言實(shí)際是引入了一種“突變”機(jī)制，使得算法搜索過(guò)程可及時(shí)從局部極值點(diǎn)中跳出。

3.3.4 算法步驟

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

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

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

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

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

步驟6 若iter

3.4 測(cè)試序列合成

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

圖5 合成測(cè)試序列

4 仿真實(shí)驗(yàn)

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

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

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

圖6 各次實(shí)驗(yàn)結(jié)果

表2 算法對(duì)比

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

5 結(jié)束語(yǔ)

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

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