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

5.6 Tabu Search

Tabu search [ 22 - 25 ] is an effectivemetaheuristic searchmethod for solving optimiza-
tion problems. Tabu (taboo) means “forbidden”, “prohibited”, “banned”. Tabu search
improves the performance of local search methods by remembering the recently vis-
ited solutions. If a certain region of the search space has been visited recently, then
it is marked as tabu, and the search process is not allowed to visit the region again
(in the near future).
Nurmela [ 37 ] uses tabu search to find small covering arrays of strength t .As
usual, the problem is regarded as an optimization problem, whose cost function is
the number of uncovered t -combinations.
The approach starts with a randommatrix and moves to neighbors repeatedly until
a matrix with zero cost (covering array) is found or the number of moves has reached
a prescribed limit. At each step, the approach selects one uncovered t -combination
at random. It checks which rows require only the change of one element such that the
row covers the selected combination. These changes are the moves to be considered.
The cost change corresponding to each move is calculated and the move leading to
the smallest cost is selected, provided that the move is not tabu. If there are several
equally good non-tabu moves, a move is selected randomly. The tabu condition
prevents changing an element of the matrix, if it has been changed during the last T
moves. Here T is some small positive integer (e.g., 1

10).
Recently, Walker and Colbourn [ 49 ] introduced an effective tabu search method
for finding certain covering arrays. Such covering arrays have a compact represen-
tation which employs “permutation vectors”. With the new technique, improved
covering arrays of strength 3, 4, and 5 have been found.
Gonzalez-Hernandez and Torres-Jimenez [ 27 ] proposed another tabu search
method (called MiTS) for constructing mixed covering arrays. This approach uses a
mixture of neighborhood functions and a fine tuning process to improve the perfor-
mance of tabu search.
Let N denote the number of rows (test cases), and k denote the number of columns
(parameters). Let s denote a candidate solution, and

≤ T ≤

is an arbitrary position in
thematrix(the i th row, the j th column). Suppose the j th parameter can take v j
different values.
Instead of using a single neighborhood function F

( i , j )

( s ) , MiTS uses the following

three functions:

• F 1 ( s ) : A neighbor is obtained by changing the symbol/value at position ( i , j ) .

Using this function, s has v j − 1 possible neighbors.

• F 2 ( : A neighbor is obtained by changing the symbol/value at any position in

column j - but only one position is allowed to change each time. Using this
function, s has

s )

( v j − 1 ) ∗ N possible neighbors.

• F 3 ( : The change can be made to any single element in the matrix. Using this

function, s has

s )

( v j − 1 ) ∗ N ∗ k possible neighbors.