Information Technology Reference
In-Depth Information
Acceptance of the transition to that new state if ∆ E ij
E t
E i .
Here, E t
E i is the kinetic energy of the system when it is in state i . Note
that transitions to states with higher potential energy are allowed, under the
condition that enough kinetic energy is available to compensate the increase
of the potential energy, and therefore keep a constant total energy.
Microcanonical Annealing
The microcanonical annealing algorithm consists in reductions of the total
energy, from an initial high total energy, within the Creutz algorithm. Several
decreasing laws for the total energy can be used in practice, similarly to the
cooling schedules in simulated annealing.
Pros and Cons
The Creutz algorithm is much simpler than the Metropolis algorithm, and
requires fewer computations. Moreover, it does not require a good numerical
accuracy. If the problem is coded in integer numbers, it is not necessary to
make calculations with floating point numbers. Moreover, it is neither nec-
essary to compute an exponential, nor to pick at random a real number to
compare it with the result of the exponential function. Therefore, the compu-
tations used are extremely simple.
For large-size problems, microcanonical annealing provides solutions whose
quality is comparable to that of the simulated annealing, while being partic-
ularly cheap in terms of required calculations. Moreover, a parallelization of
this approach is possible.
Note that microcanonical annealing generates families of solutions with
comparable qualities, because all the solutions with the same level of total
energy are equiprobables. When the total energy is small, all accessible states
have a smaller energy (since the kinetic energy is a positive quantity) and are
good solutions.
However, at present, there is no proof of convergence, in contrast to sim-
ulated annealing. One of the reason is the existence of energetic barriers that
cannot be jumped with this algorithm, contrary to the simulated annealing:
in the Creutz criterion, the transition probability from a state i to a state j
can be zero when E t becomes small. More efforts are still needed to prove the
convergence properties.
8.5.3 Example: Travelling Salesman Problem
Let us consider the following coding for the travelling salesman problem. It is
one of the simplest coding schemes [Reinelt 1994].
Initially, the algorithm starts from a random feasible tour. A tour is rep-
resented by a vector of integer numbers, where the i -th component indicates
the position of city i in the tour.
Search WWH ::




Custom Search