Information Technology Reference
In-Depth Information
the network, as with simulated annealing, the temperature parameter de-
creases progressively.
Considering for instance the TSP, the same encoding as the one used by
Hopfield networks, and based on permutation matrices, can be performed.
The binary outputs of the neurons code a solution of the problem. Energies
associated with the cost function and the constraints are exactly the same as
those defined for a binary Hopfield network. The neuron outputs are randomly
initialized with the values 0 or 1. Therefore the initial state does not necessarily
code for a valid solution of the problem.
To present, we have proceeded as with Hopfield networks. But the updating
of the neurons is different. To make the network evolve, a neuron i is picked at
random. Independently of the value of its output, the probability p i of setting
the output of that neuron to 1 is determined. To this end, the difference ∆ E i
between the network energy value when p i is equal to 0 and when p i is equal
to 1 is computed. These energy values depend on the current state of the other
neurons of the network. The probability to set the output of neuron i to1is
computed from ∆ E i and from the temperature according to the formula used
in simulated annealing,
1
if ∆ E i
0 ,
exp
otherwise .
p i =
E i
T
If the probability is equal to 1, the output of neuron i is set to 1. Otherwise, a
random number between 0 and 1 is generated. If it is lower than the computed
probability, then the output of neuron i is set to 1; otherwise, it is set to
0. That updating procedure is iterated until the system is brought close to
thermodynamical equilibrium at temperature T .
The above-described procedure is applied on decreasing temperature steps,
as in simulated annealing.
The network has converged when the number of state changes minimal.
The above procedure shows the close relation between simulated anneal-
ing, Hopfield recurrent neural networks and Boltzmann machines. That is the
reason why the algorithms derived from statistical physics are often consid-
ered as neural techniques. The convergence properties of Boltzmann machines
are considered in detail in [Aarts et al. 1989].
8.6.5.5 Mean Field Annealing
Another approach, whose objectives are similar to those of the previous tech-
nique, is the mean field theory ,or mean field annealing . The principle is to
manipulate statistical means of the visited states in the Metropolis procedure
used in simulated annealing. Unfortunately, it is necessary to make the so-
called mean field approximation handle those means mathematically. That
approximation consists in replacing very complex functions by their Taylor
Search WWH ::




Custom Search