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

'Simulated Annealing' is named so because it was inspired by the physical
process of annealing; the cooling of a material in a heat bath. When a solid
material is heated past its melting point and then cooled back into its solid
state, the structural properties of the final material will vary depending on the
rate of cooling.
Hill Climbing and Simulated Annealing are said to be local searches , because
they operate with reference to one candidate solution at any one time, choosing
'moves' based on the neighbourhood of that candidate solution. Genetic Algo-
rithms, on the other hand, are said to be global searches , sampling many points
in the search space at once (Figure 7), offering more robustness to local optima.
The set of candidate solutions currently under consideration is referred to as the
current population , with each successive population considered referred to as a
generation . Genetic Algorithms are inspired by Darwinian Evolution, in keeping
with this analogy, each candidate solution is represented as a vector of compo-
nents referred to as individuals or chromosomes . Typically, a Genetic Algorithm
uses a binary representation, i.e. candidate solutions are encoded as strings of 1s
and 0s; yet more natural representations to the problem may also be used, for
example a list of floating point values.
The main loop of a Genetic Algorithm can be seen in Figure 8. The first
generation is made up of randomly selected chromosomes, although the popu-
lation may also be 'seeded' with selected individuals representing some domain
information about the problem, which may increase the chances of the search
converging on a set of highly-fit candidate solutions. Each individual in the pop-
ulation is then evaluated for fitness.
On the basis of fitness evaluation, certain individuals are selected to go for-
ward to the following stages of crossover, mutation and reinsertion into the next
generation. Usually selection is biased towards the fitter individuals, however the
possibility of selecting weak solutions is not removed so that the search does not
converge early on a set of locally optimal solutions. The very first Genetic Al-
gorithm, proposed by Holland 1 , used 'fitness-proportionate' selection, where the
expected number of times an individual is selected for reproduction is propor-
tionate to the individual's fitness in comparison with the rest of the population.
However, fitness-proportionate selection has been criticised because highly-fit in-
dividuals appearing early in the progression of the search tend to dominate the
selection process, leading the search to converge prematurely on one sub-area of
the search space. Linear ranking [100] and tournament selection [23] have been
proposed to circumvent these problems, involving algorithms where individuals
are selected using relative rather than absolute fitness comparisons.
In the crossover stage, elements of each individual are recombined to form
two offspring individuals. Different choices of crossover operator are available,
including 'one-point' crossover, which splices two parents at a randomly-chosen
position in the string to form two offspring. For example, two strings ' 111 'and
' 000 ' may be spliced at position 2 to form two children ' 100 'and' 011 '. Other
1 This was introduced by Holland [54], though Turing had also briefly mentioned the
idea of evolution as a computational metaphor [94].