基于改進引力搜索算法的高鐵信號系統測試案例生成方法研究

史增樹，李 耀，郭 進，張亞東

當前我國已成為世界上高鐵運營里程最長、運輸密度最高、運營場景最復雜的國家。信號系統是保障高鐵安全、高效運行的核心，是典型的安全關鍵系統。如何高效生成覆蓋全部測試需求的測試案例是高鐵信號系統的重要研究內容［1-2］。

目前，對于高鐵信號系統在測試案例生成方面的研究主要基于模型的測試理論，包含抽象測試案例生成和抽象測試案例實例化為具體測試案例等。如針對列控系統測試，文獻［3-5］ 研究基于UML模型的測試案例生成方法；文獻［6］結合混合通信順序進程和時間自動機模型，研究測試案例自動生成問題；文獻［7-8］將時間自動機理論和變異測試技術相結合，提出列控系統安全功能測試案例生成技術；針對車載設備邏輯復雜的特點，文獻［9-10］提出基于SCADE 模型的測試案例生成方法；文獻［11-12］基于UPPAAL Cover 工具，研究基于自動機模型的測試案例生成技術；文獻［13］提出基于Colored Petri Net 模型的測試案例生成方法。以上研究重點關注抽象測試案例的全面性和重復度。

在抽象測試案例實例化為具體測試案例方面，文獻［14］針對列控系統抽象測試案例實例化的問題，基于確定性有限狀態機模型，提出輸入空間劃分和邏輯覆蓋相結合的抽象測試案例自動實例化方法；文獻［15］以CTCS-3級列控系統等級轉換場景為例，研究基于時間自動機模型的抽象測試案例生成方法，進一步提出基于排列組合的具體測試案例生成流程；文獻［16］從組合測試的角度，基于有限狀態機模型研究信號系統具體測試案例的實例化方法。

高鐵信號系統抽象測試案例實例化時，測試項可能包括多個實例化取值，導致具體測試案例的數量龐大。如何將抽象測試案例實例化為高效的具體測試案例是高鐵信號系統測試中的重要問題，目前的研究尚未深入地對該問題展開探討。為此，本文基于有限狀態機建模方法，引入并改進引力搜索算法，對信號系統抽象測試案例實例化為具體測試案例的過程進行研究，在保證具體測試案例全面性的同時，降低測試案例的數量，對降低高鐵信號系統測試成本具有一定的意義。

1 高鐵信號系統測試案例生成過程

高鐵信號系統測試案例生成過程見圖1。基于模型的測試是高鐵信號系統測試的重要研究方向，主要包括系統需求分析、測試模型建立、抽象測試案例生成、抽象測試案例實例化、測試執行和測試結果分析6 個階段。首先，基于信號系統的需求規格等文件對系統功能進行抽象，建立系統的測試模型；其次，依據測試模型，選取測試覆蓋準則，自動生成抽象測試案例；然后結合行業知識，將抽象測試案例實例化為可執行的具體測試案例；最后，將具體測試案例加載到測試環境中執行測試，觀察、分析測試結果。

圖1 高鐵信號系統測試案例生成過程

在將抽象測試案例實例化為具體測試案例的過程中，抽象測試案例可能包括多個實例化取值，如抽象測試案例“開放允許信號”，實例化的具體測試案例可能為L 碼、LU 碼等。在生成具體測試案例時，需要覆蓋每個實例化取值。在如圖2 所示的有限狀態機（Finite State Machine，FSM）［17-18］測試模型中，s0為初始狀態，sf為終止狀態，g1~g5為轉移；g1~g4有1個實例化取值，g5有2個實例化取值。模型存在3條抽象測試案例p1、p2、p3：

圖2 FSM模型

為覆蓋g5的2 個實例化取值，生成具體測試案例時，可以分配p2中g5取值z5，p3中g5取值z6，即模型通過3 條具體測試案例T1、T2、T3，覆蓋抽象測試案例和所有的實例化取值：

通常，鐵路信號系統抽象測試案例的實例化取值較多。文獻［16］對ZPW-2000軌道電路接收器進行了研究，其抽象測試案例“電壓無效”包括20個實例化取值，“頻率無效”包括24個實例化取值。信號系統測試需要覆蓋所有的抽象測試案例和全部的實例化值；同時，為節省測試資源，應當使測試成本（消耗的資源、時間等）盡量較低，具體要求如下。

1）覆蓋所有抽象測試案例，即每個抽象測試案例至少需要測試1次。

2）覆蓋所有的實例化值，即每一個實例化取值至少被一條具體測試案例覆蓋。

3）總體測試成本較低。信號系統測試繁瑣復雜，將實例化值合理分配到抽象測試案例，能夠有效降低具體測試案例的數量，減少系統的測試成本。

