基于多線程的多目標任務優先級排序方法仿真

黃小平，謝蓉蓉

(1.廣州軟件學院網絡技術系，廣東廣州 510990；2.西安石油大學計算機學院，陜西西安 710065)

1 引言

在科學信息技術時代，軟件已與人們生活密不可分[1]。軟件開發的核心環節是軟件測試[2]。軟件測試主要是通過回歸測試完成，因軟件的復雜性高、規模巨大，增加回歸測試的測試強度和難度。據相關資料表明，回歸測試占軟件測試成本的一半以上[3]。優先級排序準則是按照軟件測試要求，選取合適的評價準則。因軟件程序的越來越繁瑣，以往方法已無法達到回歸測試的標準，多目標任務優先級排序已經成為當前回歸測試中亟待解決的一個重要問題[4-5]。

但是以往多目標任務優先級排序方法非常局限，如文獻[6]提出基于AHP的回歸測試用例優先級排序方法，在多目標任務優先級排序過程中，由于該方法計算過程非常繁瑣，導致多目標任務優先級排序效率不佳；文獻[7]提出基于直覺梯形模糊信息的目標優先級排序方法，在多目標任務優先級排序過程中，由于該方法評價指標單一化導致多目標任務優先級排序耗時間久。隨著海量數據的涌入，系統在同一時間里的計算強度也隨之增大，此時單線程的環境已經無法滿足系統的運行，導致系統運行效率低。多線程可同時完成多目標任務，提高資源使用效率。因此將多線程的多目標任務優先級排序方法應用在多目標任務優先級排序過程中，通過該方法解決回歸測試中多目標任務優先級排序效率低的問題。

2 基于多線程的多目標任務優先級排序方法

2.1 基于多線程并發的多目標演化算法

遺傳算法是演化算法中的一種算法，為采用模擬生物進化尋找最優解的算法。該遺傳算法運行過程，具體內容如圖1所示。

圖1 遺傳算法運行流程

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

圖2 新的固定線程池

在圖2中，線程調度是通過共享無界隊列實現，新任務在線程池內無閑置的線程的情況下，需在隊列內排隊，等待產生可用線程[8]。管理器是在執行期間發生線程異常，任務被迫終止時，將安排新線程實施下一個任務。

2.2 融合選擇函數的非支配遺傳算法

為了適用多線程環境，通過多目標演化算法的重構，為深入優化遺傳算法作鋪墊[9-11]。融合選擇函數的非支配遺傳算法在遺傳算法的個體評價機制中融入了選擇函數，對多目標任務優先級實施排序。多目標任務優先級排序方法的過程，具體內容如圖3所示。

圖3 多目標任務優先級排序方法的過程

在圖3中，多目標任務優先級排序是采用融合選擇函數的非支配遺傳算法，通過設計算子，選擇適宜的方案，計算個體評價函數，選取適宜的優化目標完成排序。

2.2.1 編碼及算子

排序序列用種群個體描述，下面是個體編碼、算子設計過程：

1)編碼方案

利用十進制編碼對種群個體實施編碼，優先級排序序號用基本基因位描述。

2)選擇算子

為了選取最優的父代個體，通過錦標賽選取方法實現。

3)交叉算子

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

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

4)變異算子

通過選取2點交換2點的值實施變異算子計算。

2.2.2 個體評價

因在遺傳算法的種群內，個體相關度與兩個個體的相似度成正相關，與相異度成反相關。所以，在遺傳算法的個體評價內融入選擇函數。

1)個體的相似度計算方法

為了提升收斂速度，加強搜尋目的，按照個體相似度描述個體評價函數內的相似度，具體計算用式(1)描述

(1)

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

(2)

式中

1)個體的相異度計算方法

為了提升搜索空間的多樣性，按照個體相異度描述個體評價函數內的相異度，具體計算用式(3)描述

(3)

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

(4)

2.2.3 優化目標

優化目標設為平均故障檢測率、有效執行時間。

多目標任務優先級排序度量指標：平均故障檢測率(Average Percentage of Fault Detection，APFD)、有效執行時間(Effective Execute Time，EET)。

