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

8.6.5.9 Potts Neural Networks

To solve many combinatorial optimization problems, it is often interesting to
encode the neurons in a vector form, by generalizing the neuron structure
with K activation potentials, and K coupled outputs, whose sum is constant.
By analogy with the Potts spin glasses in statistical physics, those neurons
are called Potts neurons.
That form allows a natural encoding of constraints of the type 1-out-of-
K or n -out-of- K . In other words, among the K outputs of a vector neuron,
exactly n must be at +1 in a solution, all the others being 1. That type

of constraint could be expressed under the form of an energy to minimize.
But that strict constraint might not be satisfied at the convergence on a local
minimum.
Making use of Potts neurons consists in replacing sigmoid activation func-
tions by multidimensional activation functions. For a constraint of type 1-out-
of- K , that amounts to defining binary neurons ( i , a ), with potential v ia

−

and

output y ia defined by

exp( v ia )
K

y ia = , i =1 ,...,N, a =1 ,...,K.

exp( v ib )

b =1

Clearly, for each Potts neuron i ,wehave a =1 y ia =1.
In other words, at the end of the convergence process, the constraint is
automatically satisfied.
The mean field equations previously mentioned can also be defined with
analog Potts neurons [Peterson et al. 1989; Peterson 1990; Herault et al. 1989,
1991].
The use of those neurons has the following benefits:

• The energy function contains a smaller number of competing terms.

• It is not necessary to tune a parameter which weight an energy function

associated with the violation of this type of constraint.

• Results are generally much better than those provided by scalar neurons.

That type of neural network has been applied to many problems, such
as graph partitioning problems [Herault et al. 1989], knapsack problems
[Ohlsson et al. 1993], or scheduling problems [Lagerholm et al. 1997].

8.6.5.10 Rangarajan Neural Networks

When the solutions of a problem are expressed under the form of a permuta-
tion matrix, the neural network proposed by Rangarajan can be used. It has
the advantage of not requiring the addition of penalty terms to the energy
function in order to satisfy this constraint [Rangarajan et al. 1995, 1999]. It
combines the Hopfield network with a projection algorithm on the space of