On the Properties of Hop eld Neural Networks with Chaotic
Noise for Traveling Salesman Problem

Katsuya Shimoji3, Tohru Kawabey, Tetsushi Uetaz and Yoshifumi Nishiox
3Master's Program in Science and Engineering, University of Tsukuba Tsukuba 305-8573 Japanshimoji@fmslab.is.tsukuba.ac.jpyInstitute of Information Sciences and Electronics, University of Tsukuba, Tsukuba 305-8573 Japanzkawabe@is.tsukuba.ac.jp

Department of Information Sciences and Intelligent Systems, Tokushima University, Tokushima 770-8506 Japantetsushi@is.tokushima-u.ac.jp

xDepartment of Electrical and Electronic Engineering, Tokushima University, Tokushima 770-8506 Japannishio@ee.tokushima-u.ac.jp

Abstract| In this paper, we investigate generalsolving abilities of the Hop eld neural network withchaotic noise injected into each neuron for several
kinds of the traveling salesman problems. Especially,
based on several numerical simulation studies, we inspect which number of periodic intermittency chaotic
noise for Hop eld neural network is most e ective inthe solving performance against the variety of TSP
problem types.

problem types, for example, di erence of number ofcities or reshuing the placement of cities. We use twoperformance criterion for this object, one is whether
the global minimum is detected or not ( the detecting
rate of global minimum per one trial ) and the otheris how many local minima is detected ( the average
number of detected local minima per one trial ).

I. Introduction

In this paper, we use the original H-NN for comparison
with former studies. For solving N -city TSP, N × N
neurons are required and the following energy function
is de ned to re (i; j ) neuron at the optimal position:
01NN
A X @XE =(x (t) 0 1)2 A
2 i=1 j =1 ij!
NN
BX X
2(x (t) 0 1)
+2 j =1 i=1 ij

Solving the traveling salesman problem (abbr.
TSP)[1], a kind of combinatorial optimization problems, is an important application of Hop eld neuralnetwork (abbr. H-NN)[2]. Generally, there are many
local minima in TSP[1] and the state in the H-NN
is often trapped into these local minima. It remains,therefore, an unsettled questions how to escape easily from them and reach the global minimum. Aboutthese points, recently, many researchers suggested thatH-NN with chaotic sequences is e ective.
Hayakawa et al.[4] mentioned that chaotic noise
is more e ective than stochastic one, and they also
pointed out the intermittency chaos near the periodic3 window of the logistic map gains the best performance for a kind of TSP. On the other hand, Ueta etal.[6] and Okahisa et al. [7]. concluded in their papers that the e ective intermittency chaotic noise is
not only 3-window but also periodic-5 and 7 for samekind of TSP.
In this paper, hence, we investigate general solving abilities of the H-NN with chaotic noise injected
into each neuron for several kinds of TSPs. Especially,
based on several numerical simulation studies, we inspect which number of periodic intermittency chaotic
noise for Hop eld neural network is most e ective inthe solving performance against the variety of TSP

II. Hop eld Neural Network for TSP+N X
N XNDXd x (t)(xi k+1 (t) + xj k01 (t))
2 i=1 j =1 k=1 ij ik(1)The neurons are coupled each other with the synaptic connection weight. Suppose that the weight between (j; l)-th neuron and the threshold of the (i; k )-thneuron are described by:
wikjl =0Afij (1 0 kl ) + kl(1 0 ij )g0dij (l k+1 + l k01 )i;k = A + B(2)where A and B are positive constant, and i;j is Kronecker's delta. The states of N 2 N neurons are up-

dated due to the following di erence equation:
01N XNX
xik (t + 1) = f @!ikjl xjl (t) + ik + zik (t)A

=1 l=1z(t)j(3)
where f is sigmoidal function de ned as follows:x11 + tanh
(4)f (x) =
2"where " = 0:5, zik (t) is an additional noise, and limits amplitude of the noise. Figure 1 shows a conceptual
neuron model for this H-NN.

1.5
10.5
0
-0.5
-1
-1.5
-2

200(5)x^ik (t) =

1; if xij (y )  x~(t)0; otherwize(6)

where x^ik (t) is new state of xik (t), and where xik (t) isthe (i; k )th neuron's average value of output of fromt 0  to t. And where x~(t) is N -th value in the xij (t)of N 2 N neurons. And we set  = N as stated in [5].

1"5-city"

0.8

0.6

0.6
y0.8

"10-city"

0.4

0.4

0.2

0.2

000.2

0.4

x

0.6

10.8

0

1

00.2

0.4

x0.6

1

"15-city"

0.8

0.8

0.6

0.6

0.8

1

"20-city"

0.4

0.4

0.2

0.2

00

0.2

0.4

x

0.6

0.8

1

0

0

0.2

0.4

x

0.6

0.8

1Figure 3: 5-city, 10-city, 15-city and 20-city TSPs

III. H-NN with Chaotic Noise
For solving TSP by H-NN with noise, we generate atime series by the logistic map:zik (t + 1) = azik (t)(1 0 zik (t))

1000

yt
1 Xx (l) l=t0 +1 ik

800

We also simulate H-NN with chaotic time series noisefor several kinds of TSPs. Figure 3 shows some type ofTSPs. The initial values of all neurons and noises areselected in randam, and the values of A, B, D (parameters of energy function) and (amplitude of thenoise)
are set as stated in [4][5]. Table 1 shows these value.

yWe also use the method of how to distinct each neurons re or not refered from [4][7]. In this method, thestate of a neuron xik (t) at the time t is described by:

600IV. Simulations

yFigure 1: A neuron modelt

Figure 2: period-3 intermittency chaos

