基于多目標(biāo)進化算法的測試用例生成.pdf

1、軟件測試是保證軟件質(zhì)量的重要手段，而生成測試用例是成功進行軟件測試的前提。測試數(shù)據(jù)生成問題本質(zhì)上是一個優(yōu)化問題，這使得已有的優(yōu)化方法有可能用于測試數(shù)據(jù)的生成。常用的方法主要包括:隨機法、約束求解法、啟發(fā)搜索法等等。其中啟發(fā)搜索法又稱基于搜索的軟件測試(SBST)，被視為最有前景的自動測試生成方法，該方法將測試用例自動生成問題轉(zhuǎn)化為一個數(shù)學(xué)優(yōu)化問題，并通過啟發(fā)式搜索算法求解。
　　將啟發(fā)搜索法應(yīng)用于面向?qū)ο筌浖淖詣訙y試生成問題已取

2、得了顯著進展。目前已有eToc、EvoUnit、Evacon、TestFul和EvoSuite等進化測試原型工具可以用于為面向?qū)ο筌浖詣由蓽y試用例。其中EvoSuite是基于WBGA(WholeSuite Based Genetic Algorithm)方法的優(yōu)秀開源測試框架，能夠生成有效的測試用例集。然而，高昂的測試代價嚴重影響EvoSuite在實際軟件測試中的廣泛應(yīng)用。為了高效地生成具有高分支覆蓋率的測試用例集，本文從多目標(biāo)優(yōu)化

3、的角度，研究求解測試用例生成問題的新方法，最終提出了一種基于分支覆蓋準則的可擴展性的測試用例生成方法:基于偏好的多目標(biāo)進化算法，即PMOGA(Preference-based Multiple-Obj ective Genetic Algorithm)。
　　首先，將分支覆蓋轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，提出測試用例生成問題的多目標(biāo)優(yōu)化模型，該模型引入基于分層策略的偏好關(guān)系，從而增大個體的選擇壓力，縮減Pareto前沿個體數(shù)量;其次，在求

4、解該模型時，選擇針對性的適應(yīng)度函數(shù)和設(shè)計合理選擇算子，并且采用外部歸檔集保留優(yōu)秀個體;最后，在PMOGA算法基礎(chǔ)上使用局部搜索算子對種群中的最優(yōu)個體進行局部搜索，優(yōu)化算法的局部搜索精度，減少進化搜索開銷。
　　本文在開源框架EvoSuite中實現(xiàn)了上述方法，為了驗證本文方法的有效性，選取2個基準程序和4個開源程序?qū)MOGA與WBGA方法進行了實驗比較，最后還對加入局部搜索算子的LS-PMOGA與PMOGA進行了實驗對比。實驗結(jié)果