基于蟻群算法的測試任務調度優化方法

胡濤, 馬晨輝, 申立群, 梁潔

(1.哈爾濱工業大學 儀器科學與工程學院， 黑龍江 哈爾濱 150001; 2.北京宇航系統工程研究所， 北京 100076)

0 引言

復雜系統測試的時間長、效率低、成本高，提高測試效率、減小儀器閑置已經成為測試系統亟待解決的問題。并行測試技術[1-3]通過提高單位時間內被測對象的數量及在每一個被測對象內部并行進行參數測試，來提高測試儀器的利用率和測試效率，因此并行任務調度算法的設計與實現是關鍵。

蟻群算法是一種仿生智能算法，應用很廣，對于任務調度問題具有很好的適用性。熊婧[4]為蟻群算法應用于調度問題提供了思路，適合于車間作業調度的實際問題；付新華等[5]將蟻群算法與并行測試任務調度相結合，然而算法全局搜索能力仍有待進一步完善；路輝等[6]提出了任務調度方案的詳細問題描述，但多目標優化降低了測試效率的要求。上述方法未考慮測試時間最短的任務調度矩陣存在多解的問題，算法體系不完整。

本文針對測試系統測試效率低、資源浪費問題，提出基于蟻群算法的測試任務并行調度優化方法，建立了算法的完整體系。明確了測試任務，分析了可優化空間，應用蟻群算法設計了啟發函數和狀態轉移概率；通過與隨機窮舉法對比驗證了算法的有效性；針對多解問題，提出了資源均衡度的評價標準。仿真結果表明，本文方法是有效的，在實現最短測試時間的同時獲得了資源均衡度最高的任務調度序列。

1 并行測試任務調度優化

由于復雜系統測試項目眾多，而且嚴格的約束關系存在于各測試任務之間，有效提取可以并行執行的任務是調度優化的前提，因此需要詳細分析并行測試任務及相關約束條件。并行測試任務調度優化的研究框架如圖1所示。

圖1 測試系統優化總流程Fig.1 Optimization process of test system

由圖1可知，測試系統優化流程如下：1)明確測試系統流程及資源任務關系，確定可優化空間；2)將問題進行抽象描述，結合實際蟻群算法、設計算法流程，得到測試時間最短的任務序列；3)對任務序列多解的問題，提出資源均衡度作為評價標準，從而求解出較優的資源、任務調度序列。

2 基于蟻群算法的測試任務調度

復雜系統的測試任務一般可分為單元測試、分系統測試和總檢查3部分，各部分之間為串行執行關系，其中單元測試和分系統測試中存在一個任務可由多個資源完成的多方案情況，有可優化的空間。本節將蟻群算法基本原理與并行測試任務調度具體問題結合起來，設計并行測試的蟻群算法啟發函數、狀態轉移概率、信息素更新公式等。

2.1 并行測試任務問題描述

某系統具有x件測試儀器(測試儀器即代表并行任務調度中的資源)、y項待測任務。其中任務占用資源情況為：1)一個任務對應多個資源；2)一個資源對應多種任務；3)一個任務同時需要幾個資源。每種方案中的儀器組合具有明確的測試時間。本文研究的最終目標是在任務約束條件下，獲取時間最短的測試任務調度序列。

由于測試時序上有嚴格約束，某些任務具有明確和固定的優先級關系[7]。任務約束[8]主要包括控制相關、資源相關和數據相關3種類型：1)控制相關，即測試任務t1、t2具有優先級關系，例如在t1執行完成后才可執行t2；2)資源相關，即任務t1、t2所需的資源集r1、r2滿足r1∩r2≠?；3)數據相關，即任務t1的測試結果是任務t2的輸入，這種約束在本文中并不涉及。根據以上約束關系，對測試任務進行正確合理的優先級設定，優先級高的任務需要先執行完畢才能執行低優先級的任務。

2.2 并行測試的蟻群算法

將蟻群算法基本原理[9-10]與并行測試任務調度具體問題相結合，得到測試時間最短的并行任務調度矩陣TP，該調度矩陣中的行表示資源、列表示資源對任務的測試順序，內部元素表示任務序號：

