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

•

a heuristic to generate good initial solutions. Typically, the initial array is ran-
domly generated, and then the SA process is started. But ISA uses an initialization
procedure that keeps a balanced number of symbols in each column of the array.

• a compound neighborhood function, which combines two carefully designed

neighborhood relations. The neighborhood function specifies the set of poten-
tial solutions that can be reached (in one step) from the current solution. For every
potential solution/array A , it assigns a set of neighboring solutions, which is called
the neighborhood of A .

Simulated annealing can be combined with other techniques. Cohen et al. [ 8 ]
proposed a method for constructing covering arrays, which combines SA with the
algebraic approach (based on mathematical results). Using this method, the authors
obtained new bounds on the size of some strength three covering arrays.
Rodriguez-Cristerna and Torres-Jimenez [ 41 ] proposed a hybrid approach to the
construction of mixed covering arrays, which combines SA with a Variable Neigh-
borhood Search function. It is called SA-VNS.

5.5 Particle Swarm Optimization

Particle Swarm Optimization (PSO) [ 30 , 42 ] is a method for optimizing continuous
nonlinear functions. For example, finding an assignment to variables x and y (within
a certain range), so as to minimize a function like x 2

+ −

3. The algorithm
simulates some social behaviors of humans and animals (e.g., that of flying birds).
In a PSO algorithm, there are also a population of candidate solutions (called
a swarm of particles). The position of each particle represents a possible solution.
However, different from other evolutionary methods like genetic algorithms, a PSO
has a velocity vector. Each particle moves in the search space with some velocity.
PSO is an iterative process. In each iteration, each particle's current velocity is
first updated; then its position is updated using the new velocity.
There are several parameters in the PSO algorithm, e.g., the number of particles,
the neighborhood size (that is, how many nearest neighbors can influence an article),
the maximum velocity. The values of these parameters have quite some influence
on the performance of the algorithm. Various researchers have studied how to select
good parameter values for PSO. See for example, [ 16 , 38 , 48 ].
There are some open-source implementations of PSO. For example, SwarmOps
(for numerical and heuristic optimization) is available at http://www.hvass-labs.org/
projects/swarmops/
Ahmed et al. [ 1 , 2 ] applied PSO to the construction of covering arrays. Their tool
Particle Swarm-based t -way Test Generator (PSTG) can be used to generate uniform
and variable strength covering arrays. It compares favorably with other tools like
PICT, Jenny, IPOG/IPOG-D etc., in terms of the size of the generated test suite.

xy