第41卷第4期2020年4月哈尔滨工程大学学报JournalofHarbinEngineeringUniversityVol.41№.4Apr.2020萤火虫算法在测试用例集约简中的应用宫云战1,徐健豪1,邢颖2(1.北京邮电大学网络与交换技术国家重点实验室,北京100876;2.北京邮电大学自动化学院,北京100876)摘要:为了研究智能算法在测试用例集约简中的应用,本文提出一种基于萤火虫算法的测试用例集约简算法。将测试用例集约减问题转化为二元优化的集覆盖问题;对萤火虫算法进行改进,通过设置萤火虫细胞的方法,将萤火虫位置转化为0/1序列;将萤火虫算法与贪心算法相结合,进行求解。对不同程序和不同规模的测试用例集的仿真实验,在相同的测试次数下,萤火虫算法得到最优解的次数高于贪心算法和优化的GRE算法,萤火虫算法约简后测试开销比贪心算法减少了12.6%,比优化的GRE算法减少了2.3%。结果表明:该算法在约简能力和稳定性方面均优于传统算法。关键词:软件测试;回归测试;测试用例集约简;二元优化;智能算法;萤火虫算法;集覆盖问题;分支覆盖DOI:10.11990/jheu.201901007网络出版地址:http://www.cnki.net/kcms/detail/23.1390.u.20190926.0856.002.html中图分类号:TP311.5文献标志码:A文章编号:1006-7043(2020)04-0577-06ApplicationoffireflyalgorithmintestsuitereductionGONGYunzhan1,XUJianhao1,XINGYing2(1.StateKeyLaboratoryofNetworkingandSwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China;2.SchoolofAutomation,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)Abstract:Tostudytheapplicationofanintelligentalgorithmtotestsuitereduction,inthispaper,weproposeatest-suite-reductionalgorithmbasedonthefireflyalgorithm.First,wetransformthetest-suite-reductionproblemin-toabinary-optimization-set-coverageproblem.Next,weimprovethefireflyalgorithmbyestablishingfireflycellsandconvertthecellpositionsintoa0/1sequence.Lastly,wecombinethefireflyalgorithmwiththegreedyalgo-rithmtoobtainthebestsolution.Thetest-suitesimulationresultsusingdifferentprogramsandscalesshowthat,withthesamenumberoftests,thefireflyalgorithmcanobtaintheoptimalsolutionmoreoftenthanboththegreedyalgorithmandtheoptimizedGREalgorithm.Thecostassociatedwiththefireflyalgorithmis12.6%lowerthanthatofthegreedyalgorithmand2.3%lowerthanthatoftheoptimizedGREalgorithm,whichindicatesthatthisalgo-rithmissuperiortotraditionalalgorithmsintermsofitsreductionabilityandstability.Keywords:softwaretesting;regressiontesting;testsuitereduction;binaryoptimization;intelligentalgorithm;fire-flyalgorithm;setcoveringproblem;branchcoverage软件测试在检验和提升软件设计和实现质量的过程中是非常重要但耗时的环节。在软件开发需要检查版本迭代过程中是否产生了新错误。但是在每次更改后没有必要执行全部测试用例,一方面,多个测试用例可能集中在一段相同的代码上,从而产生收稿日期:2019-01-03.网络出版日期:2019-09-26.基金项目:国家自然科学基金项目(61702044);中央高校基本科研业务费专项资金项目(2019XD-A20).作者简介:宫云战,男,教授,博士生导师;邢颖,女,副教授,博士生导师.通信作者:邢颖,E-mail:xingying@bupt.edu.cn.冗余和浪费;另一方面,在一个大型项目中执行一次测试套件需要大约1h[1],频繁的代码更改需要大量时间来进行测试。测试用例集约简旨在保障覆盖率不变的情况下限度地减少执行的测试用例的数量,约简测试用例集,在进行约简时,约简后测试用例集必须要满足跟原始测试用例集具有相同的覆盖率,例如语句覆盖率等[2]。Harrold等[3]提出测试用例集约简的概念并提出一种启发式方法。在随后的发展中,出现了许多方法,包括贪心算法、启发式算法和整数规划等[4]。{RS,Chvatal[5]介绍的种贪心算法是一种经典的用于寻找测试用例集问题的近似最优解的方法。然而,贪心算法并不能尽早处理基本测试用例(唯一可以覆试需求j的测试关系表示为Sij=1,测试开...