基于混合人工蜂群算法的并行測試任務優化研究

毛志賓，任慧敏，魯承金，沈海闊

(1.北京交通大學 機械與電子控制工程學院，北京 100044；2.北京航天自動控制研究所，北京 100854；3.北京航天萬源科技有限公司，北京 100176)

0 引言

在自動測試領域，傳統的測試方法是對被測單元(UUT，unit under test)進行串行測試，比如在主線程中直接調用測試函數執行測試任務，測試系統往往是單線程的，不能同時進行多項任務的測試。雖然這種方式對于管理測試任務比較方便，但是測試的效率比較低，不能滿足當下測試任務的需求[1]。

串行測試任務中往往高達80%的時間處在空閑時間[2]，而并行測試技術則可以很好地解決這些問題。它可以通過將測試任務分解為多個被測單元子任務，利用多個處理器、多核心或者多臺計算機同時執行這些子任務，來提高測試效率和測試覆蓋率。并行測試技術的關鍵在于對并行測試調度任務的建模，找到最優的調度方案[3]。

針對并行測試任務，需要根據實際問題采用特定的方法。進行并行測試的目標可以是單一的，也可以是多個的。梁旭[4]等對并行測試任務進行工序建模，以完工時間作為目標函數設計遺傳算法實現了對測試任務和資源的并行調度。

縮短測試完成時間很多情況可以從并行測試時間極限定理出發。王正元[5]等基于并行測試時間極限定理設計算法實現對并行測試任務的調度，確定測試完成最短時間。姚靜波[6]等以測試任務的資源約束為出發點，同時深入研究了并行測試時間極限定理，對并行測試模型進行改進，設計出一種基于測試資源數量約束的并行任務調度改進算法，但是沒有考慮到測試任務之間的時序約束，雖然縮短了測試時間，但是卻增加了測試的成本。李恒璐[7]和宋春霞[8]則不以時間最短為目的求解任務調度序列。

在進行并行測試任務調度時，不僅要考慮到任務之間的時序約束，還要考慮到資源約束。夏銳[9]等將并行測試任務抽象為數學模型，提出了并行率的概念，設計了一種滿足資源約束和任務時序約束的混合遺傳退火算法。Yang[10]等針對傳統測試任務調度問題(TTSP，test task scheduling problem)的不足，提出了一種求解任務調度問題的混合整數線性規劃模型(MILP)，通過隱含序列尋找過程(ISF)和基于序列的迭代優化(SBIO)過程來減少計算時間。

在進行并行測試任務調度時經常用到元啟發式算法，但是這些算法容易陷入局部最優，導致不能得到期望的結果。為此Jain[11]等使用混合整數線性規劃模型來解決調度問題，將資源約束和測試任務的排序結合起來獲得全局最優解；Lu[12]等設計集成編碼方案，以遺傳算法為基礎加入混沌映射算子，避免了陷入局部最優，獲得高質量的解。Guan[13]等提出了一種基于信息熵的蟻群優化算法，提高了蟻群算法求解約束滿足問題(CSP)的解質量；Shi[14]設計了適合于TTSP問題的方案選擇規則，并將其與遺傳算法相結合，用于求解最優測試序列。劉正雷[15]將petri網和蟻群算法相結合，避免算法陷入局部最優解。陸曉飛[16]對粒子群算法進行改進，在粒子群迭代前期或者沒有取得期望的最優解時，粒子進行全局開拓；在粒子群后期或者已經取得期望的最優解時，尋找鄰域內適應值最小的點，從而以更快的速度跳出局部最優解并提高求解的精度。秦勇[17]等重新設計編碼方式，將貪婪算法與遺傳算法相結合，提高了種群質量，但是該方法只能用來求解任務間無前后約束關系的并行測試調度問題。盧茜[18]等在遺傳算法中引入模擬退火算法和禁忌搜索算法的思想，避免了遺傳算法過早收斂的問題，但是僅考慮了多個被測設備之間的并行測試任務調度，而不能實現一個被測設備的各個測試任務之間的并行執行。