(1)

式中：tri j中的ri為資源序號(i=1,2,…,x)；j為任務序號(j=1,2,…,y)。若任務tl(l∈{1,2,…,y})在第j步被ri測試，則tri j=tl，否則tri j=0表示空任務，此時資源空閑，可以被其他任務選擇。

結合并行測試任務調度問題特點，蟻群算法設計如下：

1) 啟發函數ηij[11-12]。啟發函數ηij表示任務tj被資源ri選擇的期望程度，

(2)

啟發函數數值表示先驗客觀因素的影響情況，依據貪心規則進行計算，即基于當前一步，測試時間越短的路徑其啟發函數數值越大、轉移概率越高，但是有時會發生早熟現象[13-14]。因此，任務選擇還需要利用信息素的影響，以免陷入局部最優解。

(3)

式中：α表示信息素的重要程度[15]，其值越大，搜索的隨機性越弱，螞蟻越容易匯聚到一個可行解；τij表示資源選擇任務的信息素濃度；β=1-α反映了啟發式信息的重要程度，β越大，先驗知識越重要；tabuk(i)表示螞蟻k在資源ri的禁忌表，即已執行過的任務；s表示未執行的任務號。任務的選擇概率即轉移概率主要受到信息素和啟發函數的影響。為使算法具有良好的搜索能力，需要合理設置α、β的值。

(4)

3) 全局信息素更新規則τij. 信息素的更新在一次完整迭代后，根據所有螞蟻為任一儀器的任務選擇進行計算：

(5)

(6)

利用(2)式～(6)式，通過蟻群算法得到最短測試時間的任務調度矩陣。但其中存在多種滿足測試需求的可執行測試方案，方案多解的原因如下：某些測試任務的測試順序發生變化，測試順序不影響測試時間；測試資源在不同時間被使用；測試資源的可測任務集發生變化。雖然總測試時間相同，但還需要依據實際情況從其他方面綜合考慮具體配置方案。

下面引用云計算領域的負載均衡度概念[16]，提出并行測試任務調度中的資源均衡度定義，來解決任務矩陣的多解問題。

具體解決方式為：在最短測試時間的測試方案中選取資源均衡度最大的資源、任務調度方案。用資源均衡度σ表示同種資源測試任務時間的平均程度，σ越大，儀器的工作時間越均衡，對每個儀器的損耗越小。σ的定義如下：

(7)

(8)

式中：s表示第c種資源的數量；Trv、Tru表示對應資源的任務時間。

2.3 算法流程設計

測試需求與蟻群算法相結合，對并行任務優化調度問題建立蟻群算法流程如圖2所示，其中迭代序數和螞蟻序數分別用Nc和k表示，可并行任務的提取通過遍歷所有儀器實現。

圖2 蟻群算法并行調度流程Fig.2 Parallel scheduling process of ant colony algorithm

3 實例仿真分析

在仿真實例中選取測試任務50項、資源節點10個，來源為公開資料的典型測試流程，資源情況[17]如表1所示。

表1 測試資源情況

測試流程為：首先進行單元測試，然后進行分系統測試，最后進行總檢查。具體約束情況如圖3所示。

圖3 測試約束限定Fig.3 Testing constraints

由圖3可見，若任務ti優先于任務tj，則用ti?tj表示，即ti的測試要先于tj的測試。單元測試任務約束關系為：t1?(t2,t3,…,t19)，t8?t9,t10?t11，t12?t13?t14.

同理，分系統測試任務約束關系為(t20,t21,…,t26)?(t27,t28,…,t46)，t37?t38，(t27,t28,…,t31)?(t35,t36,…,t46)，(t43,t44,t45)?t46，(t32,t33,t34)?(t35,t36,t37,t38)，t35?t36，t39?t40?t41；總檢查測試任務約束關系為t47?t48?t49?t50.

