2004 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'04)
Hawaii, USA, Mar. 5-7, 2004.

On Update Methods of Chaos Neural Network for TSPs
Isao TANAKA† , Yoshifumi NISHIO† and Mikio HASEGAWA‡† Dept. of Electrical and Electronic Eng.,
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Email: {isao130, nishio}@ee.toushima-u.ac.jp

Abstract
In this study, we investigate two different update methods ofthe chaos neural network in order to approach to finding theglobal minimum solution of TSPs.
By computer simulations for various TSPs, we confirm thatthe method to change the weights connecting the firing neurons can successfully restrain the regeneration of the onceappeared-solutions.

‡Wireless Communications Division
Communications Research Laboratory
3-4 Hikarino-Oka, Yokosuka, Japan
Email: mikio@crl.go.jp

required and the following energy function is define to fire(i, j) neuron at the optimal position:NNA X X2E =(xi,j (t) − 1) 
2 i=1 j=1
ÃN!
NBX X
2+(xi,j (t) − 1)
2 j=1 i=1N+

1. IntroductionNND XXXdi,j xi,k (t)(xi,k (t) + xj,k−1 (t))(1)2 i=1 j=1
k=1

Combinatorial optimization problems can be solved with
the Hopfield neural network [1]. 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 network state is often
trapped into a local minimum and do not reach the global
minimum. In order to avoid this critical problem, chaos neural networks have been applied to various optimization problems successfully.
Several researchers have also proposed the methods tosolve TSPs by using the Hopfield neural networks. However,the Hopfield neural network can find only one solution among
numerous possible solutions.
In this study, we try to find the global minimum solutionsof TSPs by using neural network. The chaos neural network
could find several solutions because of its chaotic dynamicalmotion. However, the network state visits the once-appeared
solution quite often. We investigate three different update
methods of the chaos neural network in order to restrain theregeneration of the once-appeared-solutions. By computer
simulations for various TSPs, we confirm that the method tochange the weights connecting the firing neurons can successfully find many different solutions of TSPs.

The neurons are coupled each other with the synaptic connection weight. Suppose that the weight between (k, l)-th neuron
and the (i, j)-th neuron are described by:
ωi,j,k,l=−Aδi,k (1 − δj,l ) − Bδj,l (1 − δi,k )−Ddi,k (δl,j+1 + δl,j−1 )(2)where A,B and D are positive constant, and δr,s is the twodimentional Kronecker delta, which is defined as½
1, if r = s
δr,s =(3)0, if r 6= s.
In order to find different solutions, as many as possible, weapply the chaos neural network to the TSPs.
The equation of the chaos neural network is given asxi,j (t + 1)

=kxi,j (t) +N X
NX

ωi,j,k,l f (xk,l (t))

k=1 l=1−αf (xi,j (t)) + θi,j (1 − k)(4)where f (x) is a sigmoid function
f (x) =

2. TSPs and Chaos Neural Network1¡ ¢1 + exp − xε(5)The TSPs consists of finding the shortest closed path by and k is time attenuation constant and α controls nonlinearity.
which every city out of a set of N cities is visited once and Also, we use the method suggested by Sato et al. (1.1 in [4])only once. For solving N -city TSPs, N × N neurons are to decide firing of neurons.

- 285 -