并行測試任務的調度方法往往與所研究的實際問題密切相關。蘇萍貞[19]使用任務調度引擎，基于異步調用的方式實現對測試任務的多線程異步執行，但是比較依賴.NET框架，適用范圍比較單一。付新華[20]等對蟻群算法進行改進，使算法的使用范圍由一維靜態優化問題擴展到多維動態組合優化問題，解決了并行測試任務調度復雜、難以優化的問題。談恩民[21]等使用遺傳算法對多IP核進行并行測試，相較于傳統Soc測試，在功耗約束的情況下縮短了測試時間。

對于本文所要優化的問題而言，各個測試任務均有各自的資源依賴關系。所以，需要設計有效的算法既要保證各測試任務的時序關系，還要保證其在資源約束上沒有沖突。國內外學者對此類問題研究較少，即使有前人對類似問題提出過可行性方案，針對本文所研究的問題也不能直接使用。為此，本文基于所研究的調度任務，設計每個任務的編碼方式以及各測試任務之間的時序約束和資源依賴關系，通過將基于動態規劃的遞歸搜索方法與人工蜂群算法結合，提出了混合人工蜂群算法，以實現在保證各測試任務在滿足其對應的資源依賴關系和時序約束關系的基礎上最終測試完工時間最小化。

1 并行測試任務調度問題描述

1.1 相關概念介紹

1)并行度：并行度是指在并行計算中同時執行的任務或線程的數量。在并行計算中，可以將一個任務分解成多個子任務并在多個處理器或計算節點上并行執行。并行度是用于衡量并行計算系統中的任務并行性能的一個指標。如果并行度越高，則意味著系統能夠同時處理更多的任務或線程，從而提高計算性能。并行度通?？梢酝ㄟ^以下公式計算：

(1)

式中，η為并行度，T1為執行時間，T2為等待時間。執行時間是指計算任務實際運行的時間，等待時間是指任務等待資源或其他線程完成的時間。在測試任務確定后，并行度越高，測試完成時間越少。

2)時序約束：設ra，rb是兩個測試任務，并且它們的測試順序在測試任務中不能改變，那么就認為它們存在時序約束。

3)串行任務鏈：在并行測試系統中，由于不同測試任務之間存在的時序相關性或資源相關性，以及在單個UUT上進行多個測試任務時，UUT存在的唯一性等原因，導致這些測試任務只能串行測試，將這些任務組成的集合稱為測試資源串行任務鏈。假設存在測試任務A，測試任務B和測試任務C，其中B和C都依賴于A的輸出。在這種情況下，我們需要按照A→B→C的順序依次執行這些任務，以確保B和C可以使用A的輸出進行測試。如果我們將這些任務并行執行，可能會導致測試結果不準確或出現錯誤。因此，必須按照正確的順序執行串行任務鏈，以確保測試結果的準確性和可靠性。

4)并行測試完成時間極限定理：在并行測試中，測試任務的完成時間受限于最慢的測試任務，即使其他任務已經完成，整個測試任務也必須等待最慢的任務完成。這是由于并行測試的結果取決于所有測試任務的完成情況，而最終結果必須等待所有任務完成后才能確定。

1.2 組合優化問題描述

并行測試任務調度通常被歸類為TTSP。因此，一個測試項目的并行測試任務優化需求可以被抽象描述為，m個測試任務需要被分配到n個資源上執行，并且部分測試任務之間由于既定工程約束需要滿足一定的順序關系。此外，每個測試任務的執行需依賴一個或多個資源才能完成，且每個資源上不允許出現測試任務間的搶占沖突。圖1為一個并行測試任務調度結果的可視化展示。

圖1 并行測試任務調度典型實例

