基于H-ABC算法的并行測試任務優化研究

和 楓，王曉明，葉志鵬，沈海闊

（1.北京宇航系統工程研究所，北京，100076；2.北京交通大學，北京，100044）

0 引言

測試在制造業，尤其是在航空航天以及特種設備制造領域中具有舉足輕重的作用，新的產品開發通常需要一系列的測試項目。一般來說，每臺設備由多個子系統組成，每個子系統都需要通過一些特定的測試項目。要測試的子系統被命名為待測單元，待測單元的特定測試項被命名為測試任務。待測單元的不同測試任務可能有預定的技術測試順序，并且取決于不同類型的資源（儀器）。技術測試順序的限制來源于測試任務的工程需求，即部分測試任務必須在其他相關任務完成后才能開展測試。

對于并行測試任務其目標可以是單一的，也可以是多個。Jain和Grossman［1］首先將并行測試任務調度建模為一個混合整數線性規劃模型，該模型將兩個相關目標加權為單個優化目標。與上述線性加權法不同，Lu等［2-6］針對該優化問題提出了一系列基于帕累托法則的優化方法，主要是采用NSGA-II作為算法框架［3-5］，提出可變鄰域方法使交叉跨度合理［5］，利用混沌映射避免陷入局部最優［4］，其中考慮了最小化最大測試完成時間和平均工作量兩個待優化目標。此外，其對特定場景下的單目標優化也進行了充分的研究。Do Ngoc等［7］考慮大型發動機測試過程的額外空間和時間約束，利用遺傳算法來尋找候選項目的最佳組合，以獲得最大利潤。對于具有單一目標的標準TTSP，Lu 和Zhang［8］采用分布估計算法求解測試任務排序，并結合禁忌搜索防止迂回搜索。Shi 等［9］提出了解決TTSP 中資源沖突的方案選擇規則，并開發了遺傳算法來尋找合適的任務序列。隨后，Yang等［10］在充分考慮預先確定的技術測試順序的基礎上，重點研究了標準TTSP，提出了隱含序列尋找過程和基于序列的迭代優化過程，以減少計算時間。Liao等［11］研究了在有交貨期限制的過載情況下的加權任務，其目標是使延遲任務的總權重值最小。約束滿足問題通常出現在拓撲學研究領域［12］，其主要特點是變量之間存在指定的拓撲關系［13］，但約束滿足技術也已廣泛應用于規劃和調度等領域［14］。求解約束滿足問題的關鍵步驟是構造一個不違反任何拓撲關系約束的可行調度［15］。

并行測試任務調度在于縮短測試進程的最終完成時間，對于本文而言，每個測試任務的可用資源都有各自的依賴關系。因此，需要設計有效的算法保證各測試任務在依賴資源無沖突的前提下，滿足測試任務間的既定時序依賴關系，而國內外學者對此類問題鮮有研究。本研究通過對每個任務編碼以及輸入既定各測試任務間的時序約束與任務與資源間的依賴關系，通過設計有效的人工蜂群啟發式算法（Hybrid artifical Bee Colong，H-ABC）進行優化，以獲得各測試任務在其相應資源上的先后安排，同時使得最終測試項目的完成時間最小化。

1 H-ABC算法理論研究

首先通過定義以下符號集對本項目所需解決的問題做如下簡要概述。令集合T={ti：1 ≤i≤m}表示m個測試任務，集合R={rk：1 ≤k≤n}表示n個測試所需的資源或設備，集合τ={τi：1 ≤i≤m}對應于所有測試任務的時間消耗，TR是一個m×n維的矩陣，表示測試任務和資源之間的依賴關系。矩陣TS表示預定的技術測試順序矩陣，與實際問題需要滿足的約束有關，例如TS(1)=[i，j]表示對任務ti的測試必須在對任務tj的前面。為了實現并行測試，可以通過預定的線程數量d來同時處理不同的測試任務，所有滿足TS限制的時間序列都可以被認為是可行的解決方案。

另外，本項目所需解決的問題可以做如下改進：

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

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

c）所有測試任務的排序必須滿足預定的技術測試順序；

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

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

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

