Information Technology Reference
In-Depth Information
t1
t3
t0
t2
t5
t4
Fig. 9.
One possible candidate solution for TCP with a regression test suite with 6
tests,
{
t
0
,...,t
5
}
Neighbouring Solutions.
Unless the characteristics of the search landscape is
known, it is recommended that the neighbouring solutions of a given solution for
a local search algorithm is generated by making the smallest possible changes to
the given solution. This allows the human engineer to observe and understand
the features of the search landscape.
It is also important to define the neighbouring solutions in a way that produces
a manageable number of neighbours. For example, if the set of neighbouring
solutions for TCP of size
n
is defined as the set of all permutations that can be
generated by swapping two tests, there would be
n
(
n
1) neighbouring solutions.
However, if we only consider swapping adjacent tests, there would be
n
−
1. If the
fitness evaluation is expensive, i.e. takes non-trivial time, controlling the size of
the neighbourhood may affect the eciency of the search algorithm significantly.
−
Genetic Operators.
The following is a set of simple genetic operators that
can be defined over permutation-based representations.
- Selection:
Selection operators tend to be relatively independent of the
choice of representation. It is more closely related to the design of the fit-
ness function. One widely used approach that is also recommended as the
first step is
n
-way tournament selection. First, randomly sample
n
solutions
from the population. Out of this sample, pick the fittest individual solution.
Repeat once again to select a pair of solutions for reproduction.
- Crossover:
Unlike selection operators, crossover operators are directly linked
to the structure of the representation of solutions. Here, we use the crossover
operator following Antoniol et al. [6] to generate, from parent solutions
p
1
and
p
2
, the offspring solutions
o
1
and
o
2
:
1. Pick a random number
k
(1
n
)
2. The first
k
elements of
p
1
become the first
k
elements of
o
1
.
3. The last
n
≤
k
≤
k
elements that
remain when the
k
elements selected from
p
1
are taken from
p
2
, as illus-
trated in Figure 10.
4.
o
2
is generated similarly, composed of the first
n
−
k
elements of
o
1
are the sequence of
n
−
−
k
elements of
p
2
and
the remaining
k
elements of
p
1
.
- Mutation:
Similarly to defining the neighbouring solutions for local search
algorithms, it is recommended that, initially, mutation operators are defined
to introduce relatively small changes to individual solutions. For example,
we can swap the position of two randomly selected tests.
Search WWH ::
Custom Search