王晴

（徐州開放大學(xué)電子信息工程學(xué)院，徐州221006）

基于Memetic的多路徑測試在網(wǎng)絡(luò)課程平臺中的應(yīng)用

王晴

（徐州開放大學(xué)電子信息工程學(xué)院，徐州221006）

Memetic Algorithm（MA）是一種以遺傳算法為基礎(chǔ)的智能優(yōu)化算法。以某高職院校網(wǎng)絡(luò)課程的平臺為應(yīng)用基礎(chǔ)，將MA應(yīng)用于該平臺的多路徑測試數(shù)據(jù)生成方面，對多路徑代碼的測試數(shù)據(jù)生成技術(shù)進行深入的研究。

0 引言

MA算法以遺傳算法為基礎(chǔ)，集合了遺傳算法中的全局搜索法和局部啟發(fā)式搜索算法，在單路徑測試數(shù)據(jù)生成方面已獲得了優(yōu)異的研究成果。本文在現(xiàn)有的研究成果上，結(jié)合某高職校網(wǎng)絡(luò)課程平臺的開發(fā)，運用MA算法，對多路徑代碼的測試數(shù)據(jù)生成技術(shù)進行了深入的研究，有效地避免了該網(wǎng)絡(luò)課程平臺相關(guān)代碼的重復(fù)迭代時間，從而實現(xiàn)了路徑間的資源共享，提高了該平臺測試數(shù)據(jù)生成的效率，為平臺的代碼優(yōu)化提供了強有力的支持。

1 測試環(huán)境

測試平臺：Apach操作系統(tǒng)，PHP語言及MySQL數(shù)據(jù)庫。

2 測試數(shù)據(jù)生成步驟和方法

測試數(shù)據(jù)的生成步驟如圖1所示。

（1）設(shè)置各項參數(shù)，包括種群規(guī)模n，值域，交叉因子和變異因子，鄰域搜索時的增量δ，最大迭代次數(shù)以及終止條件等等。并選定m條不同的路徑，組成目標路徑集Road。然后根據(jù)設(shè)定的參數(shù)對種群進行初始化，如 D0={d1,d2,...,dn}。

（2）進化種群：利用之前設(shè)置的交叉因子和變異因子實現(xiàn)個體的變異和個體間的交叉操作，從而進化種群，得到新個體。針對新個體采用適當?shù)姆椒ㄇ蠼獬跏挤N群個體的適應(yīng)度函數(shù)值，將結(jié)果所對應(yīng)的路徑記錄下來，并對每個個體分別進行局部搜索。

圖1 測試數(shù)據(jù)的生成步驟

（3）所有種群按適應(yīng)度函數(shù)值的大小進行排序，淘汰較差的個體，從而優(yōu)化種群，最后恢復(fù)種群規(guī)模仍為n。

（4）迭代找尋最優(yōu)解。在優(yōu)化后的種群中找出最優(yōu)解，判斷是否滿足終止條件，若是，則從Road中剔除其對應(yīng)的路徑，然后檢查Road是否為空，若為空就終止迭代，否則就繼續(xù)進化種群。

3 多路徑測試數(shù)據(jù)生成的適應(yīng)度值求解方法

在測試數(shù)據(jù)的生成過程中，適應(yīng)度函數(shù)的計算起著重要的作用，因為適應(yīng)度函數(shù)的作用是在種群迭代過程中來引領(lǐng)種群更新方向的。對于單路徑中的測試數(shù)據(jù)生成，計算一次適應(yīng)度函數(shù)值即可。但在多路徑測試數(shù)據(jù)生成中，適應(yīng)度函數(shù)值的計算要相對復(fù)雜些，最常用的針對多路徑測試數(shù)據(jù)生成的適應(yīng)度函數(shù)有均值法和min值法。

（1）均值法。均值法是最早提出的面向多路徑測試數(shù)據(jù)生成的方法之一。這種思想最為直接，是指將種群中的每個個體代入每一條目標路徑，并逐個計算出各個路徑的適應(yīng)度函數(shù)值，然后計算它們的平均值，以此作為該個體最終的適應(yīng)度值。

如式（1）所示一個程序中的多條路徑：

個體d={d1,d2,...,ds}是初始種群中的一個，經(jīng)過計算，d對m條路徑的適應(yīng)度值為{vd1,vd2,...,vdm}，取平均值，得最終的適應(yīng)度值 vˉd，公式如式（2）所示。

然后，根據(jù)給定的閾值T，以式（3）所示的公式進行迭代，從種群中逐步找到合適的個體，作為測試數(shù)據(jù)。

