覆蓋表生成的遺傳算法并行化

魏晶+王燕+徐家喜

摘要：啟發(fā)式搜索算法因其能夠生成規(guī)模較小的覆蓋表，一直是組合測試中覆蓋表生成主要技術(shù)之一。然而，因該類算法需要較長的計算時間，在實際應(yīng)用中往往受限。近年來，一些研究對啟發(fā)式搜索算法進行并行化，以提高算法速度。但這些研究未能全面考慮影響并行化效果的各種因素，如測試模型、覆蓋強度以及搜索算法配置等。為此，該文選取了8個測試模型，使用遺傳算法進行2-3維覆蓋表的生成，系統(tǒng)地探索了影響遺傳算法并行化性能的因素，從而為遺傳算法并行化提供理論和實踐基礎(chǔ)。

關(guān)鍵詞：組合測試；覆蓋表；遺傳算法；并行化

1背景

近年來，軟件系統(tǒng)的功能日益強大，其運行環(huán)境也具有分布式化、網(wǎng)絡(luò)化和復(fù)雜化等特點。為支持多平臺和多場景，大部分軟件系統(tǒng)都被設(shè)計成可配置系統(tǒng)。但這也導(dǎo)致這些系統(tǒng)的測試面臨龐大的組合空間。當(dāng)配置選項較多時，要進行窮盡測試幾乎是不可能的，也是不切實際的。例如，對于一個有10個參數(shù)、每參數(shù)3個取值的待測系統(tǒng)，它的組合測試空間在不考慮約束的情況下將高達3。為此，我們需要對巨大的組合測試空間進行抽樣，組合測試就是其中一種抽樣測試。組合測試（Combinatorial Testing，CT）采用系統(tǒng)的抽樣機制對參數(shù)間的交互作用進行有針對性的覆蓋，從而極大地減少測試用例的規(guī)模。已有研究表明，軟件系統(tǒng)中大約70%的故障是由兩個參數(shù)間的交互作用引起的，并且與故障相關(guān)的參數(shù)個數(shù)一般不超過6個，因此CT是一種能有效地檢測系統(tǒng)中交互式故障的測試方法。

組合測試使用覆蓋表（Covering Arrays，CA）作為測試用例集，它的重要研究內(nèi)容之一是如何為待測系統(tǒng)生成一個滿足特定覆蓋需求且規(guī)模最小的覆蓋表。目前生成覆蓋表的方法主要有3類：貪心方法、啟發(fā)式搜索方法以及數(shù)學(xué)方法。數(shù)學(xué)方法能快速地生成理論上規(guī)模最小的覆蓋表，但其對參數(shù)及參數(shù)取值個數(shù)有一定的限制；貪心算法和隨機算法雖然在參數(shù)上沒有限制，但其生成的覆蓋表規(guī)模往往較大。與上述方法相比，啟發(fā)式搜索算法如禁忌搜索算法、遺傳算法、模擬退火算法、蟻群算法、粒子群算法等既能生成較小規(guī)模的覆蓋表，又能不受參數(shù)及其取值個數(shù)限制，應(yīng)用于任何待測系統(tǒng)。近年來啟發(fā)式搜索算法受到眾多研究者的青睞，然而啟發(fā)式搜索算法通常需要較長運行時間，這限制了其在實際中的應(yīng)用。

為了提高啟發(fā)式搜索算法運行速度，一些研究者開始對啟發(fā)式算法進行并行化。例如，基于Hadoop MapReduce進行遺傳算法并行化，并為開源軟件庫Apache Commons Primi—tives生成JUnit測試用例集。而基于Spark進行遺傳算法并行化，并選取四個測試模型進行2維覆蓋表的生成。雖然這些研究能不同程度地提高算法速度，但也存在一些不足之處：第一，文獻選取的待測實例過少，不足以說明并行化效果。例如，只有一個待測實例，也只有四個。第二，啟發(fā)式搜索算法通常存在多個影響算法性能的決策點，但現(xiàn)有的研究未能考慮這些決策點不同取值對并行化效果的影響。針對已有工作不足，本文從如下兩方面開展工作：

第一，選取多種遺傳算法決策點取值，探索算法決策點對并行化影響。

