Ant colony optimization for software engineers
Pages 1527 - 1541
Abstract
Many software engineering tasks can be formulated as search problems. Building tests requires selecting among infinite test inputs to maximise code coverage. In systems with large test-suites and limited resources, developers choose test execution order among all possible test-case permutations to maximise fault detection. Search-Based Software Engineering (SBSE) is the application of search-based optimisation algorithms to software engineering problems. In this tutorial, we showcase SBSE by demonstrating the application of Ant Colony Optimisation (ACO) to software testing.
The ACO metaheuristic is inspired by the foraging behaviour of ants. Artificial ants build candidate solutions, depositing pheromone over its solution components. Pheromone deposits are proportional to solution quality, and ants prefer components with high pheromone values. Over time, the colony converges towards an optimal solution.
This tutorial is divided into three parts. In the first part, we introduce the ACO metaheuristic. We discuss ant, graph, and pheromone matrix representations for discrete and continuous problems. In the second part, we detail an ACO application to automatic test generation for multiple corpora. Finally, in the third part, we demonstrate Isula, a Java library for implementing ACO algorithms (available at: https://github.com/cptanalatriste/isula). We use Isula to incrementally solve an instance of the Unicost Set Covering Problem.
References
[1]
[A] Mao, C., Xiao, L., Yu, X., & Chen, J. (2015). Adapting ant colony optimization to generate test data for software structural testing. Swarm and Evolutionary Computation, 20, 23--36.
[2]
[B] Socha, K., & Dorigo, M. (2008). Ant colony optimization for continuous domains. European journal of operational research, 185(3), 1155--1173.
[3]
[C] Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28--39.
[4]
[D] Cotlieb, A., & Petit, M. (2010). A uniform random test data generator for path testing. Journal of Systems and Software, 83(12), 2618--2626.
[5]
[E] Bruce, D., Menéndez, H. D., & Clark, D. (2019, August). Dorylus: An ant colony based tool for automated test case generation. In International Symposium on Search Based Software Engineering (pp. 171--180). Springer, Cham.
[6]
[F] Bruce, D., Menéndez, H. D., Barr, E. T., & Clark, D. (2020, October). Ant colony optimization for object-oriented unit test generation. In International Conference on Swarm Intelligence (pp. 29--41). Springer, Cham.
[7]
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29--41.
[8]
Dorigo, M., & Cambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1). 53--66.
[9]
Wiesemann, W., & Stützle, T. (2006). Iterated Ants: An Experimental Study for the Quadratic Assignment Problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Vol. 4150 LNCS (pp. 179--190).
[10]
Stutzle, T., & Hoos, H. (1997). MAX-MIN Ant System and local search for the traveling salesman problem. Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC'97), 309--314.
[11]
Stützle, T (1998). Parallelization strategies for Ant Colony Optimization. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Vol. 1498 LNCS (Issue March, pp. 722--731).
[12]
Cavidia-Calderon, C., & Beltrán Castañon, C. (2020). Isula: A java framework for ant colony algorithms. SoftwareX, 11, 100400.
[13]
Brévilliers, M., Lepagnot, J., & Idoumghar, L. (2021). CECCO 2021 Competition on the Optimal Camera Placement Problem (OCP) and the Unicost Set Covering Problem (USCP).
[14]
de A Silva, R. M., & Ramalho, G. L. (2001). Ant system for the set covering problem. 2001 IEEE International Conference on Systems, Man and Cybernetics. e-Systems and e-Man for Cybernetics in Cyberspace (Cat.No.01CH37236), 5(1), 3129--3133.
[15]
Brownlee, J. (2011). Clever Algorithms: Nature-inspired Programming Recipes. United Kingdom: Lulu.com.
[16]
Stützle, T., & others. (1998). An ant approach to the flow shop problem. Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT'98), 3, 1560--1564.
[17]
Malisia, A. R., & Tizhoosh, H. R. (2006). Applying Ant Colony Optimization to Binary Thresholding. 2006 International Conference on Image Processing, 2409--2412.
[18]
Ouadfel, S., & Batouche, M. (2002). Unsupervised Image Segmentation Using a Colony of Cooperating Ants. In Biologically Motivated Computer Vision (pp. 109--116).
[19]
Ren, Z. G., Feng, Z. R., Ke, L. J., & Zhang, Z. J. (2010). New ideas for applying ant colony optimization to the set covering problem. Computers and Industrial Engineering. 58(4). 774--784.
Index Terms
- Ant colony optimization for software engineers
Index terms have been assigned to the content through auto-classification.
Recommendations
Ant colony optimization
Swarm intelligence is a relatively new approach to problem solving that takes inspiration from the social behaviors of insects and of other animals. In particular, ants have inspired a number of methods and techniques among which the most studied and ...
Study on Immunized Ant Colony Optimization
ICNC '07: Proceedings of the Third International Conference on Natural Computation - Volume 04Ant Colony Optimization (ACO) is a new natural computation method from mimic the behaviors of ant colony.It is a very good combination optimization method. To extend the ant colony optimization, some continuous Ant Colony Optimizations have been ...
The ant colony optimisation solving continuous problems
This paper presents an approach for solving the economic power dispatch EPD problem using the ant colony optimisation for continuous domains ACOR algorithm Socha and Dorigo, 2008. ACO family algorithms are inspired by the way that real ants searching ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
2395 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 July 2022
Check for updates
Qualifiers
- Tutorial
Funding Sources
Conference
GECCO '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 68Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in