基于H-ABC算法的并行測試任務(wù)優(yōu)化研究

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

（1.北京宇航系統(tǒng)工程研究所，北京，100076；2.北京交通大學(xué)，北京，100044）

0 引言

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

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

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

1 H-ABC算法理論研究

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

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

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

b）占用資源的時間消耗等于相關(guān)測試任務(wù)的時間消耗；

c）所有測試任務(wù)的排序必須滿足預(yù)定的技術(shù)測試順序；

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

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

該問題的混合整數(shù)規(guī)劃線性模型建立如下：

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

2 H-ABC算法設(shè)計

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

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

圖1 優(yōu)化算法基本流程Fig.1 Flow chart of the optimization algorithm

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

2.1 時序遞歸搜索技術(shù)

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

2.2 鄰域搜索技術(shù)

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

多點插入算子：基于既定的交換點數(shù)量與兩個個體，通過給定的規(guī)則生成子個體。Nnbr表示為既定交換的個體中的節(jié)點數(shù)量。例如，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中保留點位的其他數(shù)值并依次填充入Xt。最終的Xt可以被重新生成為Xt=（6，5，3，2，9，1，7，8，4，10）。上述過程是多點插入算子的標(biāo)準(zhǔn)流程，多點插入算子擅長于在調(diào)度問題中更大幾率發(fā)現(xiàn)質(zhì)量更高的解。

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

2.3 局部搜索技術(shù)

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

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

3 實例分析

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

其次，在并行測試任務(wù)的真實案例上對算法的性能和優(yōu)化過程進(jìn)行了進(jìn)一步的驗證，對優(yōu)化結(jié)果和迭代過程進(jìn)行了展示。

3.1 小規(guī)模用例算法性能測試

小規(guī)模測試用例1 如表1 所示，規(guī)模為任務(wù)數(shù)量m=8，資源數(shù)量n=7的測試用例數(shù)據(jù)。

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

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

圖2 小規(guī)模測試用例1結(jié)果甘特圖Fig.2 Gantt chart of example 1

小規(guī)模測試用例2 如表2 所示，規(guī)模為任務(wù)數(shù)量為15，資源數(shù)量為5的測試用例數(shù)據(jù)。

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

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

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

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

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

3.2 大規(guī)模用例算法性能測試

大規(guī)模算例：任務(wù)數(shù)量m=100，資源數(shù)量n=10，結(jié)果如圖5所示。

圖5 大規(guī)模測試用例結(jié)果甘特圖Fig.5 Gantt chart of large-scale test example

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

3.3 算法優(yōu)化流程展示

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

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

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

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

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

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

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

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

4 結(jié)束語

H-ABC 算法可以通過迭代的方式找到測試任務(wù)的最優(yōu)方案，極大縮短測試流程所用的總時間。通過小規(guī)模用例和大規(guī)模用例測試，H-ABC 算法都可以實現(xiàn)目標(biāo)，驗證了算法的普適性。本算法可應(yīng)用于相關(guān)弱約束條件復(fù)雜內(nèi)容執(zhí)行過程的優(yōu)化處理，較傳統(tǒng)MIP算法表現(xiàn)出更高的收斂效率和執(zhí)行效果。