Performance of Quadratic Assignment Problem by Hopfield NN withRecalling the Best Memory
Hironori Kumeno† and Yoshifumi Nishio††Dept. of Electrical and Electronic Eng.
Tokushima University Tokushima 770-8506, JAPAN
Email: kumeno@ee.tokushima-u.ac.jp
Abstract
In our past study, the solving ability of the Hopfield Neural Network with noise for quadratic assignment problem
is investigated. However, even if we injected the noise tothe network, the optimal solution can not occasionally befound. In this study, we propose the method adding noisewith recalling the best memory to the Hopfield Neural Network for achieve better performance. We investigate effective search with proposal technique for quadratic assignment problem.
1. Introduction
Hopfield Neural Network (abbr. NN) [1] is one of thetools to solve combinatorial optimization problems. To
solve the problems, the global minimum can be searchedby energy decent principle of the Hopfield NN. However,the network is a model aiming at the energy of the local
minimum rather than the global minimum. So, in a lotof cases, the network finds local minimums, and can notescape from there. In order to avoid this critical problem, many researchers proposed the method adding somekinds of noises to the Hopfield NN. Hayakawa and Sawada
pointed out the chaos near the three-periodic window of thelogistic map gains the best performance as noise [2].
Recalling the best memory is one of routine of thepsyshological human thinking, and the human find a solution by rethinking from the best memory.
In this study, we propose a method adding noise with recalling the best memory. Adding the noise is effective forthe solution to escape from the local minimum, but at thesame time it may obstruct the energy decent principle. We
investigate solving ability of adding the noise with recalling the best memory to the Hopfield NN for QAP. We confirm that the method is effective to solve QAP by computer
simulations.

noting the distances between the factories and flow matrix
D denoting the flow of the products between the factories,
and is to find the permutation P which corresponds to theminimum value of the objective function f (P) in Eq. (1).
f (P) =N X
NX(1)where Ci j and Di j are the (i,j)-th elements of C andD,respectively, p(i) is the i-th element of vector P, and N is
the size of the problem. There are many real applications
which are formulated by Eq. (1). For solving N−element
QAP by the Hopfield NN, N × N neurons are required andthe following energy function is defined to fire (i,j)-th neuron at the optimal position:
E=N X
NX

wi,m: j,n xi,m x j,n +i,m=1 j,n=1

NX

θi,m xi,m .

(2)

i,m=1