綜上，高鐵信號系統抽象測試案例的實例化過程存在一個典型的優化問題：如何在保證100%覆蓋抽象測試案例和實例化取值的前提下，總體測試成本控制較低，即：

式中：n為測試模型轉移的數量；C(gi)為轉移gi的測試成本；E(gi)為轉移gi實例化取值的數量；K(gi) 為轉移gi實際的執行次數。

2 基于引力搜索算法的測試案例生成方法

結合FSM提出基于引力搜索算法的高鐵信號系統測試案例生成方法［19］，見圖3，具體步驟如下。

圖3 基于改進引力搜索算法的測試案例生成方法

Step 1采用FSM描述高鐵信號系統的測試需求，建立FSM測試模型。

Step 2利用FSM測試案例生成算法自動生成高鐵信號系統的抽象測試案例。

Step 3根據測試需求，提取FSM模型中各個轉移的實例化取值，計算抽象測試案例的測試成本。

Step 4克服算法早熟的缺點，綜合高鐵信號系統抽象測試案例、實例化取值和測試成本3 個因素進行搜索，生成具體化的測試案例。

2.1 引力搜索算法

2009 年，Esmat Rashedi 等學者結合萬有引力定律，提出了一種新型的群體智能優化算法——引力搜索算法（Gravitational Search Algorithm，GSA）。研究發現，該算法具有較強的全局搜索能力，在標準測試函數優化試驗中，尋優精度和收斂速度都明顯優于粒子群優化算法（PSO）和遺傳算法（GA）［20］。

引力搜索算法首先在解空間和速度空間分別對位置和速度進行初始化，然后評價各個個體的目標函數值，確定每個個體的質量和受到的引力，計算加速度，更新速度和位置。

2.1.1計算質量

對N個個體，個體i的質量Mi( )

t定義為式中：fiti(t)為第t次迭代個體i的適應度函數值；best(t)和worst(t)為在第t次迭代時，所有個體中最優的適應度函數值和最差的適應度函數值。

2.1.2計算引力

在第d維上，個體j對個體i的引力定義為

式中：G(t) 為在第t次迭代時的萬有引力常數；Rij(t)為個體i和j之間的歐氏距離，i，j∈{1，2，…，N}，且i≠j，d=1，2，…；ε為防止分母為零的常數；分別為個體i、j在第d維的位置分量。

式中：G0和a為常數，T為最大迭代次數。

在第d維上，個體i所受的合力為

式中：randj為在[0， 1]之間服從均勻分布的隨機變量；kbest為個體質量按降序排在前k個的個體，且k的取值隨迭代次數線性減小，初值為N，終值為1。

2.1.3計算加速度

個體i在第d維的加速度方程為

2.1.4更新速度和位置

式中：u為在[0， 1]之間服從均勻分布的一個隨機變量。

2.2 基于改進引力搜索算法的測試案例生成

對于FSM 測試模型，其包含的轉移集合記為Γ={g1，g2，…，gn}，轉移實例化取值數量記為E={E(g1)，E(g2)，…，E(gn)}，抽象測試案例集記為P，p∈P的測試成本記為C（p）。對于圖2 所示的FSM 模型，Γ={g1，g2，g3，g4，g5}，E(g5)=2，P={p1，p2，p3}，假設g1，g2，g3，g4，g5的測試成本分別為10，30，50，20，20，則C(p1)=60，C(p2)=50，C(p3)=50。

抽象測試案例實例化問題可轉化為計算FSM模型抽象測試案例的執行次數，使其在實例化時能夠全面覆蓋抽象測試案例所有的實例化取值，且測試成本較低。引力搜索算法在測試成本{C(p1)，C(p2)，…，C(pn)}的約束下，根據抽象測試案例包含的各個轉移實例化取值數量，搜索抽象測試案例的執行次數。由于需要對抽象測試案例至少覆蓋1 次，則x(t)下轉移gi的執行次數記為Kx(t)(gi)，則抽象測試案例實例化過程的適應度函數fit(t)為

迭代過程中，所有個體最優適應度函數值best(t)和最差適應度函數值worst(t)定義為

由于傳統的引力搜索算法存在局部收斂，導致早熟的問題［21］，因此需進行改進，引入遺傳算法中應用較好的最優保存策略［22-23］，并加入末位淘汰機制。即：每次算法迭代后，如果某個體優于當前最優個體，則保持該個體的當前位置，淘汰適應度最差的個體，即將適應度最差的個體重新初始化到解空間，將所有個體迭代次數重置為0。

基于改進引力搜索算法的測試案例生成流程見圖4，包括以下階段：

圖4 基于改進引力搜索算法的測試案例生成流程

