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

Effect of Chaos Noise for Tabu Search Neural Network with 2-Opt for TSPs
Shuichi Aono† , Yoshifumi Nishio† and Mikio Hasegawa∗†

Department of Electrical and Electronics Engineering
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470, Fax:+81-88-656-7471
Email: {aoichi, nishio}@ee.tokushima-u.ac.jp∗Communication Research Laboratory

1. Introduction

In order to realize this tabu search on a neural network, aequations with a synchronous is given as follows:

Although it would be possible to solve combinatorial optimization problems with a huge number of elements, if wehave infinite long time, it does not make any sense for practical problems. Realistically, obtaining nearly optimal solutions as quickly as possible is much more important. Atechnique using the tabu search neural network with 2-opt isvery powerful tool to find good solutions within limited time.
Moreover, the technique is extended to the neural networkwith chaotic dynamics to avoid the local minimum problems[1][2].
In this research, we investigate the effect of chaos noise
added to the tabu search neural network with 2-opt for TSPs.
By carying out computer simulations for various problems,
we confirm that the chaos noise has a good effect to avoid
local minimum problems and achieves a good performance
to find good solutions of the TSPs as well as the tabu searchneural network with chaotic dynamincs.
2. Tabu search neural network based on paths [2]ξij (t + 1) = β(Do (t) − Dij (t))ζij (t + 1) = −αs−1Xkrd xij (t − d)

(1)
(2)

d=0

xij (t + 1) = {ξij (t + 1) + ζa(i)a(j) (t + 1)
+ ζij (t + 1) + γzij (t + 1)}(3)

where Do (t) and Dij (t) are the length of the tour at time t andthat with the 2-opt exchange which links cities i and j, β, thescaling parameter of the gain effect, kr , the decay parameterof the tabu effect, α, the scaling parameter of the tabu effect,xij (t), the output of the (i, j)th neuron at time t, and ξij (t)and ζij (t) are the internal states of the (i, j)th neuron at time
t corresponding to the gain effect and the tabu effect of thepath between i and j, respectively. And zij (t) is a chaotic
noise to pour in at time t.
If the summation of internal states which expressed Eq.
(3), is the largest in all neurons, this (i, j)th neuron fires
and the path between cities i and j is connected by the 2opt exchange. For memorizing the connection of this path,xij (t + 1) is set to 1, and the outputs of all other neurons
xkl (t + 1), (k, l) 6= (i, j) and (k, l) 6= (a(i), a(j)) are set to0.

We utilize the 2-opt method for updating solutions of theTSP. As shown in Fig. 1, the 2-opt algorithm interexchanges
two paths, i − a(i) and j − a(j), with another two paths, i − jand a(i) − a(j), where a(i) and a(j) are cities next to i andj,respectively. When the 2-opt exchange is done that links thecities i and j, (i, j)th neuron which corresponds to the path
between the cities i and j is memorizes in the tabu list.
3. Chaos noise
In the case of solving an n-city TSP, the number of neurons
In this research, we use as a noise the time series of theN necessary for the network is n2 in this approach.
chaos generated by the logistic map of the following equation:zij (t + 1) = rzij (t)(1 − zij (t)).
(4)
The chaotic sequence is normalized byẑij (t + 1) =Figure 1: An example of the 2-opt exchange.

