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

Space of all possible solutions

Fig. 5. Simulated Annealing also seeks to improve a single solution, but moves may be
made to points in the search space of poorer fitness (adapted from McMinn [66])

potential moves along with better neighbouring solutions. As the search pro-
gresses, however, the temperature reduces, making moves to poorer solutions
more and more unlikely. Eventually, freezing point is reached, and from this point
on the search behaves identically to Hill Climbing. Pseudo-code for the Simulated
Annealing algorithm can be seen in Figure 6. The probability of acceptance p of
an inferior solution is calculated as p = e − t ,where δ is the difference in fitness
value between the current solution and the neighbouring inferior solution being
considered, and t is the current value of the temperature control parameter.

Select a starting solution s

S
Select an initial temperature t> 0
Repeat
it ← 0
Repeat
Select s ∈ N ( s ) at random
Δe

∈

fit ( s )

← fit ( s ) −

If Δe < 0
s s ←

Else

Generate random number r ,0 ≤ r< 1

If r<e − t Then s

← s

End If
it it +1

Until it = num solns
Decrease t according to cooling schedule
Until Stopping Condition Reached

←

Fig. 6. High level description of a simulated annealing algorithm, for a problem with
solution space S ; neighbourhood structure N ; num solns , the number of solutions to
consider at each temperature level

t ;and fit , the fitness function to be maximised

(adapted from McMinn [65])