2006 RISP International Workshop
on Nonlinear Circuits and Signal Processing (NCSP'06)
Waikiki Beach Marriott, Honolulu,Hawaii, USA, March 3-5, 2006

Solving Ability of Hopfield Neural Network with Mix Noise for Quadratic Assignment Problem
Yoshifumi Tada, Yoko Uwate and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470 FAX:+88-88-656-7471
Email: {y-tada, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract
Solving combinatorial optimization problem is one of the important applications of neural network (abbr. NN). However,the solutions are often trapped into a local minimum and do
not reach the global minimum. In order to avoid this criticalproblem, several people proposed the method adding somekinds of noise.
In this study, we consider torus noise generated by thesine circle map for the Hopfield NN. By computer simulations, solving abilities of Hopfield NN for quadratic assignment problem (QAP) with various kinds of noises based on
the torus noise are investigated.
1. Introduction
The use of Hopfield NN in broad fields is expected, suchas combinatorial optimization problem, associative memory,and pattern recognition. If we choose connection weights between neurons appropriately according to given problems, wecan obtain a good solution by the energy minimization principle. However, the solution are often trapped into a local
minimum and do not reach the global minimum. In order
to avoid this critical problem, several people proposed themethod adding some kind of noise for solving traveling salesman problem (TSP) with the Hopfield NN [1]. Hayakawa andSawada pointed out the chaos near the three-periodic windowof the logistic map gains the best performance [2]. They concluded and that the good result might be obtained by a property of the chaos noise; short time correlations of the timesequence. Hasegawa et al. investigated solving abilities ofthe Hopfield NN with various surrogate noise, and they conclude that the effects of the chaotic sequence for solving optimization problems can be replaced by stochastic noise withautocorrelation [3]. We have also studies the reason of thegood performance with Hopfield NN with chaotic noise. We
imitated the intermittency chaos noise by the burst noise generated by Gilbert model [4] with 2 states; a laminar state anda burst state. We conclude that the irregular switching of laminar part and burst part is one of the reasons of the good performances of the chaotic noise [5][6].

In this study, we consider torus noise generated by the sinecircle map. We tune the parameters of the sine circle map
to generate torus including intermittent feature. Further, we
propose a mix noise, which is a mixture of the intermittent
torus and chaos/random noise, in order to investigate the performance of the noise including intermittet feature. By computer simulations, solving abilities of Hopfield NN for QAP
with various kinds of noises based on the torus noise are investigated.
2. Solving QAP with Hopfield NN
Various methods are proposed for solving QAP which isone of the NP-hard combinatorial optimization problems.
QAP is expressed as follows: given two matrices, distancematrix C and flow matrix D, and find the permutation P whichcorresponds to the minimum value of the objective function
f (P) in (1).
f (P) =N XNXCij 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 the vector P, and N
is the size of the problem. There are many real applications
which are formulated by (1). One example of QAP is to findan arrangement of the factories to make a cost the minimum.
The cost is given by the distance between the factories andflow of the products between the factories. Other examples
are the placement of logical modules in an IC chip, the distribution of medical services in large hospital, and so on.
Because QAP is very difficult, it is almost impossible tosolve the optimum solutions in large problems. The largest
problem which is solved by deterministic methods may be
only 24 in recent study. Further, computation time is very
long to obtain the exact optimum solution. Therefore, it isusual to develop heuristic methods which search nearly optimal solutions in reasonable time.
For solving N -element QAP by Hopfield NN, N ×N neurons are required and the following energy function is defined- 317 -

to fire (i, j)-th neuron at the optimal position:

10.9NNXXwim;jn xim xjn +i,m=1 j,n=1NX

0.8

θim xim .

(2)

0.7

i,m=1

chaos noise

E=The weight between (i, m)-th neuron and (j, n)-th neuron
and the threshold of the (i, m)-th neuron are described by:
Cij Dmn
wim;jn = −2 A(1 − δmn )δij + βδmn (1 − δij ) +q(3)θim = A + B
(4)

0.3

0.2

0.1
0200

300

400

500
t

600

700

800

900

1000

(a) Intermittency chaos (αz =3.82676).
0.9
0.8

chaos noise

0.7
0.6
0.5
0.4

(5)0.3where f (·) is the sigmoidal function defined as follows: x,
1 + exp −ε100

1j,n=110.50.4

where A and B are positive constants, and δij is Kroneker’s
delta. The state of N ×N neurons are asynchronously updated due to the following difference equation:!
NX
wim;jn xim (t)xjn (t)−θim +βzim (t)xim (t+1) = ff (x) =

0.6

0.2
0.1(6)

00100

200

300

400500
t

600

700

800

900

1000

(b) Fully-developed chaos (αz =3.999).

zim is additional noise, and β limits the amplitude of thenoise.

Figure 1: Chaotic time series.

3. Intermittency noise

3.2. Torus noise

3.1. Chaos noise

The following sine circle map is used to generate the torus
noise.

The logistic map is used to generate the intermittencychaos noise.
ẑim (t + 1) = αz ẑim (t)(1 − ẑim (t)).

ŷim (t + 1) = ŷim (t) + αy sin {6 ŷim (t)} + D.

(9)(7) Figure 2 shows the shape of the sine circle map for αy =0.04
and D=0.05. We tune the parameters of the sine circle map toIncreasing the parameter αz , the logistic map behaves chaotgenerate torus including intermittent feature. Figure 3 shows
ically via a periodic-doubling cascade. Further, it is well
an example of intermittency torus.
known that the map produces intermittent burst just before
When we inject the intermittency torus noise to the Hopperiodic-windows appear. Figure 1(a) shows an example offield NN, we normalize ŷim by the following equation.
the intermittency chaos near the three-periodic window obtained from (7) for αz = 3.82676. As we can see fromŷim (t) − ȳ(10)yim (t) =Fig. 1(a), the chaotic time series could be divided into two
σyphases; laminar part of periodic behavior with period threeand burst parts of spread points over the invariant interval. where ȳ and σy are the average and the standard deviation of
We obtain fully-developed chaos shown in Fig. 1(b) for αz = ŷ(t), respectively.
3.999. This time series are more similar to random uniform
noise.
3.3. Simulated results
When we inject the intermittency chaos noise to the HopWe carry out computer simulations of the Hopfield NN
field NN, we normalize ẑim by the following equation.
with the intermittency chaos noise and the intermittency torusẑim (t) − z̄(8) noise for 12-element QAP. The problem used here was chozim (t) =σz
sen from the site QAPLIB [7] named “Nug12,” The global
where z̄ and σz are the average and the standard deviation of minimum of this target problem is known as 578. The parameters of the Hopfield NN are as A = 0.9, B = 0.9, q = 140,ẑ(t), respectively.

- 318 -10.9
0.8
10.7
0.9
Yim(t+1)

0.6
0.8
0.5
0.7
0.4
mix noise

0.6
0.3
0.2

0.5
0.4

0.1
0.3
00

0.1

0.2

0.3

0.4

0.5
Yim(t)

0.6

0.7

0.8

0.9

10.2

αy =0.04 and D=0.05.

0.1
00100

200

300

400

500

600

700

800

900

1000

800

900

1000

800

900

1000

900

1000

t

Figure 2: Sine circle map.

(a) torus : chaos = 2 : 8.
1

1
0.9
0.9
0.8
0.8
0.7
0.7
mix nosie

0.6
torus noise

0.6
0.5

0.5
0.4

0.4
0.3
0.3
0.2
0.2
0.1
0.1
00100

200

300

400

00100200300400500t

600

7008009001000500t

600700(b) torus : chaos = 7 : 3.

αy =0.04 and D=0.05.

10.9

Figure 3: Intermittency torus time series.

0.80.7

mix noise

0.6

ε=0.02, and the amplitude of the injected noise is fixed as
β = 0.55.
The average solution and the best minimum solution aresummarized in Table 1. For comparison, the results for thecases of the fully-developed chaos noise and random noise
are shown together. The results show that the intermittencychaos noise gains the best performance. The intermittency
torus noise is better than the random noise, but still far fromthe chaotic noises.

0.5
0.4
0.3
0.2
0.1
00100200300400500t600700(c) torus : random = 2 : 8.
1
0.9
0.8
0.7

4. Mix noise
Since the intermittency torus noise does not have a better
performance, we try to add a burst feature of the intermittencychaos. Mix noise is made by inserting fully-developed chaosor random noise into the intermittency torus noise. The obtained mix noise is shown in Fig. 4. Figures 4(a) and (b) are
the mix noise obtained by inserting the fully-developed chaoswith different rates. While Figs. 4(d) and (e) are the mix noiseobtained by inserting random noise with different rates. The
simulated results of the Hopfield NN with the mix noise aresummarized in Table 2. The problem and the parameters ofthe Hopfield NN are the same as the case of the intermittency- 319 -mix noise

0.6
0.5
0.4
0.3
0.2
0.1
00100

200

300

400500t

600

700

800(d) torus : random = 7 : 3.
Figure 4: Mix noise.

Iteration
2000
4000
6000
8000
10000

Iteration

2000
40006000800010000

Table 1: Solving abilities of intermittency noise.
Chaos NoiseIntermittency
Random NoiseIntermittency Fully-developed
Torus Noiseaverage best average
bestaverage best average best
613.4
586
636.0
606
667.0
638
724.2
680
607.8
586
636.0
606
667.0
638
724.2
680
607.8
586
636.0
606
667.0
638
724.2
680
604.0
586
636.0
606
667.0
638
724.2
680
604.0
586
636.0
606
667.0
638
724.2
680

Table 2: Solving abilities for of mix noise.
Mix Noise
torus noise : chaos noise
torus noise : random noise
2: 8
7: 3
2: 8
7: 3
average best average best average best average best
604.4
578
617.4
586
612.0
582
614.6
590
595.2
578
608.6
578
604.8
582
604.2
590
591.6
578
601.4
578
601.6
582
599.8
586
590.4
578
595.6
578
601.6
582
598.8
586
587.8
578
595.6
578
596.6
582
598.0
586

noises in Table 1.
We can see that the mix noise with chaos achieves the best
performance and that the mix noise with random noiose alsoachieves a good performance.
We can conclude that the burst feature of the noise is important to gain a good performance of the Hopfield NN forQAP.
5. Conclusions
In this study, we have considered the torus noise generated
by the sine circle map for the Hopfield NN. We have investigated the performance of various noises based on the torus
noise injected to Hopfield NN for QAP. By computer simulations, we confirmed that the mix noise of the intermittency
torus noise with chaos achieved the best performance.
References[1] J. J. Hopfield, “Neurons with Graded Response Have
Collective Computational Properties like Those of TwoState Neurons,” Proc. Natl. Acad. Sci. USA, vol. 81,pp. 3088-3092, 1984.

[3] M. Hasegawa, T. Ikeguchi, T. Matozaki and K. Aihara,“An Analysis on Adding Effects of Nonlinear Dynamics for Combinatorial Optimization Problems,” IEICE
Trans. Fundamentals, vol. E80-A, no. 1, pp. 206-213,
1997.
[4] M. C. Jeruchim, P. Balaban and K. S. Shanmugan, Simulation of Communication System, pp. 245-247, Plenum
Press, New York, 1992.
[5] T. Ueta, Y. Nishio and T. Kawabe, “Comparison Between Chaotic Noise and Burst Noise on Solving Ability of Hopfield Neural Network,” Proc. of NOLTA’97,
vol. 1, pp. 409-412, 1997.
[6] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe andT. Ikeguchi, “Performance of Chaos and Burst Noise
Injected to the Hopfield NN for Quadratic Assignment
Problems,” IEICE Trans. Fundamentals, vol. E87-A,
no. 4, pp. 937-943, 2004.
[7] R. E. Bedkard, S. E. Karisch and F. Rendl, “QAPLIB-A
Quadratic Assignment Problem Library,”
http://www.opt.math.tu-graz.ac.at/qaplib[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. 2639-2696, 1995.

- 320 -