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

Coding of the Optimization Problems

The practical performances of the simulated annealing are closely related to
the coding of the problem, and in particular to the choice of

• the variables;

• the elementary transitions, which define the topology of the solution space:

in that space, the distance between two states is the number of elementary
transitions necessary to go from one state to the other;

• the functions coding the cost and the constraints. Relaxable constraints

can be combined with the cost function; strict constraints can, for in-
stance, be automatically satisfied by an ad-hoc choice of the elementary
transitions.

Some Theoretical Results

The theoretical behaviour of the simulated annealing has been investigated
in great detail, through a Markov chain modelling (see Chap. 5). A good
overview of those results is given in [Aarts et al. 1989]. We summarize here
the most important results.
The Metropolis algorithm at a given temperature converges asymptoti-
cally towards the thermodynamical equilibrium at that temperature, which is
characterized by a stationary distribution of the states.
The homogeneous simulated annealing, which assumes that a stationary
distribution was reached by the Metropolis algorithm at each temperature
step, converges towards the optimal solutions of the problem, irrespective of
the cooling schedule.
As far as inhomogeneous simulated annealing (the only one used in prac-
tice) is concerned, Hajek found a necessary and su cient condition on the
cooling schedule between two (or more) elementary transitions [Hajek 1988]:
the temperature at the k -th transition, or at the k -th temperature step, must
satisfy

C
log(1 + k ) ,
where C is a constant equal to the maximum depth of the local minima.

T ( k ) ≥

Pros and Cons

That technique is very successful for two main reasons. First, the values of the
parameters of the method can be easily determined and a black-box operation
is often possible for real applications. Secondly, theoretical results show that
simulated annealing can reach solutions as close as expected of the optimal
solutions at a higher speed than an exhaustive exploration of the solution
space. Nevertheless, it is at the cost of the user's patience. In practice it is
generally possible, depending on the amount of time available to solve the
problem, to automatically adjust the internal parameters of the method in