IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

937

PAPER

Performance of Chaos and Burst Noises Injected to the Hopfield NN
for Quadratic Assignment Problems
Yoko UWATE†a) , Student Member, Yoshifumi NISHIO†b) , Tetsushi UETA††c) , Members,
Tohru KAWABE†††d) , Nonmember, and Tohru IKEGUCHI††††e) , Member

SUMMARY
In this paper, performance of chaos and burst noises injected to the Hopfield Neural Network for quadratic assignment problems
is investigated. For the evaluation of the noises, two methods to appreciatefinding a lot of nearly optimal solutions are proposed. By computer simulations, it is confirmed that the burst noise generated by the Gilbert modelwith a laminar part and a burst part achieved the good performance as theintermittency chaos noise near the three-periodic window.
key words: chaos, intermittency, burst noise, neural network, combinatorial optimization problems, QAP

1.

Introduction

Solving combinatorial optimization problem is one of theimportant applications of the neural network (abbr. NN). If
we choose connection weights between neurons of the Hopfield NN appropriately according to given problems, we canobtain a good solution by the energy minimization principle[1]. However, the solutions are often trapped into a local
minimum and do not reach the global minimum (namely
optimal solution). In order to avoid this critical problem,
several people proposed the method adding some kinds ofnoise for solving traveling salesman problems (abbr. TSP)
with the Hopfield NN. Hayakawa and Sawada pointed outthat intermittency chaos near the three-periodic window of
the logistic map gains the best performance [2]. They concluded that the good result might be obtained by some properties of the chaos noise; short time correlations of the timesequence. Hasegawa et al. investigated solving abilities ofthe Hopfield NN with various surrogate noises, and they
concluded that the eﬀects of the chaotic sequence for solving optimization problems can be replaced by stochastic
noise with the similar autocorrelation [3]. However, their
Manuscript received April 16, 2003.
Manuscript revised September 19, 2003.
Final manuscript received January 14, 2004.
†
The authors are with the Department of Electrical and Electronic Engineering, Tokushima University, Tokushima-shi, 7708506 Japan.
††
The author is with Center for Advanced Information Technology, Tokushima University, Tokushima-shi, 770-8506 Japan.
†††
The author is with Institute of Information Sciences and Electronics, University of Tsukuba, Tsukuba-shi, 305-8577 Japan.
††††
The author is with Graduate School of Science and Engineering, Saitama University, Saitama-shi, 338-8570 Japan.
a) E-mail: uwate@ee.tokushima-u.ac.jpb) E-mail: nishio@ee.tokushima-u.ac.jpc) E-mail: tetsushi@is.tokushima-u.ac.jpd) E-mail: kawabe@is.tsukuba.ac.jpe) E-mail: tohru@nls.ics.saitama-u.ac.jp

researches treated relatively easy problem (TSP) only andthey evaluated the performance of the noises by whether tofind the optimal solution or not. We consider that the performance of the noises should be evaluated by finding a lot ofnearly optimal solutions within a certain period, especiallyfor diﬃcult problems. Hence, we do not consider that thereason of good performance of chaos noise has been completely disclosed. Especially, we emphasize that it is important to probe into the reason why the intermittency chaos isbetter than fully developed chaos.
In this paper, the intermittency chaos noise near thethree-periodic window is modeled by the Gilbert model [4]with a laminar part and a burst part. Both of intermittencychaos noise and the burst noise generated by the Gilbert
model are injected to the Hopfield NN for quadratic assignment problems (abbr. QAP) said to be much more diﬃcult
to solve than TSP [5], [6]. We examine frequency distribution of the obtained solutions to compare the performance ofthe noises in detail. Furthermore, we propose two methods
Depth 1 and Depth 2 to appreciate finding a lot of nearly
optimal solutions for the evaluation of the noises. By computer simulations we confirm that the burst noise generated
by the Gilbert model is also eﬀective to solve QAP and we
can say that the irregular switching of the laminar parts andthe burst parts is one reason of the good performance of the
Hopfield NN with chaos noise.
2.

Solving QAP with the Hopfield NN

Various methods are proposed for solving QAP which is oneof the NP-hard combinatorial optimization problems. QAP
is expressed as follow: given two matrices, distance matrix 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) =NN 
Ci j D p(i)p( j) ,(1)

i=1 j=1

where Ci j and Di j 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 Eq. (1). One example of QAP is
to find an arrangement of factories to make a cost the minimum. The cost is given by the distance between the cities
and the flow of the products between the factories (Fig. 1).

IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

938

