2009 IEEE Workshop on
Nonlinear Circuit Networks, Tokushima, Dec 11-12, 2009

Effect of Chaos Noise to City Placement withOr-opt Algorithm for TSPs
Yasuyuki YoshidaShuichi Aono

Yoshifumi Nishio

Tokushima University
SESAME Technology
Tokushima University
2-1 Minami-Josanjima,
Incubation Division 215, 3-5-1 Johoku,
2-1 Minami-Josanjima,
Tokushima, Japan
Hamamatsu 432-8561, Japan
Tokushima, Japan
Phone:+81-88-656-7470
E-mail: aono@tzasai7.sys.eng.shizuoka.ac.jp
Phone:+81-88-656-7470
Fax:+81-88-656-7471
Fax:+81-88-656-7471
Email: yasu0824@ee.tokushima-u.ac.jpEmail:nishio@ee.tokushima-u.ac.jp

Abstract— In this study, we propose an novel algorithm pouring the chaos noise to the city placement for solving the travelingsalesman problems. We investigate the effect of chaos noise
poured in the city placement with 2-opt algorithm and Or-opt
algorithm. In addition, we investigate changing the amplitudeof chaos noise poured in the city placement. By carrying out
computer simulations for various problems, we confirm that thechaos noise has a good effect to avoid local minima and achieves
to a good solution of the traveling salesman problems.

I. I NTRODUCTION
Although it would be possible to solve combinatorial optimization problems with a huge number of elements if we haveinfinite long time, it does not make any sense for practicalproblems. In several approximation methods, the solutions aretrapped into local minima and do not escape. In order to avoid
this problem, technical methods to escape from local minima
are required.
Many researchers have proposed that the approximation
method with the chaos noise [1][2]. The chaos noise is directly
poured to the algorithm in these proposed method.
In this study, we propose an algorithm that pouring thechaos noise to the city placement. It supports to find goodsolutions and avoid local minima. In the past study, we haveinvestigated the effect of chaos noise poured in the city
placement with 2-opt algorithm [3], hence we extend the idea
to more strong Or-opt algorithm and changing the amplitudeof choas noise.
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 whichvisits each city exactly once [4]. The TSP belongs to a class ofNP-hard in the computational complexity. Solving for TSPs,
it is reported that the good solution is achieved to used byneural network as other efficient method [5][6].
In this study, we propose an novel algorithm pouring thechaos noise to the city placement for solving the travelingsalesman problems. Furthermore, we compare changing theamplitude of noise and the several types of noises such as
intermittency chaos, fully developed chaos and random noise.
By carrying out computer simulations for various problems,

we confirm that the chaos noise has a good effect to avoid
local minima and achieves a good solution of the TSPs.
II. P ROPOSED M ETHOD
In the approximation methods, the solutions are trapped into
local minima. Therefore, it is important to develop effective
methods to avoid the local minima. In this study, we propose
an novel algorithm that the chaos noise is poured to the city
placement.
The simulations are carried out according to the following
procedure.
Step1 The 2-opt algorithm exchanges two paths for otherpaths.
Step2 The Or-opt algorithm exchanges multiple paths forother paths.
Step3 Pouring the noise to city placement, the city placement is changed.
Step4 Step. 1 - Step. 3 repeats several times.
These procedure details following below;
A. 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, i-j and k-l, with the anothertwo paths, i-k and j-l, where j and l are cities next to i andk. If a trial exchange shortens total tour length, the exchange
is really executed.

- 90 -Fig. 1.

Example of 2-opt exchange.

B. Or-opt algorithm
The Or-opt algorithm exchange multiple paths in a similar
to 2-opt algorithm. In this study, the Or-opt exchanges after the2-opt exchanged. The Or-opt exchange is the 3-opt exchange
at a maximum containing the 2-opt algorithm. Therefore, theOr-opt algorithm can find new candidates which the 2-opt
algorithm is not able to find.
C. Pouring NoisetTo avoid local minima, we propose the noise poured to cityplacement. The noise is poured in the city placement after theOr-opt exchange. Namely the city placement is changed by
the noise, the 2-opt algorithm and Or-opt algorithm find newcandidates for exchange. The city placement returns the initialstate after the new candidates are found by 2-opt exchange andOr-opt exchange. The 2-opt algorithm and Or-opt algorithm
are searching the new path again.
To be iterated these processes, the solutions avoid the local
minima and achieve the good solutions.

