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

L. Herault
∆ E ij = E j −

E target 2

E i −

E target 2

− .

This modification is a generalization of the Metropolis algorithm: the latter
is retrieved by imposing E target =0.
It can be shown that the following decreasing law of the target energy
guarantees satisfactory asymptotic convergence to the optimal solutions,

E target = αT 2 ,

where α is a positive real number.
That generalization of simulated annealing can be viewed as modifying
the energy landscape during the convergence of the algorithm. The rescaled
simulated annealing starts from a flattened energy landscape, which is then
progressively unfolded in an ad-hoc manner, at each temperature step. It is im-
portant to note that that unfolding does not affect the location of the extrema
of the original function. To illustrate this behaviour, consider the example of
a mono-dimensional function to be minimized, given on Fig. 8.3. Figure 8.4
shows the evolution of that function as a function of the target energy. When
the latter is zero, the recomputed function is the original one. When the tar-
get energy is high, the minima of the recomputed function correspond to the
maxima of the original function. Therefore, if the target energy is high at the
beginning of the search, the most probable states derived from the Metropolis
criterion will be the crests of the original function. Once the target energy is
smaller than the absolute minimum of the original function, the recalculated
function and the original one have their minima at the same locations, with
the same relative depths. Moreover, when the target energy decreases, the
minima of the recomputed function converge to those of the original function.
As in simulated annealing, homogeneous and inhomogeneous algorithms can
be defined. In terms of coding, no modification compared to the simulated
annealing is necessary.
The properties of asymptotic convergence to optimal solutions have been
proved; they compare favourably with those of simulated annealing.
The Metropolis algorithm minimizes the free energy of the system with
the corrected energies. In other respects, it can be shown that the asymptotic
convergence to thermodynamical equilibrium (stationary distribution of the
states) is estimated faster than with the Metropolis algorithm. Therefore, at
each temperature step, the distance to stationarity after a finite number of
elementary transitions is smaller than with the original metropolis algorithm.
As with simulated annealing, it can be shown that the homogeneous algo-
rithm converges asymptotically to the optimal solutions.
As far as the inhomogeneous algorithm is concerned, a su cient condition
on the cooling schedule between two elementary transitions is the following:

C 1
log (1 + k )+ C 2 ,

T ( k ) ≥