Other examples are the placement of logical modules in an
IC chip, the distribution of medical services in a large hospital, and so on.
Because the QAP is very diﬃcult, it is almost impossible to solve the optimum solutions in larger problems. The
largest problem whose optimal solution can be obtained may
be only 36 in recent study [7]. Further, computation time isvery long to obtain the exact optimum solutions. Therefore,
it is usual to develop heuristic methods which search nearly
optimal solutions in reasonable time.
For solving an N-element QAP by the Hopfield NN,
N × N neurons are required and the following energy function is defined:
E=

N
N 


wim; jn x jn +i,m=1 j,n=1

Nθim xim .

(2)

i,m=1

The neurons are coupled each other with the synaptic
connection weight. Suppose that the 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 )δi j

Ci j Dmn+Bδmn (1 − δi j ) +qθim = A + B(3)noise.
Also, we use the method suggested by Sato et al. (1.1
in [8]) to decide firing of neurons.
3.

Chaos and Burst Noises

3.1 Chaos NoiseIn this subsection, we describe chaos noise injected to the
Hopfield NN. The logistic map is used to generate the chaosnoise:ẑim (t + 1) = αẑim (t)(1 − ẑim (t)).

(6)

Varying the parameter α, Eq. (6) behaves chaotically via
a period-doubling cascade. Further, it is well known thatthe map produces intermittent bursts just before periodicwindows appear. Figure 2 shows an example of the intermittency chaos near the three-periodic window obtained from
Eq. (6) for α = 3.8274. As we can see from the figure, thechaotic time series could be divided into two phases; laminarparts of periodic behavior with period three and burst partsof spread points over the invariant interval. As increasing
α, the ratio of the laminar parts becomes larger and finallythe three-periodic window appears. For the comparison, we
also carry out computer simulations for the case of fully developed chaos in Fig. 3 which is obtained from Eq. (6) for
α = 4.0000. This noise is much more similar to the random
noise.
When we inject the chaos noises to the Hopfield NN,
we normalize ẑim by Eq. (7).

where A and B are positive constants, q is a normalization parameter to correspond given problems, and δi j is the
Kronecker’s delta. The states of N × N neurons are asynchronously updated due to the following diﬀerence equation:
 N

 
wim; jn x jn (t) − θim + βzim (t)(4)
xim (t + 1) = g where z̄ is the average of ẑ(t), and σz is the standard deviation of ẑ(t).

where g is a sigmoidal function defined as follows:

3.2 Burst Noisej,n=1g(x) =1 x
1 + exp −ε(5)

zim is an additional noise, and β limits the amplitude of theFig. 1

An example of QAP.

zim (t) =ẑim (t) − z̄σz

(7)In this subsection, we model the intermittency chaos by using the two-state Gilbert model shown in Fig. 4. The Gilbert
model is sometimes used for characterizing error-generating
mechanisms in digital communication channels.

Fig. 2

Intermittency chaos noise near three-periodic window. α=3.8274.

UWATE et al.: PERFORMANCE OF CHAOS AND BURST NOISES INJECTED TO THE HOPFIELD NN

939

Figure 5 shows an example of the burst noise generated by
the Gilbert model.
4.

Fig. 3

Simulated Results

In this section, the simulated results of the Hopfield NN for
QAP with the three diﬀerent noises, namely the intermittency chaos noise, the fully developed chaos noise, and theburst noise generated by the Gilbert model are shown.
The first target problem is named as “Nug12” chosenfrom the site QAPLIB [7]. The number of the elements is
12 and the optimal solution is known as 578. The parametersof the Hopfield NN are fixed as A = 0.9, B = 0.9, q = 140,and ε = 0.02 and the amplitude of the injected noise is fixedas β = 0.6. The iteration number Niteration of the network isfixed as 10000.

Fully developed chaos noise. α=4.0000.

4.1 Solving Ability

Fig. 4Since we know the optimal solution in advance, we define
the Success such that the NN finds the optimal solution atleast once during the defined iteration number Niteration . We
repeat this trial 100 times and count the number of the Success for the solving ability S A defined as

Two-state Gilbert model.

SA =Number of Success× 100 [%].
Number of Trials(10)

We also record the minimum cost found during each trial
and use the Average of the minima for the evaluation. The
Error is also defined as
Error =

Fig. 5 Burst noise generated by the Gilbert model with p1 = 0.247 andp2 = 0.238.

