基于離散蝙蝠算法的艦船作戰系統測試性分析

范苗，許一川，謝定君，彭輝

1中國艦船研究設計中心，湖北武漢430064

2武漢大學電氣工程學院，湖北武漢430072

0 引 言

測試性作為裝備的一種設計特性，是構成武器裝備質量特性的重要組成部分。優良的測試性設計可以提高裝備的戰備完好性、任務成功性和安全性，減少維修人力和其他保障資源，降低全壽期費用［1］。測試集優化以及測試序列求解是測試性分析的重要研究內容，其正確性和診斷能力的優劣將直接影響到裝備維修保障的效率。

對艦船作戰系統而言，系統級測試是指針對任務通道的測試，目的是驗證作戰系統的功能與性能是否滿足技術規格書的定義，用以為故障診斷提供信息。目前，艦船作戰系統所應用的測試性分析方案主要源自專家經驗或啟發式函數。隨著艦船武器系統的復雜性和集成性的不斷提高，艦船設備單元的層級和數量也在大量增加，因此難以保證診斷策略的正確性和優化精度。同時，人工手動測試方法耗時長、測試序列重復度高，其相應的測試性分析結果已無法滿足現代艦船系統的維護效率要求。因此，研究適用于艦船作戰系統的高效、準確的測試性分析方案以及實用化的工具與技術手段，已成為海軍艦船裝備能力發展亟待解決的問題。

測試集優化和測試序列求解是測試性分析的關鍵內容，在減少冗余測試、提高故障檢測率和故障隔離率、降低期望測試代價等方面具有重要意義，其正確性和診斷能力的優劣將直接影響裝備維修保障的效率。在測試集優化的相關研究中，有關學者提出了基于蟻群算法［2］、Rollout算法［3］、多目標離散粒子群算法［4］、模擬退火算法［5］的優化方案，其中前2種方法存在優化目標單一、優化精度不高等缺點，后2種方法存在初始搜索空間較為龐大、因適應度函數構造不唯一導致的搜索效率較低等問題。而測試序列優化是NP完全問題（Non-deterministic Polynomial complete problem），即在測試集優化的前提下，尋求測試代價最小的診斷策略［6］。為此，Shakeri等［7］提出了基于信息理論概念和啟發式函數的AO*算法，即通過啟發式評估函數計算各候選測試的優先程度，自頂而下擴展診斷樹節點并同時向上回溯修正。在此基礎上，相關學者提出了改進信息熵算法以及一步前向回溯的Rollout算法［8］等改進方案，其通過縮小待擴展節點范圍、減少回溯次數來降低原有AO*算法的計算復雜度。然而，這些方法仍然存在高效啟發式評價函數的選取問題以及不能保證獲得全局最優解的問題。在智能算法方面，基于混合粒子群算法和蟻群算法［9］的優化方案已被成功用于求解最優診斷策略。由于適應度函數直接由測試序列所對應的測試代價構造，其優化精度較高、算法運行時間較長，故適用于對計算實時性要求不高的測試性分析。

鑒此，本文將首先通過評估艦船作戰系統初始相關性矩陣的隔離能力，確定最小完備測試集所包含的測試數目，構造唯一的適應度函數，從而采用離散蝙蝠算法實現測試集的優化工作；然后，將對優化結果采用離散蝙蝠算法，得到比其他算法平均期望測試代價更小的測試序列，用以為測試性分析方案提供新的思路。

1 艦船作戰系統的測試性建模

艦船作戰系統是通過警戒、跟蹤、目標識別、數據處理、威脅估計以及控制武器實現對敵作戰功能的各要素綜合體［10］。作為艦船的核心，作戰系統集成了大量的先進電子武器裝備［11］，包括雷達系統、作戰指揮系統、武器系統和綜合通信系統等分系統。本文將采用以多信號流圖模型為基礎的測試性建模理論，選取作戰系統中較為典型的故障模式來表述各故障模式之間的關聯并進行測試性的初步分析。1994年，美國康涅狄格大學的Pattipati教授和Somnath教授提出了多信號流圖模型。該方法基于研究對象的結構和功能，以分層有向圖的形式來表示信號流向與各功能單元之間的連接關系，即通過定義信號與組成單元所包含的故障模式、測試點所包含的測試信息，來表示系統組成、故障、信號以及測試點之間相關性的一種模型化表示方法［12］。

