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

if (count >= 4)

FALSE TRUE

approach level = 2
branch distance = 4 - count + K

if (count <= 10)

FALSE TRUE

approach level = 1
branch distance = count - 10 + K

if (checksum % 10
== checkdigit)

FALSE TRUE

approach level = 0
branch distance =|(checksum % 10) - checkdigit| + K

TARGET

Fig. 16. Fitness function computation for execution of the true branch from line 19 of
the CAS registry number check program of Figure 15, taken from McMinn [66]

When execution of a test case diverges from the target branch, the second
component, the branch distance , expresses how close an input came to satisfying
the condition of the predicate at which control flow for the test case went 'wrong';
that is, how close the input was to descending to the next approach level. For
example, suppose execution takes the false branch at node 17 in Figure 15, but
the true branch needs to be executed. Here, the branch distance is computed
using the formula 4

count + K ,where K is a constant added when the undesired,
alternate branch is taken. The closer count is being greater than 4, the 'closer'
the desired true branch is to being taken. A different branch distance formula
is applied depending on the type of relational predicate. In the case of y>=x ,
and the >= relational operator, the formula is x

−

y + K . For a full list of branch
distance formulae for different relational predicate types, see Tracey et al. [93].
The complete fitness value is computed by normalising the branch distance
and adding it to the approach level:

−

fit ( t, i )= approach level ( t, i )+ normalise ( branch distance ( t, i ))

Since the maximum branch distance is generally not known, the standard ap-
proach to normalisation cannot be applied [7]; instead the following formula is
used:

1 . 001 −d

normalise ( d )=1 −