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

type of network has been used successfully to solve problems where the so-
lutions are required in very short response times, such as resource allocation
problems (for instance, problems of allocation of weapons on targets [Herault
1995a,b,c], and problems of extraction of maximum cliques encountered in
fluid mechanics [Derou et al. 1996]).

8.6.5.7 High-Order Neural Networks

In order to better satisfy the constraints during convergence, some neural
networks with continuous outputs have been defined; their particularity is
that they use penalty terms of order greater than 2 [Sun 1993]. That gives
rise to equations of neurons that are based on Newton methods, which have
a convergence speed of order 2, such as, for instance,

∂E
∂y i
∂ 2 E
∂y 2
i

d v i
d t =

− .

That type of network has been successfully applied to combinatorial prob-
lems, by using a particular dynamics, which consists in selecting the neuron
to be updated by the following procedure:

• Compute in parallel all the ∆ v i associated with the penalty energy of the

constraints, and select those which have the smallest ∆ v i .

• Compute the gradient of the cost function for the neurons selected in the

previous step, and keep the neuron degrading the least the cost value.

Example of the TSP

We consider again the TSP, with the same encoding as for a Hopfield network
(permutation matrix encoded by the neuron outputs); in order to make use of
the above equations, the penalty terms associated with the constraint violation
must be of high order. They are derived from the following conditions, which
are required for a solution to be valid:

For each city i : j =1 (1 • − y i,j )=0and ∀ j,l y i,j y i,l =0.

For each position j on the tour: i =1 (1 • i,k y i,j y k,j =0.

An energy associated with the constraint violations is then derived,

− y i,j )=0and ∀

N N N N N N N

(1 −y i,j ) 2 + (1 −y i,j ) 2 + y 2

i,j

y 2
i,l

E c =

i =1 j =1 j =1 i =1 i =1 j =1

l =1
l = j

N N N

y 2
i,j

y 2
k,j

+ .

j =1 i =1

k =1
k = i