Information Technology Reference
In-Depth Information
Space of all possible solutions
(a) A climb to a local optimum
Space of all possible solutions
(b) A restart resulting in a climb to the global optimum
Fig. 3.
Hill Climbing seeks to improve a single solution, initially selected at random,
by iteratively exploring its neighbourhood (adapted from McMinn [66])
Select a starting solution
s
∈
S
Repeat
Select
s
∈
N
(
s
) such that
fit
(
s
)
>fit
(
s
) according to ascent strategy
s
Until
fit
(
s
)
s
←
≥
fit
(
s
)
,
∀
s
∈
N
(
s
)
Fig. 4.
High level description of a hill climbing algorithm, for a problem with solution
space
S
; neighbourhood structure
N
;and
fit
, the fitness function to be maximised
(adapted from McMinn [65])
Simulated Annealing (Figure 5), first proposed by Kirkpatrick et al. [56], is
similar to Hill Climbing in that it too attempts to improve one solution. How-
ever, Simulated Annealing attempts to escape local optima without the need
to continually restart the search. It does this by temporarily accepting candi-
date solutions of poorer fitness, depending on the value of a variable known
as the
temperature
. Initially the temperature is high, and free movement is al-
lowed through the search space, with poorer neighbouring solutions representing
Search WWH ::
Custom Search