該函數(shù)能使適應(yīng)度值更好地反映該個體對多條路徑整體的適應(yīng)度，確保計算出的適應(yīng)度值在有效范圍內(nèi)。當找到的數(shù)據(jù)滿足其中一條路徑時，就從目標路徑集中刪除這條路徑，繼續(xù)用函數(shù)公式迭代，在這個過程中不改變種群結(jié)構(gòu)，判斷迭代結(jié)束的條件是：目標路徑集為空。

均值法是根據(jù)基于路徑相似性提出的。只有相似的路徑，才會產(chǎn)生相似的數(shù)據(jù)，對相似的數(shù)據(jù)取均值才能有效地代表整體。但當路徑數(shù)目過大，且路徑間的差異較大時，均值法的優(yōu)勢就不明顯了。

例如：閾值為10，個體d對某兩條路徑的適應(yīng)度值若分別為vd1=9，vd2=69，代入適應(yīng)度值迭代函數(shù)，得到Ffitness(d)=( )vd1+vd2/2=39；個體p對某兩條路徑的適應(yīng)度值若為 vp1=16，vp2=48，得出Ffitness(p)=(vp1+vp2)/2=32，由于 Ffitness(p)＜Ffitness(d)，因此 d被淘汰，但實際上vd1已非常接近閾值10，若用d迭代，很快就可以成功。

（2）min值法。min值法是一種采用適應(yīng)度值集合中的最小值來作為某個體的整體適應(yīng)度值，并以該值參與進化過程的方法。用min值法計算個體適應(yīng)度值的方法如下：

還是以式（1）中所示的路徑集為例，依照min值法，個體d的適應(yīng)度函數(shù)如式（4）所示：

其中，F(xiàn)fitness(d)同樣表示個體d的適應(yīng)度值求解函數(shù)，且結(jié)果是與執(zhí)行路徑最相近的那條目標路徑的適應(yīng)度值。此處再用上述平均值法中的例子來看，個體d對某兩條路徑的適應(yīng)度值分別為vd1=9，vd2=69，用min值 法 得 到Ffitness(d)=min(9,69)，結(jié) 果Ffitness(d)=9；個體p對某兩條路徑的適應(yīng)度值若為vp1=16，vp2=48，用min值法得到Ffitness(p)=min(16,48)，結(jié) 果Ffitness(p)=16，因 為Ffitness(d)＜Ffitness(d)，所以雖然個體d離第二條路徑比較遠，但由于它距離第一條路徑的適應(yīng)度值十分小而被保留了下來，而p被淘汰。

所以，當路徑數(shù)目過多，且之間存在較大差異時，使用min值法能夠保證那些較接近某一條路徑的種群個體被保留下來，而不會因為它距離另外一條路較遠而被淘汰。因為在進化的過程中，始終保留的都是那個適應(yīng)度值較小的個體，且這個個體至少接近某一個路徑。

本文就采用min值法來計算適應(yīng)度函數(shù)值，從而生成多路徑測試數(shù)據(jù)。

4 局部搜索過程中的個體比較方法

在測試數(shù)據(jù)的生成過程中，局部搜索的方法和過程設(shè)計是核心問題。而在局部搜索過程中，值得一提的是值域范圍內(nèi)的種群個體與其搜索到的鄰域的種群個體的比較，有兩種不同的方法：全局法和單一路徑法。

例如：前提條件如下：

R={r1,r2,...,rk}——路徑集。其中k為路徑的數(shù)目。

D0={d1,d2,...,di,...dn}——種群規(guī)模集合。

V={v1,v2,...,vn}——種群中個體的適應(yīng)度值集合。

Ffitnessi=min(vi1,vi2,...,vik)——采用最小值法迭代適應(yīng)度函數(shù)，其中k為路徑的數(shù)目，i為種群中的某個個體。

全局法：假設(shè)種群中的某個個體di，其鄰域的一個種群個體，采用min值法計算的適應(yīng)度函數(shù)值為，若Ffitness′i＜Ffitnessi，則di=d′i（保留 d′i），否則 di不變。

優(yōu)點：針對所有的路徑進行局部搜索，可以更快地發(fā)現(xiàn)最優(yōu)解。

缺點：該方法需要消耗大量的時間去計算d′i對所有路徑的適應(yīng)度值，由于要在眾多適應(yīng)度值中選取min值來做最終結(jié)果，所以它更容易使種群中的個體趨向于某一條路徑，從整體上看，喪失一定的多樣性。而在求解過程中，若該條路徑得出最優(yōu)解且被剔除后，種群中的個體卻都趨近這條已被剔除的路徑，這樣的話對其他路徑的適應(yīng)度就會較差。

單一路徑法：對于同樣的di和d′i，計算 d′i在路徑Ri上 的 適 應(yīng) 度 函 數(shù) 值 Ffitness′iPi，若Ffitness′iPi＜

