基于多線(xiàn)程的多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法仿真

黃小平，謝蓉蓉

(1.廣州軟件學(xué)院網(wǎng)絡(luò)技術(shù)系，廣東廣州 510990；2.西安石油大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710065)

1 引言

在科學(xué)信息技術(shù)時(shí)代，軟件已與人們生活密不可分[1]。軟件開(kāi)發(fā)的核心環(huán)節(jié)是軟件測(cè)試[2]。軟件測(cè)試主要是通過(guò)回歸測(cè)試完成，因軟件的復(fù)雜性高、規(guī)模巨大，增加回歸測(cè)試的測(cè)試強(qiáng)度和難度。據(jù)相關(guān)資料表明，回歸測(cè)試占軟件測(cè)試成本的一半以上[3]。優(yōu)先級(jí)排序準(zhǔn)則是按照軟件測(cè)試要求，選取合適的評(píng)價(jià)準(zhǔn)則。因軟件程序的越來(lái)越繁瑣，以往方法已無(wú)法達(dá)到回歸測(cè)試的標(biāo)準(zhǔn)，多目標(biāo)任務(wù)優(yōu)先級(jí)排序已經(jīng)成為當(dāng)前回歸測(cè)試中亟待解決的一個(gè)重要問(wèn)題[4-5]。

但是以往多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法非常局限，如文獻(xiàn)[6]提出基于AHP的回歸測(cè)試用例優(yōu)先級(jí)排序方法，在多目標(biāo)任務(wù)優(yōu)先級(jí)排序過(guò)程中，由于該方法計(jì)算過(guò)程非常繁瑣，導(dǎo)致多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率不佳；文獻(xiàn)[7]提出基于直覺(jué)梯形模糊信息的目標(biāo)優(yōu)先級(jí)排序方法，在多目標(biāo)任務(wù)優(yōu)先級(jí)排序過(guò)程中，由于該方法評(píng)價(jià)指標(biāo)單一化導(dǎo)致多目標(biāo)任務(wù)優(yōu)先級(jí)排序耗時(shí)間久。隨著海量數(shù)據(jù)的涌入，系統(tǒng)在同一時(shí)間里的計(jì)算強(qiáng)度也隨之增大，此時(shí)單線(xiàn)程的環(huán)境已經(jīng)無(wú)法滿(mǎn)足系統(tǒng)的運(yùn)行，導(dǎo)致系統(tǒng)運(yùn)行效率低。多線(xiàn)程可同時(shí)完成多目標(biāo)任務(wù)，提高資源使用效率。因此將多線(xiàn)程的多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法應(yīng)用在多目標(biāo)任務(wù)優(yōu)先級(jí)排序過(guò)程中，通過(guò)該方法解決回歸測(cè)試中多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率低的問(wèn)題。

2 基于多線(xiàn)程的多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法

2.1 基于多線(xiàn)程并發(fā)的多目標(biāo)演化算法

遺傳算法是演化算法中的一種算法，為采用模擬生物進(jìn)化尋找最優(yōu)解的算法。該遺傳算法運(yùn)行過(guò)程，具體內(nèi)容如圖1所示。

圖1 遺傳算法運(yùn)行流程

由圖1可知，以往多目標(biāo)遺傳算法，雖然可求解在目標(biāo)函數(shù)內(nèi)不相互占優(yōu)的多個(gè)最優(yōu)解，但是，計(jì)算過(guò)程復(fù)雜導(dǎo)致計(jì)算時(shí)間長(zhǎng)，程序反應(yīng)遲緩。因此，通過(guò)多線(xiàn)程的并發(fā)技術(shù)，提高算法的執(zhí)行效率。采用多線(xiàn)程的多目標(biāo)任務(wù)演化算法在種群基因構(gòu)造階段使種群初始化的時(shí)間減少，因該階段個(gè)體之間不用實(shí)施信息交互，只需按照實(shí)際情況完成內(nèi)容初始化。在求解個(gè)體的目標(biāo)值時(shí)，個(gè)體間獨(dú)立存在，因用戶(hù)數(shù)目與個(gè)體編碼長(zhǎng)度呈正比，導(dǎo)致求解時(shí)間會(huì)更長(zhǎng)。為了增強(qiáng)多目標(biāo)遺傳算法的效率，需通過(guò)多線(xiàn)程并發(fā)技術(shù)實(shí)施算法的演化。設(shè)計(jì)1個(gè)線(xiàn)程數(shù)固定的線(xiàn)程池規(guī)避資源浪費(fèi)問(wèn)題發(fā)生，新的固定線(xiàn)池，具體執(zhí)行過(guò)程，具體內(nèi)容如圖2所示。

