2009 International Workshop on Nonlinear Circuits and Signal Processing
NCSP'09, Waikiki, Hawaii, March 1-3, 2009

Eﬀect of Chaos Noise on City Placement by Using 2-Opt Algorithm for TSPs
Yasuyuki Yoshida, Shuichi Aono and Yoshifumi Nishio
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Phone:+81-88-656-7470 Fax:+81-88-656-7471
Email: yasu0824, aoichi, nishio@ee.tokushima-u.ac.jp

Abstract

used by neural network as other eﬃcient method [6]-[9]. It
is believed that it is almost impossible to obtain the optimal
solution of the TSP in the limited time. Therefore, it needs
the eﬀective algorithm to find the near optimal solutions orapproximation solutions for TSPs.

In this study, we propose the algorithm that pouring the chaosnoise to the city placement for the traveling salesman problems. We investigate the eﬀect of chaos noise poured in
the city placement with 2-opt algorithm. By carrying out
computer simulations for various problems, we confirm thatthe chaos noise has a good eﬀect to avoid local minima and 3. Chaos noise poured in the city placement with 2-opt
achieves a good performance to find a good solution of the algorithm
TSPs.
We proposed the algorithm that pouring the chaos noise tothe city placement.
1. Introduction
Although it would be possible to solve combinational optimization problems with a huge number of elements if wehave infinite long time, it does not make any sense for practical problems. In the approximation method, the solutions
get into local minima. Therefore, the solutions need to avoid
local minima. It is possible that the solutions become close toa good solution by avoiding local minima.
Many researchers have proposed that the approximation
method with the chaos noise [1]-[4]. The chaos noise is directly poured to the algorithm in these proposed method. In
this study, we propose the algorithm that pouring the chaosnoise to the city placement. It supports to find the good solution and avoid the local minima. We investigate the eﬀect ofchaos noise poured in the city placement with 2-opt algorithm
for the traveling salesman problems.
By carrying out computer simulations for various problems, we confirm that the chaos noise has a good eﬀect toavoid local minima and achieves a good performance to finda good solution of the traveling salesman problems.

3.1. 2-opt algorithm
The 2-opt algorithm exchanges two paths for other twopaths until no further improvement can be obtained. Figure 1
shows an example of the 2-opt exchange. In Fig. 1, the 2-opt
algorithm exchanges two paths, a-b and c-d, with the othertwo paths, a-c and b-d, where b and d are cities next to a andc. If a trial exchange shortens total tour length, the exchange
is really executed.

acacdbdbFigure 1: Example of the 2-opt exchange.

3.2. Proposed method
2. Traveling Salesman Problems
The traveling salesman problems(TSPs) is one of the combinational optimization problems, which is described as follows: given city placements, find the minimum length tour
which visits each city exactly once [5]. The TSP belongs toa class of NP-hard in the computational complexity. Solvingfor TSPs, it is reported that the good solution is achieved to

In the approximation method, the solutions get into localminima. Therefore, we poured the chaos noise to the city
placement for solving this problem.
The proposed method is described as follows:
1. The initial tour is made at random. Figure 2 shows a
initial tour.

- 357 -present paths
candidates

Figure 2: Initial tour

Figure 5: Candidates for 2-opt exchange

2. The tour is exchanged two paths with other paths by the2-opt algorithm. Figure 3 shows the tour exchanged by
the 2-opt algorithm.

5. These processes are iterated several time.
4. Chaos noise
In this study, we use the time series of the chaos generated
by the logistic map as a noise. The logistic map is given as
following equation.
xn (t + 1) = αxn (t)(1 − xn (t))(1)

where α is a bifurcation parameter. The behavior of sequences are changed by this parameter.
The chaotic sequence is normalized byx̂n (t) =Figure 3: 2-opt algorithm exchanges

3. After the 2-opt algorithm, the chaos noise is poured in
the city placement. The cities placement are slightly
changed by adding noise. Figure 4 shows the city placement with chaos noise.

