Ant Colony Optimization for Software Engineers

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