基于蟻群算法的測(cè)試任務(wù)調(diào)度優(yōu)化方法

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

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

0 引言

復(fù)雜系統(tǒng)測(cè)試的時(shí)間長(zhǎng)、效率低、成本高，提高測(cè)試效率、減小儀器閑置已經(jīng)成為測(cè)試系統(tǒng)亟待解決的問題。并行測(cè)試技術(shù)[1-3]通過提高單位時(shí)間內(nèi)被測(cè)對(duì)象的數(shù)量及在每一個(gè)被測(cè)對(duì)象內(nèi)部并行進(jìn)行參數(shù)測(cè)試，來提高測(cè)試儀器的利用率和測(cè)試效率，因此并行任務(wù)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)是關(guān)鍵。

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

本文針對(duì)測(cè)試系統(tǒng)測(cè)試效率低、資源浪費(fèi)問題，提出基于蟻群算法的測(cè)試任務(wù)并行調(diào)度優(yōu)化方法，建立了算法的完整體系。明確了測(cè)試任務(wù)，分析了可優(yōu)化空間，應(yīng)用蟻群算法設(shè)計(jì)了啟發(fā)函數(shù)和狀態(tài)轉(zhuǎn)移概率；通過與隨機(jī)窮舉法對(duì)比驗(yàn)證了算法的有效性；針對(duì)多解問題，提出了資源均衡度的評(píng)價(jià)標(biāo)準(zhǔn)。仿真結(jié)果表明，本文方法是有效的，在實(shí)現(xiàn)最短測(cè)試時(shí)間的同時(shí)獲得了資源均衡度最高的任務(wù)調(diào)度序列。

1 并行測(cè)試任務(wù)調(diào)度優(yōu)化

由于復(fù)雜系統(tǒng)測(cè)試項(xiàng)目眾多，而且嚴(yán)格的約束關(guān)系存在于各測(cè)試任務(wù)之間，有效提取可以并行執(zhí)行的任務(wù)是調(diào)度優(yōu)化的前提，因此需要詳細(xì)分析并行測(cè)試任務(wù)及相關(guān)約束條件。并行測(cè)試任務(wù)調(diào)度優(yōu)化的研究框架如圖1所示。

圖1 測(cè)試系統(tǒng)優(yōu)化總流程Fig.1 Optimization process of test system

由圖1可知，測(cè)試系統(tǒng)優(yōu)化流程如下：1)明確測(cè)試系統(tǒng)流程及資源任務(wù)關(guān)系，確定可優(yōu)化空間；2)將問題進(jìn)行抽象描述，結(jié)合實(shí)際蟻群算法、設(shè)計(jì)算法流程，得到測(cè)試時(shí)間最短的任務(wù)序列；3)對(duì)任務(wù)序列多解的問題，提出資源均衡度作為評(píng)價(jià)標(biāo)準(zhǔn)，從而求解出較優(yōu)的資源、任務(wù)調(diào)度序列。

2 基于蟻群算法的測(cè)試任務(wù)調(diào)度

復(fù)雜系統(tǒng)的測(cè)試任務(wù)一般可分為單元測(cè)試、分系統(tǒng)測(cè)試和總檢查3部分，各部分之間為串行執(zhí)行關(guān)系，其中單元測(cè)試和分系統(tǒng)測(cè)試中存在一個(gè)任務(wù)可由多個(gè)資源完成的多方案情況，有可優(yōu)化的空間。本節(jié)將蟻群算法基本原理與并行測(cè)試任務(wù)調(diào)度具體問題結(jié)合起來，設(shè)計(jì)并行測(cè)試的蟻群算法啟發(fā)函數(shù)、狀態(tài)轉(zhuǎn)移概率、信息素更新公式等。

2.1 并行測(cè)試任務(wù)問題描述

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

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

2.2 并行測(cè)試的蟻群算法

將蟻群算法基本原理[9-10]與并行測(cè)試任務(wù)調(diào)度具體問題相結(jié)合，得到測(cè)試時(shí)間最短的并行任務(wù)調(diào)度矩陣TP，該調(diào)度矩陣中的行表示資源、列表示資源對(duì)任務(wù)的測(cè)試順序，內(nèi)部元素表示任務(wù)序號(hào)：

(1)

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

結(jié)合并行測(cè)試任務(wù)調(diào)度問題特點(diǎn)，蟻群算法設(shè)計(jì)如下：

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

(2)

