2011 International Workshop on Nonlinear Circuits,Communication and Signal Processing
NCSP'11, Tianjin, China, March 1-3, 2011

Hopfield Neural Network with Chaotic Pulse Wave
Solving Traveling Salesman Problems
Kana KURATA† , Yoko UWATE† and Yoshifumi NISHIO††Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470, Fax:+81-88-656-7471
Email: {kana, uwate, nishio}@ee.tokushima-u.ac.jp

Abstract

2. Hofield NN solving TSP

In this study, in order to investigate the effect of chaotic oscillations of real biological signals on information processing
ability, we investigate the performance of the Hopfield neural networks solving traveling salesman problems when thesampled data of chaotic pulse waves obtained from real biological experiments are poured into the neurons. Computer
simulated results show that the performance of the chaotic
pulse wave is better than the case of random noise.

In this study, we choose a problem “bayg29” fromTSPLIB [10]. The map points of “bayg29” is shown in Fig. 1.
The optimum solution is known as 9.074e+03.
For solving N -element TSP by Hopfield NN, N × N neurons are required and the following energy function is defined
to fire (i, j)th neuron at the optimal position:
E=NNX
X
i,m=1 j,n=1

ωim;jn xim xjn + wij

NXθim xim .

(1)

i,m=1

The neurons are coupled each other with the synaptic connection weight. Suppose that the weight between (i, m)th neuron
The pulse wave is a change of the volume caused by the and (j, n)th neuron and the threshold of the (i, m)th neuron
blood current and is measured from the surface of various are described by:parts of the body. Biological signals including the pulse
ωim;jn = Aδij (1 − δmn ) + Bδmn (1 − δij )wave, the brain wave, and the heart beat wave are said to(2)− C − Ddij (δj,i+1 + δj,i−1 ),exhibit chaotic behaviors [1][2]. Some reports suggest that
healthy biological systems possess chaotic features and periodic states indicate sick or fatal conditions.
θim = A + B,
(3)
On the other hand, in the optimization problems, many algorithms pouring chaotic oscillations to the Neural Networks where A and B are positive constants and δij is Kronecker’s(NN) have been proposed in order to avoid the local minimum delta. The state of N × N neurons are asynchronously upproblems [3]. We have also investigated various methods to dated due to the following difference equation:
exploit chaotic features to enhance the ability of the neuralNX
networks [4]-[9]. However, in the past studies, only mathexi (t + 1) = f ωim;jn xjm (t)matical abstract models, e.g. the logistic map and the cubicj,n=1
map, are considered as chaotic source.
! (4)In this study, in order to investigate the effect of chaotic− θim (t) + βzim (t)oscillations of real biological signals, we use chaotic pulse
waves obtained by real biological experiments and pour thesampled chaotic data to the Hopfield NN solving Traveling where f is sigmoidal function defined as follows:
Salesman Problems (TSP). By computer simulations, we in1
f (a) =,(5)vestigate the effect of the chaotic pulse wave. We also com1 + e−apare the results with the case of random noise. Further, thisstudy may be a first step to clarify the relationship between zim is additional noise, namely chaotic pulse wave in thisthe performance of the neural networks and the stress added study. Figure 2 shows a conceptual neuron model for thisNN.
to the subject.
1. Introduction- 296 -

2700

Relative voltage

2500
2300
2100
1900
1700
1500
11001

2001

3001

4001

5001

Time (s)Figure 3: Example of pulse waves.

Figure 1: Example of TSP.

Figure 4: Example of reconstructed attractors of pulse wave.

Figure 2: A neuron model.

punov exponents λi as

3. Chaotic pulse wave

N −1

We obtained pulse waves from real biological experiments.
The subjects were 4 healthy male student (21 to 22 years old).
We gave them the body and mental stress and measured theirpulse waves. The pulse waves measured at 8pm are assumed
to be their reference data. After the four hours, the pulse
waves are measured five times every two hours; 0am, 2am,4am, 6am, and 8am. The sampling frequency of the data is
200 Hz and the measurement time length is 5 minutes. It is
not allowed for the subjects to sleep during the night, because
we keep to give the stress to the subjects.
An example of the time waveforms of the pulse wave andthe corresponding reconstructed attractor are shown in Fig. 3and Fig. 4, respectively. The attractor is reconstructed basedon the Takens’ theorem [11] with the following parameters:
embedding dimension = 4, super-sphere size = 0.08, data
points = 60000 and calculation points = 36000.
By Sano-Sawada method [12][13], we calculate the Lya-1 X
ln|e0i (t)|N →∞ N
t=1λi = lim(6)

