Evolutionary Computation and Metaheuristics - Automatic Generation of Combinatorial Test Data - page 55

5.7 Other Methods
During the past 20years, many evolutionary algorithms have been developed. In this
section, we briefly describe several such algorithms that have been used for finding
combinatorial test suites.
Ant Colony optimization (ACO) [ 13 - 15 ] is an algorithm inspired by the behavior
of ants. Each ant is very small and its ability is very limited. However, by working
together, the ants are very good at performing various tasks. For example, they can
often find a short path to a food source. Thus a natural application of ACO is to find
optimal paths, e.g., solving the traveling salesman problem (TSP) [ 12 ].
In addition to AETG-GA, Shiba et al. [ 43 ] also proposed a test generation pro-
cedure called AETG-ACA, which extends the basic AETG algorithm with the ant
colony algorithm.
Chen et al. [ 5 ] also extended the one-test-at-a-time strategy to build test suites.
When generating a single test case, they adopted the ant colony system (ACS) strat-
egy, which is an effective variant in the ACO family.
The Bees algorithm, proposed by Duc Truong Pham et al. [ 39 ], is a population-
based search algorithm for solving optimization problems. It is inspired by the food
foraging behaviour of swarms of honey bees.
Independently, Dervis Karaboga and his collaborators proposed the Artificial Bee
Colony algorithm ( http://mf.erciyes.edu.tr/abc/index.htm ) .
McCaffrey [ 33 ] implemented the Bee Colony algorithm to find pair-wise test
suite. His tool SBC compares favorably with other tools like PICT and AETG on the
size of the test suite. But its running time is much longer. For some instance, it needs
around 20min to find a solution, while PICT finishes within a few seconds.
Harmony search [ 18 , 19 ] is another evolutionary algorithm for solving optimiza-
tion problems, which is inspired by musical processes. Alsewari and Zamli [ 3 ]pro-
posed a test generation method based on harmony search algorithm, called Harmony
Search Strategy (HSS). HSS addresses the support for high interaction strength and
the support for constraints. HSS was implemented in Java. Compared with other
tools like PICT, Density and IPOG, HSS is shown to be able to obtain smaller test
suites.
References
1. Ahmed, B.S., Zamli, K.Z.: A variable strength interaction test suites generation strategy using
particle swarm optimization. J. Syst. Softw. 84 (12), 2171-2185 (2011)
2. Ahmed, B.S., Zamli, K.Z., Lim, C.P.: Application of particle swarm optimization to uniform
and variable strength covering array construction. Appl. Soft Comput. 12 (4), 1330-1347 (2012)
3. Alsewari, A.R.A., Zamli, K.Z.: Design and implementation of a harmony-search-based
variable-strength t-way testing strategy with constraints support. Inf. Softw. Technol. 54 (6),
553-568 (2012)