圖1為10個測試任務在8個資源上的測試實例，其中允許最大并發任務數為3。圖1(a)展示了測試任務順序拓撲關系，其中從測試任務t13到測試任務t23均有既定測試的時序關系。圖1(b)為各測試任務與依賴資源的調度順序甘特圖，顯然任意兩個任務在所需相關資源上無搶占沖突。圖1(c)為在限制最大任務并發數量為3的約束下，所有測試任務在多個線程上分布式執行的順序安排。此外，該分布式執行順序與所依賴資源的調度安排的時刻相對應。

由圖1的實例可知，既要考慮各個測試任務在依賴資源上的搶占沖突，又要滿足既定資源之間的執行順序與最大并發任務數，顯然并行測試任務的優化場景是極其復雜的。該問題特性使得相應優化技術需采用啟發或元啟發算法框架，傳統的精確求解技術無法在可接受時間內得到最優解。

1.3 并行測試任務數學模型描述改進

對于并行測試任務，首先定義測試任務集T={t1，t2，t3，...，tm}和測試資源集R={r1，r2，r3，...，rn}，集合τ={τ1，τ2，τ3，...，τm}對應于所有測試任務的時間消耗，TR是一個m×n維的矩陣，表示測試任務和資源之間的依賴關系。矩陣TS表示預定的技術測試順序矩陣，與實際問題需要滿足的約束有關。為了實現并行測試，可以通過預定的線程數量來同時處理不同的測試任務，所有滿足TS限制的時間序列都可以被認為是可行的解決方案。

為滿足并行測試任務的需求，并結合本文所研究實際問題特點的抽象，并行測試任務調度模型進行如下改進：

1)任何資源最多可以同時由一個測試任務占用；

2)占用資源的時間消耗等于相關測試任務的時間消耗；

3)所有測試任務的排序必須滿足預定的技術測試順序(TS)；

4)所有資源上同時的測試任務數量必須小于預定的線程數量。這個問題的目標是盡量減少上次測試任務的完成時間。

資源任務集由TR的列向量中對應元素為1的任務組成，這些任務之間彼此互斥；并行任務序列用來約束任務間的時序關系。

1.4 優化問題數學建模

為建立一個標準的整數規劃模型，以下內容首先定義了相關的決策變量。令二值變量zij∈{0，1}表示任務ti與任務tj之間的排布關系，其中zij=1表示任務tj排布在任務ti之后(可以不連續)；反之表示任務tj排布在任務ti之前。令非負整型變量si表示任務ti的最早開始測試時間，因此任務ti完成測試的時間為si+τi。非負整型變量Tmax表示整個并行測試系統的完工時間。此外，M表示為一個極大的正整數，在數學模型中對非關鍵約束起到虛化的作用。

該問題的混合整數規劃線性模型建立如下：

MinimizeTmax

(2)

Subject to

si+τi≤sj+τj

(3)

sj-si≥τi-M(1-zij)

(4)

Tmax≥si+τii=1，…，m

(5)

si≥0i=1，…，m

(6)

zij∈{0，1}i=1，…，m，j=1，…，m，i≠j

(7)

Tmax≥0

(8)

公式(2)為模型的目標函數，即最小化整個系統的總測試時間。剩余公式定義了本模型的約束和決策變量。約束(3)為各測試任務完工時間的時序約束。當TS(i，j)=1時，約束1轉化為si+τi≤sj+τj，即要求任務tj的結束時間大于任務ti；反之，模型中沒有任務tj與任務ti的結束約束。約束(4)是保證多任務占用資源的非沖突約束。約束(6)～(8)為相應的決策變量定義。

2 混合人工蜂群算法設計

為解決優化場景中存在既定的測試任務順序約束，本文主要基于動態規劃的遞歸搜索以及人工蜂群算法框架開發出了混合人工蜂群算法。通過遞歸搜索技術找到一系列任務隱含序列，然后使用找到的隱含序列糾正人工蜂群算法的單個編碼。

2.1 算法總體設計

