NOLTA 2006
11-14 september
Bologna - ITALY

Solving Ability of Hopfield Neural Network for QAP
by Changing Chaotic Behavior of Switching Noise
Yoshifumi Tada, Yoko Uwate and Yoshifumi Nishio
Department of Electrical and Electronic Engineering,
Tokushima University, Japan
2-1 Minami-Josanjima Tokushima 770-8506, Japan
Email: {y-tada, uwate, nishio}@ee.tokushima-u.ac.jp
Abstract—In our previous research, we confirmed thatthe chaotic switching noise generated by the cubic map
gained a good performance for solving combinatorial optimization problems when the noise was injected to the Hopfield neural network. However, the reason of the good effect of chaotic switching noise has not been clarified completely. In this study, we investigate the solving ability of
Hopfield neural network for QAP when the chaotic behavior of the switching noise is changed.

dow [9]. However, the reason of the good effect of chaotic
switching noise has not been clarified completely.
In this study, we investigate solving ability of Hopfield
NN for QAP when the chaotic behavior of the switching
noise is changed. By computer simulation, we confirm thatthe network can find good solutions, even when the chaotic
behavior is partly replaced by random time series.

1. Introduction

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, distance matrix C and flow matrix D, and find the
permutation P which corresponds to the minimum value ofthe objective function f (p) in Eq. (1).

Combinatorial optimization problems can be solved with
the Hopfield neural network (abbr. NN). If we choose connection weights between neurons appropriately according
to given problems, we can obtain a good solution by theenergy minimization principle. However, the solutions areoften trapped into a local minimum and do not reach theglobal minimum. In order to avoid this critical problem,
several people proposed the method adding some kinds ofnoise for solving traveling salesman 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 thatthe good result might be obtained by a property of thechaos noise; short time correlations of the time-sequence.
Hasegawa et al. investigated solving abilities of 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 by the burst
noise generated by the Gilbert [4] model with 2 states; alaminar state and a burst state. We concluded that the irregular switching of laminar part and burst part is one of thereasons of the good performance of the chaotic noise [5][6]. Further, we have investigated a performance of chaotic
switching noise generated by the cubic map when the noise
is injected to the Hopfield NN for quadratic assignment
problem (abbr. QAP). We have confirmed that the chaotic
switching noise was effective for solving QAP similar to
the intermittency chaos noise near the three-periodic win-

2. Solving QAP with Hopfield NN

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
the size of the problem. There are many real applications
which are formulated by Eq. (1). One example of QAP isfind an arrangement of the factories to make a cost the minimum. The cost is given by the distance between the factories and flow of the products between the factories. Other
examples are the placement of logical modules in a IC chip,
the distribution of medical services in large hospital.
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 24 in recent study. Further, computation times
is very long to obtain the exact optimum solution. Therefore, it is usual to develop heuristic methods which searchnear optimal solutions in reasonable time.
For solving N -element QAP by Hopfield NN, N ×N
neurons are required and the following energy function isdefined to fire (i, j)-th neuron at the optimal position:
E=

N
N


i,m=1 j,n=1

107

wim;jn xim xjn +

N

i,m=1

θim xim .

(2)yim(t+1)

The neurons are coupled each other with the following
weight between (i, m)-th neuron and (j, n)-th neuron andthe threshold of the (i, m)-th neuron is described by:
Cij Dmn
wim;jn = −2 A(1−δmn )δij +Bδmn (1−δij )+q(3)
θim = A + B
(4)

1

0.5

0

where A and B are positive constant, and δij is Kroneker’s
delta. The state of N ×N neurons are asynchronously update due to following difference equation:
 N
wim;jn xim (t)xjn (t)−θim +βzim (t)xim (t+1) = f-0.5

yim(t)

-1
-1

-0.5

0

0.5

1

Figure 1: Cubic map (αc = 3.600).

j,n=1

(5)
where f is sigmoidal function defined as follows:
f (x) =1,