The neurons are coupled each other with weight between(i,m)-th neuron and (j,n)-th neuron and the threshold of the(i,m)-th neuron are described by:)
(Ci j Dmn.
wi,m: j,n = −2 A(1 − δmn )δi j + Bδmn (1 − δi j ) +q(3)θim = A + B(4)where A and B are positive constant, and δi j is Kroneker’s
delta. The state of N × N neurons are asynchronously updated due to the following difference equation:
 N

 X

wi,m: j,n xi,m (t)x j,n (t) − θim + βzim (t) (5)xim (t + 1) = f j,n=1

where f is sigmoidal function defined as follows:

2. Solving QAP with hopfield NN

f (x) =

Various methods are proposed for solving QAP which isone 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 de-Ci j D p(i)p( j) ,i=1 j=11
1 + exp(− εx )(6)

zim is additional noise injected to the network, and β limits
amplitude of the noise. Also, we use the method suggestedby Sato et al. (Ref. [3]) to decide firing of neurons.

- 67 -3. Chaos noiseenergy state. Then, repeat the update. Figure 2 shows theflow chart of recalling the best memory.

In this section, we describe chaos noise injected to theHopfield NN. The logistic map is used to generate thechaos noise:lˆim (t + 1) = αlˆim (t)(1 − lˆim (t)).

(7)

Varying parameter α, Eq. (7) behaves chaotically via aperiodic-doubling cascade. Further, it is well known thatthe map produces intermittent bursts just before periodicwindows appear. Figure 1 shows an example of the intermittency chaos near the three-periodic window obtained
from Eq. (7) for α = 3.8274. As we can see from the figure,the chaotic time series could be divided into two phases;
laminar parts of periodic behavior with period three andburst parts of spread points over the invariant interval. As
increasing α, the ratio of the laminar parts becomes larger
and finally the three-periodic window appears. We use theintermittency chaos time series after the following normalization.
lˆim (t) − l¯(8)lim (t + 1) =σl
where l¯ and σl are the average and the standard deviation
ˆ respectively.
of l(t),Figure 2: Flow chart of recalling the best memory.

5. Simulation results
In this section, the simulation results of Hopfield NN
with recalling the best memory for 12-element QAP areshown. The problem used here was chosen from the site
QAPLIB named “Nug12”. The global minimum is known
as 578. The parameters of Hopfield NN are fixed as A =0.9, B = 0.9, q = 140, ε = 0.02 and β = 0.64. We carriedout 1000 trails of 10000 iterations. The control parameterof the logistic map is fixed as αl = 3.8274. The limit ofupdate number of the recalling the best memory is fixed as
LI MIT = 50.
Table 1: Solving abilities for Nug12.
Iteration Conventional Recalling
1000
632.96606.8022000
623.30598.4503000
619.82594.4824000
616.18592.1165000
613.56590.5886000
612.68589.4667000
611.74588.5628000
610.48587.952
9000
610.30587.448
10000
609.96586.998

Figure 1: Time series obtained from logistic map. αl =3.8274.

4. Recalling the best memory
we consider that a energy state of some of the neurons ina local minimum correspond to the energy state in a global
minimum. For this reason, to add noise to the state which
is near the global minimum is more efficient than to add
noise immoderately. In this study, we propose a method toadd noise with recalling the best memory. In the method,noises are added every update. In the update, the state ofeach neuron which has the lowest energy is memorized.
After the lowest energy update, if the memorized energy is
not updated by the dicided update number (named LI MIT ),the state of all neurons is returned to the memorized lowest

Next, we tried another problem, whose name is“Tai12a”. The global minimum is 224416. The parameters of the Hopfield NN are fixed as A = 0.9, B = 0.9, q =16000, and ε = 0.02. We carried out 1000 trails of 40000- 68 -iterations. Othe parameters are β0 = 0.64, αl = 3.8274 and
LI MIT = 40.
Table 2: Solving abilities for Tai12.
Iteration Conventional
Recalling
4000
252624.44
245091.840
8000
251337.90
242225.154
12000
250291.38
240731.618
16000
249638.16
239919.308
20000
249520.72
239180.534
24000
249495.62
238717.33828000
249458.04
238176.598
32000
249335.58
237803.944
36000
249228.40
237485.112
40000
249225.84
237098.142

Figure 4: Simulation result of Tai12. Horizontal axis:
LIMIT. Vertical axis: Average of solutions.
References

Tables 1 and 2 show the mean values of the best solutions obtained during each iteration numbers for Nug12and Tai12a, respectively. From these results, the proposed method gains better performance than the conventional method.
Finally, we investigate the performance against changing
the limit of the update number of recalling the best memory.
From the results of changing LI MIT (Fig. 3 and Fig. 4), bychange LI MIT the performance of the proposed method isperturbed, however the proposed method gains better performance than the conventional method.

[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 modelfor optimization problems,” Physical Review E, vol.51,
no.4, pp.2693-2696, Apr. 1995.
[3] 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).

Figure 3: Simulation result of Nug12. Horizontal axis:
LIMIT. Vertical axis: Average of solutions.

6. Conclusions
In this study, we proposed the method adding noise withrecalling the best memory to the Hopfield Neural Network.
By computer simulations, we investigated the solving ability of the Hopfield NN with the recalling the best memory
for QAP. We confirmed that the proposed method is effective to solve QAP.

- 69 -