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

algorithm provides better solutions that simulated annealing because the ele-
mentary transitions to be performed are selected more e ciently.

8.5.2 Microcanonical Analysis

Microcanonical analysis in statistical physics assumes that the physical system
under investigation is isolated: it cannot exchange heat with its environment.
As a consequence, the total energy of the system is constant. That total en-
ergy is the sum of the kinetic energy and of the potential energy. To solve a
combinatorial optimisation problem, the cost function is associated with the
potential energy of the physical system.
At thermodynamical equilibrium, the entropy of a physical system is max-
imum. The latter represents the missing quantity of information to determine
exactly the state of the system. As a consequence, at thermodynamical equi-
librium, the states are uniformly distributed on constant energy hypersphere,
and thus are equiprobable.
Thermal noise is used in canonical analysis for exploring a wide area in
solution space; similarly, some kinetic noise is used in microcanonical analysis.
When the number of particles in interaction is very large, statistical physics
shows that the canonical analysis and the microcanonical analysis are equiv-
alent. Nevertheless, applied to combinatorial optimisation, microcanonical
analysis has some advantages in terms of implementation simplicity and con-
vergence speed.

8.5.2.1 Microcanonical Annealing

The principle of microcanonical annealing is similar to that of simulated an-
nealing. The main difference is the fact that microcanonical annealing per-
forms steps of decreasing total energy by decreasing the kinetic energy between
two steps, while simulated annealing performs steps of decreasing tempera-
ture. Therefore, the algorithm converges by decreasing the energy of energy
reduction of a set of solutions around the optimal ones.
In terms of coding of the optimisation problem, the coding can be strictly
the same as with simulated annealing.
Instead of using a Metropolis algorithm, microcanonical annealing uses
the Creutz algorithm, which allows maximizing the entropy for a given total
constant energy [Creutz 1983]. As the Metropolis algorithm, that method
evaluates a sequence of elementary transitions.

Creutz Algorithm. For a total energy E t , an iterative algorithm allows as-
ymptotic convergence to thermodynamical equilibrium. It consists in iterating
a large number of times the two following steps:
•

Evaluation of the energy variation associated with a random elementary
transition from the current state i , with potential energy E i ,toanew
state j ,ofenergy:∆ E ij = E j − E i .