Information Technology Reference
In-Depth Information
Space of all possible solutions
Fig. 7. Genetic Algorithms are global searches, taking account of several points in the
search space at once (adapted from McMinn [66])
Randomly generate or seed initial population P
Repeat
Evaluate fitness of each individual in P
Select parents from P according to selection mechanism
Recombine parents to form new offspring
Construct new population P from parents and offspring
Mutate P
P
P
Until Stopping Condition Reached
Fig. 8. High level description of a Genetic Algorithm, adapted from McMinn [65]
operators may recombine using multiple crossover points, while 'uniform' crossover
treats every position as a potential crossover point.
Subsequently, elements of the newly-created chromosomes are mutated at ran-
dom, with the aim of diversifying the search into new areas of the search space.
For GAs operating on binary representation, mutation usually involves randomly
flipping bits of the chromosome. Finally, the next generation of the population
is chosen in the 'reinsertion' phase, and the new individuals are evaluated for
fitness. The GA continues in this loop until it finds a solution known to be glob-
ally optimal, or the resources allocated to it (typically a time limit or a certain
budget of fitness evaluations) are exhausted. Whitley's tutorial papers [101, 102]
offer a further excellent introductory material for getting starting with Genetic
Algorithms in Search Based Software Engineering.
5 Getting the First Result: A Simple Example for
Regression Testing
This section presents an application of a search-based approach to the Test
Case Prioritisation (TCP) in regression testing, illustrating the steps that are
Search WWH ::




Custom Search