1)為了檢查出多目標任務優先級排序過程中，缺陷的平均累計比例是通過平均故障檢測率實現[12]。平均故障檢測率，用式(5)描述

(5)

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

2)計算多目標任務的故障檢測率最高執行總時間為有效執行時間。有效執行時間，用式(6)描述

(6)

式中：執行第i個多目標任務時所消耗的時間用ETi描述。

3 實驗分析

為了驗證本文方法的性能，實驗對象選取4種測試程序。仿真運行環境：Window 10系統，CPU內存8GB。實驗對比方法選取本文方法與文獻[6]基于AHP的回歸測試用例優先級排序方法、文獻[7]基于直覺梯形模糊信息的目標優先級排序方法實施多目標任務優先級排序實施仿真。實驗程序基本信息如表2所示。

表2 基本信息

實驗設置迭代次數為1000次時，采用三種方法的目標函數迭代曲線，結果如圖4所示。

圖4 目標函數迭代曲線

由圖4分析可知，本文方法的收斂性好，求解目標函數速度快，目標函數求解效率高達98%，分別比另兩種方法高17%、26%。說明本文方法多目標任務優先級排序效率高且能迅速地達到高收斂狀態。

采用三種方法，在不同測試程序中，對實驗數據運行30次，記錄目標函數計算的均值和標準差和運行時間，實驗結果用表3描述。

表3 函數計算均值、標準差與時間

由表3數據可知：本文方法明顯比其它兩種方法效率高，本文方法目標函數計算均差與標準均小，計算時間最短，平均計算時間1.215ms，其它兩種方法計算時間均值分別為4.37ms、9.61ms，說明本文方法誤差小、計算效率高。

在不同測試程序下，采用三種方法對每組實驗數據獨立運行30次，記錄平均故障檢測率、有效執行時間，平均故障檢測率，用圖5描述。有效執行時間，用圖6描述。

圖5 平均故障檢測率

圖6 有效執行時間

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

由圖6分析可知，其它兩種方法的有效執行時間明顯高于本文方法。其它兩種方法的平均有效執行時間分別為43.7ms、32.5ms，而本文方法的平均有效執行時間為5.8ms。說明本文方法有效執行時間最短，多目標任務優先級排序效率最佳。

在不同測試程序下，采用三種方法實施多目標任務優先級排序準確率測試。測試結果用圖7描述。

圖7 排序準確率

由圖7分析可知，采用本文方法的多目標任務優先級排序準確率明顯高于其它兩種方法。本文方法排序準確率為96%，分別比其它兩種方法高出12%、24%。說明本文方法的多目標任務優先級排序精準度高，提升多目標任務優先級排序效率。

多目標任務優先級排序的效率直接影響軟件測試成本，實驗測試三種方法應用后軟件測試成本情況，結果用圖8描述。

圖8 軟件測試成本

分析圖8可以看出，相對于其它兩種方法，本文方法軟件測試成本更低，本文方法平均軟件測試成本為11.5萬元，分別比其它兩種方法節省6.5萬元、7.5萬元。說明本文方法實施多目標任務優先級排序的過程中，降低軟件測試成本，提升軟件測試效益。

4 結論

為了解決單目標優化確定因素比較單一的情況，適應軟件測試的要求，提高多目標任務優先級排序效率，研究基于多線程的多目標任務優先級排序方法。采用多線程并發技術優化算法的可行性，融合選擇函數的非支配遺傳算法解決多目標任務優先級排序問題，采用序列編碼，每個基本基因位代表優先級排序序號，實驗研究表明：

1)設計算子通過錦標賽選取最優的父代個體，對個體相似度與相異度的計算與評價，提升收斂速度。

2)將優化目標設置為平均故障檢測率(APFD)有效執行時間(EET)，實現多目標任務優先級排序。

3)本文方法誤差小、計算效率高，平均有效執行時間為5.8ms，多目標任務優先級排序效率最佳，可提升軟件測試有效性。

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

1)為了更好地驗證軟件測試的效率，以后實施仿真時，需執行更復雜的并行程序作為驗證本文方法有效性的測試標準。

2)運用更先進的技術，不斷完善本文方法，進一步提高本文方法的運行效率。

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