where e0 is the Lyapunov spectrum. At least, if the value of
λ1 is positive, the orbital instability exists that is the featureof chaos. The Lyapunov exponent of the attractor in Fig. 4 iscalculated as 4.5032 and hence we can say the pulse wave inFig. 3 is chaotic. Similar can be said for other subjects’ pulsewaves.
Further, we calculated the Lyapunov exponent with sliding
the time interval for calculations. The Lyapunov exponent of
the reference data changes like Fig. 5.
The Lyapunov exponents of all 4 subjects are summarizedin Fig. 6.
In order to pour this chaotic pulse wave to the Hopfield NN,
we normalize the wave and use only one of every 15 samples.
Further, in this study, we fix the amplitude parameter β = 0.7.

- 297 -

2350010922500
Sum Length of TSP

Lyapunov exponent

87
6542150020500

32119500

11

Lyapunov

Time (s)Random

3A

4B

C

5

6
Trial times

D

Figure 7: Simulated results 1.

Figure 5: Time evolution of Lyapunov exponents with sliding
time interval.

Table 1: Simulated results 2.

9.50008.5000

Lyapunov exponent

2NoiseABCD

7.50006.50005.50004.5000

Average
2.2025e+04
2.1068e+04
2.0853e+04
2.0767e+04
2.0920e+04

Error rate
143%
132%
130%
129%
131%

3.50002.500012345

5. Conclusions

6Trial times

We have investigated the effect of the chaotic pulse wave
poured in the Hopfield NN solving TSP. By carrying out comFigure 6: Change of Lyapunov exponents of 4 subjects with puter simulations for the problem, we have confirmed thatstress.
the chaotic pulse wave had an effect to avoid local minimumproblems and achieved a performance to find good solutionsof TSP.
4. Simulation results
In this study, we could not obtain an enough results to conWe carry out computer simulations for 10 times of 100 it- clude on the relationship between the performance of the neuerations and recorded the minimum and the average values ral networks and the stress added to the subject. That is ourof the tour length. The simulated results of 4 subjects (A, important future research topic.
B, C, D) are summarized in Fig. 7. We compared the resultswith the result of random noise case. We use the error rate as
References
follows;AB

CD(7)[1] C.D. Wagner and P.B. Persson, “Chaos in cardiovascular system: an update,” Cardiovascular Research,vol.40, no.2, pp.257–264, Nov. 1998.

The results are summarized in Table 1. From this table, we
can confirm that the chaotic pulse wave gains better performance than the random noise.

[2] A. Das, P. Das and A.B. Roy, “Applicability of Lyapunov exponent in EEG data analysis,” Complexity International, vol.9, pp.1–8, 2002.

Error rate[%]=(obtained solution) − (optimal solution)(optimal solution)- 298 -[3] Y. Hayakawa and Y. Sawada, “Effects of chaotic noiseon the performance of a neural network model for optimization problems,” Physical Review E, vol.51, no.4,
pp.2693–2696, 1995.

[8] Y. Tada, Y. Uwate and Y. Nishio, “Solving ability ofHopfield neural network with scale-rule noise for QAP,”
Proceedings of IEEE International Symposium on Circuits and Systems, pp.105–108, May 2008.

[4] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe andT. Ikeguchi, “Performance of chaos and burst noises
injected to the Hopfield NN for quadratic assignment problems,” IEICE Transactions on Fundamentals,
vol.E87-A, no.4, pp.937–943, Apr. 2004.

[9] S. Aono, Y. Nishio and D. He, “Solving ability ofcoupled map lattice with 2-opt algorithm for travelingsalesman problems,” RISP Journal of Signal Processing,vol.13, no.4, pp.303–306, Jul. 2009.

[10] “TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/[5] Y. Uwate and Y. Nishio, “Search of many good solutions
comopt/software/TSPLIB95/of QAP by connected Hopfield NNs with intermittency[11] F. Takens, “Detecting strange attractors in turbulence,”chaos noise,” RISP Journal of Signal Processing, vol.8,
Lecture Notes in Mathematics, No.898: Dynamical Sysno.6, pp.439–447, Nov. 2004.
tems and Turbulence (ed. by Rand, D.A and Young, L.s.),[6] Y. Tada, Y. Uwate and Y. Nishio, “Performance ofSpringer Verlag, Berlin, pp.366–381, 1981.
chaotic switching noise injected to Hopfield NN for[12] M. Sano and Y. Sawada, “Measurement of the Lyapunov
quadratic assignment problem,” Proceedings of IEEE
spectrum from a chaotic time series,” Physical Review
International Symposium on Circuits and Systems,Letters, pp.1082–1085, 1985.
pp.5519–5522, May 2006.
[7] Y. Tada, Y. Uwate and Y. Nishio, “Effective search withhopping chaos for Hopfield neural networks solving
QAP,” Proceedings of IEEE International Symposium
on Circuits and Systems, pp.1783–1786, May 2007.

[13] T. Ikeguchi, K. Aihara, S. Itoh and T. Utsunomia,“An analysis on Lyapunov spectrum of electroencephalographic (EEG) potentials,” Transactions of IEICE, vol.E73, no.6, pp.842–847, Jun. 1990.

- 299 -