式（1）表示為模型的目標函數，即為最小化整個系統的總測試時間。剩余公式定義了本模型的約束和決策變量。約束（2）為各測試任務完工時間的時序約束。當TS(i，j)=1 時，約束1 轉化為si+τi≤sj+τj，即要求任務tj的結束時間大于任務ti；反之，模型中沒有任務tj與任務ti的結束約束。約束（3）、（4）是保證多任務占用資源的非沖突約束。在約束（3）和約束（4）中，當存在條件TR(i，k)·TS(j，k)=1 時，表明任務ti與任務tj都與資源rk有關聯。為避免出現這兩個任務搶占同一資源的情況，任務ti與任務tj必然存在其完成時間與開始時間的時序關系。因此，約束（3）與約束（4）有效，反之，約束（3）與約束（4）不存在于模型中。同時，二值變量zij保證了兩個任務之間無沖突的時序關系；當zij=1時，約束（3）轉換為sj≥τi+si，即任務tj在任務ti之后，而約束（4）無效；當zij=0 時，約束（4）轉換為si≥τj+sj，即任務ti在任務tj之后，而約束（3）無效。約束（5）建立了整個系統測試完工時間與測試任務之間的關系，即測試結束時間Tmax為所有測試任務結束時間的最大值。約束（6）和（8）為相應的決策變量定義。

2 H-ABC算法設計

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

不同的是，在全局個體優化搜索流程中，每次進入鄰域搜索模塊的是一個順序選擇個體和一個經過二進制選擇的個體；而進入部分個體強化搜索流程中鄰域搜索模塊兩個個體均為經過二進制選擇的個體。當執行完全局個體優化和部分個體強化搜索流程后，則會在少量個體淘汰搜索流程階段對超過限定迭代次數而未優化的個體進行淘汰。最后，經過一次迭代之后更新全局最優個體記錄。H-ABC 算法的基本流程如圖1所示。

圖1 優化算法基本流程Fig.1 Flow chart of the optimization algorithm

圖1中的二進制選擇主要用來進行高質量個體的選擇，其操作為從種群中連續隨機選擇兩個不同的個體，然后選擇這對個體中最佳的（適應度值最高的）作為二進制選擇的輸出個體。

2.1 時序遞歸搜索技術

時序遞歸搜索技術是為了找到一系列任務隱含序列，這些序列不違反屬于每個待測單元任務的預定測試順序，然后使用找到的隱含序列糾正ABC 算法的單個編碼。讓序列表示包含受限制任務w的待測單元的序列，Zw是包含輸出子序列?Zw的矩陣。此外，Qw=是一個標準序列。標簽設置（Lebel Settings，LS）算法是一個典型的遞歸過程，li=(i，，)表示LS 中的標簽，其中i是任務編碼，是在任務i結束的分區計劃，是任務集，可在節點i擴展。假設lj=(j，，)是li的后繼標簽，因此可以根據擴展方程對li進行擴展，如式（9）所示。

2.2 鄰域搜索技術

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

多點插入算子：基于既定的交換點數量與兩個個體，通過給定的規則生成子個體。Nnbr表示為既定交換的個體中的節點數量。例如，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中隨機選擇Nnbr（通常Nnbr=3）個保留點位，則包含保留點位的Xt可以被表示為

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

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

2.3 局部搜索技術

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

本文綜合多種搜索技術，可以有效解決多模態問題即存在多個局部最優解的問題，可以更好地探索全局搜索空間，減少陷入局部最優解的風險。同時，可以更好地處理問題的多樣性，將問題分解為更小的可管理部分，并針對每個部分選擇合適的搜索策略。而傳統的啟發式算法多采用單一搜索技術求解最優序列，求解效率低，易陷入局部最優，面對復雜問題甚至可能無法求出最優解。

3 實例分析

本部分首先采用隨機生成的算例測試H-ABC 的效率和最優性。其中，對于小規模問題采用整數規劃精確算法（Mixed Integer Pragramnrg，MIP）作為HABC的對比算法，驗證H-ABC的最優性和求解效率。此外，采用了隨機生成的大規模算例n=100，以驗證H-ABC 算法的極限性能。測試用例提供了小規模算例的具體數據，并通過甘特圖展示了大小規模算例的求解結果。

其次，在并行測試任務的真實案例上對算法的性能和優化過程進行了進一步的驗證，對優化結果和迭代過程進行了展示。

3.1 小規模用例算法性能測試

小規模測試用例1 如表1 所示，規模為任務數量m=8，資源數量n=7的測試用例數據。

表1 小規模測試用例1Tab.1 Small-scale test example 1

