Performance of Chaotic Switching Noise Injected toHopfield NN for Quadratic Assignment Problem
Yoshifumi TADA∗ , Yoko UWATE∗ and Yoshifumi NISHIO∗∗ Department of Electrical and Electronic Engineering

Tokushima University
2–1 Minami-Josanjima Tokushima 770–8506, Japan
Telephone: +81–88–656–7470, Fax: +81–88–656–7471
Email: {y-tada, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract— Solving combinatorial optimization problems is oneof the important applications of the neural network. Many
researchers have reported that exploiting chaos achieves good
solving ability. However, the reason of the good effect of chaos has
not been clarified yet. In this study, we investigate a performanceof chaotic switching noise injected to the Hopfield neural networkfor quadratic assignment problems. By computer simulation weconfirm that the chaotic switching noise is effective for solving
quadratic assignment problems as well as intermittent chaos near
three-periodic window.

bifurcates from two-band chaos to one-band chaos via aninterior crisis. In the two-band chaos, the solution moves between the upper band and the lower band alternately. Namely,
the solution has a kind of regularity even if it is chaotic
in each band. However, the crisis makes the two bands tomerge into one band and the switching between the upperband and the lower band becomes irregular. We consider thatthe edge behavior between regular and irregular gains a goodperformance.

I. I NTRODUCTION
6e+080-7803-9390-2/06/$20.00 ©2006 IEEE

5e+08

Depth_2

4e+08
3e+08
2e+08
1e+08
0-1e+08-2e+08
3.6

3.65

3.7

3.75

3.8

3.85

3.9

3.95

4

α(a) Performance of chaos noises for QAP.
10.9
0.8
0.70.6Zim(t)Combinatorial optimization problems can be solved with theHopfield neural networks (abbr. NN). If we choose connection
weights between neurons appropriately according to given
problems, we can obtain a good solution by the energy minimization principle. However, the solutions are often trapped
into a local minimum and do not reach the global minimum.
In order to avoid this critical problem, several people proposed
the method adding some kinds of noise for solving travelingsalesman problems (TSP) with the Hopfield NN [1]. Hayakawa
and Sawada pointed out the chaos near the three-periodic
window of the logistic map gains the best performance [2].
They concluded that the good result might be obtained bya property of the chaos noise; short time correlations of thetime-sequence. Hasegawa et al. investigated solving abilitiesof the Hopfield NN with various surrogate noise, and they
concluded that the effects of the chaotic sequence for solving
optimization problems can be replaced by stochastic noise withsimilar autocorrelation [3]. We have also studied the reasonof the good performance of the Hopfield NN with chaotic
noise. We imitated the intermittency chaos noise by the burst
noise generated by the Gilbert model [4] with 2 states; alaminar state and a burst state. We concluded that the irregularswitching of laminar part and burst part is one of the reasonsof the good performance of the chaotic noise [5][6].
Further, we have investigated the performance of chaosnoises when the control parameter of the logistic map ischanged, and the intermittency chaos near the three-periodic
window of the logistic map is not only special chaos noise
gaining a good performance as shown in Fig. 1 [7]. For
example, the chaos noise achieves a good performance around
α = 3.67. At this point, the attractor of the logistic map

0.5
0.4
0.3
0.2
0.1
0
3.6

3.65

3.7

3.75

3.8
alpha

3.85

3.9

3.95

4(b) Bifurcation diagram of logistic map.
Fig. 1. Performance of chaos noises when the control parameter is changed.

In this study, we investigate a performance of chaotic
switching noise, which is generated by a cubic map, injectedto the Hopfield NN for quadratic assignment problems (abbr.
QAP). By computer simulation we confirm that the chaotic
switching noise is effective for solving QAP as well as theintermittent chaos noise near the three-periodic window.

5519

ISCAS 2006

II. S OLVING QAP WITH H OPFIELD NN
Various methods are proposed for solving the QAP which
is one of the NP-hard combinatorial optimization problems.
The QAP is expressed as follow: 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 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). One example of QAP is to find an
arrangement of the factories to make a cost the minimum. The
cost is given by the distance between the factories and flowof the products between the factories. Other examples are theplacement of logical modules in a IC chip, the distribution of
medical services in large hospital, and so on.
Because the QAP is very difficult, it is almost impossible
to solve the optimum solutions in large problems. The largest
problem which is solved by deterministic methods may be
only N = 36 in recent study [8]. Further, computation timeis 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 Hopfield NN, N ×N
neurons are required and the following energy function isdefined to fire (i, j)-th neuron at the optimal position:

where f is sigmoidal function defined as follows:1f (x) =1 + exp − xε(6)uim is additional noise, and β limits amplitude of the noise.
III. N OISE G ENERATION
A. Chaotic Switching NoiseIn this section, we describe chaotic switching noise injectedto the Hopfield NN.
The following cubic map is used to generate the chaoticswitching noise.
2ŷim (t + 1) = −ŷim (t)(αc ŷim(t) + 1 − αc )(7)Figure 2 shows the shape of the cubic map. The one-parameterbifurcation diagram of this map is shown in Fig. 3. The
attractor becomes symmetric at around αc = 3.600 via aninterior crisis. Because the transition of the solution from thepositive/negative part to the other part is seldom just after
the crisis, the behavior looks like an irregular switching asFig. 4(a). As the parameter increases, the transition becomes
more frequent as Figs. 4(b) and (c). For αc = 4.000, the timeseries become similar to a uniform random noise as Fig. 4(d).
We use the time series in Figs. 4(a), (b) and (c) as chaotic
switching noises after the following normalization.
yim (t) =ŷim (t) − ȳσy(8)where ȳ and σy are the average and the standard deviation ofŷ(t), respectively.
yim(t+1)
1

E=NN



wim;jn xim xjn +i,m=1 j,n=1Nθim xim ,(2)

i,m=1

0.5

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:wim;jn = −2 A(1 − δmn )δij-0.5



Cij Dmn+ βδmn (1 − δij ) +qyim(t)-1-1-0.5

Fig. 2.

Cubic map (αc = 3.600).

00.5

1(3)

θim = A + B(4)where A and B are positive constants, and δij is Kroneker’s
delta. The state of N ×N neurons are asynchronously update
due to the following difference equation:
 N
wim;jn xim (t)xjn (t)xim (t + 1) = fj,n=10− θim + βuim (t)(5)

B. Intermittency Chaos Noise
We have confirmed that the intermittency chaos near thethree periodic window has the good performance to the Hopfield NN for combinatorial optimization problems. In order toevaluate the performance of the chaotic switching noise in thelast subsection, we carry out the same simulation when theintermittency chaos is injected to the Hopfield NN as a noise.
The logistic map is used to generate the intermittency chaosnoise.
(9)ẑim (t + 1) = αl ẑim (t)(1 − ẑim (t)).

5520

1
0.8

yim(t+1)

0.6

1

0.4

0.8
Yim(t)

0.2

0.6

00.4

-0.2
-0.4

0.2

-0.6

0-0.8-1
2.4

-0.2
2.6

Fig. 3.

2.8

3

3.2
alpha

3.4

3.6

3.8

4

-0.4
-0.6

Bifurcation of cubic map.

-0.8
-10

Varying parameter αl , Eq. (9) behaves chaotically via aperiodic-doubling cascade. Further, it is well known that themap produces intermittent bursts just before periodic-windows
appear. Figure 5(a) shows an example of the intermittencychaos near the three-periodic window obtained from Eq. (9)for αl = 3.82676. As we can see from the figure, the chaotic
time series could be divided into two phases; laminar parts ofperiodic behavior with period three and burst parts of spread
points over the invariant interval. As increasing αl , the ratio of
the laminar parts becomes larger and finally the three-periodic
window appears. Just for the comparison, we also carry out
computer simulations for the case of fully developed chaos inFig. 5(b) which is obtained from Eq. (9) for αl = 4.0000.
This time series is similar to a uniform random noise as wellas the cubic map for αc = 4.0.
When we inject the intermittency chaos noise to the Hopfield NN, we normalize ẑim by Eq. (10).
zim (t) =ẑim (t) − z̄σz100

200300

400

500

600

700

800

900

1000

700

800

900

1000

800

900

1000

800

900

1000

t(a) αc = 3.599.
yim(t+1)
1
0.8
0.6
0.4
0.2
0-0.2-0.4-0.6
-0.8
-1

t
0

100

200

300

400

500

600(b) αc = 3.600.
yim(t+1)
1
0.8
0.6(10)where z̄ and σz are the average and the standard deviation ofẑ(t), respectively.

0.4
0.2
0-0.2
-0.4

C. Regular Switching Noise
For comparison, we compose a regular switching noise.
We use the time series of the cubic map (7) just before theinterior crisis (αc = 3.598). Because the generated time series
do not transit to the negative part before the crisis, we change
the sign of the sequence in every L iterations. An example of
the regular switching noise is shown in Fig. 6.
This noise is also normalized in a similar way before theinjection.

-0.6
-0.8
-1

t
0

100

200

300

400

500

600700(c) αc = 3.604.
yim(t+1)
1
0.8
0.6
0.4

IV. S IMULATED R ESULTS