啟發(fā)函數(shù)數(shù)值表示先驗(yàn)客觀因素的影響情況，依據(jù)貪心規(guī)則進(jìn)行計(jì)算，即基于當(dāng)前一步，測(cè)試時(shí)間越短的路徑其啟發(fā)函數(shù)數(shù)值越大、轉(zhuǎn)移概率越高，但是有時(shí)會(huì)發(fā)生早熟現(xiàn)象[13-14]。因此，任務(wù)選擇還需要利用信息素的影響，以免陷入局部最優(yōu)解。

(3)

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

(4)

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

(5)

(6)

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

下面引用云計(jì)算領(lǐng)域的負(fù)載均衡度概念[16]，提出并行測(cè)試任務(wù)調(diào)度中的資源均衡度定義，來解決任務(wù)矩陣的多解問題。

具體解決方式為：在最短測(cè)試時(shí)間的測(cè)試方案中選取資源均衡度最大的資源、任務(wù)調(diào)度方案。用資源均衡度σ表示同種資源測(cè)試任務(wù)時(shí)間的平均程度，σ越大，儀器的工作時(shí)間越均衡，對(duì)每個(gè)儀器的損耗越小。σ的定義如下：

(7)

(8)

式中：s表示第c種資源的數(shù)量；Trv、Tru表示對(duì)應(yīng)資源的任務(wù)時(shí)間。

2.3 算法流程設(shè)計(jì)

測(cè)試需求與蟻群算法相結(jié)合，對(duì)并行任務(wù)優(yōu)化調(diào)度問題建立蟻群算法流程如圖2所示，其中迭代序數(shù)和螞蟻序數(shù)分別用Nc和k表示，可并行任務(wù)的提取通過遍歷所有儀器實(shí)現(xiàn)。

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

3 實(shí)例仿真分析

在仿真實(shí)例中選取測(cè)試任務(wù)50項(xiàng)、資源節(jié)點(diǎn)10個(gè)，來源為公開資料的典型測(cè)試流程，資源情況[17]如表1所示。

表1 測(cè)試資源情況

測(cè)試流程為：首先進(jìn)行單元測(cè)試，然后進(jìn)行分系統(tǒng)測(cè)試，最后進(jìn)行總檢查。具體約束情況如圖3所示。

圖3 測(cè)試約束限定Fig.3 Testing constraints

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

