Information Technology Reference
In-Depth Information
is discrete. For certain problems, simulated annealing may be more effective
than exhaustive enumeration—provided that the goal is merely to find an
acceptable good solution in a fixed amount of time, rather than the best pos-
sible solution.
In the SA method, each point
s
of the search space is analogous to a state
of some physical system, and the function
E
(
s
) to be minimized is analo-
gous to the internal energy of the system in that state. The goal is bring
the system, from an arbitrary initial state, to a state with the minimum
possible energy.
The neighbors of each state (the candidate moves) are specified by the user,
usually in an application-specific way.
The probability of making the transition from the current state
s
to a can-
didate new state
s
′ is specified by an acceptance probability function
P
(
e
,
e
′,
T
), that depends on the energies
e
=
E
(
s
) and
e
′ =
E
(
s
′) of the two states, and on
a global time-varying parameter
T
called the temperature. The pseudo code
is shown in Figure 3.18.
3.5.6 Performance evaluation
There are a total of 54 samples of video files. We use a different size of train-
ing sets to estimate the PEVQ expression. The training set is separated to 5,
10, 18, and 30.
s := s0; e := E(s) // Initial state,energy.
1.
2.
sb := s; eb := e // Initial “best” solution
3.
k := 0 // Energy evaluation count.
while k < kmax and e > emax // While time remains and not good enough:
4.
5.
sn := neighbor(s) // Pick some neighbor.
6.
en := E(sn) // Compute its energy.
if en < eb then // Is this a new best?
7.
sb := sn; eb := en // Yes, save it.
8.
9.
if P(e,en,temp(k/kmax)) > random()then // Should we move to it?
s := sn; e := en // Yes, change state.
10.
k := k + 1 // One more evaluation done
11.
12.
return sb // Return the best solution found.
Figure 3.18
Simulated annealing pseudo code.