1xik (t) =400(7)where a is a bifurcating parameter of the logistic map.
Hayakawa[4] shows the period-3 intermittent chaosof the logistic map is more e ective than other chaotic
noise. Figure 2 shows a time series of period-3 intermittent chaos of the logistic map in the case ofa = 3:8250;  = 0:4114, where  is Lyapunov index.

Table 1: The value of parameters
City number
The value of parameters
5
A=1.0, B=1.0, D= 1.0, = 0:45
10
A=1.1, B=1.1, D= 4.0, = 0:47
15
A=1.1, B=1.1, D=16.9, = 0:50
20
A=1.0, B=1.0, D=25.0, = 0:45

100

100

"5-city""10-city"

60

60%

80%

80

"15-city""20-city"

40

40

20

200
3.65

3.7

3.75

a3.8

3.85

3.9

Figure 4: The detecting rate of global minimum(5, 10-city)

03.65

3.7

3.75

a3.8

"5-city""10-city"14121210103.9

Figure 5: The detecting rate of global minimum(15, 20-city)
1416

3.85

"15-city""20-city"

88664
4220
3.65

3.7

3.75

a3.8

3.85

3.9

Figure 6: The average number of detected local
minima (5, 10-city)
Hayakawa[4] use how long the state of NN stays in
the global minimum per one trial as performance criterion. But, generally, the golobal minimum of TSP
is not known. We use, therefore, two performance criterion, one is whether the global minimum is detectedor not ( the detecting rate of global minimum per onetrial ) and the other is how many local minima is detected ( the average number of detected local minima
per one trial ). And one trial in simulations is de ned
as follows: Fixed values of parameters (A, B , D, ) as
shown in table 1.

 Select the initial values of all neurons in randam.
 Repeat 1000 times of transfer of every neurons'
input-output signal.

03.65

3.7

3.75

a3.8

3.85

3.9

Figure 7: The average number of detected local
minima (15, 20-city)

A. Simulation results

Figures 4 and 5 show the detecting rate of global minimum per one trial, and gures 6 and 7 show the average number of detected local minima per one trial.
From these results, we can con rm that not only 3window (a = 3:8250) but also other chaotic noises aree ective except if the noise is stable periodic sequence.
And these results roughly go for other kinds of TSPs
that is not shown in gure 3, too. Especially, we canobtain very stable results with the intermittent chaos.

B. The parformance of the intermittent chaos

Table 2 shows the detecting rate of global minimum
and the average number of detected local minima ofperiodic-3,5,7 intermittent chaos. From this table,

Table 2: The performance of the intermittent chaos

City Type of intermittent Lyapunov The detecting rate of The average number of
numberchaos
index global minimum(%) detected local minima
period-7( = 3 7001) 0.3576
100
11.6
5 period-5( = 3 7380) 0.2951
100
11.7
period-3( = 3 8250) 0.4114
100
11.8
period-7( = 3 7001) 0.3576
100
7.5
10 period-5( = 3 7380) 0.2951
100
8.8
period-3( = 3 8250) 0.4114
100
13.1
period-7( = 3 7001) 0.3576
49
5.2
15 period-5( = 3 7380) 0.2951
43
5.9
period-3( = 3 8250) 0.4114
41
4.8
period-7( = 3 7001) 0.3576
100
9.2
20 period-5( = 3 7380) 0.2951
98
9.9
period-3( = 3 8250) 0.4114
96
13.1
a:

a:

a:

a:

a:

a:

a:

a:

a:

a:

a:

a:

References
these noises almost mark 100% in the detecting rateof global minimum, and get more number of detected
local minima than other chaotic noise. So we can concluded that periodic-7 intermittent chaos is the moste ective in the detecting rate of global minimum, andperiodic-3 intermittent chaos is the most e ective in
the average number of detected local minima.

V. Conclusion
We investigate the general solving abilities of the HNN with chaotic noise for several kinds of TSPs. And
we con rm that the periodic-7 intermittency chaotic
noise is most e ective in the solving performance
criterion for searching the global minimum and theperiodic-3 intermittency chaotic noise is most e ective in the solving performance criterion for the detecting rate of local minima. Further more, we also conrm that these periodic chaotic noises have robustness
property against the variety of TSP problem types andthat the periodic intermittency chaotic noise is one of
the most suitable chaotic noise for H-NN as solving
method for TSP.

[1] K. Iwano, Recent Topics aroud the Traveling
Salesman Problem, J. IECIE, Vol.78, No.10,
pp.1045-1047, 1995 (in Japanese).
[2] J. J. Hop eld, Neurons with Graded Response
Have Collective Computational Properties likeThose of Two-State Neurons, Proc. Natl. Acad.
Sci. USA, Vol.81, pp.3088-3092, 1984.
[3] T.Yamada and K.Aihara, Chaotic Neural Network and Optimization Problems: Complex
Computational Dynamics, In Proc. NOLTA '94,
pp.161-164, 1994.
[4] M. Hayakawa and Y. Sawada, E ects of theChaotic Noise on the Performance of a Neural Network Model, Technical report of IEICE,NLP94-39, pp.47-52, 1994 (in Japanese).
[5] M.Hasegawa, T.Ikeguti, T.Matozaki, K.Aihara,
An Analysis on Adding E ects of Nonlinear Dynamics for Combinatorial Optimization, IEICE
Trans. Fundamentals, Vol.E80-A, No.1, 1997
[6] Ueta, Y. Nishio and T. Kawabe, Solving Abilitiesof the Hop eld Neural Networks with Burst Noise,
Proc. NOLTA'97, pp.409-412, 1997.
[7] E. Okahisa, T. Ueta, Y. Nishio and T. Kawabe,
Investigation of Solving Abilities of Neural Network Injected with Chaotic Noise for Combinational Optimization Problems, Technical reportof IEICE, NLP98-38, pp.1-8, 1998 (in Japanese).