xn (t) − x̄
σx(2)

where x̄ is the average of xn and σ x is the standard divisionof xn . In this study, we use the intermittency chaos near thethree-periodic window obtained from the logistic map with α= 3.828. It is reported that the intermittency chaos obtained
from the logistic map with α = 3.828 gains good performancefor combinational optimization problems [1]. The chaotic sequence is shown in Fig. 6.
1.5

1x(t)

0.50-0.5-1

Figure 4: City placement with the chaos noise

-1.5
0100

200

300

400500600

700800900t

4. Then, the 2-opt exchange executes when the 2-opt algorithm finds new candidates. In Fig. 5, the candidates areexchanged as the new paths by the 2-opt algorithm.

- 358 -Figure 6: Intermittency chaos (α = 3.828).

1000

5. Simulated results
In this study, we use four problems, “bayg29”, “lin105”,“pr124” and “KroE100” from TSPLIB[10]. The results aresummarized in Table 1. Here, the number of iterations is 100times. The results are average values of 10 trials with thediﬀerent initial value.
Table 1: The results of the 2-opt algorithm (conventionalmethod) and the 2-opt algorithm with chaos noise (proposedmethod).
Problembayg29lin105pr124
KroE100

Optimalsolution
9074
14379
59030
22068

Conventional
method
9416
15596
62950
24303

Proposedmethod
9148
14728
59847
23371

[4] Y. Tada, Y. Uwate and Y. Nishio, “Eﬀective Search withHopping Chaos for Hopfield Neural Networks Solving
QAP,” Proceedings of ISCAS’07, pp. 1783-1786, 2007.
[5] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, andD. B Shmoys, John Wiley and Sons, Chichester, “Thetraveling salesman problem,” 1985.
[6] K. Aihara, T. Takabe and M. Toyoda, “Chaotic neural networks,” Physics Letters A, vol. 144, pp. 330-340,
1990.
[7] L. Chen and K. Aihara, “Chaotic simulated annnealing
by a neural network model with transient chaos,” NeuralNetworks, vol. 8, pp. 915-930, 1995.
[8] M. Hasegawa, T. Ikeguchi and K. Aihara, “Combination of chaotic neurodynamics with the 2-opt algorithm
to solve traveling salesman problems,” Physical Review
Letters, vol. 79, pp. 2344-2347, 1997.

From this table, we can confirm that the 2-opt algorithmwith chaos noise exhibits better performance than the 2-optalgorithm.

[9] M. Hasegawa, T. Ikeguchi, K. Aihara, “Solving large
scale traveling salesman problems by chaotic neurodynamics,” Neural Networks, pp. 271-283, 2002.
[10] “TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/

6. Conclusions
In this study, we have proposed the algorithm that pouring
the chaos noise to the city placement. And we have investigated the eﬀect of chaos noise poured in the city placementwith 2-opt algorithm. By carrying out computer simulations
for various problems, we have confirmed that the chaos noise
has a good eﬀect to avoid local minima and achieves a good
performance to find a good solution of the TSPs.
As the future subject, we will investigate the eﬀect to pourdiﬀerent noises to the city placement.
References[1] Y. Hayakawa and Y. Sawada, “Eﬀects of the chaotic noiseon the performance of a neural network model for optimization problems,” Physical Review E, vol. 51, no. 4,
pp. 2693-2696, 1995.
[2] T. Ueta, Y. Nishio and T. Kawabe, “Comparison between
Chaotic Noise and Burst Noise on Solving Ability ofHopfield Neural Networks” Proceedings of NOLTA’97,
vol. 1, pp. 409-412, 1997.
[3] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T. Ikeguchi,“Performance of Chaos Noise Injected to Hopfield NN
for Quadratic Assignment Problems,” Proceedings ofNOLTA’02, vol. 1, pp. 267-270, 2002.

- 359 -