同理，分系統(tǒng)測(cè)試任務(wù)約束關(guān)系為(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；總檢查測(cè)試任務(wù)約束關(guān)系為t47?t48?t49?t50.

測(cè)試任務(wù)、測(cè)試方案、儀器資源以及時(shí)間的對(duì)應(yīng)關(guān)系[17]如表2所示，其中tj表示測(cè)試任務(wù)，ri表示資源(在資源項(xiàng)中，以逗號(hào)相隔的ri表示方案中任意一個(gè)資源都不能缺少，以頓號(hào)相隔的ri表示一個(gè)方案中只需要任意一個(gè)資源)，方案號(hào)為1～6，表示一個(gè)任務(wù)最多有6個(gè)方案，時(shí)間為對(duì)應(yīng)的任務(wù)完成時(shí)間。

表2 測(cè)試任務(wù)、方案、資源及時(shí)間

使用MATLAB 2016對(duì)算法進(jìn)行編程實(shí)現(xiàn)，運(yùn)行平臺(tái)為：Intel Core i5 CPU，2.13 GHz，內(nèi)存4.0 GB. 算法參數(shù)設(shè)置依據(jù)多次仿真結(jié)果選取，具體參數(shù)如表3所示。算法的最大迭代次數(shù)為100次，達(dá)到迭代次數(shù)后算法終止。

表3 仿真測(cè)試參數(shù)設(shè)置

3.1 仿真結(jié)果及分析

仿真實(shí)驗(yàn)結(jié)果如圖4所示。圖4中3條曲線分別為每次迭代的多種測(cè)試方案測(cè)試時(shí)間最大值、平均測(cè)試時(shí)間，以及測(cè)試時(shí)間最小值即每次迭代的最優(yōu)解。

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

由圖4可見，最短時(shí)間收斂到74 min，大約經(jīng)過了12次迭代。雖然時(shí)間最大值在迭代過程中仍然存在波動(dòng)，這是由于螞蟻的隨機(jī)性引起，但其峰值具有減小趨勢(shì)，平均測(cè)試時(shí)間同時(shí)趨向于最小值而最小值已保持穩(wěn)定，因此可以認(rèn)為測(cè)試任務(wù)調(diào)度的最優(yōu)解已成功找到。

在最短測(cè)試時(shí)間為74 min的多種任務(wù)矩陣中，資源均衡度最大值maxσ為0.885 min-2的最優(yōu)任務(wù)調(diào)度矩陣對(duì)應(yīng)的Gantt圖如圖5所示，其中數(shù)字為任務(wù)序號(hào)。

圖5 并行任務(wù)調(diào)度方案Fig.5 Parallel task scheduling scheme

3.2 與隨機(jī)窮舉法對(duì)比

在同種約束限定下，將隨機(jī)窮舉法與本文算法進(jìn)行對(duì)比，驗(yàn)證本文算法的有效性。以本文優(yōu)化出的流程為參考，結(jié)合型號(hào)的實(shí)際情況如人員操作、子系統(tǒng)協(xié)調(diào)等無法量化為約束的情況，設(shè)計(jì)人員可以設(shè)計(jì)出比傳統(tǒng)流程更優(yōu)秀的結(jié)果。

在滿足約束條件下，用隨機(jī)方式產(chǎn)生并行任務(wù)序列，4 000種隨機(jī)序列的用時(shí)情況如圖6所示。

圖6 4 000次隨機(jī)序列用時(shí)Fig.6 Time consumption of 4 000 random sequences

由圖6可見，在滿足約束條件下，最大測(cè)試時(shí)間為94 min，大多數(shù)測(cè)試時(shí)間集中于84 min左右，最短時(shí)間為76 min. 由此可見，任務(wù)調(diào)度的最優(yōu)解并沒有被隨機(jī)窮舉方法找到，雖然通過增加搜索次數(shù)可能找到最優(yōu)解，但對(duì)于復(fù)雜測(cè)試系統(tǒng)，隨機(jī)窮舉法并不是一個(gè)很好的選擇，其搜索效率相對(duì)于蟻群算法低很多。

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

表3 仿真效果比較

對(duì)比蟻群算法與隨機(jī)窮舉法可知，用蟻群算法進(jìn)行測(cè)試任務(wù)并行優(yōu)化調(diào)度在尋優(yōu)速度上表現(xiàn)更好，具有較大的優(yōu)勢(shì)。

3.3 與半串行測(cè)試方式對(duì)比

目前，本文的測(cè)試實(shí)例在實(shí)際工作中多以半串行方式進(jìn)行測(cè)試，即大測(cè)試項(xiàng)目間串行，測(cè)試項(xiàng)目?jī)?nèi)分解任務(wù)并行，在一定程度上使得測(cè)試時(shí)間減小，但仍然存在較大的優(yōu)化空間，半串行的總測(cè)試時(shí)間為130 min. 改變大項(xiàng)目之間的任務(wù)約束，可以更充分地進(jìn)行并行分解，其測(cè)試效率的提升率由(9)式可得：

(9)

式中：Ts為半串行測(cè)試總時(shí)間；Tp為并行測(cè)試總時(shí)間。根據(jù)(9)式，經(jīng)蟻群算法優(yōu)化后，并行測(cè)試較半串行測(cè)試，測(cè)試效率提升了43.07%.

4 結(jié)論

本文分析了測(cè)試任務(wù)調(diào)度優(yōu)化問題，將蟻群算法應(yīng)用于并行測(cè)試的任務(wù)調(diào)度優(yōu)化，并針對(duì)最短時(shí)間任務(wù)調(diào)度序列多解的問題，用資源均衡度的概念尋找資源均衡度最好的最短時(shí)間任務(wù)調(diào)度序列。仿真結(jié)果表明，與隨機(jī)窮舉法對(duì)比，本文算法能有效地找到最短時(shí)間任務(wù)調(diào)度序列，大大改善了測(cè)試系統(tǒng)的測(cè)試效率，與現(xiàn)有的半串行測(cè)試方法相比，節(jié)約了測(cè)試時(shí)間，提升了測(cè)試效率；提出了資源均衡度的概念作為評(píng)價(jià)標(biāo)準(zhǔn)，解決了最短時(shí)間任務(wù)調(diào)度序列多解的問題。如果在特定情況下資源均衡度比較重要，則可以將接近于最短時(shí)間的測(cè)試方案也包括進(jìn)來，以選取資源均衡度較好的測(cè)試序列。