表1 展示了規模為任務數量為m=8 以及資源數量為n=7的一個小規模算例，其中該算例沒有任務間的時序約束。表1的算例分別調用了基于MIP模型的商業求解器以及H-ABC 算法求解。兩算法都求解到了該算例的最優解，即最優完工時間為Tmax=47，兩算法都在1 秒內求解到最優解，其最優解的甘特圖如圖2所示。

圖2 小規模測試用例1結果甘特圖Fig.2 Gantt chart of example 1

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

表2 小規模測試用例2Tab.2 Small-scale test example 2

表2展示了任務數量為15以及資源數量為5的一個小規模算例，其中該算例有預定時序約束。表2的算例同樣分別調用了MIP模型以及H-ABC算法求解。兩算法都求解到了該算例的最優解，即最優完工時間為Tmax=412。兩種算法都在7 s內求解到最優解，其最優解的甘特圖如圖3所示。

圖3 小規模測試用例2結果甘特圖（有時序約束）Fig.3 Gantt diagchart ram of example 2（with temporal constraints）

圖4 展示了表2 數據下沒有預定時序約束的算例結果。兩算法都求解到了該算例的最優解，即最優完工時間為Tmax=412，MIP 的求解時間為122.6 s，H-ABC的求解時間小于10 s。MIP模型在無時序約束的問題下，求解性能會顯著下降。相比于MIP 模型，H-ABC在求解大規模算例方面有著較大優勢。

圖4 小規模測試用例2結果甘特圖（無時序約束）Fig.4 Gantt chart of example 2（without temporal constraints）

3.2 大規模用例算法性能測試

大規模算例：任務數量m=100，資源數量n=10，結果如圖5所示。

圖5 大規模測試用例結果甘特圖Fig.5 Gantt chart of large-scale test example

對大規模算例，H-ABC 算法可以完全滿性能需求。H-ABC 搜索到最小的完工時間為Tmax=3 964，HABC 的求解時間約為412 s。對于該規模的問題，MIP模型以及常用求解已無法處理。相比現行傳統求解器對該問題的求解性能，H-ABC 在求解加大規模算例方面有極大優勢。

3.3 算法優化流程展示

圖6 至圖9 展示了任務數為15，資源數為5 時的規模示例調用H-ABC算法進行迭代收斂的相關結果。其中，鄰域搜索概率為0.7，局部搜索概率為0.3，最大迭代次數為100。完工時間隨迭代次數的收斂曲線如圖6所示。圖7至圖9則分別展示了第1次、第4次及第5次迭代結果的甘特圖，相應的完工時間分別為438 s、415 s、412 s。

圖6 H-ABC求解上述15×5規模示例的算法收斂Fig.6 Algorithm convergence process of the 15×5 scale example

圖7 第1次迭代結果的甘特圖：完工時間438 sFig.7 Gantt chart of the first iteration: completion time 438 s

圖8 第4次迭代結果的甘特圖：完工時間415Fig.8 Gantt chart of the fourth iteration: completion time 415

圖9 第5次迭代結果的甘特圖：完工時間412 sFig.9 Gantt chart of the 5th iteration: completion time 412 s

圖10和圖11分別展示了任務數為46和80的大規模測試的結果，由于測試任務的規模較大，難以用甘特圖去展示其迭代結果，因此只繪制了完工時間和CPU迭代耗時的收斂曲線。由圖10a可以看出，完工時間在迭代40次左右趨于穩定，耗時1 064 s；圖10b顯示了任務數為46 時，進行100 次迭代CPU 耗時229.23 s。當測試任務達到80 次時，完工時間收斂于2 493 s，算法迭代CPU 耗時1 113.62 s，具體結果如圖11a和11b所示。

圖10 H-ABC求解46×10規模示例性能展示Fig.10 Performance of H-ABC solving 46×10 scale example

圖11 H-ABC求解80×10規模示例性能展示Fig.11 Performance of H-ABC solving 80×10 scale example

4 結束語

H-ABC 算法可以通過迭代的方式找到測試任務的最優方案，極大縮短測試流程所用的總時間。通過小規模用例和大規模用例測試，H-ABC 算法都可以實現目標，驗證了算法的普適性。本算法可應用于相關弱約束條件復雜內容執行過程的優化處理，較傳統MIP算法表現出更高的收斂效率和執行效果。