第二，選取多種測試模型和覆蓋強度，探索測試模型和覆蓋強度對并行化影響。

本文剩余部分內(nèi)容安排如下：第2節(jié)介紹相關(guān)背景知識，如覆蓋表，啟發(fā)式搜索算法等基本概念；第3節(jié)給出遺傳算法生成覆蓋表框架以及并行化方法；第4節(jié)為具體實驗及實驗結(jié)果分析；第5節(jié)討論影響實驗結(jié)果的有效性因素；最后一節(jié)給出本文結(jié)論及未來研究方向。

2相關(guān)知識

2.1覆蓋表相關(guān)概念

組合測試使用覆蓋表CA作為測試用例集，CA是一個大小為NXK大小為N×K的矩陣，通常表示如下

其中N為覆蓋表的大小即測試用例條數(shù)，t為覆蓋強度，待測系統(tǒng)參數(shù)個數(shù)，其中取值個數(shù)為v，的參數(shù)有。覆蓋表的一個重要性質(zhì)是表中任何一個Nxt子矩陣都能覆蓋相應(yīng)t個參數(shù)所有可能t維取值組合至少一次，覆蓋強度為t的覆蓋表稱t-way或t維覆蓋表。這里的參數(shù)可為待測系統(tǒng)配置選項、輸入以及消息事件等。在未作特殊說明情況下，本文用N表示覆蓋表大小，k表示參數(shù)個數(shù)，v表示所有參數(shù)取值集合，表示第i個參數(shù)取值集合，表示第i個參數(shù)取值個數(shù)。

例如，表1為一部手機通話功能的簡單測試模型，該測試模型共5個參數(shù)，每參數(shù)3個取值。對于該系統(tǒng)，可找到一個大小為11的覆蓋進行2-way測試，對應(yīng)的2-way覆蓋表可表示為CAfll；2，3），覆蓋表具體內(nèi)容見表2。

容易看出，該手機通話功能測試模型中的任意兩個參數(shù)的9個取值組合在表2中都至少出現(xiàn)一次。例如號碼來源和對方系統(tǒng)設(shè)置這兩個參數(shù)的9個取值組合（直接輸入，無限制）、（直接輸入，黑名單）、（直接輸入，呼叫轉(zhuǎn)移）、（電話簿，無限制）、（電話簿，黑名單）、（電話簿，呼叫轉(zhuǎn)移）、（通話記錄，無限制）、（通話記錄，黑名單）、（通話記錄，呼叫轉(zhuǎn)移）分別出現(xiàn)在表2中第4f或91行、第7行、第1行、第11行、第5行、第8行、第2行、第3行、第6（或10）行。

2.2啟發(fā)式搜索算法

啟發(fā)式搜索算法在覆蓋表生成時，通過適應(yīng)度函數(shù)將覆蓋表生成問題轉(zhuǎn)化為函數(shù)優(yōu)化問題，然后利用某搜索算法來解決函數(shù)優(yōu)化。目前常見用于覆蓋表的啟發(fā)式算法主要有：遺傳算法、粒子群優(yōu)化算法、蟻群算法、爬山算法、模擬退火算法、禁忌搜索算法等。

本文以遺傳算法為例，探索影響啟發(fā)式搜索算法并行化的因素。在接下來的第3節(jié)首先對遺傳算法生成覆蓋表的流程以及并行化方法進行介紹。

3遺傳算法生成覆蓋表框架及并行化

遺傳算法（Genetic Algorithm）是一種通過模擬自然世界生物進化過程，探索問題最優(yōu)解的演化搜索算法，該算法已被廣泛地用于復(fù)雜的優(yōu)化問題。在遺傳算法中，問題的一組候選解以染色體的形式構(gòu)成算法的初始種群，算法對每一代種群中的染色體進行交叉變異，然后通過適應(yīng)度函數(shù)值這一評價標(biāo)準(zhǔn)淘汰適應(yīng)值較差的染色體，保留適應(yīng)值較好染色體進人下一代，直到某一代種群中出現(xiàn)適應(yīng)值滿足問題要求的染色體，該染色體即為問題的最優(yōu)解。

3.1遺傳算法生成覆蓋表流程

