Neural Networks without Training for Optimization - Neural Networks: Methodology and Applications - page 461

Microcanonical Annealing Algorithm

Set Nb accepted =1.
While Nb accepted is non-zero
Nb tested = Nb accepted =0
While Nb tested <Nb maxtest /* Creutz algorithm */
Increment Nb tested .
Pick at random a valid transition.
Calculate the energy variation ∆ E .
If ∆ E = E t −

E is positive, then /* Accepted transition */
Perform the transition.
Update the energy E : E := E +∆ E .
Increment Nb accepted .
If ∆ E< 0, compare the new state with the best state
found from the beginning of the search, and memorize it if
it is better.
Decrease the total energy: E t := dec E t /* Annealing */
Return the best state encountered during the search.

To come close to optimal solutions of the problem illustrated on Fig. 8.1,
the following values of the parameters can be used:

• p = 90%

• dec =0 , 99

• Nb maxtest = 500000 .

With those parameter values, Figs. 8.5 and 8.6 show, for the standard simu-
lated annealing and the rescaled simulated annealing, the decrease of the mean
energy of the states visited during the convergence, as well as the length of
the best tour, found as the search converges. The mean energy of the solutions
is computed as

E i exp

√ E i −

αT 2

−

T

i

E =

exp

.

√ E i −

αT 2

−

T

i

Those curves were obtained by computing averages over 100 runs with
different initializations of the random number generator. With identical pa-
rameters in the two algorithms, one observes that the energy rescaling speeds