At first, we distinguish the laminar part and the burst
part of the intermittency chaos. Because we treat only theintermittency chaos near the three-periodic window, we regard three successive sequences starting from a point whose
value is 1.194 or more as one-period of the laminar part.
Other points are regarded as the burst part.
One state S 1 corresponds to the burst part and generates
uniformly distributed noise over the interval {−1.56–1.236},
while the other state S 2 corresponds to the laminar part andgenerates three-periodic sequence {1.236, −1.560, −0.320}
imitating the three-periodic window of the logistic map. The
transition probabilities p1 and p2 are calculated by the average lengths of the laminar parts and the burst parts in theintermittency chaos in Fig. 2 according to
Average length of the burst parts =1
p1

Average length of the laminar parts =

(8)
1
p2

(9)

Average − Optimal Solution
× 100 [%]. (11)Optimal Solution

The results are summarized in Table 1. The results
show that the intermittency chaos noise and the burst noise
have much better performance than the fully developed
chaos noise. Furthermore, it is interesting to note that the
burst noise generated by the Gilbert model has the similar
Average to the intermittency chaos noise.
4.2 Frequency Distribution
In order to make clear the reason of the good performanceof the intermittency chaos noise and the burst noise, we examine frequency distribution of the obtained solutions.
At first, we explain how to accept the solutions. The
Hopfield NN with the noises can find various solutions.
However, the state of the Hopfield NN sometimes stays
around one solution or a group of several solutions. We consider that such a behavior is not useful to find the optimalor nearly optimal solutions. So, we take the only-diﬀerentsolutions method. Namely, we take into account only thesolutions whose firing patterns have not found ever in eachtrial. In other words, we accept only the first time if the completely same firing patterns appear more than once in eachtrial.
The results of the frequency distribution are shown inIEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

940
Table 1

Solving abilities for 12-element QAP.

Intermittency chaos
Niteration
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000

S A[%]
1
1
3
3
5
7
7
7
7
7

Average612.66607.64604.04602.36601.02600.24599.32599.08598.42598.14

Error[%]
5.997
5.128
4.505
4.214
3.983
3.848
3.689
3.627
3.533
3.484

Burst
S A[%]
1
1
1
1
1
1
2
2
2
2

Fig. 6 Frequency distribution of solutions with intermittency chaos noise
for Nug12.

Average615.52607.96604.36602.34601.42600.70599.76599.42598.96598.74

Fully developed chaos
Error[%]
6.491
5.183
4.561
4.211
4.052
3.927
3.765
3.706
3.626
3.588

S A[%]
0
0
0
0
0
0
0
0
0
0

Average629.46628.08627.98627.98627.98627.98627.98627.98627.98627.98Error[%]
8.903
8.664
8.647
8.647
8.647
8.647
8.647
8.647
8.647
8.647

Fig. 8 Frequency distribution of solutions with fully developed chaosnoise for Nug12.

4.3 Depth

Fig. 7Frequency distribution of solutions with burst noise for Nug12.

Figs. 6, 7 and 8. The frequency means the number of theaccepted solutions with the corresponding costs found during 10000 iterations. We can see that a lot of solutions arefound for the cases of the intermittency chaos noise and theburst noise. On the other hand, only a very small number ofthe solutions are found for the fully developed chaos. (Notethat the scale of the vertical axis of Fig. 8 is 1/10 of those ofFigs. 6 and 7.) Although the result in Table 1 would reflect
the diﬀerence of the numbers of the obtained solutions, we
can see that the methods using only the best solution in eachtrial are not suﬃcient to evaluate the performances of thenoises.

Until now, we have evaluated the performance of the Hopfield NN with noises by using only the best solution foundin each trial; time to find the optimal solution, frequency
of finding the optimal solution during a given time, averageof the minimum cost in each trial, and so on. However, as
shown in the previous subsection, such methods are not sufficient to reflect the number of the obtained solutions. Further, when the network can not find the optimal solution, themethods using only the optimal solution do not give a correct evaluation of the network. Namely, for very diﬃcult
problems, we consider that it is more important to find a lotof nearly optimal solutions than to happen to find the optimal solution. Therefore, we propose two evaluation methods to appreciate finding a lot of nearly optimal solutions.
4.3.1

Depth 1

The first evaluation method Depth 1 is defined as
Depth 1 =n

{ f (pk ) − D∞ }2

(12)

k=0

where D∞ is a constant which is large enough to include
the costs of all solutions, n is the number of the accepted
solutions and the cost f (pk ) is calculated by Eq. (1) using the
permutation pk corresponding to the k-th accepted solution.

UWATE et al.: PERFORMANCE OF CHAOS AND BURST NOISES INJECTED TO THE HOPFIELD NN

941
Table 2Depth 1 for Nug12.
Depth 1

D∞
1000

Intermittency
chaos
1.07e+08

Table 3

Burst
0.80e+08

Fully developed
chaos
7.36e+06