考慮到覆蓋表是一個NxK大小的矩陣，因此本文將種群中的染色體也稱個體設(shè)置為NxK大小的矩陣，個體的適應(yīng)度函數(shù)值為矩陣所覆蓋的t維取值元組數(shù)。生成思路為：首先采用某種方法初始化種群中的每個個體，然后通過一定的交叉變異等進化使種群中的某個體達到全覆蓋，那么這個個體便是最終的覆蓋表，算法框架如算法1。

在算法1中，行1一行5為覆蓋表生成初始化工作；行6至行18構(gòu)成的循環(huán)為種群的進化；行19返回種群中適應(yīng)度函數(shù)值最大的個體。當(dāng)適應(yīng)度函數(shù)最大值為NATf需要被覆蓋的t維參數(shù)取值元組數(shù)）時，對應(yīng)個體即為覆蓋表。在進化過程中，首先在種群中按照一定的算法選取一半個體作為雙親，然后進行兩兩交叉（行8至行11），交叉產(chǎn)生的子代依一定的概率進行變異（行13），最后再用這些子代去替換父代中適應(yīng)度函數(shù)值較差的那些個體進行種群更新（行15）。

顯然，算法1只提供了遺傳算法生成覆蓋表的框架，在具體實現(xiàn)時還需要確定種群初始化方法、種群大小、最大迭代次數(shù)、雙親選擇算法、交叉算法、變異概率等。這些決策點會影響算法的性能，它們的取值我們將在第5節(jié)實驗部分進行討論。

我們注意到，在算法1的輸人中需要給出覆蓋表大小N，為了降低測試成本，通常該值是算法針對某個待測系統(tǒng)所能生成的覆蓋表規(guī)模最小值。但事實上卻很難事先確定這一值。本文解決的方法是：我們在算法1外面加了一層循環(huán)，用來確定N。首先讓N從一個較大值開始保證該規(guī)模的覆蓋表能成功生成；如果某一規(guī)模N的覆蓋表成功生成，則將N=N-1；然后重新利用算法1生成新規(guī)模覆蓋表；否則，算法結(jié)束，N-1便是所能生成的覆蓋表規(guī)模最小值。

3.2遺傳算法生成覆蓋表并行化

并行計算（Parallel Computing）是指同時使用多種計算資源解決計算問題的過程，是提高計算機系統(tǒng)計算速度和處理能力的一種有效手段。它的基本思想是利用多個處理器來協(xié)同求解同一問題，即將被求解的問題分解成若干個部分，各部分均由一個獨立的處理機來并行處理。并行計算系統(tǒng)既可以是專門設(shè)計的、含有多個處理器的單臺計算機，也可以是以某種方式互連的若干臺的獨立計算機構(gòu)成的集群。通過并行計算集群完成數(shù)據(jù)的處理，再將處理的結(jié)果返回給用戶。本文采用單臺計算機進行本地并行化，集群下的并行化將是我們下一步工作。

在編程模型方面，本文選用了Java提供的ForkJoin框架。在該框架下，對于一個能被分解成多個子任務(wù)，并且通過組合多個子任務(wù)的結(jié)果，就能夠獲得最終結(jié)果的應(yīng)用，軟件開發(fā)人員僅需關(guān)注如何劃分任務(wù)和組合中間結(jié)果，其余工作，如同步、通信、死鎖等各種并行相關(guān)事務(wù)由ForkJoin來完成，這樣大大簡化了并行程序的編寫。ForkJoin原理如圖1所示。

在圖1中，當(dāng)原始任務(wù)Task0的規(guī)模比設(shè)定的閾值大，則按照向下箭頭將其一分為二拆分成2個子任務(wù)Task0-1和Task0-2。如果Task0-1、Task0-2的規(guī)模仍然比設(shè)定的閾值大，則繼續(xù)拆分它們，這樣得到4個子任務(wù)Task0-1-1、Task0-1-2、Task0-2-1、Task0-2-2。如果這4個子任務(wù)的規(guī)模不再大于設(shè)定的閾值，則開始執(zhí)行這些子任務(wù)，并將執(zhí)行結(jié)果按照向上箭頭進行合并，這樣可得到最終結(jié)果。

1）任務(wù)拆分

