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

Solving Ability of Coupled Map Lattice with 2-Opt Algorithm for TSPs
Shuichi AONO and Yoshifumi NISHIO
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

Abstract
In this study, we propose a new method using the coupled
map lattice with the 2-opt algorithm for solving travelingsalesman problems. In this method, we utilize the 2-opt algorithm for updating solutions of traveling salesman problems,
and we use sequences generated by the coupled map lattice
as a adding noise. By carrying out computer simulations, weconﬁrm that the chaotic noise generated by the coupled map
lattice has a good eﬀect to escape local minima and achieves
a good performance to ﬁnd near optimal solutions.
1. Introduction
Combinatorial optimization problems can be used for anarrangement and wiring of LSI in an engineering ﬁeld. Whenthe number of element increases, a calculation time becomes
longer and a calculation becomes almost impossible in realtime. Therefore, it is important to develop heuristic algorithms for ﬁnding good solutions in a short time. A techniqueusing the Hopﬁeld neural network [1] is one of the powerful tool to ﬁnd good solutions within limited time. Recently
many researchers suggested that the chaotic noise is more effective than the stochastic noise with the Hopﬁeld neural network for solving traveling salesman problems (TSPs) [2]-[4].
Moreover, the technique is extended to the neural networkwith chaotic dynamics to avoid the local minimum problems[5][6].
In this study, we propose a new method using the coupled
map lattice (CML) with the 2-opt algorithm for solving TSPs.
We utilize the 2-opt algorithm for updating solutions of TSPs.
The 2-opt algorithm is one of the simplest local search to ﬁnd
good solutions. The 2-opt Algorithm exchanges two baths,
i−a(i) and j−a( j), with another two paths, i− j and a(i)−a( j)as shown in Fig. 1. However, a tour obtained by the 2-opt algorithm is often trapped into local minima. In order to escapefrom local minima, we applied the chaotic noise generated
by the CML to the 2-opt algorithm. The 2-opt algorithm canﬁnd new candidates for 2-opt exchange by adding the chaoticnoise. And we investigate solving abilities of the noise generated by the CML for TSPs.

Figure 1: Example of the 2-opt algorithm.
2. Coupled Map Lattice
A CML is known as good models to describe spatiotemporal chaos and pattern dynamics [7][8]. In the CML, the each
map connects to only adjacent maps. The CML is shown inFig. 2. Also the CML is able to generate complex pattern [9]and phenomena [10]. And it applied to the pseudo-randombit generator in the engineering ﬁeld [11].

- 360 -Figure 2: Coupled map lattice.