圖2 新的固定線(xiàn)程池

在圖2中，線(xiàn)程調(diào)度是通過(guò)共享無(wú)界隊(duì)列實(shí)現(xiàn)，新任務(wù)在線(xiàn)程池內(nèi)無(wú)閑置的線(xiàn)程的情況下，需在隊(duì)列內(nèi)排隊(duì)，等待產(chǎn)生可用線(xiàn)程[8]。管理器是在執(zhí)行期間發(fā)生線(xiàn)程異常，任務(wù)被迫終止時(shí)，將安排新線(xiàn)程實(shí)施下一個(gè)任務(wù)。

2.2 融合選擇函數(shù)的非支配遺傳算法

為了適用多線(xiàn)程環(huán)境，通過(guò)多目標(biāo)演化算法的重構(gòu)，為深入優(yōu)化遺傳算法作鋪墊[9-11]。融合選擇函數(shù)的非支配遺傳算法在遺傳算法的個(gè)體評(píng)價(jià)機(jī)制中融入了選擇函數(shù)，對(duì)多目標(biāo)任務(wù)優(yōu)先級(jí)實(shí)施排序。多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法的過(guò)程，具體內(nèi)容如圖3所示。

圖3 多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法的過(guò)程

在圖3中，多目標(biāo)任務(wù)優(yōu)先級(jí)排序是采用融合選擇函數(shù)的非支配遺傳算法，通過(guò)設(shè)計(jì)算子，選擇適宜的方案，計(jì)算個(gè)體評(píng)價(jià)函數(shù)，選取適宜的優(yōu)化目標(biāo)完成排序。

2.2.1 編碼及算子

排序序列用種群個(gè)體描述，下面是個(gè)體編碼、算子設(shè)計(jì)過(guò)程：

1)編碼方案

利用十進(jìn)制編碼對(duì)種群個(gè)體實(shí)施編碼，優(yōu)先級(jí)排序序號(hào)用基本基因位描述。

2)選擇算子

為了選取最優(yōu)的父代個(gè)體，通過(guò)錦標(biāo)賽選取方法實(shí)現(xiàn)。

3)交叉算子

通過(guò)部分映射交叉方法實(shí)施交叉算子的匹配。部分映射交叉方法流程，如表1所示。

表1 部分映射交叉方法流程

4)變異算子

通過(guò)選取2點(diǎn)交換2點(diǎn)的值實(shí)施變異算子計(jì)算。

2.2.2 個(gè)體評(píng)價(jià)

因在遺傳算法的種群內(nèi)，個(gè)體相關(guān)度與兩個(gè)個(gè)體的相似度成正相關(guān)，與相異度成反相關(guān)。所以，在遺傳算法的個(gè)體評(píng)價(jià)內(nèi)融入選擇函數(shù)。

1)個(gè)體的相似度計(jì)算方法

為了提升收斂速度，加強(qiáng)搜尋目的，按照個(gè)體相似度描述個(gè)體評(píng)價(jià)函數(shù)內(nèi)的相似度，具體計(jì)算用式(1)描述

(1)

式中：φ1表示個(gè)體的相似度，P(xi，xj)表示xi和xj的相似度。兩個(gè)個(gè)體的相似程度是以個(gè)體編碼總長(zhǎng)度n與xi和xj相同編碼的長(zhǎng)度的比值反映。xi和xj的相似度，用式(2)描述

(2)

式中

1)個(gè)體的相異度計(jì)算方法

為了提升搜索空間的多樣性，按照個(gè)體相異度描述個(gè)體評(píng)價(jià)函數(shù)內(nèi)的相異度，具體計(jì)算用式(3)描述

(3)

式中：個(gè)體的相異度用φ2描述，xi和xj的相異度用C(xi，xj)描述。兩個(gè)個(gè)體的相異程度是以個(gè)體編碼總長(zhǎng)度n與xi和xj不同編碼的長(zhǎng)度的比值反映。xi和xj的相異度，用式(4)描述

(4)

2.2.3 優(yōu)化目標(biāo)

優(yōu)化目標(biāo)設(shè)為平均故障檢測(cè)率、有效執(zhí)行時(shí)間。

多目標(biāo)任務(wù)優(yōu)先級(jí)排序度量指標(biāo)：平均故障檢測(cè)率(Average Percentage of Fault Detection，APFD)、有效執(zhí)行時(shí)間(Effective Execute Time，EET)。

