求解测试用例自动生成问题的多因子回溯搜索优化算法

doi:10.11772/j.issn.1001-9081.2022030393

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (4): 1214-1219.DOI: 10.11772/j.issn.1001-9081.2022030393

求解测试用例自动生成问题的多因子回溯搜索优化算法

胡中波(), 王旭鹏

长江大学信息与数学学院，湖北荆州 434023

收稿日期:2022-04-08 修回日期:2022-05-30 接受日期:2022-06-17 发布日期:2023-04-11 出版日期:2023-04-10
通讯作者: 胡中波
作者简介:王旭鹏（1997—），男，山西大同人，硕士研究生，主要研究方向：智能计算、自动测试用例生成。
基金资助:
国家自然科学基金资助项目(61972136)

Multifactorial backtracking search optimization algorithm for solving automated test case generation problem

Zhongbo HU(), Xupeng WANG

School of Information and Mathematics，Yangtze University，Jingzhou Hubei 434023，China

Received:2022-04-08 Revised:2022-05-30 Accepted:2022-06-17 Online:2023-04-11 Published:2023-04-10
Contact: Zhongbo HU
About author:WANG Xupeng， born in 1997， M. S. candidate. His research interests include intelligent computing， automated test case generation.
Supported by:
National Natural Science Foundation of China(61972136)

摘要/Abstract

摘要：

路径覆盖测试用例自动生成（ATCG-PC）问题是自动化软件测试领域的热点。ATCG-PC问题中群智能进化算法常用的适应度函数之间具有高度的相似性，然而现有的解决ATCG-PC问题的群智能进化算法尚未考虑这一相似性特征。受相似性特征启发，将两个相似的适应度函数看作两个任务，从而将ATCG-PC问题转化为多任务ATCG-PC问题，并提出了一种新的解决多任务ATCG-PC问题的群智能进化算法，即多因子回溯搜索优化算法（MFBSA）。所提算法通过多因子选择Ⅰ的记忆种群功能提高全局搜索能力，并通过选型记忆交配使得相似任务之间能够通过知识转移提高彼此的优化效率。在6个雾计算测试程序和6个自然语言处理测试程序上对所提算法性能进行了评价。与回溯搜索优化算法（BSA）、免疫遗传算法（IGA）、收敛速度控制器粒子群优化（PSO-CSC）算法、自适应粒子群优化（APSO）算法和超立方体差分进化（DE-H）算法相比，MFBSA覆盖12个测试程序上的路径所使用的测试用例总数分别减少了64.46%、66.64%、67.99%、74.15%和61.97%。实验结果表明，所提算法能够有效降低测试成本。

关键词: 路径覆盖测试用例自动生成, 相似性特征, 多任务优化, 记忆种群, 知识转移

Abstract:

Automated Test Case Generation for Path Coverage （ATCG-PC） problem is a hot topic in the field of automated software testing. The fitness functions commonly used by swarm intelligence evolutionary algorithms in ATCG-PC problem are highly similar with each other， but the existing swarm intelligence evolutionary algorithms for solving ATCG-PC problem do not consider this similarity feature yet. Inspired by the similarity feature， the two similar fitness functions were treated as two tasks， so that ATCG-PC problem was transformed into a multi-task ATCG-PC problem， and a new swarm intelligence evolutionary algorithm called Multifactorial Backtracking Search optimization Algorithm （MFBSA） was proposed to solve multi-task ATCG-PC problem. In the proposed algorithm， the memory population function of multifactorial selection Ⅰ was used to improve the global search ability， and the similar tasks were able to improve each other’s optimization efficiency through knowledge transfer by assortative memory mating. The performance of MFBSA was evaluated on six fog computing test programs and six natural language processing test programs. Compared with Backtracking Search optimization Algorithm （BSA）， Immune Genetic Algorithm （IGA）， Particle Swarm Optimization with Convergence Speed Controller （PSO-CSC） algorithm， Adaptive Particle Swarm Optimization （APSO） algorithm and Differential Evolution with Hypercube-based learning strategies （DE-H） algorithm， MFBSA has the total test cases used to cover the paths on 12 test programs reduced by 64.46%， 66.64%， 67.99%， 74.15%， and 61.97%， respectively. Experimental results show that the proposed algorithm can effectively reduce testing cost.

Key words: Automated Test Case Generation for Path Coverage (ATCG-PC), similarity feature, multitasking optimization, memory population, knowledge transfer

中图分类号:

TP311

胡中波, 王旭鹏. 求解测试用例自动生成问题的多因子回溯搜索优化算法[J]. 计算机应用, 2023, 43(4): 1214-1219.

Zhongbo HU, Xupeng WANG. Multifactorial backtracking search optimization algorithm for solving automated test case generation problem[J]. Journal of Computer Applications, 2023, 43(4): 1214-1219.

图/表 6