3. Two Proposed Methods
Next, the simulated results for ulysses22 are shown inThe chaos neural network can find several solutions as it Tab. 3.
is because of its chaotic dynamical motion. However, thenetwork state visits the once-appeared solution quite often.
Table2 Result of ulysses22 (∆W = 0.001 and ∆θ = 0.0009).
We propose two different update methods of the chaos neuNormal Method 1 Method 2
ral network in order to restrain the regeneration of the onceRG
95.38
87.14
92.89
appeared-solutions.
Rave
99.16
94.66
98.25
3.1. Method 1
From these tables, we can say that the proposed two methIn the Method 1, the weights connecting the firing neurons ods can find smaller solutions than the ordinary chaos neuralare reduced to restain the regeneration of the firing pattern networks, especially for the Method1.
after every updating. Namely, we choose one of the firing
And Fig. 1 and 2 show the update of the network state byneurons. A constant value “∆W ” is subtracted from the con- the case of same initial value.
necting weights from this neuron to the other firing neurons.
From these figures, we can say that the proposed two methMoreover, in order to maintain the activity of the network, ods can extend to over the update of the network state.
“∆W/{N (N + 1)}” is added to the rest of the weights. This
procedure is applied to the all firing neurons.
5. Conclusions
3.2. Method 2
In the Method 2, the threshold of the firing neurons are
reduced to restain the regeneration of the firing pattern after
every updating. A constant value “∆θ” is subtracted fromthe thresholds of the all firing neurons. Moreover, in order tomaintain the activity of the network, “∆θ/(N − 1)” is added
to the non-firing neurons.
4. Simulated results
Computer simulations of TSPs are performed for the casesof “ulysses16” and “ulysses22” by TSPLIB of a benchmark
site. The number of the update of the network state is fixed as
10,000 and the minimum solution of the obtained solutions isevaluated. This trial is iterated 10 times for different initialconditions. and the average of the obtained minimum solutions is “Rave ”, the shortest is “RG ”. The simulated results
using the two proposed methods are compared with the results obtained from the normal chaos neural network. Moreover, for character of TSPs, proposed Methods are applied
when the obtained solutions is larger than a constant value“P ”.
The parameter α = 1.65(ulysses16), 1.80(ulysses22),
K = 0.3, θ = 3.0, A, B = 1.0, D = 2.0 and ε = 0.15.
We carried out computer simulations for various values of theparameters of the ∆W , ∆θ and P . The following results are
the best we obtained.
Table 2 shows the simulated results for ulysses16.
Table.1 Result of ulysses16 (∆W = 0.0001 and ∆θ = 0.001).

RG
Rave

Normal
78.15
84.15

Method 175.83
80.89

Method 275.91
79.57

In this study, we have tried to find the global minimum
solutions of the TSPs by using the chaos neural network.
We investigated two different update methods of the chaos
neural network in order to restrain the regeneration of theonce-appeared-solutions. By computer simulations for various TSPs, we confirm that the method to change the weights
connecting the firing neurons can successfully find different
smaller solutions of TSPs than the normal chaos neural network.
Finding new methods better than the two methods is ourimportant future research.
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] K. Shimoji, T. Kawabe, T. Ueta and Y. Nishio,“On the Properties of Hopfield Neural Networks withChaotic Noise for Traveling Salesman Problem,” Proc.
of NOLTA’99, vol. 1, pp. 9-12, 1999.
[3] 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.
[4] 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).

- 286 -200

240

220

180200160

Distance

Distance

180140120160

140
100
12080

100

60

80
01000

2000

3000

4000

5000

6000

7000

8000

9000

10000

01000

2000

3000

4000

t

5000

6000

7000

8000

9000

10000

8000

9000

10000t(a) Chaos Neural Network.

(a) Chaos Neural Network.

200240220

180200160

Distance

Distance

180140120160

140
100
12080

100608001000

2000

3000

4000

5000

6000

7000

8000

9000

10000

01000

2000

3000

4000t

5000

6000

7000

t

(b) Method 1. 4W = 0.0001 and P = 100.

(b) Method 1. 4W = 0.001 and P = 130.

200

240

220

180

200160Distance

Distance

180140120160

140
10012080100

60

80
01000

2000

3000

4000

5000

6000

7000

8000

9000

10000

0t

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

t

(c) Method 2. 4θ = 0.001 and P = 100.

(c) Method 2. 4θ = 0.0009 and P = 130.

Figure 1: Update of the network state (ulysses16).

Figure 2: Update of the network state (ulysses22).

- 287 -

- 288 -