由圖1可以看出，并行化的第一步是任務(wù)拆分，一個任務(wù)能被拆分成多個子任務(wù)的條件是這些子任務(wù)之間需要相互獨立，能并行執(zhí)行。在遺傳算法生成覆蓋表的算法1中，行6至行18構(gòu)成的循環(huán)是算法的主體，因此，將該部分進行并行化能有效提高算法執(zhí)行效率。容易看出，在算法1的循環(huán)中，每次循環(huán)都依賴前一次的結(jié)果，因此不同循環(huán)之間不能并行進行，此時只能考慮將循環(huán)中需要執(zhí)行的比較耗時的操作進行拆分。我們注意到算法1中行12所描述的交叉操作共涉及到pSize/4對雙親兩兩交叉，這些雙親交叉之間相互獨立，因此可以拆分，利用不同子任務(wù)實現(xiàn)對不同雙親的交叉。同理，子代變異（行13）、子代個體適應(yīng)度函數(shù)值計算（行14）以及種群更新（行15）也都可以拆成多個可并行執(zhí)行的子任務(wù)，圖2給出了算法1可以并行執(zhí)行的操作，用加粗部分表示。

2）編程實現(xiàn)

任務(wù)拆分后，接下來進行編程實現(xiàn)，下面以子代的變異并行化為例，對ForkJoin框架下的并行化編程進行說明。

首先，將所有需要進行變異的子代存入一數(shù)組offspring中。

然后，創(chuàng)建一個ForkJoin任務(wù)，如

上式中MutateTask是一個用戶自定義類。為了實現(xiàn)Fork-Join任務(wù)，MutateTask需要繼承Java提供的RecursiveAction或者RecursiveTask類，這兩個類的區(qū)別是前者用于任務(wù)沒有返回結(jié)果的場景，后者用于任務(wù)有返回結(jié)果的場景，MutateTask具體實現(xiàn)請參見算法2。其中參數(shù)offspring為第一步中定義的數(shù)組，offspring.Jen為offspring中的元素個數(shù)也就是子代的個體數(shù)。參數(shù)1和offspring.len表示需要變異的個體從第一個子代個體到最后一個子代個體，即對所有子代個體進行變異。

最后，通過ForkJoinPool來執(zhí)行任務(wù)，如

在MutateTask類中：

首先，MutateTask選擇繼承RecursiveAction（行1），因為變異后的子代直接存放回原數(shù)組offspring中，因此不需要返回結(jié)果。

接著，在該類的構(gòu)造函數(shù)中進行相關(guān)數(shù)據(jù)賦值（行5-9），這些數(shù)據(jù)包括存放子代的數(shù)組offspring，本次任務(wù)中需要進行變異的個體在offspring中的位置下界beg和上界end。

最后，重寫computer方法（行11-23）。在compute方法中，首先判斷當(dāng)前任務(wù)中需要進行變異的個體個數(shù)是否大于設(shè)定的閾值（行12）。若不大于，則對規(guī)定區(qū)間中的每個個體逐個進行變異（行19-21）。否則，把當(dāng)前任務(wù)一分為二（行13-15），然后啟動這兩個子任務(wù)的執(zhí)行（行16）。由于這兩個子任務(wù)又屬于MutateTask類，因此在它們的執(zhí)行過程中又會進人該con-pute方法。該方法體現(xiàn)了圖1所示的Fork/Join原理，通過遞歸來完成任務(wù)的拆分和計算，它是區(qū)別于其他普通類的關(guān)鍵之處。

有關(guān)ForkJoin框架并行化編程更多細節(jié)請參考Java相關(guān)幫助文檔。

3實驗及結(jié)果分析

并行化是提高啟發(fā)式搜索算法生成覆蓋表速度的有效手段，但并行化性能通常會受到多種因素的影響，本文通過研究遺傳算法并行化明確了影響搜索算法并行化性能的主要決策點，并進一步闡述了待測系統(tǒng)和覆蓋強度對搜索算法并行化性能的影響。

3.1實驗設(shè)計

為了回答上述問題，我們首先選取多種不同測試模型和覆蓋強度，然后在某種決策點配置下分別使用串、并行遺傳算法進行相應(yīng)覆蓋表生成，接著改變決策點取值重復(fù)實驗，最后通過比較和分析并行化前后覆蓋表生成速度，來探索影響搜索算法并行化性能的因素。

