基于混合人工蜂群算法的并行測試任務(wù)優(yōu)化研究

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

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

0 引言

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

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

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

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

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

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

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

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

1 并行測試任務(wù)調(diào)度問題描述

1.1 相關(guān)概念介紹

1)并行度：并行度是指在并行計算中同時執(zhí)行的任務(wù)或線程的數(shù)量。在并行計算中，可以將一個任務(wù)分解成多個子任務(wù)并在多個處理器或計算節(jié)點(diǎn)上并行執(zhí)行。并行度是用于衡量并行計算系統(tǒng)中的任務(wù)并行性能的一個指標(biāo)。如果并行度越高，則意味著系統(tǒng)能夠同時處理更多的任務(wù)或線程，從而提高計算性能。并行度通常可以通過以下公式計算：

(1)

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

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

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

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

1.2 組合優(yōu)化問題描述

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

圖1 并行測試任務(wù)調(diào)度典型實(shí)例

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

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

1.3 并行測試任務(wù)數(shù)學(xué)模型描述改進(jìn)

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

為滿足并行測試任務(wù)的需求，并結(jié)合本文所研究實(shí)際問題特點(diǎn)的抽象，并行測試任務(wù)調(diào)度模型進(jìn)行如下改進(jìn)：

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

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

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

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

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

1.4 優(yōu)化問題數(shù)學(xué)建模

為建立一個標(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ī)劃線性模型建立如下：

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)為模型的目標(biāo)函數(shù)，即最小化整個系統(tǒng)的總測試時間。剩余公式定義了本模型的約束和決策變量。約束(3)為各測試任務(wù)完工時間的時序約束。當(dāng)TS(i，j)=1時，約束1轉(zhuǎn)化為si+τi≤sj+τj，即要求任務(wù)tj的結(jié)束時間大于任務(wù)ti；反之，模型中沒有任務(wù)tj與任務(wù)ti的結(jié)束約束。約束(4)是保證多任務(wù)占用資源的非沖突約束。約束(6)～(8)為相應(yīng)的決策變量定義。

2 混合人工蜂群算法設(shè)計

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

2.1 算法總體設(shè)計

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

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

圖2 算法流程圖

當(dāng)在既定的優(yōu)化場景中通過混合人工蜂群算法的數(shù)據(jù)流輸入接口傳入原始的數(shù)據(jù)之后，就會將其存儲在混合人工蜂群算法的變量中，通過調(diào)用混合人工蜂群算法內(nèi)部的函數(shù)對相應(yīng)的原始數(shù)據(jù)進(jìn)行一定的操作，最后通過混合人工蜂群算法的數(shù)據(jù)流輸出接口將處理后的數(shù)據(jù)返還給外部。

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

(9)

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

圖3 時序約束的遞歸路徑

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

2.3 鄰域搜索技術(shù)

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

多點(diǎn)插入算子(Multi-insertion)：基于既定的交換點(diǎn)數(shù)量與兩個個體，通過給定的規(guī)則生成子個體。假設(shè)Xt是一個按照順序選擇的個體，Xf為通過二進(jìn)制選擇的一個個體，即為Xt的鄰域個體。nbrNum為既定交換的個體中的節(jié)點(diǎn)數(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中隨機(jī)選擇nbrNum(通常nbrNum)個保留點(diǎn)位，則包含保留點(diǎn)位的Xt可以被表示為：

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

(10)

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

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

2.4 局部搜索技術(shù)

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

3 實(shí)驗(yàn)驗(yàn)證分析

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

3.1 小規(guī)模用例測試

小規(guī)模測試用例1如表1所示，規(guī)模：測試任務(wù)數(shù)為8，資源數(shù)為7。

表1 小規(guī)模測試用例1

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

圖5 小規(guī)模測試用例1結(jié)果甘特圖

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

表2 小規(guī)模測試用例1結(jié)果比較

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

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

表3 小規(guī)模測試用例2

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

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

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

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

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

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

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

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

混合人工蜂群算法可以在小于10 s內(nèi)完成，而整數(shù)規(guī)劃精確算法的求解時間約為123 s，遺傳算法的求解時間為230 s。這表明在沒有時序約束的情況下，混合人工蜂群算法的性能要遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)并行測試算法。

3.2 大規(guī)模用例測試

大規(guī)模算例：測試任務(wù)數(shù)為100，資源數(shù)為10。測試結(jié)果如表6所示。

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

當(dāng)測試規(guī)模擴(kuò)大到一定程度，整數(shù)規(guī)劃精確算法以及遺傳算法已經(jīng)不能完成任務(wù)，無法求得最優(yōu)解。而混合人工蜂群算法依然可以在400多秒內(nèi)搜索到最小完成時間。這表明，相比傳統(tǒng)的啟發(fā)式算法，混合人工蜂群算法在大規(guī)模測試任務(wù)下有很大的優(yōu)勢。

4 結(jié)束語

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