1 + exp − xε(6)zim is additional noise, and β limits the amplitude of thenoise.
3. Chaotic Switching NoiseIn this section, we describe chaotic switching noise injected to the Hopfield NN.
The following cubic map is used to generate the chaotic
switching noise.
2(t) + 1 − αc ).
ŷim (t + 1) = −ŷim (t)(αc ŷim

Figure 2: Bifurcation diagram of cubic map.
1
0.8

(7)

0.6
0.4

Figure 1 shows the shape of the cubic map Eq. (7). The
one-parameter bifurcation diagram of this map is shown in
Fig. 2. The attractor becomes symmetric at around αc =3.600 via an interior crisis. Because the transition of thesolution from the positive/negative part to the other partis seldom just after the crisis, the behavior looks like anirregular switching as shown in Fig. 3. We use these timeseries after the following normalization.
yim (t + 1) =ŷim (t) − ȳσyYim(t)

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

100

200

300

400

500

600

700

800

900

1000

700

800

900

1000

t

(a) αc = 3.599.

(8)

1
0.8

where ȳ and σy are the average and the standard deviationof ŷ(t), respectively.
In our previous research [9], we have confirmed that thischaotic switching noise was effective for solving QAP.

0.6
0.4

Yim(t)

0.2
0-0.2

4. Changing Chaotic Behavior of Switching Noise

-0.4
-0.6

We consider that the chaotic switching noise (Figs. 3)
contains two kinds of chaotic features; one is the switching
timing of the upper part and the lower part, the other is the
behavior inside the each part.
In the previous research [9], we have confirmed that regular switching between the two parts makes the performance worse. Hence, the former chaotic feature can be

-0.8
-1
0

100

200

300

400

500

600

t

(b) αc = 3.600.
Figure 3: Time series obtained from cubic map.

108

said to be important for solving QAP. How about the latterchaotic feature? In order to answer this question, we replace the chaotic time series inside the each interval of thechaotic switching noise by other time series.
Figure 4 shows three kinds of time series made by replacing the original chaotic time series by chaos, random,and torus. The switch was to multiply the sequance number
either by 1 or by −1. Please note that we keep the switching timing between the upper part and the lower part.

4.1. Switching Chaos
The logistic map is used to generate the chaotic time series inside the each interval.
l̂im (t + 1) = αl l̂im (t)(1 − l̂im (t)).

(9)

Varying parameter αl , Eq. (9) behaves chaotically via aperiodic-doubling cascade. In this study, we carry out computer simulations using the fully-developed chaos, which is
obtained from Eq. (9) for αl = 4.0.

1

4.2. Switching Random

0.8
0.6

Random time series are generated by using random function of C compiler. The range of random noise is set to 0 ∼1.

0.4

Zim(t)

0.2
0-0.2

4.3. Switching Torus

-0.4
-0.6

The sine circle map is used to generate the torus timeseries inside the each interval.

-0.8
-1
0

100

200

300

400

500
t

600

700

800

900

1000

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

(a) Switching chaos.

(10)

The parameters are fixed as αx =0.04 and D=0.1.

1
0.8
0.6

5. Simulation Results

0.4

Zim(t)

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

100

200

300

400

500
t

600

700

800

900

1000

(b) Switching random.
1
0.8
0.6

In this section, the simulation results of Hopfield NN
with three kinds of switching noise for 12-elements QAP
are summarized in Tables 1 and 2. The problem used here
was chosen from QAPLIB, whose name is “Nug12.” The
global minimum of this target problem is known as 578.
The parameters of Hopfield NN are fixed as A = 0.9, B =0.9, q = 140, ε = 0.02 and β= 0.55.
The tables show the average of the obtained solutionsin 10 trials with different initial conditions, the minimum
solution in 10 trials, and the error between the average andthe optimal solution calculated by the following equation.

0.4

Error =

Zim(t)

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

100

200

300

400

500

600

700

800

900

1000

t

(c) Switching torus.
Figure 4: Changing chaotic behavior of switching noise.

Ave − Opt
× 100,
Opt(11)

where Opt denotes the optimal solution of the target problem.
From these tables, we can confirm that the switchingchaos and the switching random can gain similar performance to the cubic map (chaotic switching noise). Thismeans that the chaotic feature inside the each interval is
not very important for solving QAP.
However, we can also notice that the switching torus can
not find a good solution. We can conclude that some kindsof irregularity are important inside the each interval of theswitching noise.

109

Iteration
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

Iteration
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

Table 1: Solving abilities for 12-elements QAP. (αc =3.599)
switching chaos
switching random
switching torus
Ave
Min error
Ave
Min
error
Ave
Min
error
624.8 586 8.097 645.4 626 11.661 657.6 632 13.772
620.2 586 7.301 631.2 606
9.204
654.8 632 13.287
619.0 586 7.903 627.6 606
8.581
646.4 606 11.834
617.8 586 6.886 623.4 594
7.855
646.4 606 11.834
615.8 586 6.540 619.8 594
7.232
646.4 606 11.834
615.8 586 6.540 617.2 594
6.782
646.4 606 11.834
614.0 586 6.228 616.8 594
6.713
646.4 606 11.834
613.4 586 6.125 614.6 594
6.332
646.4 606 11.834
611.4 586 5.779 614.0 594
6.228
646.4 606 11.834
611.4 586 5.779 612.6 594
5.986
646.4 606 11.834

Cubic Map
Ave
Min error
635.2 616 9.896
627.0 616 8.478
627.0 616 8.478
626.0 616 8.304
621.2 608 7.470
619.6 608 7.197
616.8 606 6.713
616.6 606 6.678
616.6 606 6.678
615.6 606 6.505

Table 2: Solving abilities for 12-elements QAP. (αc =3.6)
switching chaosswithing randomswithing torus
Ave
Min
error
Ave
Min
error
Ave
Min
error
635.8 612 10.000 637.0 606 10.207 662.4 664 14.602
633.6 612
9.619
627.4 606
8.547
656.6 622 13.599
623.8 598
7.924
624.8 606
8.097
654.8 622 13.287
621.4 598
7.509
617.8 606
6.886
654.8 622 13.287
619.2 598
7.128
613.6 586
6.159
654.8 622 13.287
614.6 598
6.332
613.6 586
6.159
654.4 622 13.218
610.6 598
5.640
613.4 586
6.125
654.4 622 13.218
609.4 598
5.433
613.4 586
6.125
654.4 622 13.218
609.4 598
5.433
611.8 586
5.848
654.4 622 13.218
608.4 598
5.259
611.8 586
5.848
654.4 622 13.218

Cubic Map
Ave
Min error
632.4 582 9.412
625.4 582 8.201
623.0 582 7.785
615.8 582 6.540
615.6 582 6.505
614.6 582 6.332
614.0 582 6.228
608.8 582 5.329
608.8 582 5.329
606.6 582 4.948

6. Conclusions
In this study, we have investigated the solving ability of
Hopfield NN when the chaotic behavior of the switching
noise was replaced by another chaos, random and torus.
By computer simulation, we confirmed that the network
can find good solution, even when the chaotic behavior
was partly replaced by random time series. We conclude
that the reason of the good performance of the chaotic
switching noise generated from the cubic map is the chaotic
switching between the upper part and the lower part, andthat chaotic behavior inside the each interval is not important but some kinds of irregularity are necessary.

[4] M. C. Jeruchim, P. Balaban and K. S. Shanmugan, Simulation ofCommunication Systems, 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 Hopfi eld Neural Network,” Proc. of NOLTA’97, vol. 1, pp. 409-412, 1997.
[6] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi, “Performance of Chaos and Burst Noises Injected to the Hopfi eld 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, “Performance of Chaos Noise Injected to Hopfi eld NN for Quadratic Assignment Problems,” Proc. NOLTA’02, vol. 1, pp. 267-270, 2002.
[8] R. E. Bedkard, S. E. Karisch and F. Rendl, ”QAPLIB-A Quadratic
Assignment Problem Library,”

References[1] J. J. Hopfi eld, “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.

http://www.opt.math.tu-graz.ac.at/qaplib[9] Y. Tada, Y. Uwate and Y. Nishio,“Performance of Chaotic Switching
Noise Injected to Hopfi eld NN for Quadratic Assignment Problem,”Proc. ISCAS’06, pp. 5519-5522, 2006.

[2] Y. Hayakawa and Y. Sawada, ”Effects of Chaotic Noise on the Performance of a Neural Network Module for Optimization Problems,”
Physical Review E, vol.51, no. 4, pp. 2693-2696, 1995
[3] M. Hasegawa, T. Ikeguchi, T. Matozaki and K. Aihara, “An Analysis
on Adding Effects of Nonlinear Dynamics for Combinatorial Optimization,” IEICE Trans. Fundamentals, vol. E80-A, no. 1, pp. 206213, 1997.

110