本文衡量算法覆蓋表生成速度的方法是：實驗中記錄每個覆蓋表生成時間與所經(jīng)過迭代次數(shù)，然后計算出兩者的比值，將該比值記為單次迭代時間。每個實驗重復(fù)5次，最后用5次的平均單次迭代時間來衡量算法速度。

這里用單次迭代時間來衡量算法的速度，主要是考慮到在實驗次數(shù)較少的情況下，覆蓋表生成時間隨機性比較大，然而單次迭代時間卻能基本保持不變，因此用單次迭代時間較覆蓋表生成時間更能真實地反映算法本身速度。

本文從中選取了8個測試模型（見表3），實驗中，對每個模型分別使用串、并行遺傳算法進行2-3維覆蓋表生成。

為了描述方便，我們將串、并行遺傳算法分別命名為SGA（sequential Genetic Algorithm）和PGA（Parallel Genetic Algo-rithm）。

實驗選用的軟硬件配置為：Intel i7-4790CPU、3.60GHZ、8.0GB內(nèi)存、64位Windowsl0、32位JAVA7。

3.2實驗結(jié)果

1）決策點初始配置及實驗結(jié)果

決策點的配置會影響算法生成覆蓋表的時間和所生成的覆蓋表規(guī)模。然而大量研究表明，實際上不存在任何一種決策點配置能夠?qū)θ我獯郎y系統(tǒng)在最短時間內(nèi)生成最小覆蓋表。本文旨在研究并行化對算法速度的影響，因此不要求這些決策點取值都達到最優(yōu)，故決策點初始配置選用了一些常用取值。初始配置具體如下：

隨機初始化種群、種群大小80、根據(jù)個體適應(yīng)度函數(shù)值利用輪盤賭算法選擇雙親、單點交叉、變異概率0.01。兩雙親單點交叉時，首先隨機生成交叉位置pos，其中然后互換兩雙親pos前后的行，這樣產(chǎn)生兩子代個體；子代變異時子代個體對應(yīng)矩陣中的每個元素以0.01的概率隨機改變?nèi)≈怠?/p>

SGA和PGA在初始配置下的實驗結(jié)果如表4所示。其中，size為覆蓋表規(guī)模，SGAtime和PGAtime分別為SGA和PGA生成覆蓋表的單次迭代時間（單位為秒），speed up為兩者的比值，該比值反映了PGA的速度與SGA的速度的比值，因此，可以用該指標(biāo)表示并行化加速情況，稱其為并行化加速比。

2）決策點新配置及實驗結(jié)果

接下來，我們首先改變遺傳算法的種群大小，將其設(shè)置為160，算法其它參數(shù)配置與初始配置相同。為了使結(jié)果不受覆蓋表行數(shù)的影響，覆蓋表行數(shù)也保持與前一實驗相同。在新配置下，重新對表3中的測試模型進行2-3維覆蓋表生成，實驗結(jié)果如表5。

對比表4和表5可知，增大種群大小明顯提高了并行化加速比。平均來看，遺傳算法的加速比由原來的3.38倍提高到6.1倍。這一結(jié)果有力說明了，種群大小是影響并行化性能的重要因素。分析其中原因不難發(fā)現(xiàn)，在硬件資源足夠多和不考慮子任務(wù)之間通信時間方面開銷的情況下，并行執(zhí)行的子任務(wù)數(shù)是影響并行化提速的主要原因，并行執(zhí)行的子任務(wù)數(shù)越多，并行化加速越快。對于遺傳算法，由3.2節(jié)可以看出，種群大小是決定并行執(zhí)行子任務(wù)數(shù)的主要因素，因此，增大種群大小明顯提高了并行化加速比。

隨后，我們又依次改變種群初始化方法、雙親選擇策略、交叉方法、變異概率等，實驗結(jié)果表明，改變這些決策點的配置都不會明顯影響遺傳算法并行性能。限于篇幅，本文沒有給出這些實驗具體結(jié)果。

3）測試模型及覆蓋強度對并行化影響