多信號流圖模型的主要建模過程［12］如下：

1）熟悉建模對象，明確系統的組成結構，識別和提取模型信息，主要包括系統各組成單元和功能單元的輸入/輸出信號、故障模式、故障率信息和測試信息等。

2）構建多信號流圖模型。首先，根據系統組成建立系統的結構模型（原理圖或概念框圖）；然后，將功能信號添加至系統各組成單元，并根據信號流向確定組成單元的輸入、輸出以及各單元之間的連接關系，從而建立有向圖；最后，添加測試點位置以及測試點所包含的測試信息，并設置模型中各節點的屬性。

3）對模型的測試性能進行初步評估，并結合工程實際對模型進行調整、校驗和修改。

本文利用TesLab軟件提供的測試性建模與分析工具，對系統的測試性水平進行分析和評估，并選取20種典型的故障模式來完成艦船作戰系統的多信號流圖建模。故障模式模型和相關性矩陣分別如圖1和表1所示。表1中，F0為無故障狀態，F1～F20分別為圖1中的20種故障模式，t1～t18為測試性建模過程中初步選定的測試方案。表1中的故障概率數據來源于各二級系統的設計數據以及裝備實際應用的統計數據（本文中數據僅為示例，并非實船數據）。

圖1 艦船作戰系統的故障模式模型圖Fig.1 Illustration model of ship combat system failure mode

表1 故障—測試的依賴關系矩陣Table 1 Dependency matrix of fault-test

2 離散蝙蝠算法

2010年，提出了一種新的元啟發式算法，即蝙蝠算法［13］（Bat Algorithm，BA），其優化機理是模擬自然界微型蝙蝠躲避障礙物并尋找目標的回聲定位原理。針對這種已成功應用于連續域函數優化問題的隨機搜索優化算法，為了對其進行改進以解決組合優化問題，文獻［14-16］以旅行商（TSP）問題為例提出了離散蝙蝠算法（Discrete Bat Algorithm，DBA），仿真結果表明離散蝙蝠算法在尋優能力、偏差率、收斂率、時間耗費等指標上的優勢遠超其他傳統算法。由于測試性分析中的測試序列優化問題僅與旅行商問題的目標函數不同，因此可以采用DBA來完成測試執行順序的優化求解，并可將該方法應用于測試集優化問題。

在離散蝙蝠算法中，每個蝙蝠的位置表示待優化問題的一個可行解。對于種群規模為m的蝙蝠而言，蝙蝠個體i（i=1，2，…，m）發出聲波的頻率f(i)為

式中：fmax，fmin分別為聲波頻率的最大值和最小值；β∈[0，1]，為隨機數。

設蝙蝠個體i在t時刻的速度矩陣和位置向量分別為vt(i)，xt(i)，則蝙蝠個體i在t+1時刻的速度vt+1(i)和位置xt+1(i)為：

式中：x*為t時刻搜索過程中蝙蝠的全局最優位置向量。

式（2）中，向量xt(i)與向量x*的差值定義如下：

設xt(i)=(x1，x2，…，xn)，x*=(x*1，x*2，…，x*n)，其中n為蝙蝠搜索空間的維度；設vd為第i個蝙蝠的位置差，初始化矩陣vd為空集。逐一檢查xt(i)，x*的每個分量，若xn-x*n≠0 ，則將向量 (xn，x*n)作為矩陣vd的第1列，并以此方式逐列疊加。

式（2）中，vt+1(i)的定義如下：

設速度向量vt(i)為n×2的整數矩陣，且矩陣元 素 為 1～n 的 自 然 數 ；設v=vt(i)∪vd，l=round[f(i)·n)]+1，其中round函數表示向下取整。從矩陣v中隨機抽取l行，即可得到蝙蝠個體i在t+1時刻的速度向量vt+1(i)。

式（3）中，xt+1(i)的定義如下：