参考文献 21

1	INCE D C. The automatic generation of test data［J］. The Computer Journal， 1987， 30（1）： 63-69. 10.1093/comjnl/30.1.63
2	GONG D W， TIAN T， WANG J X， et al. A novel method of grouping target paths for parallel programs［J］. Parallel Computing， 2020， 97： No.102665. 10.1016/j.parco.2020.102665
3	NOSRATI M， HAGHIGHI H， VAHIDI-ASL M. Using likely invariants for test data generation［J］. Journal of Systems and Software， 2020， 164： No.110549. 10.1016/j.jss.2020.110549
4	MALHOTRA R， GARG M. An adequacy based test data generation technique using genetic algorithms［J］. Journal of Information Processing Systems， 2011， 7（2）：363-384. 10.3745/jips.2011.7.2.363
5	张岩，巩敦卫. 基于稀有数据扑捉的路径覆盖测试数据进化生成方法［J］. 计算机学报， 2013， 36（12）：2429-2440. 10.3724/sp.j.1016.2013.02429
	ZHANG Y， GONG D W. Evolutionary generation of test data for paths coverage based on scarce data capturing［J］. Chinese Journal of Computers， 2013， 36（12）：2429-2440. 10.3724/sp.j.1016.2013.02429
6	ANDALIB A， BABAMIR S M. A new approach for test case generation by discrete particle swarm optimization algorithm［C］// Proceedings of the 22nd Iranian Conference on Electrical Engineering. Piscataway： IEEE， 2015：1180-1185. 10.1109/iraniancee.2014.6999714
7	李龙澍，郭紫梦. 应用混沌果蝇算法的路径覆盖测试用例优化技术研究［J］. 小型微型计算机系统， 2018， 39（2）：362-366. 10.3969/j.issn.1000-1220.2018.02.032
	LI L S， GUO Z M. Optimization techniques research on testing data through path coverage with chaotic fruit fly algorithm［J］. Journal of Chinese Computer Systems， 2018， 39（2）：362-366. 10.3969/j.issn.1000-1220.2018.02.032
8	LAKSHMINARAYANA P， SureshKUMAR T V. Automatic generation and optimization of test case using hybrid cuckoo search and bee colony algorithm［J］. Journal of Intelligent Systems， 2021， 30（1）： 59-72. 10.1515/jisys-2019-0051
9	TRACEY N， CLARK J， MANDER K， et al. An automated framework for structural test-data generation［C］// Proceedings 13th IEEE International Conference on Automated Software Engineering. Piscataway： IEEE， 1998： 285-288.
10	ARCURI A. It does matter how you normalise the branch distance in search based software testing［C］// Proceedings of the 3rd International Conference on Software Testing， Verification and Validation. Piscataway： IEEE， 2010： 205-214. 10.1109/icst.2010.17
11	CAI G C， SU Q H， HU Z B. Automated test case generation for path coverage by using grey prediction evolution algorithm with im-proved scatter search strategy［J］. Engineering Applications of Artificial Intelligence， 2021， 106： No.104454. 10.1016/j.engappai.2021.104454
12	CAI G C， SU Q H， HU Z B. Binary searching iterative algorithm for generating test cases to cover paths［J］. Applied Soft Computing， 2021， 113（Pt A）： No.107910. 10.1016/j.asoc.2021.107910
13	GUPTA A， ONG Y S， FENG L. Multifactorial evolution： toward evolutionary multitasking［J］. IEEE Transactions on Evolutionary Computation， 2016， 20（3）： 343-357. 10.1109/tevc.2015.2458037
14	SAHOO R R， RAY M. PSO based test case generation for critical path using improved combined fitness function［J］. Journal of King Saud University - Computer and Information Sciences， 2020， 32（4）： 479-490. 10.1016/j.jksuci.2019.09.010
15	CIVICIOGLU P. Backtracking search optimization algorithm for numerical optimization problems［J］. Applied Mathematics and Computation， 2013， 219（15）：8121-8144. 10.1016/j.amc.2013.02.017
16	MA X L， YIN J， ZHU A M， et al. Enhanced multifactorial evolutionary algorithm with meme helper-tasks［J］. IEEE Transactions on Cybernetics， 2022， 52（8）： 7837-7851. 10.1109/tcyb.2021.3050516
17	LIU F Q， HUANG H， YANG Z M， et al. Search-based algorithm with scatter search strategy for automated test case generation of NLP toolkit［J］. IEEE Transactions on Emerging Topics in Computational Intelligence， 2021， 5（3）： 491-503. 10.1109/tetci.2019.2914280
18	HUANG H， LIU F Q， YANG Z M， et al. Automated test case generation based on differential evolution with relationship matrix for iFogSim toolkit［J］. IEEE Transactions on Industrial Informatics， 2018， 14（11）： 5005-5016. 10.1109/tii.2018.2856881
19	BOUCHACHIA A. An immune genetic algorithm for software test data generation［C］// Proceedings of the 7th International Conference on Hybrid Intelligent Systems. Piscataway： IEEE， 2007： 84-89. 10.1109/his.2007.37
20	HUANG H， LV L， YE S J， et al. Particle swarm optimization with convergence speed controller for large-scale numerical optimization［J］. Soft Computing， 2019， 23（12）： 4421-4437. 10.1007/s00500-018-3098-9
21	SU Q H， CAI G C， HU Z B， et al. Test case generation using improved differential evolution algorithms with novel hypercube-based learning strategies［J］. Engineering Applications of Artificial Intelligence， 2022， 112： No.104840. 10.1016/j.engappai.2022.104840

