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