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

The transition from one state to another one is defined as the exchange of
the respective positions of two cities, chosen randomly in the tour. That type
of transition has two advantages. Firstly, it is simple to implement, thus quite
cheap. Moreover, it allows visiting the space of feasible tours. A transition
between two states is made of two steps:
• random selection of two cities,

• exchange of their positions in the tour.

8.5.3.1 Examples of Annealing Algorithms

In the following, we give some practical examples of annealing algorithms: sim-
ulated annealing, rescaled simulated annealing and microcanonical annealing.
More specifically, we present quasi-homogeneous algorithms, i.e., algorithms
that perform, at each step, a large number of elementary transitions bringing
close to thermodynamical equilibrium.

Remarks. For comparison purposes, note that
• Minor modifications are requested to upgrade a standard simulated anneal-

ing algorithm to a rescaled simulated annealing; only a few lines of code
must be added. In practice, the performances of those two approaches can
be compared at a small software development cost. In a fixed resolution
time, rescaled simulated annealing will perform a smaller number of ele-
mentary transitions than simulated annealing; their evaluation is slightly
more complex, but they are more e cient: the smaller the allotted resolu-
tion time, the larger the gain in e ciency.

• Microcanonical annealing is simpler to implement than simulated anneal-

ing, and can produce as good results. But if the user has a limited time to
solve the problem, it might appear less e cient, because it builds during
the search some impassable energetic barriers, which might trap it into
areas of solution space where no good solution exists.

8.5.3.2 Simulated Annealing

Initialization of the Algorithm

Define the minimal percentage p of accepted transitions on the first step.
Determine the initial temperature T = T 0 such that p % of the tested
transitions are accepted.
Generate randomly an acceptable solution and compute 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 .