- 141 -zij (t) − z̄σz(5)where. z̄ is the average of zij (t) and σz is the standard deFor numerical calculation, Eq. (8) can be reduced to theviation of zij (t). In this research we use intermittent chaos following forms: if t < s,near the three-periodic window obtained from the logistic
ζij (t + 1) = kr ζij (t) − αxij (t) + R(10)map with r = 3.828. The time series of the intermittent chaosnoise near the three-periodic window to be used is shown inotherwise (t ≥ s),
Fig. 2.
ζij (t + 1) = kr ζij (t) − αxij (t) + R + αkrs xij (t − s) (11)where R = θ(1 − kr ). Here, we assume that xij (u) = 0 for
u < 0, which means that there is generally no tabu effect for
initial conditions.
5. Simulated results
In this research, we use three problems, “bays29”, “rd100”
and “lin105” from TSPLIB [3]. The results are summarizedin Table 1. And convergence of the solution to “lin105” isshown in Figs. 3 and 4. Figure 3 shows that the convergence of the solution of the tabu search and the tabu searchwith chaos noise. Figure 4 shows that the convergence ofFigure 2: Intermittent chaos noise near the three-periodic the solution of the tabu search with chaos noise and thewindow.
chaotic search. Here, parameter values are fixed as β = 75.0,
kr = 0.99, R = 0.05, W = 0.15, ² = 0.002, and γ = 0.07.
Moreover, the number of iterations is 10,000.
4. Chaotic neural network based on paths [2]
For the comparison we consider the technique extended to Table 1: The results of the tabu search (TS), the tabu search
the neural network with chaotic dynamics. This technique with chaos noise (TS-C) and the chaotic search (CS).
is almost the same as the tabu effect of the exponential tabu
Problem Optimal Solution
TSTS-CCS
search realized by the tabu search neural network describedbays29
9074
9074
9074
9074
above. However, there is a significant difference on the output
rd100
7910
7955.0 7950.2 7940.6
function. The output of each neuron xij (t) of the above tabu
lin10514379
14500.4 14436.3 14391.7
search neural network is determined to be 0 or 1 by detecting
the maximum internal state of Eq. (3) among all neurons. On
the other hand, the chaotic neural network originally adopts
an analog sigmoidal function.
Then, this method, which includes both of the tabu effectand chaotic dynamics, is realized by the following equations
with an asynchronous updating:ξij (t + 1) = β(Do (t) − Dij (t))ηij (t + 1) = −WnnXX(6)xkl (t) + W(7)

krd {xij (t − d)} + θ(8)

k=1 l=k+1

ζij (t + 1) = −αs−1X
d=0xij (t + 1) = f {ξij (t + 1) + ηij (t + 1)
+ ζa(i)a(j) (t + 1) + ζij (t + 1)}(9)

If xij (t + 1) > 1/2, the (i, j)th neuron fires and the path Figure 3: Convergence of the solution of the tabu search (TS)between cities i and j is connected with the 2-opt exchange and the tabu search with chaos noise (TS-C).
as shown in Fig. 1.

- 142 -

[3]Figure 4: Convergence of the solution of the tabu search withchaos noise (TS-C) and the chaotic search (CS).
Table 1 shows that the tabu search with chaos noise exhibits much better performance than the tabu search. Although the chaotic search can find the solutions closer to theoptimal solution than the tabu search with chaos noise, there
are many parameters to be tuned in the chaotic search. Moreover, the chaotic search applied an asynchronous updating,so that the convergence speed of the tabu search with chaosnoise is faster than the chaotic search from Fig. 4.
6. Conclusion
In this research, we have investigated the effect of the chaosnoise added to the tabu search neural network with 2-opt for
TSPs. By carying out computer simulations for various problems, we confirmed that the chaos noise has a good effect toavoid local minimum problems and achieves a good performance to find good solutions of the TSPs as well as the tabu
search neural network with chaotic dynamincs.
As a future subject, we investigate the effect to add different noises to the network.
Acknowledgement
This work was partly supported by Kayamori Foundationof Informational Science Advancement’s Research Grant.
References[1] Hasegawa, M., Ikeguchi, T., Aihara, K., Combinationof Chaotic Neurodynamics with the 2-opt Algorithm toSolve Traveling Salesman Problems”, Physical Review
Letters, Vol. 79, pp. 2344-2347, 1997.
[2] Hasegawa, M., Ikeguchi, T., Aihara, K., Solving large
scale traveling salesman problems by chaotic neurodynamics”, Neural Networks, 15, pp. 271-283, 2002.

- 143 -TSPLIB”, http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/

- 144 -