1)為了檢查出多目標(biāo)任務(wù)優(yōu)先級(jí)排序過(guò)程中，缺陷的平均累計(jì)比例是通過(guò)平均故障檢測(cè)率實(shí)現(xiàn)[12]。平均故障檢測(cè)率，用式(5)描述

(5)

式中：多目標(biāo)任務(wù)集用T描述，T中的多目標(biāo)任務(wù)數(shù)量用n描述。排序后多目標(biāo)任務(wù)集用T′描述，T′內(nèi)首次檢測(cè)到缺陷i的多目標(biāo)任務(wù)在該執(zhí)行任務(wù)內(nèi)所排的順序用TSm描述，被測(cè)軟件缺陷總數(shù)量用m描述。[0，1]為APFD的值域，平均故障檢測(cè)率與排序在前的多目標(biāo)任務(wù)檢測(cè)出的缺陷成正比，平均故障檢測(cè)率越大，表明多目標(biāo)任務(wù)優(yōu)先級(jí)排序效果最佳。

2)計(jì)算多目標(biāo)任務(wù)的故障檢測(cè)率最高執(zhí)行總時(shí)間為有效執(zhí)行時(shí)間。有效執(zhí)行時(shí)間，用式(6)描述

(6)

式中：執(zhí)行第i個(gè)多目標(biāo)任務(wù)時(shí)所消耗的時(shí)間用ETi描述。

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

為了驗(yàn)證本文方法的性能，實(shí)驗(yàn)對(duì)象選取4種測(cè)試程序。仿真運(yùn)行環(huán)境：Window 10系統(tǒng)，CPU內(nèi)存8GB。實(shí)驗(yàn)對(duì)比方法選取本文方法與文獻(xiàn)[6]基于AHP的回歸測(cè)試用例優(yōu)先級(jí)排序方法、文獻(xiàn)[7]基于直覺(jué)梯形模糊信息的目標(biāo)優(yōu)先級(jí)排序方法實(shí)施多目標(biāo)任務(wù)優(yōu)先級(jí)排序?qū)嵤┓抡?。?shí)驗(yàn)程序基本信息如表2所示。

表2 基本信息

實(shí)驗(yàn)設(shè)置迭代次數(shù)為1000次時(shí)，采用三種方法的目標(biāo)函數(shù)迭代曲線(xiàn)，結(jié)果如圖4所示。

圖4 目標(biāo)函數(shù)迭代曲線(xiàn)

由圖4分析可知，本文方法的收斂性好，求解目標(biāo)函數(shù)速度快，目標(biāo)函數(shù)求解效率高達(dá)98%，分別比另兩種方法高17%、26%。說(shuō)明本文方法多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率高且能迅速地達(dá)到高收斂狀態(tài)。

采用三種方法，在不同測(cè)試程序中，對(duì)實(shí)驗(yàn)數(shù)據(jù)運(yùn)行30次，記錄目標(biāo)函數(shù)計(jì)算的均值和標(biāo)準(zhǔn)差和運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果用表3描述。

表3 函數(shù)計(jì)算均值、標(biāo)準(zhǔn)差與時(shí)間

由表3數(shù)據(jù)可知：本文方法明顯比其它兩種方法效率高，本文方法目標(biāo)函數(shù)計(jì)算均差與標(biāo)準(zhǔn)均小，計(jì)算時(shí)間最短，平均計(jì)算時(shí)間1.215ms，其它兩種方法計(jì)算時(shí)間均值分別為4.37ms、9.61ms，說(shuō)明本文方法誤差小、計(jì)算效率高。

在不同測(cè)試程序下，采用三種方法對(duì)每組實(shí)驗(yàn)數(shù)據(jù)獨(dú)立運(yùn)行30次，記錄平均故障檢測(cè)率、有效執(zhí)行時(shí)間，平均故障檢測(cè)率，用圖5描述。有效執(zhí)行時(shí)間，用圖6描述。

圖5 平均故障檢測(cè)率

圖6 有效執(zhí)行時(shí)間

由圖5分析可知，本文方法的平均故障檢測(cè)率明顯高于其它兩種方法，本文方法的平均故障檢測(cè)率為95%，分別比其它兩種方法的平均檢測(cè)率高出22%、12%。本文方法的平均故障檢測(cè)率越大則表明多目標(biāo)任務(wù)優(yōu)先級(jí)排序效果最佳，缺陷檢測(cè)速度最快。

由圖6分析可知，其它兩種方法的有效執(zhí)行時(shí)間明顯高于本文方法。其它兩種方法的平均有效執(zhí)行時(shí)間分別為43.7ms、32.5ms，而本文方法的平均有效執(zhí)行時(shí)間為5.8ms。說(shuō)明本文方法有效執(zhí)行時(shí)間最短，多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率最佳。