0.2In this section, the simulated results of the Hopfield NN withthe chaotic switching noise, the intermittency chaos noise andthe regular switching noise for 12-element QAP are shown.
The problem used here was chosen from the site QAPLIB [8]named “Nug12.” The global 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, ε = 0.02 and the amplitude of
the injected noise is fixed as β = 0.55.
Table 1 shows simulation results. We carried out each simulation 10 times with different initial conditions and calculated

5521

0-0.2
-0.4-0.6-0.8
-1t0

100

200

300

400

500

600700(d) αc = 4.000.
Fig. 4.

Time series obtained from cubic map.

TABLE I
S OLVING ABILITIES FOR 12- ELEMENT QAP.
Iteration

Cubic map
Chaotic switching
αc =3.599
αc =3.600 αc =3.604
635.2
632.4
630.0
627.0
625.4
626.8
627.0
623.0
625.0
626.0
615.8
625.0
621.2
615.6
625.0
619.6
614.6
624.8
616.8
614.0
622.6
616.6
608.8
621.0
616.6
608.8
621.0
615.6
606.6
621.0

1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

full
αc =4.000
642.6
642.6
642.6
642.6
642.6
642.6
642.6
642.6
642.6
642.6

Logistic map
Intermittency chaosfull
αl =3.82676
αl =4.00000
623.4
630.2
613.4
622.8
613.4
622.8
607.8
622.8
607.8
622.8
607.8
622.8
607.0
622.8
604.0
622.8
604.0
622.8
604.0
622.8

Regular switching
L=50
651.8
634.6
634.2
629.6
624.6
624.6
622.8
622.8
622.8
621.6

L=100
654.4
641.6
637.4
631.2
629.6
626.4
625.8
625.8
625.0
624.6

L=200
684.2
662.8
651.6
645.8
633.8
633.8
631.4
630.6
630.6
625.6

L=500
691.8
669.0
663.8
658.6
652.4
646.0
641.4
640.0
640.0
622.0

the average value. The results show that the chaotic switching
noise for αc = 3.600 gains a good performance similar to
the intermittency chaos noise for αl = 3.82676. We can also
see that the regular switching noise and fully-developed chaos
cannot achieve a good performance.

zim(t+1)
1
0.9
0.80.7
0.6

V. C ONCLUSIONS

0.5
0.4
0.3
0.2
0.1

0100

200300400500

600

700

800

900

1000t(a). αl = 3.82676.
zim(t+1)
1
0.9
0.8
0.7
0.6
0.5

In this study, we have investigated a performance of chaotic
switching noise injected to the Hopfield NN for QAP. By
computer simulation we confirmed that the chaotic switching
noise is effective for solving QAP similar to the intermittencychaos near the three-periodic window.
A positive part and a negative part repeat alternately in thechaotic switching noise. Hence, this noise can be said to be lesschaotic than fully-developed chaos. By combining the result inthis study with our past study explaining the good performanceof the intermittency chaos, we conclude that the edge behavior
between regular and irregular can play an important role in
information processing.
R EFERENCES

0.4
0.3
0.2
0.1
00100

200

300

400

500

600

700

800

900

1000

t(b). αl = 4.00000.
Fig. 5.

Time series obtained from logistic map.

yim(t+1)
1
0.8
0.6
0.4
0.2
0-0.2
-0.4
-0.6
-0.8
-1t0200Fig. 6.

400600800[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 Chaotic Noise on the Performance of a Neural Network Module for Optimization Problems,” PhysicalReview E, vol. 51, no. 4, pp. 2693-2696, 1995
[3] M. Hasegawa, T. Ikeguchi, T. Matozaki and K. Aihara, “An Analysis onAdding Effects of Nonlinear Dynamics for Combinatorial Optimization,”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 Systems, pp. 245-247, Plenum Press, New York, 1992.
[5] T. Ueta, Y. Nishio and T. Kawabe, “Comparison Between Chaotic Noiseand 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 and T. Ikeguchi, “Performanceof Chaos and Burst Noises Injected to the Hopfield NN for Quadratic
Assignment Problems,” IEICE Trans. Fundamentals, vol. E87-A, no. 4,pp. 937-943, 2004.
[7] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi, “Performanceof Chaos Noise Injected to Hopfield NN for Quadratic Assignment
Problems,” Proc. NOLTA’02, vol. 1, pp. 267-270, Oct. 2002.
[8] R. E. Bedkard, S. E. Karisch and F. Rendl, “QAPLIB-A Quadratic
Assignment Problem Library,”
http://www.opt.math.tu-graz.ac.at/qaplib

1000

Regular switching noise (L = 50).

5522