進一步觀察表4和表5還可以發(fā)現(xiàn)，在同一算法配置下，不同測試模型及覆蓋強度下并行化加速也不同。例如，在表5中，s1模型的2維并行化加速僅為1.82，而s8模型的3維并行化加速高達6.27。

為了衡量測試模型和覆蓋強度對并行化的影響，我們根據(jù)表4-表7中的數(shù)據(jù)，給出了串行單次迭代時間與并行化加速比speedup之間的曲線圖，具體如圖3和圖4。在這些圖中，橫坐標(biāo)為串行單次迭代時間，縱坐標(biāo)為并行化加速比。我們知道，不同測試模型及覆蓋強度的覆蓋表串行生成時間是不同的。測試模型越復(fù)雜（即待測系統(tǒng)中的參數(shù)個數(shù)和每個參數(shù)取值個數(shù)越大），覆蓋強度大越大，覆蓋表串行生成時間就越長，因此覆蓋表串行生成時間能反映出測試模型的復(fù)雜度和覆蓋強度的大小。

由圖3和圖4可看出，對于遺傳算法，無論種群大小是80還是160，總體上，并行化加速比開始時隨著串行單次迭代時間增加而快速增加，然后逐漸趨于平穩(wěn)。這是因為，當(dāng)測試模型比較簡單、覆蓋強度比較小時，即串行生成時間比較短，此時并行算法中的子任務(wù)創(chuàng)建、銷毀以及子任務(wù)之間的通信等所消耗的時間占總生成時間的比例比較大，導(dǎo)致并行化加速比比較??；此后隨著測試模型復(fù)雜度以及覆蓋強度的增大，覆蓋表生成時間隨之增大，因此并行通信額外消耗的時間占總生成時間的比例將逐漸降低，并行加速比呈現(xiàn)出上升趨勢；最后當(dāng)單次迭代時間的增加到一定值后，這部分額外時間相對總生成時間可以忽略不計，此時并行加速比趨于穩(wěn)定。

3.3實驗結(jié)論

首先，并行執(zhí)行的子任務(wù)數(shù)是影響并行化加速的重要因素。對于遺傳搜索算法，種群大小是決定并行執(zhí)行的子任務(wù)數(shù)主要因素。因此，種群大小是影響遺傳算法并行化性能的主要決策點。

其次，測試模型和覆蓋強度也會影響并行化性能?？傮w上，并行化加速比隨著測試模型中的參數(shù)個數(shù)、每個參數(shù)取值個數(shù)以及覆蓋強度的增加而增加并逐漸趨于穩(wěn)定。

4影響實驗結(jié)果有效性因素

實證性和實驗性研究通常都存在影響實驗結(jié)果有效性的因素，本文也不例外，下面我們主要從三個方面對影響本文實驗結(jié)果有效性的因素進行分析：

首先，本文只選用了遺傳算法作為啟發(fā)式搜索算法研究對象，更多的搜索算法能帶來更準(zhǔn)確的實驗結(jié)果。

其次，本文雖然選取了一批具有代表性的實例作為實驗對象，但對于其它的實例實驗結(jié)果可能會有所變化。

最后，由于實驗較為耗時，本文只對實驗重復(fù)了5次，利用單次迭代時間來衡量算法速度。雖說單次迭代時間較總生成時間更為穩(wěn)定，但仍不能排除隨機因素的影響。5結(jié)論及未來研究方向

覆蓋表生成作為組合測試關(guān)鍵問題之一，一直受到工業(yè)界和學(xué)術(shù)界的重視。為了提高啟發(fā)式搜索算法速度，一些研究者開始對算法進行并行化。本文在已有的研究工作基礎(chǔ)上，系統(tǒng)地探索了遺傳算法決策點和測試模型以及覆蓋強度對并行化性能的影響。

實驗結(jié)果表明，對于遺傳算法，種群大小是影響算法并行化提速的重要因素。另外，測試模型和覆蓋強度也會對算法并行化性能產(chǎn)生一定影響。

目前，本文利用ForkJoin框架進行算法本地并行化，但由于受到單機硬件資源限制，并行化加速有限。因此，在下一步工作中，我們計劃將實驗遷移到分布式或云平臺環(huán)境中，利用這些平臺超強的并行化計算能力更快更好地實施實驗，進一步研究啟發(fā)式搜索算法并行化。