International Symposium on Nonlinear Theory and its Applications
Xi’an, PRC, October 7–11, 2002

Performance of Chaos Noise Injected to Hopfield NN
for Quadratic Assignment Problems
Yoko Uwate† , Yoshifumi Nishio† , Tetsushi Ueta‡ , Tohru Kawabe§ and Tohru Ikeguchi¶†

Dept. of Electrical and Electronics Engineering, Tokushima University
Email: {uwate,nishio}@ee.tokushima-u.ac.jp‡
Dept. of Information Science and Intelligent Systems, Tokushima University§
Institute of Information Sciences and Electronics, Tsukuba University¶
Dept. fo Information and Computer Sciences, Saitama University

1. Introduction
Combinatorial optimization problems can be solved
with the Hopfield Neural Network. 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 toavoid this critical problem, several people proposed
the method adding some kinds of noise 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
the chaos noise; short time correlations of the timesequence. Hasegawa et al. investigated solving abilitiesof the Hopfield NN with various surrogate noises, andthey concluded that the effects of the chaos sequence
for solving optimization problems can be replaced bystochastic noise with similar autocorrelation [3]. In order to make clear the reason why intermittency chaos isbetter than fully developed chaos, we have investigatedthe performance with the burst noise generated by theGilbert model [4] for TSP [5]-[7] and quadratic assignment problems (QAP) [6]-[8]. We confirmed that theburst noise gained similar performance to the intermittent chaos noise. We consider that one reason of thegood performance of the chaos noise can be explainedby the existence of the laminar part and the burst part.
However, we do not consider that ability of chaos noise
has been clarified completely.
In this study, we use various evaluation methods
to find outstanding ability of chaos noise shrouded inmystery. Control parameter α of the logistic map ischanged to generate various chaos noises. We chose
several problems from the benchmark site QAPLIB [9];-267-

“Nug12,” “Nug25” and “Nug30.” We carried out computer simulations for these problems and confirmed
various characteristics of chaos noises.

