计算机科学 ›› 2017, Vol. 44 ›› Issue (3): 209-214.doi: 10.11896/j.issn.1002-137X.2017.03.044

• 软件与数据库技术 • 上一篇    下一篇

基于改进遗传算法的测试数据自动生成的研究

高雪笛,周丽娟,张树东,柳昊明   

  1. 首都师范大学信息工程学院 北京100048;成像技术北京市高精尖创新中心 北京100190,首都师范大学信息工程学院 北京100048;成像技术北京市高精尖创新中心 北京100190,首都师范大学信息工程学院 北京100048;成像技术北京市高精尖创新中心 北京100190,北京航空航天大学计算机学院 北京100048
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金(31571563),国家科技支撑计划项目(2013BAH19F01),国外访学项目(067145301400),北京市属高等学校创新团队建设与教师职业发展计划项目,高可靠嵌入式系统技术北京市工程研究中心资助

Research on Test Data Automatic Generation Based on Improved Genetic Algorithm

GAO Xue-di, ZHOU Li-juan, ZHANG Shu-dong and LIU Hao-ming   

  • Online:2018-11-13 Published:2018-11-13

摘要: 测试数据自动生成是软件测试的基础,也是测试自动化技术实现的关键环节。为了提高测试自动化的效率,在 结合 测试数据自动生成模型的基础上,提出一种 传统遗传算法的改进算法。该算法使用了自适应交叉算子和变异算子,并引入模拟退火机制对其进行改进。同时,该算法还对适应度函数进行了合理的设计,以加速数据的优化过程。通过三角形程序、折半查找和冒泡排序程序,与基本遗传算法、自适应遗传算法进行了比较与分析,并且对改进算法做了性能分析。实验结果表明了该算法的实用性以及在测试数据生成中的可行性和高效性。

关键词: 软件测试,遗传算法,哈明函数,测试数据自动生成

Abstract: Automatic test data generation is the basis of software testing,and it is also a key link in the process of test automation technology.In order to improve the efficiency of testing automation,a new algorithm was proposed to improve the traditional genetic algorithm based on the combination of test data automatic generation system model.The adaptive crossover operator and mutation operator are used in this algorithm,and the improved simulated annealing mechanism is introduced to improve it.At the same time,the algorithm is also designed to fit the fitness function to accelerate the optimization process of the data.Through the triangle program,binary search and bubble sort program,the basic genetic algorithm and the adaptive genetic algorithm were compared,and the performance test was done for improved algorithm.Experimental results show the practicability as well as feasibility and efficiency of the algorithm in the test data generation.

Key words: Software test,Generic algorithm,Hamming function,Automatic test data generation

[1] HOLLAND J H.Genetic algorithms and the optimal allocation of trials [J].SIAMJ Comput,1973,2(2):89-104.
[2] NIE P,GENG J,QIN Z G.Survey on automatic test case genera-tion algorithms for software testing[J].Computer application research,2012,29(2):402-405.(in Chinese) 聂鹏,耿技,秦志光.软件测试用例自动生成算法综述[J].计算机应用研究,2012,29(2):402-405.
[3] HUANG L F.Simulation Research on Automatically Generate Software Test Data Algorithm[J].Computer Simulation,2012,9(10):245-247.(in Chinese) 黄丽芬.软件测试数据自动生成算法的仿真研究.[J].计算机仿真,2012,9(10):245-247.
[4] KOREL B.Automated software test data generation[J].IEEE Trans,on Software Engineering,1990,16(8):870-879.
[5] 王小平,曹立明.遗传算法一理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[6] SRNINASM,PAINAIKM.Adaptive Probabilities of Crossoverand Mutation in Genetic Algorithms[J].IEEE Tram on Systems,Manand Cybe Rnetics,1994,4(4):656-659.
[7] CHEN Y,YAO L.Software Test Data Generation Based on an Improved Generic Algorithm[J].Electronic Science and techno-logy,2009,22(7):9-12.(in Chinese) 陈雨,姚砺.基于改进的遗传算法的测试用例生成.电子科技,2009,22(7):9-12.
[8] ARABALI A,GHOFRANI M.Genetic-Algorithm-Based Opti-mization Approach for Energy Management[J].IEEE Transactions on Power Delivery,2013,8(1):162-170.
[9] LIN J C,YEH P L.Using genetic algorithms for test case genera-tion in path testing[C]∥9th Asian Test Symposium (ATS’00).Taipei,2000:241-246.
[10] LEI H,HAN X.Software Test Data Generation Method Using Hill Climbing Algorithm Combined with a Modified ARPSO[J].Journal of University of Electronic Science and Technology of China,2012,1(6):885-889.(in Chinese) 雷航,韩炫.采用HC-MARPSO算法的软件测试数据生成方法[J].计算机工程与应用,2012,1(6):885-889.
[11] YU B,JIANG S J,ZHANG Y M.Multiple Paths Test CaseGeneration Based on Complex System Genetic Algorithm[J].Computer Science,2012,9(4):139-141.(in Chinese) 于博,姜淑娟,张艳涛.基于复杂系统遗传算法的多路径覆盖测试用例生成方法[J].计算机科学,2012,9(4):139-141.
[12] FRASER G,ARCURI A.Evolutionary Generation of WholeTest Suites[J].International Conference on Quality Software,2011,14(1):31-40.
[13] ZHONG X M,ZHAO X F.Automated test case generationbased on improved tabu search algorithm[J].Computer Engineering and Design,2011,32(7):2058-2060.(in Chinese) 仲晓敏,赵雪峰.基于改进禁忌搜索算法的测试用例自动生成[J].计算机工程与设计,2011,32(7):2058-2060.
[14] FRASER G,ARCURI A.Achieving scalable mutation-basedgeneration of whole test suites[J].Empirical Software Enginee-ring,2014,20(3):783-812.
[15] RAYADURGAM S,HEIMDAHL M P E.Coverage based test-case generation using model checkers[C]∥IEEE International Conference and Workshop on the Engineering of Computer Based Systems.2015:83-91.
[16] WANG Y,WANG C,LIU H L.Application of simulated annealing generic algorithm in multiuser detection technique[J].Communition and Network,2011(4):102-105.(in Chinese) 王彦,王超,刘宏立.模拟退火遗传算法在多用户检测技术中的应用[J].通信与网络,2011(4):102-105.
[17] 邱菊.基于蚁群算法的软件测试用例生成方法研究[J].软件导刊,2011,0(3):73-74.
[18] LU H Q,CHEN L,SONG Y S,et al..An improved crossover operator of genetic algorithm[J].Journal of PLA University of Science and Technology,2007,8(3):250-253.(in Chinese) 卢厚清,陈亮,宋以胜,等.一种遗传算法交叉算子的改进算法[J].解放军理工大学学报,2007,8(3):250-253.
[19] KONG X L,WANG Y,JU A L,et al.An Improved Quantum Evolutionary Algorithm Based on Regulation Law of Hermone in Endocrine System[J].Journal of Northwestern Polytechnical University,2011,9(6):978-983.(in Chinese) 孔晓琳,王毅,巨安丽,等.基于内分泌激素调节机制的量子进化算法[J].西北工业大学学报,2011,29(6):978-983.
[20] MIRZAAGHAEI M,PASTORE F,PEZZ M.Supporting Test Suite Evolution through Test Case Adaptation[C]∥IEEE Fifth International Conference on Software Testing.2012:231-240.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!