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

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

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

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

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