2. Solving QAP with Hopfield NN
Various methods are proposed for solving QAP
which is one of NP-hard combinatorial optimization
problems. QAP is expressed as follow: given two matrices, distance matrix C and flow matrix D, and findthe permutation p which corresponds to the minimum
value of the objective function f (p) in Eq. (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 andD, respectively, p(i) is the i-th element of vector p,and N is the size of the problem. There are many realapplications which are formulated by Eq. (1). One example of QAP is to find the arrangement of factories
to make a cost the minimum. The cost is given by thedistance between the cities and the flow of the products between the factories (Fig. 1). Other examples
are the placement of logical modules in an IC chip, thedistribution of medical services in a large hospital.
Because QAP is very difficult, it is almost impossible to solve the optimum solutions in larger problems.
The largest problem which is solved by deterministic
methods may be only 20 in recent study. Further, computation time is very 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 N -element QAP by the Hopfield NN, N ×N neurons are required and the following
energy function is defined to fire (i, j)-th neuron at thex1(t)Factory
Acity-cω1
ω2x2 (t)FactoryE

FactoryB.
.
.
.

city-acity-dωnβxn (t)FactoryCx(t+1)

f-1

FactoryDcity-bcity-ez

θFigure 1: QAP model.
Figure 2: A neuron model.
optimal position:
E=NN
X
X

wim;jn xim xjn +i,m=1 j,n=1

NX

3. Chaos Noises
θ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 thresholdof the (i, m)-th neuron are described by:½wim;jn = −2 A(1 − δmn )δij
¾Cij Dmn(3)+Bδmn (1 − δij ) +q
θim

=A+B

where A and B are positive constants, and δij is Kronecker’s delta. The states of N ×N neurons are unsynchronously updated due to the following difference
equation:
NXxim (t + 1) = g wim;jn xim (t)xjn (t)j,n=1(4)¶In this section, we describe chaos noise injected tothe Hopfield NN. The logistic map is used to generatechaos noise:ẑim (t + 1) = αẑim (t)(1 − ẑim (t)).

(6)

Varying parameter α, Eq. (6) behaves chaotically via aperiod-doubling cascade. When we inject chaos noise
to the Hopfield NN, we normalize ẑim by Eq. (7).
zim (t + 1) =ẑim (t) − z̄σz(7)Where z̄ is the average of ẑ(t), and σz is the standard
deviation of ẑ(t). Figure 3 shows an example of thetime series of the chaos noise.
1.5

10.50z(t)− θim + βzim (t)-0.5

where g is sigmoidal function defined as follows:g(x) =1³ x´1 + exp −ε-1(5)zim (t) is additional noise, and β limits amplitude of thenoise. Figure 2 shows a conceptual neuron model forthis NN.
Also, we use the method suggested by Sato etal. (1.1 in [10]) to decide firing of neurons.

-268--1.5-2
0200

400

600

800

1000
t

1200

1400

1600

Figure 3: Chaos noise. α=3.8000.

1800

2000

4. Simulated Results

4.5e+104e+10
3.5e+10
Depth_1

3e+10
2.5e+102e+101.5e+101e+105e+090
3.6

3.65

3.7

3.75

α1000

800

800

Frequency

1000

600

4002002{f (Pk ) − D∞ }400

06800 7000 7200 7400 7600 7800 8000 8200 8400 8600

Energy

-269-

1000

800

800

Frequency

Frequency(b) α = 3.7020.

1000

600

400

200

600

400

200

06800 7000 7200 7400 7600 7800 8000 8200 8400 8600

06800 7000 7200 7400 7600 7800 8000 8200 8400 8600

EnergyEnergy(d) α = 3.7920.

1000

1000

800

800

Frequency

Frequency(c) α = 3.7540.

600

400

600

400

20006800 7000 7200 7400 7600 7800 8000 8200 8400 8600

06800 7000 7200 7400 7600 7800 8000 8200 8400 8600

EnergyEnergy(e) α = 3.8960.

where D∞ is a constant which is large enough to include
the energies of all solutions, n is the number of theaccepted solutions and the energy f (Pk ) is calculated
by Eq. (1) using the permutation Pk corresponding to
the k-th solution.
The calculated result of Depth 1 is shown in Fig. 4.
The horizontal axis is α and the vertical axis isDepth 1. On the contrary to our expectation, the valueof Depth 1 around α = 3.70 is very large.

4Energy

(8)

k=0

3.95

200200nX

3.9600(a) α = 3.6820.

Until now, we have evaluated the performance ofthe Hopfield NN with chaos noise by using only theoptimal solution; time to find the optimal solution, frequency of finding the optimal solution during a given
time, and so on. However, when the Network can notfind the optimal solution and can find a lot of nearly
optimal solutions, such methods do not give a correct
evaluation of the Network. We consider that it is very
important for the Network to find a lot of nearly optimal solutions. In order to evaluate the ability, we propose an evaluation method Depth 1 which is defined
as

3.85

06800 7000 7200 7400 7600 7800 8000 8200 8400 8600

4.1. Depth 1

Depth 1 =3.8

Figure 4: Depth 1 for Nug30 (D∞ = 10000).

Frequency

The problem used here was chosen from the site
QAPLIB which collects the bench mark problems. We
carried out computer simulation for three problems;“Nug12,”“Nug25” and “Nug30.” In this article, weshow the result of “Nug30” only. The global minimumof this problem is known as 6124. The parameters ofthe Hopfield NN are fixed as A = 1.0, B = 1.0, q = 640and ε = 0.02 and the amplitude of the injected chaosnoise is fixed as β = 0.6. The number of updating theNetwork Nit is 10000.
At first, we explain how to accept solutions. TheHopfield NN with the chaos noise searches various solutions. However, the state of the Hopfield NN sometimes stays around a group of several solutions. We
consider that such a behavior is not useful to find theoptimal or nearly optimal solutions. So, we take theonly-different-solutions method. Namely, we take into
account the solutions which have not found ever.
Next, we propose two methods evaluating the solutions obtained by the Hopfield NN with the chaosnoise.

Figure 5:
Nug30.

(f) α = 3.9280.

Frequency distribution of solutions for

In order to make clear the reason of the large valuesof Depth 1 around α = 3.70, we examined frequency
distribution of the solutions for several α which getlarge values of Depth 1. The results of the frequency
distribution are shown in Fig. 5. We can see that alot of solutions are found for (a) and (b). However,the distribution is similar to that obtained by random
search. On the other hand, for (c), (d), (e) and (f),the averages of the accepted solutions are better thanthose of (a) and (b). Although finding a lot of solutions is important, solutions with energies more than
the average obtained by random search should not betaken into account for the evaluation.
4.2. Depth 2
We propose another evaluation method to obtainchaos noises with better performance for finding a lotof GOOD solutions. Depth 2 is defined as follows:
 nX
2


{f (Pk ) − Dth }Depth 2 =(f (Pk ) ≤ Dth )

k=0nX
2


−{f (Pk ) − Dth }(f (Pk ) > Dth )k=0(9)In order to eliminate the effect of bad solutions, we not
only set up a threshold but give a penalty according tothe energy.
The calculated result of Depth 2 is shown in Fig. 6.
Let us note around α = 3.70. We can say that Depth 2evaluates the accepted solutions as we expect. Namely,
Depth 2 is a good method to evaluate the solutions
solved by the Hopfield NN with chaos noise.
6e+08
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αFigure 6: Depth 2 for Nug30 (Dth = 7800).
From Fig. 6 we found several characteristics of chaosnoises. Namely, as we have reported in our previous studies, intermittency chaos near the three-periodic
window (around α = 3.81) gains a good performance.
Further, as several researchers have pointed out,
fully-developed chaos near α = 4.00 can not gain a-270-

good performance. We also found that chaos noises
around α = 3.66, 3.76 and 3.93 gains good performances. We consider that the reason of the good performances is not the same for all of these regions.
5. Conclusions
In this study, we have researched the characteristicof the chaos noise when control parameter α is changed.
We proposed the two methods to evaluate the performance of the chaos noises. As a result, we foundseveral characteristics of chaos noises. In the future,
we make clear the reason of the good performances ofchaos noises obtained for various α.
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.
[2] Y. Hayakawa and Y. Sawada, “Effects of Chaotic Noiseon the Performance of a Neural Network Model,” IEICE Tech. Rep., vol. NLP94-39, pp. 47-52, 1994 (inJapanese).
[3] M. Hasegawa, T. Ikeguchi, T. Matozaki and K. Aihara,“An Analysis on Adding Effects of Nonlinear Dynamicsfor 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 Noise and Burst Noise on Solving Abilityof Hopfield Neural Network,” Proc. of NOLTA’97, vol.
1, pp. 409-412, 1997.
[6] S. Baba, Y. Nishio, T. Kawabe and T. Ueta, “Hopfield
Neural Network with Various Burst Noise for TSP,”
Proc. of NOLTA’99, vol. 1, pp. 13-16, 1999.
[7] S. Baba, N. Urushihara, Y. Nishio, T. Kawabe and T.
Ueta, “Solving Ability of the Hopfield NN with Burst
Noise,” Proc. of AFSS’00, vol. 2, pp. 914-917, 2000.
[8] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T.
Ikeguchi, “Solving Ability of Hopfield Neural Networkwith Chaotic Noise and Burst Noise for Quadratic Assignment Problem,” Proc. ISCAS’02, vol. 3, pp. 465468, May 2002.
[9] R. E. Berkard, S. E. Karisch and F. Rendl, “QAPLIB– A Quadratic Assignment Problem Library,”
http://www.opt.math.tu-graz.ac.at/qaplib[10] K. Sato, T. Ikeguchi, M. Hasegawa and K. Aihara, “AnOptimization Method for Quadratic Assignment Problems by Chaotic Dynamics and its Characterization by
Lyapunov Dimensions,” IEICE Tech. Rep., vol. NLP6413, pp. 13-20, 2001 (in Japanese).