Information Technology Reference
In-Depth Information
Rescaled Simulated Annealing Algorithm
Set
Nb
accepted
=1.
While
Nb
accepted
is non-zero
Nb
tested
=
Nb
accepted
=0
While
Nb
tested
<Nb
maxtest
/* Generalized Metropolis algorithm */
Increment
Nb
tested
.
Pick at random a valid transition.
Calculate the energy variation ∆
E
.
M
od
ify the energy variation by subtracting
2
αT
(
√
E
+∆
E
−
−
√
E
)fromit
If ∆
E<
0 then /* Accepted transition */
Perform the transition.
Update the energy
E
:
E
:=
E
+∆
E
.
Increment
Nb
accepted
.
Compare the new state with the best state found from the
beginning of the search, and store it in memory if it is bet-
ter.
Otherwise
Pick at random a real number
rand
in [0
,
1].
If
rand <
exp(
∆
E/T
) then /* Accepted transition */
Perform the transition.
Update the energy
E
:
E
:=
E
+∆
E
.
Increment
Nb
accepted
.
Decrease the temperature:
T
:=
dec T
/* Annealing */
Return the best state encountered during the search.
−
8.5.3.4 Microcanonical Annealing
Initialisation of the Algorithm
Define the minimal percentage
p
of accepted transitions on the first step.
Choose the initial total energy
E
t
such that
p
% of the tested transitions
are accepted.
Generate randomly a valid solution and calculate its energy
E
.
Select the maximal number of tested transitions on each step:
Nb
maxtest
.
Select the parameter for the temperature decrease between two steps:
dec
.
Search WWH ::
Custom Search