混合人工蜂群算法首先通過時序遞歸搜索找到一系列任務隱含序列，然后依次執行“全局個體優化”“部分個體強化”和“少量個體淘汰”3個主搜索流程，糾正找到的隱含序列混合人工蜂群算法的單個編碼。在執行“全局個體優化”和“少量個體強化”流程時，均會依次執行二進制選擇、鄰域搜索模塊、隱集編碼修正，如果隨機搜索的概率滿足局部搜索條件，還會執行局部搜索模塊以及再一次的隱集編碼修正。

不同的是，在“全局個體優化”搜索流程中，每次進入鄰域搜索模塊的是一個順序選擇個體和一個經過二進制選擇的個體；而進入“部分個體強化”搜索流程中鄰域搜索模塊兩個個體均為經過二進制選擇的個體。當執行完“全局個體優化”和“部分個體強化”搜索流程后，則會在“少量個體淘汰”搜索流程階段對超過限定迭代次數而未優化的個體進行淘汰。最后，經過一次迭代之后更新全局最優個體記錄?；旌先斯し淙核惴ǖ幕玖鞒倘鐖D2所示。

圖2 算法流程圖

當在既定的優化場景中通過混合人工蜂群算法的數據流輸入接口傳入原始的數據之后，就會將其存儲在混合人工蜂群算法的變量中，通過調用混合人工蜂群算法內部的函數對相應的原始數據進行一定的操作，最后通過混合人工蜂群算法的數據流輸出接口將處理后的數據返還給外部。

2.2 時序遞歸搜索技術

(9)

圖3顯示了示例的遞歸路徑。遞歸樹依據違反限制的節點路徑被剪枝，有效地降低算法的搜索空間，提高算法的搜索效率。圖2最終的任務隱含序列為(1，2，3，4)，(1，3，2，4)以及(1，3，4，2)。然后人工蜂群編碼序列通過對與其隱含及序列相關的局部任務排序調整，即可實現該編碼序列滿足既定時序約束，結果如圖4所示。

圖3 時序約束的遞歸路徑

圖4 時序約束TS={[1，2]，[1，3]，[3，4]}隱含集序列對應的修正人工蜂群編碼

2.3 鄰域搜索技術

鄰域搜索技術(Neighborhood Search)結合了多點插入算子與多點交換算子，該技術旨在對一個體編碼及其鄰域編碼實現高質量的子代編碼搜索。假設Xt是一個按照順序選擇的個體，Xf為通過二進制選擇的一個個體，即為Xt的鄰域個體。鄰域搜索流程主要依據概率nbrPro執行，如果隨機概率大于nbrPro，則只對Xt執行多點交換算子。如果隨機概率小于nbrPro，則首先判斷兩個體的適應度值；如果適應度值相同，仍然只對Xt執行多點交換算子；否則，對兩個體執行多點交換算子獲得子代編碼。

多點插入算子(Multi-insertion)：基于既定的交換點數量與兩個個體，通過給定的規則生成子個體。假設Xt是一個按照順序選擇的個體，Xf為通過二進制選擇的一個個體，即為Xt的鄰域個體。nbrNum為既定交換的個體中的節點數量。例如，Xt和Xf可以分別被表示為：

Xt=(1，5，3，2，9，8，10，7，4，6)和Xf=(2，6，5，9，3，1，7，8，4，10)。在Xt中隨機選擇nbrNum(通常nbrNum)個保留點位，則包含保留點位的Xt可以被表示為：

Xt=(x，5，x，2，9，x，x，x，x，x)

(10)

其中：x表示Xt的空白位置。隨后，從Xf中抽取非Xt中保留點位的其他數值并依次填充入Xt。最終的Xt可以被重新生成為Xt=(6，5，3，2，9，1，7，8，4，10)。上述過程是多點插入算子的標準流程，多點插入算子擅長于在調度問題中更大幾率的發現質量更高的解。

