平成22年度電気関係学会四国支部連合大会

336

18-37

Hopfield NN with Chaotic Pulse Wave
Solving Traveling Salesman Problems
Kana Kurata

Yoko Uwate
Yoshifumi Nishio(Tokushima University)

1. Introduction

Pulse Wave
2500

2300

εｔｔ

The Traveling Salesman Problems (TSP) is one of the applications of the Hopﬁeld Neural Networks (Hopﬁeld NN). However, the Hopﬁeld NN often stops at local minimum and does
not give a good solution. Many algorithms pouring chaotic
oscillations to the networks have been proposed in order toavoid the local minimum problems [1].
In this study, in order to investigate the eﬀect of chaotic oscillations of real biological signals, we use chaotic pulse waves
obtained by real biological experiments. We compare the performances of the Hopﬁeld NN solving TSP with random noiseand chaotic pulse waves.

2100

1900

1700
0.0

2.0

4.0

6.0

8.0

10.0

12.0

14.0

16.0

18.0

20.0

ｔime (s)Figure 2: Pulse Wave.

Attractor CI(150-180s) 2D-4

2. Hopfield NN solving TSP

2500

2400

2300

2200

2100

2000

1900

1800

1700
1700

1800

1900

2000

2100

2200

2300

2400

2500

Figure 3: Attractor of Pulse Wave.
In order to pour this chaotic pulse wave to the Hopﬁeld NN,
we normalize the wave and use only one of every 30 samples.
Further, in this study, we ﬁx the amplitude parameter β=0.7.

Figure 1: An example of TSP.
In this study, we choose a problem “bayg29” fromTSPLIB [2]. The map points of “bayg29” is shown in Fig. 1.
For solving N -element TSP by Hopﬁeld NN, N ×N neurons
are required and the following energy function is deﬁned toﬁre (i, j)th neuron at the optimal position:E=NN∑∑ωim;jn xim xjn + wij

i,m=1 j,n=1

N∑θim xim

Table 1: Simulated results.

The state of N × N neurons are unsynchronously updated
due to the following diﬀerence equation:xi (t + 1)=f)=minimum
averagepulse wave
2.0398e+04
2.6428e+04

random noise
2.2464e+04
2.6652e+04

ωim;jn xjm (t) − θim (t) + βzim (2)5. Conclusions

j,n=1

f (a)

We carry out computer simulations for 10 times of 1000
iterations and recorded the minimum and the average values.
The simulated results are summarized in Table 1. From thistable, we can conﬁrm that the chaotic pulse wave gains better
performance than the random noise.

(1)i,m=1( N∑

4. Simulation results

1
1 + e−a(3)where z is random noise or chaotic pulse wave, the function fis the sigmoidal output function, and β controls the amplitudeof the additional random noise or chaotic pulse wave.

3. Chaotic pulse wave
We obtained pulse waves from real biological experiments.
The sampling frequency of the data is 200Hz and measurement time is 5 minutes. The time waveform of the pulse wave
and the corresponding reconstructed attractor are shown inFig. 2 and Fig. 3, respectively. We calculated the averaged
Lyapunov exponent as 4.5032 and hence we can say this pulse
wave is chaotic.

We have investigated the eﬀect of chaotic pulse wave pouredin the Hopﬁeld NN solving TSP. By carrying out computer
simulations for various problems, we have conﬁrmed that thechaotic pulse wave has an eﬀect to avoid local minimum problems and achieved a performance to ﬁnd good solutions of theTSP.
References[1]Y. Hayakawa and Y. Sawada, “Eﬀects of chaotic noise on
the performance of a neural network model for optimization
problems,” Physical Review E, vol.51, no.4, pp.2693-2696,
1995.
[2]“TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/