Depth 2 for Nug12.
Depth 2

Dth
858.8
812.0
765.2

Intermittency
chaos
2.58e+07
1.21e+07
3.38e+06

Burst
1.99e+07
0.95e+07
2.92e+06

Fully developed
chaos
1.87e+06
9.11e+05
2.97e+05

Fig. 9 Frequency distribution of solutions with intermittency chaos noise
for Nug30.

The calculated result of Depth 1 is shown in Table 2.
The performances of the intermittency chaos noise and theburst noise generated by the Gilbert model are much higher
than the fully developed chaos noise. We consider that thisresult is more appropriate than the evaluation using only
the optimal solution to indicate the fact that the fully developed chaos noise is behind the others. Further, we can seethat there is still some diﬀerence between the intermittencychaos noise and the burst noise.
4.3.2

Depth 2The second evaluation method Depth 2 is defined as
Depth 2 =nFig. 10Frequency distribution of solutions with burst noise for Nug30.

{ f (pk ) − Dth }2

k∈kg

−

n


{ f (pk ) − Dth }2

kkg

where

kg = {k | f (pk ) ≤ Dth }.

(13)

This evaluation has an advantage such that we can set thethreshold Dth according to the requirement. We consider
that finding a lot of bad solutions makes the performanceof the network worse. However, the value of Depth 1 increases even if the obtained solution is very bad. Hence, inthis evaluation, we not only set up a threshold but give a
penalty according to the cost. Namely, if the network finds
a solution with the cost more than a given threshold value,
the value of Depth 2 is reduced.
The calculated result of Depth 2 is shown in Table 3.
The tendency of the result is similar to that of Depth 1.
4.4 30-Element Problem
We carried out computer simulation for a larger problem
with 30 elements named “Nug30.” The global minimumof this target problem is known as 6124. The parameters ofthe Hopfield NN are fixed as A = 0.9, B = 0.9, q = 640,and ε = 0.02 and the amplitude of the injected noise is fixedas β = 0.6. The iteration number Niteration is also fixed as
10000.
The results of the frequency distribution are shown in

Fig. 11 Frequency distribution of solutions with fully developed chaosnoise for Nug30.
Table 4

Depth 1 for Nug30.
Depth 1

D∞
10000

Intermittency
chaos
3.89e+10

Burst
2.48e+10

Fully developed
chaos
1.96e+09

Figs. 9, 10 and 11. Further, the calculated results of Depth 1
and Depth 2 are shown in Tables 4 and 5, respectively.
From these results, we can say that the intermittencychaos noise and the burst noise generated by the Gilbert
model has much better performance than the fully developed
chaos noise and that there is still some diﬀerence between
the intermittency chaos noise and the burst noise.

IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

942
Table 5Depth 2 for Nug30.
Depth 2

Dth
8536
8134
7732

Intermittency
chaos
6.04e+09
2.14e+09
2.78e+08

Fig. 12Burst
4.32e+09
1.71e+09
3.47e+08

Fully developed
chaos
3.23e+08
1.21e+08
1.99e+07

Regular burst noise.

the burst parts but also their irregular switching is an important factor of the intermittency chaos.
5.

Conclusions

In this paper, we have investigated the performance of thechaos and the burst noises injected to the Hopfield NN for
QAP. For the correct evaluation of the noises, we proposed
two methods to appreciate finding a lot of nearly optimal
solutions. We confirmed by the computer simulations thatthe burst noise generated by the Gilbert model with a laminar part and a burst part achieved the good performance as
the intermittency chaos noise near the three-periodic window. The result suggests that the irregular switching of thelaminar parts and the burst parts is one reason of the good
performance of the Hopfield NN with chaos noise. We also
found that there is still some diﬀerence between the intermittency chaos noise and the burst noise. Investigating thereason of the diﬀerence in detail is our important future research.
References

Fig. 13
Nug30.

Frequency distribution of solutions with regular burst noise for