根據式（2）可知vt+1(i)為l×2的矩陣，設矩陣vt+1(i)中第1列元素為p和q，交換向量xt(i)中第p個元素和第q個元素的位置，如此逐列操作直至vt+1(i)的第l列，即可得到t+1時刻蝙蝠個體i的位置向量xt+1(i)。

在獲取目標的過程中，為了均衡局部搜索和全局搜索，蝙蝠需要調節發射聲波的響度和頻率。設蝙蝠個體i在t時刻發出聲波的響度為At，初始聲波響度為A0，脈沖發射速率為rt，則蝙蝠個體i在t+1時刻的聲波響度At+1和脈沖發射速率rt+1為：

式中：α∈[0，1]，為聲波響度增強系數；r0為初始脈沖發射速率；γ為脈沖發射速率衰減系數，是一個常量。

局部搜索的主要步驟如下：

1）在［0，1］范圍內生成一個隨機數rand1，判斷rand1＞rt是否成立。若成立，則對當前位置施加隨機擾動，得到新解xnew，并計算新解的函數適應值fitness(xnew)，其中fitness為適應度函數。

2）在［0，1］范圍內生成另一個隨機數rand2，判斷rand2＞At和fitness(xnew)＜fitness[xt(i)]是否同時成立。如果成立，則接受新解xnew，同時按照式（4）和式（5）更新At和rt。

3）重復上述步驟不斷更新蝙蝠位置向量，直至達到最大迭代次數并輸出最優解。

3 測試集優化

首先，通過建立系統的多信號流圖模型來得到相關性矩陣；然后，合并模糊組并刪除冗余測試。以構建診斷用測試集為例，測試集優化的目的是找到滿足系統所要求故障隔離率的測試集，并在滿足最大故障隔離率的條件下令測試集中的測試數目最少、測試代價最低，其中所優化的目標按重要性依次為最大故障隔離數、最小測試數目和最低平均測試代價。對于n維蝙蝠搜索空間，初始測試集中的測試數目即為n。本文采用二進制編碼來表示相應測試的選取操作，其中編碼1表示選取相應序號的測試，編碼0表示不選取相應序號的測試。

3.1 最小測試數目

在測試集尋優過程中，為減少離散蝙蝠算法的迭代次數，首先需要確定最優測試集中所包含的測試數量。通過分析系統初始相關性矩陣，可以得到所設計的測試集合能隔離的最大故障數目Imax。理論上，n個測試的最大故障隔離數為2n，當2n＜Imax時，所選擇的測試數目不可能使系統故障隔離率最大，故需添加測試數目再次進行測試性分析。

本文采用鏈長為1的模擬退火方式，按概率接受對測試進行擾動后的故障隔離數目。采用的擾動方式為三變換法，即任選序號U，V，W(U＜V＜W≤n)，將序號U，V及其之間的二進制編碼插入序號W之后。同時，與傳統優化問題中為避免陷入局部最優而進行的局部搜索步驟不同，該算法的最大故障隔離數目已經確定，因此當找到最優解后無需再添加隨機擾動，直接輸出測試數目即可。求解最小測試數目的流程如圖2所示。其中：N為采用信息熵算法求得的最優完備測試集中所包含的測試數目，用以防止算法避開最優解；I1為隨機抽取產生的測試集的故障隔離數目；I2為擾動后所選取測試集的故障隔離數目；e為經測試集優化后所得的最小完備測試集中的測試數目。

圖2 確定最小測試數目的實現流程圖Fig.2 The realization flow chart for determining the minimum number of tests

3.2 基于離散蝙蝠算法的測試集優化

確定最小完備測試集的測試數目之后，需要構造合理的適應度函數并依據重要性來優化故障隔離數目和平均測試代價。本文采用統一的適應度函數以避免使用條件嵌套語句，從而減少程序的運行時間。

式中：cmax為所選的測試代價列向量中n個最大測試代價之和；cmin為所選的測試代價列向量中n個最小測試代價之和；X為使不等式成立的任一正實數。

為了優先考慮所選測試的故障隔離能力，式（6）實際上表示了2種最不理想的情況：一是故障隔離數目和平均測試代價同時達到最大；二是故障隔離數目第2大，平均測試代價最小。當找到合適的X值時，適應度函數可以簡化為