Fig. 2.

Intermittency chaos (α = 3.828).

III. C HAOS N OISEtIn 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)

The chaotic sequence is normalized by following equation.
x̂n (t) =xn (t) − x̄
σxFig. 3.

amplitude in poured noise (amplitude = 0.01, decreasing from0.01 to 0.0001).

(2)

TABLE IT HE RESULTS OF CONVENTIONAL METHOD , CHAOS NOISE , RANDOMwhere x̄ is the average of xn and σx is the standard devisionof xn . In this study, we use the bifurcation parameter α =3.828 and α = 4.0. The bifurcation parameter α = 3.828 is theintermittency chaos near the three-periodic window obtained
from the logistic map. As we can see from the Fig. 3, thechaotic time series is divided into two phases; laminar partsof periodic behavior with period three and burst parts of spread
points over the invariant interval. It is reported that the intermittency chaos near the three-periodic window obtained fromthe logistic map gains better performance for combinatorial
optimization problems than the fully-developed chaos. The
bifurcation parameter α = 4.0 is the fully-developed chaos.
As we can confirm from Fig. 4, the fully-developed chaos
consists of burst parts and do not have laminar parts.

NOISE

Problem
Optimalsolution
Conventional
methodRandomamplitude = 0.01
Intermittency chaos,
amplitude = 0.01
Fully-developed chaos,
amplitude = 0.01
Randomdecreasing amplitude
Intermittency chaos,decreasing amplitude
Fully-developed chaos,decreasing amplitude

IV. S IMULATION R ESULTS
In this study, we apply the proposed algorithm for four
problems, “kroE100”, “lin105”, “pr124” and “pr226” fromTSPLIB [7]. The simulated results are summarized in Table 1.
Here, the number of iterations is 100 times. The simulated results are average values of 10 trials with different initial value.
Table 1 shows the results of the Or-opt algorithm withoutchaos (conventional method), the Or-opt algorithm with chaosnoise of the bifurcation parameter α = 3.828 (intermittencychaos), α = 4.0 (fully-developed chaos) and random noise(random), respectively. We investigate two patterns of theFully-developed chaos (α = 4.0).

kroE100

lin105

pr124

pr226

22068

14379

59030

80369

22550

14790

60512

84111

22606

14995

60231

84663

22396

14804

60321

83019

22456

14903

60321

84086

22146

14425

59092

81131

22153

14401

59087

81044

22154

14405

59087

81186

From this table, we can confirm that the Or-opt algorithmwith noise exhibits better performance than the conventional
method without noise. Although the averaged values are
similar for all four proposed methods, the method with theintermittency chaos seems to be more effective to find thebest solution. In the method with the intermittency chaos,decreasing the amplitude from 0.01 to 0.0001, the solutions
become close to the optimal solution.

- 91 -V. C ONCLUSION
We have investigated the effect of chaos noise poured in thecity placement with 2-opt algorithm and Or-opt algorithm for
the TSPs. By carrying out computer simulations for various
problems, we have confirmed that the chaos noise had a goodeffect to avoid local minimum problems and achieved a goodsolutions of the TSPs.
As the future subject, we will investigate the effect topour different noises to the city placement and use the otheralgorithm for searching tour length.
R EFERENCES[1] Y. Hayakawa and Y. Sawada, “Effects of the chaotic noise on theperformance 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 Noiseand Burst Noise on Solving Ability of Hopfield Neural Networks”
Proceedings of NOLTA’97, vol. 1, pp. 409-412, 1997.
[3] Y. Yoshida, S. Aono and Y. Nishio, “Effect of chaos noise on city
placement by using 2-Opt algorithm for TSPs,” Proc. of NCSP’09,
pp.357-359, Mar. 2009.
[4] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B Shmoys,
John Wiley and Sons, Chichester, “The traveling salesman problem,”
1985.
[5] K. Aihara, T. Takabe and M. Toyoda, “Chaotic neural networks,” Physics
Letters A, vol. 144, pp. 330-340, 1990.
[6] 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.
http://www.iwr.uni-heidelberg.de/groups/
co[7] “TSPLIB,”
mopt/software/TSPLIB95/- 92 -