4.5 Regular Burst NoiseAt last, in order to support our conjecture on the good performance of the intermittency chaos, we consider a regularburst noise whose laminar parts and burst parts have fixed
lengths and appear alternately. The length of the laminarparts and the burst parts are fixed as 4-period. Figure 12
shows an example of the regular burst noise and Fig. 13
shows the frequency distribution of solutions when the noise
is applied to the network under the same conditions as 4.4.
As we can see from the frequency distribution, the regular switching of the laminar parts and the burst parts makes
the performance worse remarkably. (The diﬀerence between
Figs. 10 and 13 might looks similar to the diﬀerence between Figs. 9 and 10. However, the diﬀerence of the timeseries used for Figs. 10 and 13 is only the regularity of theswitchings and it is considered to be much smaller than thatof the time series used for Figs. 9 and 10.) Hence, we canconclude that not only the existence of the laminar parts and[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, “Eﬀects of the chaotic noise on theperformance of a neural network model for optimization problems,”
Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top.,
vol.51, no.4, pp.2693–2696, April 1995.
[3] M. Hasegawa, T. Ikeguchi, T. Matozaki, and K. Aihara, “An analysis
on additive eﬀects of nonlinear dynamics for combinatorial optimization,” IEICE Trans. Fundamentals, vol.E80-A, no.1, pp.206–213, Jan.
1997.
[4] M.C. Jeruchim, P. Balaban, and K.S. Shanmugan, Simulation of Communication Systems, pp.245–247, Plenum Press, New York, 1992.
[5] P.M. Hahn, W.L. Hightower, T.A. Johnson, M. Guignard-Spielberg,
and C. Roucairol, “A lower bound for the quadratic assignment problem based on a level-2 reformulation-linearization technique,” University of Pennsylvania, Systems Engineering Department Report, 2001.
[6] K. Anstreicher, N. Brixius, J.-P. Goux, and J. Linderoth, “QAP andother hard problems,” http://www-unix.mcs.anl.gov/metaneos/nug30/
qap-tsp.html[7] R.E. Berkard, S.E. Karisch, and F. Rendl, “QAPLIB—A quadratic assignment problem library,” http://www.opt.math.tu-graz.ac.at/qaplib[8] K. Sato, T. Ikeguchi, M. Hasegawa, and K. Aihara, “An optimization
method for quadratic assignment problems by chaotic dynamics andits characterization by Lyapunov dimensions,” IEICE Technical Report, NLP64-13, 2001.

UWATE et al.: PERFORMANCE OF CHAOS AND BURST NOISES INJECTED TO THE HOPFIELD NN

943
Yoko Uwate
was born in Tokushima, Japan,
in 1980. She received the B.E. degree from
Tokushima University, Tokushima, Japan, in
2003. She is currently working towards M.E.
degree at the same university. Her research interests include complex phenomena in chaotic
circuits and neural networks. Ms. Uwate is a
student member of the IEEE.

Yoshifumi Nishio
received the B.E., M.E.
and Ph.D. degrees in Electrical Engineeringfrom Keio University, Yokohama, Japan, in
1988, 1990 and 1993, respectively. In 1993, hejoined the Department of Electrical and Electronic Engineering at Tokushima University,
Tokushima, Japan, where he is currently an Associate Professor. From May 2000 he spent a
year in the Laboratory of Nonlinear Systems(LANOS) at the Swiss Federal Institute of Technology Lausanne (EPFL) as a visiting professor.
His research interests include analysis and application of chaos in electrical circuits, analysis of synchronization in nonlinear circuits, developmentof analytical methods for nonlinear circuits and theory and application ofcellular neural networks. Dr. Nishio is a member of the IEEE.

Tetsushi Ueta
received the B.E., M.E. and
D.E. degrees from Tokushima University, Tokushima, Japan, in 1990, 1992, and 1996, respectively. He is currently an associate professor ofCenter for Advanced Information Technology,
Tokushima University. His research interests include bifurcation problems of nonlinear dynamical systems.

Tohru Kawabe
received the B.Eng. degree
in applied mathematics and physics, M.Eng. degree in applied systems science and Dr.Eng.
degree in applied mathematics and physics allfrom Kyoto university in 1988, 1990 and 1997,
respectively. From 1990 to 1995, he was a Research Associate of the Department of Information Science and Intelligent Systems, Universityof Tokushima, and from 1995 to 1997, he was an
assistant Professor in the Information Processing Center, University of Tokushima. In 1997,
he joined the University of Tsukuba, where he is currently an Associate
Professor in the Institute of Information Sciences and Electronics. His research interests include robust control, hybrid systems, optimization theory,and signal processing.

Tohru Ikeguchi
graduated from Science
University of Tokyo in 1988 and received M.E.
degree in 1990 and Ph.D. degree in 1996 from
Science University of Tokyo. In 1990, he waswith Department of Applied Electronics, Faculty of Industrial Science and Technology, Science University of Tokyo. In 1997, he was Invited Professor at the University of Louis Pasteur, Strasbourg, France. Since 2000, he is Associate Professor at Department of Informationand Mathematical Sciences, Saitama University.
His research interests are chaotic time series analysis, nonlinear phenomena
in neural systems, applications of chaotic dynamics to combinatorial optimization problems and associative memories. He is the member of IEEE,
INNS, JNNS, and JSIAM.