多點交換算子(Multi-swap)：針對既定的一個編碼，通過多個點的位置交換，從而產生一個新個體編碼。多點交換算子依據一個隨機產生的交換點數量nrb，然后隨機交換nrb個節點的位置，從而產生新編碼。該算子旨在通過多點交換方式，從而避免算法陷入局部最優的情況。

2.4 局部搜索技術

局部搜索技術(Local Search)結合了貪婪搜索過程，通過局部枚舉的方式盡可能地實現高質量解編碼的生成。局部搜索算子通過一個弱枚舉的循環，最大限度地提升個體解的質量。對于個體編碼Xt=(x1，x2，…，xi，…，xm)，將第一個任務編號x1與相鄰位置進行交換；如果x1交換后無法提高Xt的質量(適應度值)，則重復上述過程；如果x1交換后提高了解Xt的質量(適應度值)，則終止循環返回當前生成的新個體。局部搜索算子的執行效率較低，但可以配合彌補其他算子收斂性不強的不足。

3 實驗驗證分析

本文采用整數規劃精確算法和遺傳算法作為混合人工蜂群算法的對比算法，分別通過小規模用例和大規模用例進行算法的性能測試對比。小規模用例用來測試算法處理一般測試任務調度的能力，大規模用例用來探究算法的極限性能。以測試任務完成時間和cpu占用率作為評價算法的指標。

3.1 小規模用例測試

小規模測試用例1如表1所示，規模：測試任務數為8，資源數為7。

表1 小規模測試用例1

表1的算例分別調用了整數規劃精確算法、遺傳算法以及混合人工蜂群算法求解。3個算法都可以求得該算例的最優解，并且它們的求解效率差別不大。3個算法的求解結果如圖5所示。

圖5 小規模測試用例1結果甘特圖

3個算法的求解時間和CPU占用率如表2所示。

表2 小規模測試用例1結果比較

從表2可以看出，3個算法的求解時間接近，混合人工蜂群算法的CPU占用率更低。

小規模測試用例2如表3所示，規模：測試任務數為15，資源數為5。

表3 小規模測試用例2

表3的測試用例同樣分別調用了整數規劃精確算法、遺傳算法以及混合人工蜂群算法求解。3個算法都求解到了該算例的最優解，即最優完工時間為Tmax=412。其最優解的甘特圖如圖6所示。

圖6 小規模測試用例2結果甘特圖(有時序約束)

在小規模用例2中3個算法的求解時間和CPU占用率如表4所示。

表4 小規模測試用例2結果比較(有時序約束)

圖7表示在無時序約束的情況下，3個算法的最優解甘特圖。

圖7 小規模測試用例2結果甘特圖(無時序約束)

表5為無時序約束下3個算法結果對比。

表5 小規模測試用例2結果比較(無時序約束)

混合人工蜂群算法可以在小于10 s內完成，而整數規劃精確算法的求解時間約為123 s，遺傳算法的求解時間為230 s。這表明在沒有時序約束的情況下，混合人工蜂群算法的性能要遠遠優于傳統并行測試算法。

3.2 大規模用例測試

大規模算例：測試任務數為100，資源數為10。測試結果如表6所示。

表6 小規模測試用例2結果比較(無時序約束)

當測試規模擴大到一定程度，整數規劃精確算法以及遺傳算法已經不能完成任務，無法求得最優解。而混合人工蜂群算法依然可以在400多秒內搜索到最小完成時間。這表明，相比傳統的啟發式算法，混合人工蜂群算法在大規模測試任務下有很大的優勢。

4 結束語

本文基于所研究的并行測試任務，在確保各任務間的時序約束關系和資源依賴關系的基礎上，將動態規劃的遞歸搜索方法與人工蜂群算法相結合，提出混合人工蜂群算法。分別用小規模用例和大規模用例進行測試，并與整數規劃精確算法和遺傳算法進行對比。結果表明，本文所提出的方法相較于傳統求解器節省時間接近50%，硬件資源的占用率降低了接近20%，提高了求解該類問題的效率。