測試任務、測試方案、儀器資源以及時間的對應關系[17]如表2所示，其中tj表示測試任務，ri表示資源(在資源項中，以逗號相隔的ri表示方案中任意一個資源都不能缺少，以頓號相隔的ri表示一個方案中只需要任意一個資源)，方案號為1～6，表示一個任務最多有6個方案，時間為對應的任務完成時間。

表2 測試任務、方案、資源及時間

使用MATLAB 2016對算法進行編程實現，運行平臺為：Intel Core i5 CPU，2.13 GHz，內存4.0 GB. 算法參數設置依據多次仿真結果選取，具體參數如表3所示。算法的最大迭代次數為100次，達到迭代次數后算法終止。

表3 仿真測試參數設置

3.1 仿真結果及分析

仿真實驗結果如圖4所示。圖4中3條曲線分別為每次迭代的多種測試方案測試時間最大值、平均測試時間，以及測試時間最小值即每次迭代的最優解。

圖4 蟻群算法迭代曲線Fig.4 Iterative curves of ant colony algorithm

由圖4可見，最短時間收斂到74 min，大約經過了12次迭代。雖然時間最大值在迭代過程中仍然存在波動，這是由于螞蟻的隨機性引起，但其峰值具有減小趨勢，平均測試時間同時趨向于最小值而最小值已保持穩定，因此可以認為測試任務調度的最優解已成功找到。

在最短測試時間為74 min的多種任務矩陣中，資源均衡度最大值maxσ為0.885 min-2的最優任務調度矩陣對應的Gantt圖如圖5所示，其中數字為任務序號。

圖5 并行任務調度方案Fig.5 Parallel task scheduling scheme

3.2 與隨機窮舉法對比

在同種約束限定下，將隨機窮舉法與本文算法進行對比，驗證本文算法的有效性。以本文優化出的流程為參考，結合型號的實際情況如人員操作、子系統協調等無法量化為約束的情況，設計人員可以設計出比傳統流程更優秀的結果。

在滿足約束條件下，用隨機方式產生并行任務序列，4 000種隨機序列的用時情況如圖6所示。

圖6 4 000次隨機序列用時Fig.6 Time consumption of 4 000 random sequences

由圖6可見，在滿足約束條件下，最大測試時間為94 min，大多數測試時間集中于84 min左右，最短時間為76 min. 由此可見，任務調度的最優解并沒有被隨機窮舉方法找到，雖然通過增加搜索次數可能找到最優解，但對于復雜測試系統，隨機窮舉法并不是一個很好的選擇，其搜索效率相對于蟻群算法低很多。

相比隨機窮舉法，蟻群算法顯然具有較好的效率，具體的比較情況如表3所示。

表3 仿真效果比較

對比蟻群算法與隨機窮舉法可知，用蟻群算法進行測試任務并行優化調度在尋優速度上表現更好，具有較大的優勢。

3.3 與半串行測試方式對比

目前，本文的測試實例在實際工作中多以半串行方式進行測試，即大測試項目間串行，測試項目內分解任務并行，在一定程度上使得測試時間減小，但仍然存在較大的優化空間，半串行的總測試時間為130 min. 改變大項目之間的任務約束，可以更充分地進行并行分解，其測試效率的提升率由(9)式可得：

(9)

式中：Ts為半串行測試總時間；Tp為并行測試總時間。根據(9)式，經蟻群算法優化后，并行測試較半串行測試，測試效率提升了43.07%.

4 結論

本文分析了測試任務調度優化問題，將蟻群算法應用于并行測試的任務調度優化，并針對最短時間任務調度序列多解的問題，用資源均衡度的概念尋找資源均衡度最好的最短時間任務調度序列。仿真結果表明，與隨機窮舉法對比，本文算法能有效地找到最短時間任務調度序列，大大改善了測試系統的測試效率，與現有的半串行測試方法相比，節約了測試時間，提升了測試效率；提出了資源均衡度的概念作為評價標準，解決了最短時間任務調度序列多解的問題。如果在特定情況下資源均衡度比較重要，則可以將接近于最短時間的測試方案也包括進來，以選取資源均衡度較好的測試序列。