Search Based Software Engineering: Techniques, Taxonomy, Tutorial - Empirical Software Engineering and Verification - page 31

Algorithm. A popular Genetic Algorithm for Search Based Structural Test
Data Generation is that of Wegener et al. [97], which we will refer to as the
'Wegener GA' hereinafter. The GA uses a population size of 300 individuals,
divided across 6 subpopulations, initially made up of 50 individuals each. It uses
a linear ranking method [100] as part of the selection phase. Linear ranking sorts
the population into fitness order as assigns new ranked fitness values such that
the best individual is awarded a ranked fitness of Z , the median individual a
value of 1 and the worst individual a value of Z

−

2. The Wegener GA uses a
value of Z =1 . 7. Stochastic universal sampling [14] is then used as a selection
method, whereby individuals are selected with a probability proportionate to its
ranked fitness value. The selection method therefore favours fitter individuals,
but the use of ranked fitness values rather than direct values helps prevent
super-fit individuals from being selected as many times as they would have been
normally, which may go on to dominate the next generation and cause the search
to converge prematurely.
The Wegener GA uses a special type of mutation that is well-suited for test
data generation problems involving real values. The mutation operator is de-
rived from the Breeder GA [71]. Mutation is applied with a probability p m of
1 /len ,where len is the length of the input vector. The mutation operator ap-
plies a different mutation step size, 10 −pop , depending on the subpopulation
pop, 1 6. A mutation range r is defined for each input parameter by the

product of pop and the domain size of the parameter. The 'mutated' value of an
input parameter can thus be computed as v = v

≤ pop ≤

± r · δ . Addition or subtraction

is chosen with an equal probability. The value of δ is defined to be 15

2 −y ,
where each α y is 1 with a probability of 1 / 16 else 0. If a mutated value is outside
the allowed bounds of a variable, its value is set to either the minimum or max-
imum value for that variable. Discrete recombination [71] is used as a crossover
operator. Discrete recombination is similar to uniform crossover. However with
uniform crossover, genes (input values) are guaranteed to appear in one of the
offspring. With discrete recombination offspring individuals receive 'genes' ( i.e.
input variable values) from either parent with an equal probability. Thus a par-
ticular gene may be copied into both children, one of the children or neither
child.
The Wegener GA, uses an elitist reinsertion strategy, with the top 10% of
a current generation retained and used in the next, with the remaining 90%
discarded and replaced by the best offspring.
Finally the Wegener GA incorporates competition and migration between each
of its subpopulations. A progress value, prog , is computed for each population
at the end of a generation. This value is obtained using the formula 0 . 9

y =0 α y ·

· prog +

0 . 1 rank . The average fitness rank for a population is obtained by linearly

ranking its individuals as well as the populations amongst themselves (again
with Z =1 . 7). After every 4 generations, the populations are ranked according
to their progress value and a new slice of the overall population is computed
for each, with weaker subpopulations transferring individuals to stronger ones.
However, no subpopulation can lose its last 5 individuals, preventing it from

·