来源	序号	程序名	输入变量数	路径数	代码行数
雾计算测试程序	1	transmit	3	2	30
	2	send	2	9	47
	3	processEvent	7	9	67
	4	executeTuple	7	5	41
	5	checkCloudletCompletion	5	6	43
	6	getResultantTuple	8	7	73
自然语言处理测试程序	7	initFactory	7	48	86
	8	cleanXmlAnnotator	6	3	21
	9	wordsToSentenceAnnotator	11	12	108
	10	annotate	4	3	30
	11	nerClassifierCombiner	11	4	30
	12	setTrueCaseText	6	10	37

来源	序号	程序名	输入变量数	路径数	代码行数
雾计算测试程序	1	transmit	3	2	30
	2	send	2	9	47
	3	processEvent	7	9	67
	4	executeTuple	7	5	41
	5	checkCloudletCompletion	5	6	43
	6	getResultantTuple	8	7	73
自然语言处理测试程序	7	initFactory	7	48	86
	8	cleanXmlAnnotator	6	3	21
	9	wordsToSentenceAnnotator	11	12	108
	10	annotate	4	3	30
	11	nerClassifierCombiner	11	4	30
	12	setTrueCaseText	6	10	37

参数名	值	参数名	值
种群大小（pop）	50	交叉概率（mixrate）	1
最大迭代次数（G）	6 000	随机交配参数（rmp）	0.3
最大测试用例数	300 000

参数名	值	参数名	值
种群大小（pop）	50	交叉概率（mixrate）	1
最大迭代次数（G）	6 000	随机交配参数（rmp）	0.3
最大测试用例数	300 000

程序序号	MFBSA		BSA		IGA		PSO-CSC		APSO		DE-H
程序序号	测试用例数	时间/s	测试用例数	时间/s	测试用例数	时间/s	测试用例数	时间/s	测试用例数	时间/s	测试用例数	时间/s
合计	928 063	414	2 611 412	2 563	2 782 027	2 106	2 899 282	971	3 590 478	1 643	2 440 386	809
1	2 523	15	2 675	16	10 354	5	600	1	300 000	51	1 955	2
2	300 000	39	300 000	125	300 000	69	300 000	37	300 000	80	300 000	41
3	32 756	44	300 000	235	300 000	116	300 000	67	290 478	75	300 000	86
4	13 780	13	287 595	344	193 018	167	257 021	89	300 000	190	8 286	8
5	5 027	13	12 080	31	69 378	27	288 169	89	300 000	73	300 000	85
6	10 637	12	300 000	344	300 000	242	165 157	69	300 000	137	300 000	124
7	300 000	106	300 000	312	300 000	284	300 000	198	300 000	168	300 000	106
8	7 957	6	181 811	187	292 490	268	97 776	29	300 000	157	7 784	5
9	15 810	7	300 000	391	300 000	320	290 559	149	300 000	242	290 328	133
10	206 567	71	300 000	187	300 000	218	300 000	59	300 000	124	32 033	11
11	10 133	31	27 251	125	116 787	151	300 000	94	300 000	201	300 000	115
12	22 873	57	300 000	266	300 000	239	300 000	90	300 000	145	300 000	93

求解测试用例自动生成问题的多因子回溯搜索优化算法

Multifactorial backtracking search optimization algorithm for solving automated test case generation problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 21

相关文章 5

编辑推荐

Metrics

[1]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[2]	武越, 丁航奇, 何昊, 毕顺杰, 江君, 公茂果, 苗启广, 马文萍. 多任务优化算法及应用研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1338-1347.
[3]	赵佳伟, 陈雪峰, 冯亮, 候亚庆, 朱泽轩, Yew‑Soon Ong. 优化场景视角下的进化多任务优化综述[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1325-1337.
[4]	程美英, 钱乾, 熊伟清. 信息迁移多任务优化共生生物搜索算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2237-2247.
[5]	程美英, 钱乾, 倪志伟, 朱旭辉. 信息筛选多任务优化自组织迁移算法[J]. 计算机应用, 2021, 41(6): 1748-1755.