Information Technology Reference
In-Depth Information
a local minimum, because the valleys of the solution space are wider than in
the binary case. Unfortunately, analog neurons evolving inside the hypercube
rarely converge towards a vertex of the latter. In order to force the analog
neurons to finally have binary values that code for a solution of the problem,
several possibilities exist. One of them consists in increasing the slope at the
origin of the activation function of the analog neurons during convergence. As
a further refinement, one may add to the energy function a penalty term of
the form
N
1
j .
y 2
E y =
j =1
That term is zero if the neuron outputs are discrete, with values in
{−
1 , 1
}
.
8.6.4.3 Application of Hopfield Neural Networks to Optimization
To summarize: from the above-described convergence properties, it ensues
that Hopfield neural networks can be applied to optimization problems with
the following methodology, featuring four steps:
1. Find an appropriate encoding of the problem. The question is, first, to
find a representation of the problem such that a solution, i.e., an instanti-
ation of the problem variables, is represented by the neuron outputs after
convergence.
2. Express the cost function and the constraints under the form of the energy
of a Hopfield network. Try to express the cost function as a quadratic
function. As for the constraints to be satisfied, they are of two types: those
defined by the optimization problem, and those resulting from the problem
encoding selected in the previous step. Sometimes, it is not possible to find
a quadratic energy. It is then necessary to try to express the problem as
the minimization of a function F , which can be differentiated with respect
to neuron outputs.
3. Find the equations of the neurons.
4. Randomly start the network. Generally, when no a priori knowledge on
the location of an optimal solution is available, the neuron states are
randomly initialized. Then, the equations of the neurons will drive the
network towards a local minimum of the energy.
That type of methodology has been applied to solve a wide variety of
combinatorial problems, which are generally amenable to problems of graph
theory.
Search WWH ::




Custom Search