在不同測(cè)試程序下，采用三種方法實(shí)施多目標(biāo)任務(wù)優(yōu)先級(jí)排序準(zhǔn)確率測(cè)試。測(cè)試結(jié)果用圖7描述。

圖7 排序準(zhǔn)確率

由圖7分析可知，采用本文方法的多目標(biāo)任務(wù)優(yōu)先級(jí)排序準(zhǔn)確率明顯高于其它兩種方法。本文方法排序準(zhǔn)確率為96%，分別比其它兩種方法高出12%、24%。說(shuō)明本文方法的多目標(biāo)任務(wù)優(yōu)先級(jí)排序精準(zhǔn)度高，提升多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率。

多目標(biāo)任務(wù)優(yōu)先級(jí)排序的效率直接影響軟件測(cè)試成本，實(shí)驗(yàn)測(cè)試三種方法應(yīng)用后軟件測(cè)試成本情況，結(jié)果用圖8描述。

圖8 軟件測(cè)試成本

分析圖8可以看出，相對(duì)于其它兩種方法，本文方法軟件測(cè)試成本更低，本文方法平均軟件測(cè)試成本為11.5萬(wàn)元，分別比其它兩種方法節(jié)省6.5萬(wàn)元、7.5萬(wàn)元。說(shuō)明本文方法實(shí)施多目標(biāo)任務(wù)優(yōu)先級(jí)排序的過(guò)程中，降低軟件測(cè)試成本，提升軟件測(cè)試效益。

4 結(jié)論

為了解決單目標(biāo)優(yōu)化確定因素比較單一的情況，適應(yīng)軟件測(cè)試的要求，提高多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率，研究基于多線(xiàn)程的多目標(biāo)任務(wù)優(yōu)先級(jí)排序方法。采用多線(xiàn)程并發(fā)技術(shù)優(yōu)化算法的可行性，融合選擇函數(shù)的非支配遺傳算法解決多目標(biāo)任務(wù)優(yōu)先級(jí)排序問(wèn)題，采用序列編碼，每個(gè)基本基因位代表優(yōu)先級(jí)排序序號(hào)，實(shí)驗(yàn)研究表明：

1)設(shè)計(jì)算子通過(guò)錦標(biāo)賽選取最優(yōu)的父代個(gè)體，對(duì)個(gè)體相似度與相異度的計(jì)算與評(píng)價(jià)，提升收斂速度。

2)將優(yōu)化目標(biāo)設(shè)置為平均故障檢測(cè)率(APFD)有效執(zhí)行時(shí)間(EET)，實(shí)現(xiàn)多目標(biāo)任務(wù)優(yōu)先級(jí)排序。

3)本文方法誤差小、計(jì)算效率高，平均有效執(zhí)行時(shí)間為5.8ms，多目標(biāo)任務(wù)優(yōu)先級(jí)排序效率最佳，可提升軟件測(cè)試有效性。

雖然，本文方法取得了較好的效果，但在軟件缺陷檢測(cè)速率還有待進(jìn)一步的完善。但由于本人時(shí)間與精力限制，仍有一些待解決的問(wèn)題需深入研究：

1)為了更好地驗(yàn)證軟件測(cè)試的效率，以后實(shí)施仿真時(shí)，需執(zhí)行更復(fù)雜的并行程序作為驗(yàn)證本文方法有效性的測(cè)試標(biāo)準(zhǔn)。

2)運(yùn)用更先進(jìn)的技術(shù)，不斷完善本文方法，進(jìn)一步提高本文方法的運(yùn)行效率。

3)本文所提的融合選擇函數(shù)的非支配遺傳算法優(yōu)化目標(biāo)設(shè)置為平均故障檢測(cè)率(APFD)有效執(zhí)行時(shí)間(EET)，但實(shí)際上影響多目標(biāo)任務(wù)優(yōu)先級(jí)排序的原因并不止這些，因此，為了提高本文方法的應(yīng)用性與適用性，以后需全面研究更多優(yōu)化目標(biāo)對(duì)任務(wù)優(yōu)先級(jí)排序的影響，將更多先進(jìn)的優(yōu)化目標(biāo)加入到任務(wù)優(yōu)先級(jí)排序中，使軟件測(cè)試人員按照實(shí)際情況選取合適的優(yōu)化目標(biāo)實(shí)施多目標(biāo)任務(wù)優(yōu)先級(jí)排序。