Pheromone updating strategy of ant colony algorithm for multi-objective test case prioritization

doi:10.11772/j.issn.1001-9081.2016.09.2497

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (9): 2497-2502.DOI: 10.11772/j.issn.1001-9081.2016.09.2497

Previous Articles Next Articles

Pheromone updating strategy of ant colony algorithm for multi-objective test case prioritization

XING Xing, SHANG Ying, ZHAO Ruilian, LI Zheng

College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China

Received:2016-02-02 Revised:2016-03-02 Online:2016-09-10 Published:2016-09-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61170082, 61472025), the New Century Talents Plan of Education Department (NCET-12-0757).

面向多目标测试用例优先排序的蚁群算法信息素更新策略

邢行, 尚颖, 赵瑞莲, 李征

北京化工大学信息科学与技术学院, 北京 100029

通讯作者: 李征
作者简介:邢行(1991-),女,河北武安人,硕士研究生,主要研究方向:软件测试;尚颖(1976-),女,吉林四平人,讲师,博士,CCF会员,主要研究方向:优化算法、软件测试;赵瑞莲(1964-),女,山西忻州人,教授,博士,CCF会员,主要研究方向:软件测试、软件可靠性;李征(1974-),男,河北清苑人,教授,博士,CCF高级会员,主要研究方向:软件测试、模型切片。
基金资助:
国家自然科学基金资助项目（61170082，61472025）；教育部新世纪优秀人才计划项目（NCET-12-0757）。

Abstract

Abstract: The Ant Colony Optimization (ACO) has slow convergence and is easily trapped in local optimum when solving Multi-Objective Test Case Prioritization (MOTCP). Thus, a pheromone updating strategy based on Epistatic-domain Test case Segment (ETS) was proposed. In the scheme, ETS existed in the test case sequence was selected as a pheromone updating scope, because ETS can determine the fitness value. Then, according to the fitness value increment between test cases and execution time of test cases in ETS, the pheromone on the trail was updated. In order to further improve the efficiency of ACO and reduce time consumption when ants visited test cases one by one, the end of ants' visiting was reset by estimating the length of ETS using optimized ACO. The experimental results show that compared with the original ACO and NSGA-Ⅱ, the optimized ACO has faster convergence and obtains better Pareto optimal solution sets in MOTCP.

Key words: Ant Colony Optimization (ACO), pheromone updating, Multi-Objective Test Case Prioritization (MOTCP), regression testing, Epistatic-Domain Test Case Segment (ETS)

摘要： 针对蚁群算法在求解多目标测试用例优先排序（MOTCP）时收敛速度缓慢、易陷入局部最优的问题，提出一种基于上位基因段（ETS）的信息素更新策略。利用测试用例序列中ETS可以决定适应度值的变化，选取ETS作为信息素更新范围，再根据ETS中测试用例间的适应度增量和测试用例的执行时间更新路径上的信息素值。为进一步提升蚁群算法求解效率、节省蚂蚁依次访问测试用例序列的时间，优化的蚁群算法还通过估算ETS长度重新设置蚂蚁遍历测试用例的搜索终点。实验结果表明，与优化前的蚁群算法及NSGA-Ⅱ相比，优化后的蚁群算法能提升求解MOTCP问题时的收敛速度，获得更优的Pareto解集。

关键词: 蚁群算法, 信息素更新, 多目标的测试用例优先排序, 回归测试, 上位基因段

CLC Number:

TP311.5

XING Xing, SHANG Ying, ZHAO Ruilian, LI Zheng. Pheromone updating strategy of ant colony algorithm for multi-objective test case prioritization[J]. Journal of Computer Applications, 2016, 36(9): 2497-2502.

邢行, 尚颖, 赵瑞莲, 李征. 面向多目标测试用例优先排序的蚁群算法信息素更新策略[J]. 计算机应用, 2016, 36(9): 2497-2502.

References