Step 1隨機初始化所有個體的位置，每個個體的初始速度為零。

Step 2計算每個個體的適應度函數值。

Step 3利用式（2）、（5）、（11）、（12）分別更新M（t）、G（t）、best（t）、worst（t）。

Step 4利用式（6）計算每個個體受到的引力。

Step 5利用式（4）、（6）、（7）計算每個個體的加速度。

Step 6利用式（8）、（9）更新每個個體的速度和位置。

Step 7根據優化規則，更新個體位置和迭代次數。

Step 8重復步驟Step 2~Step 8，直到滿足終止條件。

Step 9輸出當前結果并終止算法。

3 案例分析

以高鐵信號系統中CTCS-2級向CTCS-3級轉換的功能為例，介紹測試案例生成過程。

3.1 等級轉換功能抽象測試案例生成

在CTCS-2級向CTCS-3級轉換前，需要完成的工作包括：車載電臺注冊到GSM-R 網絡、車載設備與RBC 建立通信會話、車載設備從RBC 獲得系統配置參數和行車許可等信息。如果在轉換邊界不具備CTCS-3 級控車條件，列車將繼續按CTCS-2級運行，直至CTCS-3級控車條件具備后，車載設備將自動轉入CTCS-3級工作。轉換過程中，可能出現的異常情況包括：呼叫RBC不成功、取消等級轉換、未同時得到等級轉換命令和MA、轉換時超過CTCS-3級允許速度、未收到等級轉換應答器組消息。

為了在不同運行速度下對等級轉換功能的執行情況進行測試，將轉換過程中的速度等級劃分為高速（大于250 km/h）、正常速度（100~250 km/h）和低速（小于100 km/h）3 種模式，FSM 測試模型及轉移的實例化取值測試見圖5。

圖5 CTCS-2級向CTCS-3級轉換FSM測試模型

圖5中，E（g2）=2，E（g20）=3，E（g21）=3，E（g17）=5，E（g18）=5，E（g16）=7，其余轉移的實例化取值數量均為1。如g17表示列車以正常速度通過執行應答器，正常速度（單位為km/h）的實例化取值范圍包括：（0，100），［100，150），［150，250），［250，300），［300，350］，分別取不同范圍下的速度通過執行應答器進行測試。

對于測試模型，采用文獻［19］提出的測試案例生成方法，生成24條抽象測試案例，見表1。以測試人員準備車載設備上電的時間為測試成本的基礎標準，記為S。每條抽象測試案例的測試成本由測試人員根據工程測試數據，結合測試經驗進行確定。為描述方便，抽象測試案例僅保留FSM 測試模型中的關鍵轉移。以抽象測試案例p6為例，測試內容為：列車以CTCS-2 級運行，檢測到GSM-R 網絡唯一，連接GSM-R 網絡和RBC 成功后，檢測到等級轉換預告應答器，但未同時得到等級轉換命令和MA，保持CTCS-2級工作狀態進入CTCS-3 級區域后，未收到RBC發送的MA 和線路描述信息，轉為CTCS-3 級后，執行冒進防護。

表1 抽象測試案例及測試成本

3.2 等級轉換功能具體測試案例生成

改進的引力搜索算法的個體數設定為50，G為5，迭代次數為200。在第137次迭代后，測試總成本達到最小2 005，共計28 條具體測試案例，測試案例覆蓋的實例化取值信息見表2。由于p1~p6各個轉移的實例化取值唯一，對應的具體測試案例唯一，為節省篇幅，表2未列舉。

表2 等級轉換主要的具體測試案例

由表2可知，抽象測試案例p7、p8、p11、p12分別需要測試2次。如p7，其具體化測試案例分別為T1和T3，實例化取值分別為［150，250）和（0，100）。

為驗證改進引力搜索算法的性能優化效果，圖6 給出了與基于傳統的引力搜索算法測試案例生成方法的比較曲線。在傳統的引力搜索算法中，個體數設定為50，G為5，迭代次數為350。第124次迭代時，測試總成本達到最小2 412；而改進的引力搜索算法獲得的測試總成本更低，克服了引力搜索算法容易出現早熟的問題。

圖6 測試案例生成對比

4 結論

本文提出一種高鐵信號系統測試案例生成方法，重點對抽象測試案例實例化為具體測試案例的關鍵問題展開了研究。從FSM 測試模型生成抽象測試案例，采用改進引力搜索算法對抽象測試案例實例化取值及測試成本進行優化，生成覆蓋全面且測試成本較低的具體測試案例。以信號系統中的等級轉換功能為例進行了案例分析，結果表明該方法能夠滿足信號系統的測試需求。下一步，將繼續對實例化取值之間的組合問題展開研究。