A CML is consisted as following equation:] [ i+1xi (n + 1) = (1 − ) f (xi (n)) +f (x (n)) + f (xi−1 (n)) (1)2where xi (n) represents the state variable for the site i at timen,  is a coupling strength and f (·) is a site map. The periodic
boundary conditions are x0 (n) = xL (n) and xL+1 (n) = x1 (n).
In this study, we use a skew tent map and a logistic map
as the chaotic site map f . A skew tent map is expressed asfollowing equation:
 X




 pf (x) = 


X−1


p−1(0 ≤ X ≤ p)
(2)

3. Proposed Method
We propose a new method using the CML with the 2-opt
algorithm for solving TSPs. In the proposed method, internal
states of cities are deﬁned as following equation:cityi (t + 1) = max{D0 (t) − Di j (t) + βxi (t)}j(4)

where xi is sequence generated by a CML, D0 (t) is the lengthof the tour, Di j (t) is the length of the tour generated by applying the 2-opt exchange between cities i and j, β is the scaling
parameter of the noise eﬀect.
If the internal state cityi (t) is the largest in all cities, the path
between cities i and j is connected by the 2-opt exchange.

(p < X ≤ 1)
4. Simulated Results

This map is shown in Fig. 3.

Figure 3: Skew tent map.
A logistic map is expressed as following equation:f (x) = αx(1 − x)(3)where α is a bifurcation parameter. A logistic map for α = 4.0
is shown in Fig. 4.

In this research, we use a problem “lin105” from TSPLIB[12]. A known optimal tour length of “lin105” is 14372. The
simulated results are the average values of 10 trials with different initial values. And the number of iterations is 1000
times. The simulated result by using the CML consisting of
the logistic maps is shown in Fig. 5. We can see that the proposed method with α close to 4.0 becomes better solutions.
Next, we investigate the relation between each parameters
and the tour length in detail. Figure 6 shows results of the tour
length versus the amplitude of added noise. The horizontal
axis shows the value of β, and the vertical axis shows the tourlength. Here, β = 0 means that the chaotic noise does not beadded to the 2-opt algorithm. From this ﬁgure, we can seethat the solutions becomes close to the optimal solution byadding the chaotic noise.
The result of the tour length versus the coupling strengthis shown in Fig. 7. The horizontal axis shows the value of, and the vertical axis shows the tour length. In the case of = 0, the CML is not coupled. We conﬁrm that the 2-opt
algorithm with chaotic noise consisting of the CML exhibits
much better performance than the 2-opt algorithm. However,as the coupling strength becomes large, the solutions cannot
ﬁnd the solutions closer to the optimal solution than the 2-opt
algorithm with simple chaotic map. Moreover, we can seethat the proposed method has a very sensitive to the couplingstrength.
Finally, we investigate the α sensibility. α corresponds tothe bifurcation parameter of the logistic map. From Fig. 8,
we can obtain the good solution around α = 3.8.

Figure 4: Logistic map.

- 361 -

Figure 5: Simulated result(a)(a)(b)(b)

Figure 6: β vs. tour length (a) logistic map, (b) skew tent map(α = 4.0,  = 0.1, p = 5.1)

Figure 7:  vs. tour length (a) logistic map, (b) skew tent map(β = 0.2, α = 4.0, p = 5.1)

- 362 -

[4] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe and T.
Ikeguchi, “Performance of Chaos Noise Injected toHopﬁeld NN for Quadratic Assignment Problems,”
Proc. of NOLTA’02, vol. 1, pp. 267-270, 2002.
[5] M. Hasegawa, T. Ikeguchi and K. Aihara, “Combinationof Chaotic Neurodynamics with the 2-opt Algorithm toSolve Traveling Salesman Problems,” Physical Review
Letters, Vol. 79, pp. 2344-2347, 1997.
[6] M. Hasegawa, T. Ikeguchi and K. Aihara, “Solving large
scale traveling salesman problems by chaotic neurodynamics,” Neural Networks, 15, pp. 271-283, 2002.
[7] K. Kaneko, “Spatiotemporal Intermittency in Coupled
Map Lattices,” Prog. Theor. Phys, Vol. 74, no. 5, pp.
1033-1044, 1985.
Figure 8: α vs. tour length (β = 0.2,  = 0.1)

[8] K. Kaneko, “Pattern Dynamics in Spatiotemporal
Chaos,” Physica D, Vol. 34, pp. 1-41, 1989.
[9] M. Wada, K. Kitatsuji and Y. Nishio, “Spatio-temporal
Phase Patterns in Coupled Chaotic Maps with Parameter
Deviations,h Proc. of NOLTAf05, pp. 178-181, 2005.

5. Conclusions
In this study, we have proposed a method using the CML
with the 2-opt algorithm for solving TSPs. And we have investigated solving abilities of the noise generated by the CMLfor TSPs. By carrying out computer simulations, we have
conﬁrmed that the chaotic noise generated by the CML has agood eﬀect to escape local minima and achieves a good performance to ﬁnd near the optimal solution for TSPs.
As the future subject, we will investigate the potentially thetabu eﬀect by coupling chaotic maps.

[10] Y. Uwate, Y. Nishio and R. Stoop, “Synchronization
Phenomena of Chaotic Map Lattice with Time VaryingCoupling,” Proc. of NOMA’07, pp. 40-43, 2007.
[11] P. Li, Z. Li, W. Halang and G. Chen, “Analysis ofa Multiple-output Pseudo-random-bit Generator BasedOn a Spatiotemporal Chaotic System,” Internal Journalof Bifurcation and Chaos, Vol. 16, No. 10, pp. 29492963, 2006.
[12] “TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/

References[1] J.J. Hopﬁeld, “Neurons with Graded Response Have
Collective Computational Properties like Those of TwoState Neurons,h Proc. Natl. Acad. Sci. USA, vol. 81, pp.
3088-3092, 1984.
[2] Y. Hayakawa and Y. Sawada, “Eﬀects of the Chaotic
Noise on the Performance of a Neural Network Modelfor Optimization problems,” Physical Review E, Vol.
51, no. 4, pp. 2693-2696, 1995.
[3] T. Ueta, Y. Nishio and T. Kawabe, “Comparison between Chaotic Noise and Burst Noise on Solving Ability of Hopﬁeld Neural Networks,” Proc. of NOLTA’97,
vol. 1, pp. 409-412, 1997.

- 363 -