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

move

p 1

g

Fig. 5.1 Local minimum

They are sometimes called Nature-Inspired Algorithms [ 6 , 51 ]. The following are
some well-known algorithms for solving difficult optimization problems: Genetic
Algorithms, Simulated Annealing, Particle Swarm, Artificial Immune Systems, Ant
Colony Optimization, Bees Algorithm, and so on. These algorithms are also called
evolutionary algorithms [ 11 , 44 , 50 ].

5.2 Applying Evolutionary Algorithms to Test Generation

Quite some of the above-mentioned evolutionary algorithms (EAs) have been applied
to the generation of covering arrays (CAs). See for example, [ 4 , 9 , 36 , 45 ].
We may distinguish between two different ways of applying EAs to the generation
of CAs. One approach is local , i.e., embed an EA into some greedy method like
AETG. Specifically, we use an EA to find the new test case, inAlgorithm1 (Sect. 3.1 ) .
See Fig. 5.2 a. We try to determine the last row, using some EA.
The other approach is global , in the sense that, we apply an EA to find the whole
covering array. See Fig. 5.2 b. In this case, we usually assume that the array has some
fixed number of rows, e.g., N .

Fig. 5.2 Different ways of
applying evolutionary
algorithms

(a) (b)

????
????
????
????
????
????

1111
1222
2211
????