優(yōu)點：由于只針對特定的路徑，在單一的方向上進行局部搜索，所以計算適應(yīng)度值所耗費的時間較小，在一定程度上能夠保持種群的多樣性。

缺點：收斂速度較慢。

5 測試數(shù)據(jù)及分析

（1）測試1：結(jié)合以上測試數(shù)據(jù)的生成步驟與方法，以該網(wǎng)絡(luò)課程平臺的學(xué)生成績排序為例，來驗證使用MA，在計算適應(yīng)度函數(shù)值時，min值法比均值法更具優(yōu)勢。

測試參數(shù)設(shè)值如表1：

表1 參數(shù)設(shè)置

100次測試后的結(jié)果如表2和表3：

上表中的數(shù)據(jù)顯示，路徑的數(shù)目越多，路徑的差異越大，則min值法在迭代速度和迭代時間上相較均值法的優(yōu)勢就越明顯。因此，min值法更具優(yōu)勢。

（2）測試2：分別使用局部搜索的兩種比較方法，驗證使用MA在生成多路徑測試數(shù)據(jù)時，與遺傳算法相比的有效性。

測試參數(shù)設(shè)置同表1。

100次測試后的結(jié)果如表4所示：

表2 選取5條路徑測試后的結(jié)果

表3 選取10條路徑測試后的結(jié)果

表4 生成多路徑測試數(shù)據(jù)的實驗結(jié)果

從測試結(jié)果可以看出，MA在多路徑的測試數(shù)據(jù)生成方面要優(yōu)于傳統(tǒng)的遺傳算法。且對比MA算法中局部搜索的兩種方式，全局法的平均迭代時間較長，但搜索較全面，且平均迭代次數(shù)較少；單一路徑法雖不如全局法全面，且平均迭代次數(shù)較多，但迭代時間較短。所以，綜合看來，單一路徑法較全局法，在時間上更具有優(yōu)勢。

6 結(jié)語

本文結(jié)合某高職院校網(wǎng)絡(luò)課程平臺的開發(fā)，對MA在多路徑測試數(shù)據(jù)生成方面進行了深入的研究。首先提出基于MA的多路徑測試數(shù)據(jù)的生成步驟，然后對生成過程中的重點方面——適應(yīng)度函數(shù)的設(shè)計方法和局部搜索的方法進行了詳細的理論分析。最后通過對網(wǎng)絡(luò)課程平臺中學(xué)生成績排序的算法進行了實驗，實驗數(shù)據(jù)驗證了理論：

（1）當路徑數(shù)目增加時，在迭代速度和迭代時間方面，min值法更具優(yōu)勢；

（2）在多路徑的測試數(shù)據(jù)生成方面，MA算法要優(yōu)于遺傳算法

（3）局部搜索的兩種方法相較，全局法較全面，且迭代次數(shù)較少，而單一路徑法的迭代時間卻較短。

但MA在局部搜索中所耗費的時間仍然較多，所以對于MA在多路徑測試數(shù)據(jù)生成方面的性能提升有待進一步的研究。

[1]程燁.遺傳算法在路徑覆蓋測試數(shù)據(jù)生成中的研究與應(yīng)用[D].上海師范大學(xué)，2013.

[2]王蓁蓁.軟件測試理論初步框架[J].計算機科學(xué)，2014，41（3）:12-16.

[3]姜元鵬.基于遺傳算法和分支覆蓋的測試數(shù)據(jù)生成方法[J].計算機工程與設(shè)計，2016（1）：112-117.

[4]Chencyinc Mao，Xinxin Yu.Test Data Generation for Software Testing Based on Quantum-Inspired Genetic Algorithm[J].International Tournai of Computational Intelligence and Applications,2013,12（1）:1-19.

[5]林耿，關(guān)健.自適應(yīng)Memetic算法求解集合覆蓋問題[J].浙江大學(xué)學(xué)報（理學(xué)版），2016（2）：168-174.

王晴（1980-），女，江蘇徐州人，碩士研究生，講師，研究方向為軟件工程

2017-08-10

2017-10-07

Memetic Algorithm;Online Course;Multipath Testing

Application of Multipath Testing Based on Memetic in Online Course Platform

WANG Qing

(School of Electronic Information Engineering,The Open University of Xuzhou,Xuzhou 221006)

Memetic Algorithm（MA）is an intelligent optimization algorithm based on genetic algorithm.Takes an online course platform of higher voca?tional colleges as the application foundation,applies MA to the multipath test data generation on the platform，and deeply studies the test data generation technology of multipath code.

Memetic算法；網(wǎng)絡(luò)課程；多路徑測試

1007-1423（2017）29-0035-04

10.3969/j.issn.1007-1423.2017.29.009