WCCI 2012 IEEE World Congress on Computational Intelligence
June, 10-15, 2012 - Brisbane, Australia

IJCNN

Performance of Quadratic Assignment Problem
by Hopfield NN with Periodic Brake
Hironori Kumeno, Yoko Uwate and Yoshifumi Nishio
Dept. of Electrical and Electronic Eng., Tokushima University,
2-1 Minami-Josanjima, Tokushima, 770-8506 JAPAN
Email: {kumeno, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract—Solving combinatorial optimization problems is oneof the important applications of neural networks. Many researchers have proposed noise induced hopfield neural networks
in which noises are induced state values of neurons. However, thenoise inducing method to state values of neurons cause problems.
In this study, we propose hopfield neural networks withperiodic brake. In the proposed system, external noises are notinduced to state values of neurons. Thus, the proposed system
can avoid the problem caused in the noise induced system.
We investigate the solving ability of the proposed system for
quadratic assignment problems and designing of parameters.

I. I NTRODUCTION
The hopfield neural networks (HNN) is a form of recurrent
artificial neural network invented by Hopfield and have been
applied to solve combinatorial optimization problems [1].
When connection weights between neurons are related togiven problems, the network gives a good solution. Because,the energy of the network converges to a minimum value
with natural operation determined by the connection weights.
However, the solutions are often trapped into local minimums
and do not reach the global minimum demanded. In order toavoid this problem and solve the global minimum effectively,
several methods inducing some kinds of noises are proposedby researchers [2]-[8]. Especially, methods that noises are
induced into state values of neurons are well proposed andstudied. In these methods, noises are induced to state values of neurons in the HNN, and then firing neurons areforcibly switched by the noises. These methods are effective to
avoid local minimums. However these noise inducing methods
sometimes causes a problem. When the noise induced HNNs
are used to solve quadratic assignment problems (QAP), theneurons of HNNs are arranged on a plane surface in order toadapt to two-dimensional matrices of the solving problems.
The HNN without noise is constructed to fire only one neuron
on each line. However, in the noise induced HNNs, two or
more neurons located on a line sometimes fire. Figure 1 showsa pattern of the firing of two neurons on a line. In the figure,black colored squares show firing neurons, and two neurons
enclosed in the red colored circle fire on the same horizontal
line. The firing of two or more neurons on a line is a problemof this noise inducing method and causes high dependence on
solving problems.
By the way, in the real wold, human cannot concentrateon one thing for a long period of time. Human can keep
high-concentration for ten minutes at most in professional

978-1-4673-1490-9/12/$31.00 ©2012 IEEE

Fig. 1.

An example of firing of two neurons on a line.

view. So that, a break is important to refresh. It is necessary
to have a break for keep his mind clear and concentrate
again. If he continues to do his task without a break, theefficiency of his task is down. Such a break is inferred tomake neurons rest and refresh and then yields high-efficiency.
Although the HNN is not real physical neural networks, we
adapt this idea to the HNN for escape local minimums andpropose a method to escape local minimums. We call the
proposing system HNN with periodic brake (HNN-PB). In
the proposed system, random values are periodically given
to coupling weights between neurons in the network. The
state values of neurons in HNN-PB converge according to thegiven random values of the coupling weights. Then, the systemescapes from local minimums. The advantage of the proposed
method is that firing of two or more neurons on a line is notcaused because the system does not include noise terms instate values.
In this study, we investigate the solving ability of the HNNPB for QAP. We confirm that the method is effective to solve
QAP by computer simulations. Then, we investigate designingof optimal parameters for the HNN-PB.

1353

#

≧
"

#

≧
"

#
!
"

Fig. 2.

Flow chart of HNN-PB.

II. S OLVING QAP WITH HNN
Various methods are proposed for solving QAP which
is one of the NP-hard combinatorial optimization problems.
We explain QAP with a factory arrangement problem. The
problem is given by two matrices, distance matrix C denoting
the distances between the factories and flow matrix D denoting
the flow of the products between the factories, and is to findthe permutation P which corresponds to the minimum valueof the objective function f (P ) in Eq. (1).
f (P ) =N ∑N∑

Cij Dp(i)p(j) ,(1)i=1 j=1

where Cij and Dij are the (i,j)-th elements of C and D,
respectively, p(i) is the i-th element of vector P , and N is thesize of the problem. There are many real applications which
are formulated by Eq. (1). Other examples are the placement oflogical modules in an IC chip and the distribution of medical
services in large hospital.
Because the QAP is very difficult, it is almost impossible
to solve the optimum solution in large problems. Further,computation time is very long to obtain the exact optimum
solution. Therefore, it is usual to develop heuristic methods
which search nearly optimal solutions in reasonable time.

For solving N-element QAP by the HNN, N × N neurons
are required and the following energy function is defined tofire (i,j)-th neuron at the optimal position:
E=

N
N
∑
∑

ωim;jn xim xjn +i,m=1 j,n=1

N∑θim xim .

(2)

i,m=1

The neurons are coupled each other with coupling weight
between (i,m)-th neuron and (j,n)-th neuron and the thresholdof the (i,m)-th neuron are described by:}{
Cij Dmnωim,jn = −2 A(1 − δmn )δij + Bδmn (1 − δij ) +qθ =A+B(3)
where A and B are positive constant, and δij is Kroneker’s
delta. The state of N ×N neurons are asynchronously updated
due to the following difference equation:N∑
xim (t + 1) = f ωim;jn xim (t)xjn (t) − θim  , (4)j,n=1where f is sigmoidal function defined as follows:

1354

f (x) =

1.
1 + exp(− x )(5)

TABLE I
S OLVING ABILITIES FOR N UG 12.

III. A LGORITHM OF HNN-PB
We explain hopfield neural network with periodic brake(HNN-PB) in detail. Figure 2 shows flow chart of the HNNPB. The algorithm of the HNN-PB can be separated into twoparts which are alternately repeated in iteration. One of thetwo parts is a solving part in which the distance matrix andthe flow matrix of QAP are inputed to Cij and Dmn in Eq. 3.
Then, the states of the neurons in the HNN-PB are updatedwith the same updating method of the general HNN. In thesolving part, the operation of the HNN-PB is completely thesame as the general HNN. The other part is a brake part inwhich random values are inputed to Cij and Dmn in Eq. 3
every iteration. The random value is a value between 0 andNmax . The updating operation of the neurons in the brake partis the same as that of the solving part. So, all the equations
and the updating operation of neurons in the HNN-PB are
the same as the general HNN. The two parts are alternately
repeated. The iteration time of the solving part and the brakepart are denoted by Tsolve and Tbrake , respectively. The lengthof one cycle of the two parts is termed as Tperiod :Tperiod = Tsolve + Tbrake .

Iteration
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

IV. S IMULATION R ESULTS
In this section, the simulation results of HNN-PB for 12element QAP are shown. The problem used here was chosenfrom the site QAPLIB named “Nug12” [9]. The global minimum of Nug 12 is known as 578. The parameters of HNN-PB
are set as A = 0.9, B = 0.9, q = 70 and ε = 0.35. The valueof ε used in this study is larger than other general HNNs which
include noise terms in update equations of state values ofneurons. Namely, the gradient of the sigmoid function used inthis study is glacis. The glacis gradient of the sigmoid function
makes neurons need a long iteration time to converge to astable state. This prevent that state values of neurons suddenly
change to states which do not relate to the solving problem
when random values are inputed to the coupling weights inbrake parts. To prevent sudden change of the state values ofneurons in brake parts is important to solve good solutions.
The other parameters associated with the periodic brake are set
as Nmax = 5.0, Tperiod = 10 and Tbrake = 3. We carried out
1000 trails of 10000 iterations. In order to verify the solving
ability of the HNN-PB, we compare the solving ability of
the HNN-PB to the noise induced HNN that intermittency
chaotic noises are induced to update equations of state valuesof neurons, proposed in [5].
Next, we tried another problem, whose name is “Tai12a”.
The global minimum of Tai12a is 224416. The parameters ofthe HNN are fixed as A = 0.9, B = 0.9, q = 9000 and
ε = 0.20. The other parameters associated with the periodic

HNN-PB
602.234596.942594.188592.354591.114590.234
589.624588.948588.434587.916

TABLE IIS OLVING ABILITIES FOR TAI 12.
Iteration
4000
8000
12000
16000
20000
24000
28000
32000
36000
40000

(6)

In the HNN-PB, Cij and Dmn in Eq. 3 periodically become
random values, although the updating equation of the states ofneurons does not include a noise term. Therefore, firing of aneuron which is forcibly caused by a noise does not happen
in the HNN-PB. Firing of two or more neurons on a line does
not caused.

HNN with noise
632.96623.30619.82616.18613.56612.68611.74610.48610.30609.96

HNN with noise
252624.44251337.90
250291.38
249638.16
249520.72
249495.62
249458.04
249335.58
249228.40
249225.84

HNN-PB
245032.000
242803.980
240742.440
239133.920
237915.700
237111.160
236779.760
236673.520
236375.820
236044.340

brake are set as Nmax = 110, Tperiod = 10 and Tbrake = 4.
We carried out 1000 trails of 40000 iterations.
Tables 1 and 2 show the mean values of the best solutions
obtained during each iteration numbers for Nug12 and Tai12a,
respectively. From these results, the HNN-PB gains better
performance than the noise induced HNN.
The convergence speed of state values of neurons in the
HNN-PB is slow because of the glacis gradient of the sigmoid
function and the system cannot solve the global minimum inbrake parts. However, comparing with the noise induced HNN,
the HNN-PB solve better solutions in the same limit of iteration. In the noise induced HNN, chaotic noises are generated
every iterations and induced to the state values of all neurons,

Fig. 3. Passege of the state value of a neuron which shift from a non-firing
neuron to a firing neuron.

1355

(a)

(b)

(c)

(d)

(e)

Fig. 4. State values of neurons around a brake part. (a) State values of neurons before a brake part. (b), (c) and (d) shows state values of neurons every
iteration in the brake part. (e) State values of neurons after the brake part.

whereas random values are inputed to coupling weights onlyin brake parts in the HNN-PB. Thus, the computing speed of
the HNN-PB is faster than the noise induced HNN.
V. PASSAGE OF S TATE VALUES OF N EURONS
We explain the passage of state values of neurons in HNNPB when Tperiod = 10 and Tbrake = 3 which are set as an
example. Figure 4 shows the passage of the state value of aneuron which shift 0 to 1 on iteration. In the figure, horizontal
axis is iteration time. The iteration is started with a solving
part. So, from 1 to 7 iteration, the state value of the neuron
converge a local minimum in the solving part. After that, a
brake part is started in which random values are inputed tothe coupling weights. Then, the brake part is finished at 10
iteration. In the second brake part from 17 to 20 iteration, thestate value of the neuron changes significantly. After that, inthe next solving part, the state value of the neuron tend toward
1 which correspond to firing of the neuron. In the process, the
HNN-PB escape from the local minimum.
Figure 4 shows the states of all neurons around a brakepart. Figure 4(a) shows the states of the neurons before thebrake part. Almost neurons converge to a stable state. Figures
4(b), (c) and (d) show the states of the neurons every iterationin the brake part. By increasing iteration time, black coloredneurons which converged in Fig. 4(a) fade, and the number ofgray colored neurons increase. However, some neurons stayabout the same. In this way, initial values of the next solving
part become non-uniform state values which are a little similar
to the state values before the brake part. Figure 4(e) shows thestates of the neurons after the brake part. The neurons tend
toward another local minimum or the global minimum.
VI. D ESIGNING OF O PTIMAL PARAMETERS
We investigate designing of optimal parameters. For solving
Nug12, the optimal parameters are Nmax = 5.0, Tperiod = 10
and Tbrake = 3. Tperiod is designed associated with ε. If ε
is big, neurons converge a local minimum fast, whereas if
ε is small, the convergence speed is slow. When ε = 0.35,
neurons converge a local minimum for about 10 iterations.
Thus, Tperiod is set at 10. If Tperiod increase, the efficiency
to search solutions is down because states of neurons do notchange after convergence, iterations after the convergence are1356waste. If Tperiod decrease, the effect of the random values
induced in brake parts become strong. As the result, it becomesdifficult that the system close in the global minimum. Figure
5 shows the mean values of the best solutions when Nug12
is solved, the parameter Tperiod is fixed at 10 and Tbrakeand Nmax vary. Figure 6 shows the mean values of the bestsolutions when Nug12 is solved, the parameter Tperiod is fixedat 5 and Tbrake and Nmax vary. Comparing the two figures,the solving abilities in Fig. 6 are worse than that of Fig. 5.
Small value of Tperiod make the efficiency to solve the global
minimum worse.
Tbrake bears a trade-off relationship to Nmax . When Nmax
is large, small values of Tbrake gain good solving abilities.
Whereas, when Nmax is small, relatively small values ofTbrake gain good solving avility. This relationship can beseen in the figures. As we explained in the last section, thestate values of neurons which trapped in a local minimum
are changed and the system can escape the local minimum
by inputing random values to coupling weights in brake parts.
Large random values inputed in the brake parts make suddenchange of the state values of neurons. When the small random
values are inputed in the brake parts, it need long iteration
time to change the state values of the neurons. Therefore, therelationship between Tbrake and Nmax explained in the above
is obtained.
For solving Tai12a, the optimal parameters are Nmax =110, Tperiod = 10 and Tbrake = 4. Figure 7 shows themean values of the best solutions when Tai12a is solved,
the parameter Tperiod is fixed at 10 and Tbrake and Nmax
vary. A rough value of Nmax is decided in association withvalues of the flow matrices and the distance matrices of thesolving problems. The maximum values of the flow matrix andthe distance matrix in Nug12 are 10 and 5, respectively. The
maximum values of the flow matrix and the distance matrix in
Tai12 are 99. In brake parts, random values are inputed to Cij
and Dmn in Eq. 3. The maximum value of the random values
inputed to Cij and The maximum value of the random values
inputed to Dmn are the same value which is Nmax . Nmax isdesigned as become relatively similar to the maximum valuesof the solving problems. Because, the parameter q of HNNPB is decided in association with values of the matrices ofthe solving problem, and q is constant in solving parts and in
break part. Therefore, Nmax is necessary to suit to the solving
problem.
From the figures, we can see combinations of small Nmax
and some few iteration of Tbrake make better result than
combinations of large Nmax and one iteration of Tbrake . If
Nmax is large, the states of the neurons are suddenly attracted
to the states which are not related to the solving problem
in brake parts. Then, the system cannot reach to the global
minimum in solving parts, sufficiently. On the other hand, if
Nmax is small, certain informations of the local minimums
which obtained for the solving problem before brake parts
remain after the brake parts. Then, the system can searcharound the global minimum, effectively.

Fig. 5. Mean values of the best solutions for solving Nug12 Tperiod = 10.
x-axis: Nmax . y-axis: Tbrake . z-axis: Mean values of the best solutions.

Fig. 6. Mean values of the best solutions for solving Nug12 Tperiod = 5.
x-axis: Nmax . y-axis: Tbrake . z-axis: Mean values of the best solutions.

Fig. 7. Mean values of the best solutions for solving Tai12 Tperiod = 10.
x-axis: Nmax . y-axis: Tbrake . z-axis: Mean values of the best solutions.

1357

VII. C ONCLUSIONSIn this study, we proposed hopfield neural network withperiodic brake in which random values are periodically inputed
to coupling weights between neurons instead of inputing flow
and distance matrices of solving problems. One main featureof the proposed system is that external noises are not induced
to state values of neurons. We investigated the solving abilityof the proposed system for quadratic assignment problems.
By computer simulation, we have confirmed that the proposedsystem can find better solutions comparing with the noise
induced HNN in which noises are induced to state valuesof neurons. Moreover, the computing speed of the HNN-PB
is faster than the noise induced HNN. Then, we investigateddesigning of optimal parameters.
ACKNOWLEDGMENT
This work was partly supported by JSPS Grant-in-Aid forYoung Scientists 23700269.
R EFERENCES[1] J. J. Hopfield,“Neurons with Graded Response Have Collective Computational Properties like Those of Two-State Neurons,” Proc. Natl. Acad.
Sci. USA, vol. 81, pp. 3088-3092, 1984.
[2] Y. Hayakawa and Y. Sawada, “Effects of the Chaotic Noise on the
Performance of a Neural Network Model for Optimization Problems,”
Physical Review E, vol.51, no.4, pp.2693-2696, Apr. 1995.
[3] M. Hasegawa, T. Ikeguchi, T. Matozaki and K. Aihara, “An analysis on
additive effects of nonlinear dynamics for combinatorial optimization,”
IEICE Trans. Fundamentals, vol.E80-A, no.1, pp.206213, Jan. 1997.
[4] K. Sato, T. Ikeguchi, M. Hasegawa and K. Aihara, “An Optimization
Method for Quadratic Assignment Problems by Chaotic Dynamics and
its Characterization by Lyapunov Dimensions,” IEICE Tech. Rep., vol.
NLP64-13, pp. 13-20, 2001 (in Japanese).
[5] Yoko UWATE, Yoshifumi NISHIO and Akio USHIDA, “Markov Chain
Modeling of Intermittency Chaos and its Application to Hopfield NN for
QAP,” Proc. of ECCTD’03, vol. 2, pp. 57-60, Sep. 2003.
[6] Y. Uwate and Y. Nishio, “Search of Many Good Solutions of QAP by
Connected Hopfield NNs with Chaos Noise,” Proc. of NCSP 04, pp. 145148, Mar. 2004.
[7] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi, “Performanceof Chaos and Burst Noises Injected to the Hopfield NN for Quadratic
Assignment Problems,” IEICE Trans. on Fundamentals, vol.E87-A, no.4,
pp.937943, Apr. 2004.
[8] Y. Tada, Y. Uwate and Y. Nishio, “Solving Ability of Hopfield Neural
Network with Scale-Rule Noise for QAP,” Proc. of ISCAS08, pp. 105108, May 2008.
[9] R. E. Burkard, S. E. Karisch and F. Rendl, “QAPLIB-A Quadratic
Assignment Problem Library,” http://www.opt.math.tu-graz.ac.at/qaplib/

1358