[1] SHARMA I, KAUR J, SAHNI M. A test case prioritization approach in regression testing [J]. International Journal of Computer Science & Mobile Computing, 2014, 3(7): 607-614.
[2] ROTHERMEL G, UNTCH R H, CHU C, et al. Prioritizing test cases for regression testing [J]. IEEE Transactions on Software Engineering, 2001, 27(10): 929-948.
[3] LI Z, HARMAN M, HIERONS R M. Search algorithms for regression test case prioritization [J]. IEEE Transaction on Software Engineering, 2007, 33(4): 225-237.
[4] 陈翔,陈继红,鞠小林,等.回归测试中的测试用例优先排序技术述评[J].软件学报,2013,24(8):1695-1712.(CHEN X, CHEN J H, JU X L, et al. Survey of test case prioritization techniques for regression testing [J]. Journal of Software, 2013, 24(8): 1695-1712.)
[5] EPITROPAKIS M G, YOO S, HARMAN M, et al. Empirical evaluation of Pareto efficient multi-objective regression test case prioritisation [C]// Proceedings of the 2015 International Symposium on Software Testing and Analysis. New York: ACM, 2015: 234-245.
[6] DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-Ⅱ [C]// Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. Berlin: Springer, 2000: 849-858.
[7] YOO S, HARMAN M. Using hybrid algorithm for Pareto efficient multi-objective test suite minimisation [J]. Journal of Systems and Software, 2010, 83(4): 689-701.
[8] SINGH Y, KAUR A, SURI B. Test case prioritization using ant colony optimization [J]. ACM SIGSOFT Software Engineering Notes, 2010, 35(4): 1-7.
[9] DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by a colony of cooperative Agents [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 1-13.
[10] DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization [J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39.
[11] 顾聪慧,李征,赵瑞莲.基于 ACO 的测试用例预优化及参数影响分析[J].计算机科学与探索,2014,8(12):1463-1473.(GU C H, LI Z, ZHAO R L. ACO based test case prioritization and impact analysis of parameters [J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(12): 1463-1473.)
[12] 朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报,2004,15(2):185-192.(ZHU Q B, ZHANG Z J. An ant colony optimization algorithm based on mutation and dynamic pheromone updating [J]. Journal of Software, 2004, 15(2):185-192.)
[13] STUTZLE T, HOOS H. MAX-MIN ant system and local search for the traveling salesman problem [C]// Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Piscataway, NJ: IEEE, 1997: 309-314.
[14] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[15] YUAN F, BIAN Y, LI Z, et al. Epistatic genetic algorithm for test case prioritization [M]// BARROS M, LABICHE Y. Search-Based Software Engineering, LNCS 9275. Berlin: Springer, 2015: 109-124.
[16] PELLEGRINI P, STVTZLE T, BIRATTARI M. A critical analysis of parameter adaptation in ant colony optimization [J]. Swarm Intelligence, 2012, 6(1): 23-48.
[17] STÜTZLE T, LÓPEZ-IBÁÑEZ M, PELLEGRINI P, et al. Parameter adaptation in ant colony optimization [M]// HAMADI Y, MONFROY E, SAUBION F. Autonomous Search. Berlin: Springer, 2012: 191-215.

Pheromone updating strategy of ant colony algorithm for multi-objective test case prioritization

面向多目标测试用例优先排序的蚁群算法信息素更新策略

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[2]	LI Mengmeng, QIN Wei, LIU Yi, DIAO Xingchun. Hybrid ant colony optimization algorithm with brain storm optimization [J]. Journal of Computer Applications, 2021, 41(8): 2412-2417.
[3]	WEI Mingyan, CHEN Yu, ZHANG Liang. Coevolutionary ant colony optimization algorithm for mixed-variable optimization problem [J]. Journal of Computer Applications, 2021, 41(5): 1412-1418.
[4]	FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582.
[5]	WANG Hongyu, ZHANG Yu, YANG Heng, MU Nan. Salient object detection in weak light images based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2021, 41(10): 2970-2978.
[6]	XIONG Yong, ZHANG Jia, YU Jiajun, ZHANG Benren, LIANG Xuanzhuo, ZHU Qige. Intelligent layout optimization algorithm for 3D pipelines of ships [J]. Journal of Computer Applications, 2020, 40(7): 2164-2170.
[7]	XU Yingxin, SUN Lei, ZHAO Jiancheng, GUO Songhui. Virtual field programmable gate array placement strategy based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2020, 40(3): 747-752.
[8]	WANG Shuyan, YUAN Jiajuan, SUN Jiaze. Test suite reduction method based on weak mutation criterion [J]. Journal of Computer Applications, 2019, 39(2): 534-539.
[9]	WANG Qingrong, WANG Ruifeng. Reconfiguration strategy of distribution network based on improved particle swarm optimization [J]. Journal of Computer Applications, 2018, 38(9): 2720-2724.
[10]	QI Pan, BAO Kaiyang, MA Xiaoyuan. WSN hierarchical routing algorithm based on fuzzy C-means clustering and swarm intelligence [J]. Journal of Computer Applications, 2018, 38(7): 1974-1980.
[11]	CHEN Xuan, XU Jianwei, LONG Dan. Resource scheduling algorithm of cloud computing based on ant colony optimization-shuffled frog leading algorithm [J]. Journal of Computer Applications, 2018, 38(6): 1670-1674.
[12]	XU Kaibo, LU Haiyan, CHENG Biyun, HUANG Yang. Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP [J]. Journal of Computer Applications, 2017, 37(6): 1686-1691.
[13]	BAO Zhenhua, KANG Baosheng, ZHANG Lei, ZHANG Jing. Sketch-based image retrieval method using local geometry moment invariant [J]. Journal of Computer Applications, 2017, 37(6): 1753-1758.
[14]	WANG Shuyan, CHEN Pengyuan, SUN Jiaze. Reduction method of test suites based on mutation analysis [J]. Journal of Computer Applications, 2017, 37(12): 3592-3596.
[15]	WANG Shuyan, WEN Chunyan, SUN Jiaze. Test data augmentation method based on adaptive particle swarm optimization algorithm [J]. Journal of Computer Applications, 2016, 36(9): 2492-2496.