式中：fitness[xt(i)]為適應度函數值；I為所選測試集的故障隔離數目；C為測試代價列向量。

采用離散蝙蝠算法時，由于二進制編碼中蝙蝠位置向量的減法操作與TSP問題有所不同，故需要對第2節中關于蝙蝠位置向量差的操作進行重新定義。設第i個蝙蝠的位置向量為xi=(x1，x2，…，xn)，當前全局最優的蝙蝠位置向量為x*=(x*1，x*2，…，x*n)。定義第 i個蝙蝠位置向量的減法操作為：分別記錄向量xi和x*每個分量中編碼為0的序號集合矩陣xi0和x*0，則第i個蝙蝠的位置向量差為vd=[xi0；x*0]'。同時，在初始解空間中加入確定最小測試數目過程中最終輸出的蝙蝠位置向量，以進一步避免算法陷入局部最優，而其他操作定義、算子設計和算法步驟則與基本離散蝙蝠算法保持一致。

3.3 仿真對比分析

本文將以艦船作戰系統測試性模型為研究對象，對初始測試集進行優化。優化算法中的相關參數為：在確定最小測試數目的算法中，設初始溫度T0=1，降溫速率為0.99，終止溫度為6.6×10-3。在離散蝙蝠算法中，設蝙蝠種群規模m=10，fmin=0，fmax=1，A0=1.6，r0=0.000 1。由于測試集優化問題的復雜度較低，α和γ的取值對優化結果的影響很小，所以根據經驗取α=0.9，γ=0.9，迭代次數Maxgen=100。將基于離散蝙蝠算法的測試集優化結果分別與混合粒子群—遺傳算法（HPSOGA）、改進離散粒子群優化（DPSO）算法、信息熵算法、Rollout算法、蟻群優化（ACO）算法、最大/最小蟻群優化（MMACO）算法和模擬退火算法（SAA）進行比較，對各算法分別運行50次，仿真結果取平均值。其中各算法迭代次數與本文算法保持一致，均為150。

期望測試代價統一采用離散蝙蝠算法，迭代次數為Maxgen'=300。優化過程中的相關統計指標如表2所示。

從仿真結果可知，與其他主流算法相比，本文采用的優化算法在平均故障隔離數、平均測試個數、期望測試代價和最優比例方面均取得了更為理想的結果。其中故障隔離率最多可提高5.5%，平均測試個數、平均測試代價最多可分別下降1.4%和6.35%，達到最優的比例可增至86%。同時，在群智能優化算法中，本文算法的平均收斂時間也較短。仿真結果表明，本文算法可以成功應用于測試集優化問題。

4 測試序列優化

4.1 優化問題描述

在僅考慮發生單一故障的前提下，得到相關性矩陣并對測試集優化后，需要根據可靠性求解測試代價最優的診斷策略。其中，各組成單元的可靠性數據（故障率或故障概率）可從可靠性設計分析資料中獲取，而與測試相關的代價則應考慮測試時間、測試點設計費、研制費用和實施測試所需的費用等。因此，測試序列優化的目標即令隔離系統故障狀態所需的總期望測試費用J最小，其適應度函數為

表2 診斷測試集優化結果比較Table 2 Comparison of test set optimization for fault diagnosis

式中：P為故障概率向量；I為故障隔離矩陣［17］；a為故障模式數量；b為故障模式序號，b=0，為隔離故障模式Fb所需的測試序列pb的長度；j為測試序列pb的測試序號，j=1，2，…，；為pb所對應測試序號j的代價值；p(Fb)為故障模式Fb發生的概率。

在測試性設計工程中，測試序列優化的目的是找到一組合適的測試執行順序，使得期望測試費用最低，用以為裝備維修保障提供支撐。

4.2 算法基本步驟

基于離散蝙蝠算法的測試序列優化的基本步驟如下：

1）設蝙蝠種群的規模為m，隨機生成初始蝙蝠位置集合S，采用反向學習機制求出反向的蝙蝠位置集合S*。根據適應值大小對集合S，S*中的位置進行優劣排序，取適應度函數值前m位的蝙蝠位置作為初始解集。通過將初始解較為均勻地集中在優質解區域中，可以在保證優化精度的同時減少算法運行時間。

2）參數初始化。設置初始脈沖發射頻率r0、初始聲波響度A0、聲波頻率的最大值fmax和最小值fmin、聲波響度增強系數α、脈沖發射速率衰減系數γ、算法迭代次數Maxgen。設隨機生成的第i個蝙蝠速度初始矩陣為v0(i)，其中v0(i)是維度為n×2的矩陣，其元素取值范圍為自然數1～n。

3）按照式（2）和式（3）分別更新每個蝙蝠的速度與位置。

4）在［0，1］范圍內生成一個隨機數rand1，判斷rand1＞rt是否成立。若成立，則對當前位置采用3變換法施加隨機擾動，產生新解xnew，并計算新解對應的函數適應值fitness(xnew)。

5）在［0，1］范圍內生成另一個隨機數rand2，若rand2＞At且適應度函數滿足fitness(xnew)＜fitness[xi]，則接受收步驟 4）中產生的新解xnew，并按式（4）和式（5）更新At和rt。

6）更新當前時刻最優解x*，判斷迭代終止條件是否滿足。若不滿足，則轉至步驟3）；若滿足，則停止迭代計算過程。

7）輸出最優解。

4.3 仿真對比分析

完成測試集優化后，即可采用基于離散蝙蝠算法的優化方案來確定最優測試序列，離散蝙蝠算法的相關參數為：蝙蝠種群規模m=10，fmin=0，fmax=1，A0=1.5，r0=0.000 1，α=0.9，γ=0.99，Maxgen=300。其中參數α和γ的取值由仿真實驗確定，分別在0.9～1的范圍內每隔0.01取值做100組實驗。仿真結果表明，當α=0.9，γ=0.99時，算法運行結果最優。將基于離散蝙蝠算法的優化結果分別與基于信息熵、改進信息熵方案、Rollout算法、HPSO算法、ACO算法、MMA?CO算法進行對比，對各智能算法分別運行50次，其平均期望測試代價、最優期望測試代價、最優測試序列結果、算法平均收斂時間、平均偏差和收斂率指標的對比結果如表3所示。其中，平均偏差為算法的最終運算結果與其最優結果之差的平均值，收斂率為算法運行結果成功收斂至本算法最優期望測試代價的比例。

表3 測試序列優化結果對比Table 3 Comparison of test sequence optimization

由表3可知，與其他算法相比，基于離散蝙蝠算法的測試序列優化結果所需的期望測試代價最多可以降低17.01%，且平均期望測試代價最低，平均收斂速度在智能算法中最快，證明了離散蝙蝠算法應用于測試序列優化問題的優勢，但離散蝙蝠算法在收斂率方面仍有一定的改進空間。另一方面，與信息熵算法、改進信息熵算法、Rollout算法相比，群智能優化算法用時較長，考慮到本文算法僅應用于測試性設計階段而非故障的實時隔離診斷階段，為了獲得優化精度更高的結果，所以對算法的時間要求較低。由離散蝙蝠算法確定的最優測試序列所構成的系統診斷策略優化過程如圖3所示。

圖3 基于離散蝙蝠算法優化的診斷策略Fig.3 Optimizing strategy of fault diagnosis based on discrete bat algorithm optimization

5 結 語

本文采用基于離散蝙蝠算法的優化方案，完成了對艦船作戰系統測試性分析中測試集優化和測試序列優化問題的求解，為系統的測試診斷和功能驗證提供了新的研究思路。同時，該方法較為簡單，可以推廣至其他武器裝備系統的測試性工程應用中。通過在設計階段提高測試性分析的優化精度，可對武器裝備系統測試性模型的改進和后期的維修保障工作提供更高效的指導。然而，隨著測試規模的進一步增加，采用群智能優化算法進行測試性分析時需要以大量的算法運行時間為代價才能獲得更高的優化精度，這將為測試性設計工作帶來不便。但隨著測試手段智能化水平的不斷提升，可以結合數據分析對測試信息進行收集、處理，并通過初步確定故障范圍來合理縮小診斷策略優化設計過程中的測試范圍，從而實現優化精度與算法運行時間的平衡，以進一步改善測試性分析方案。