平成21年度電気関係学会四国支部連合大会

351

18-27
Eﬀect of Chaos Noise on City Placement withLocal Search Algorithm for TSPs
Yasuyuki Yoshida(Tokushima University)

Shuichi Aono(SESAME Technology)

1 Introduction
Although it would be possible to solve combinatorial optimization problems with a huge number of elements if wehave inﬁnite long time, it does not make any sense forpractical problems. In several approximation methods, thesolutions are trapped into local minima. Therefore, the solutions need to avoid the local minima. It is possible thatthe solutions become close to a good solution by avoiding
the local minima.
In this study, we propose an algorithm that pouring thechaos noise to the city placement. It supports to ﬁnd goodsolutions and avoid local minima. In the past study, weinvestigated the eﬀect of chaos noise poured in the city
placement with 2-opt algorithm [1], hence in this study
we extend the idea to more strong Or-opt algorithm. By
carrying out computer simulations for various problems,
we conﬁrm that the chaos noise has a good eﬀect to avoid
local minima and achieves a good performance to ﬁnd agood solution of the TSPs.

2 Proposed method
As shown in Fig. 1, the 2-opt algorithm exchanges twopaths, i-j and k-l, with the other two paths, i-k and j-l,where j and l are the cities next to i and k. If a trial
exchange shortens total tour length, the exchange is reallyexecuted.
ilkj

ilkj

Figure 1: Example of 2-opt exchange.
The Or-opt algorithm exchange multiple paths in a similar way. In this study, after the Or-opt exchanges, thechaos noise is poured in the city placement. Because thecity placement is changed by the chaos noise, the Or-opt
algorithm ﬁnds new candidates for exchange. These processes are iterated several times.

3 Chaos noise
In this study, we use the time series of the chaos generated by the logistic map as a noise. The logistic map isgiven as following equation.
xn (t + 1) = αxn (t)(1 − xn (t))
The chaotic sequence is normalized by
xn (t) − x̄x̂n (t) =σx

Yoshifumi Nishio(Tokushima University)from the logistic map gains good performance for combinatorial optimization problems [2].

4 Simulated results
In this study, we use three problems, “bayg29”, “lin105”,and “rat575” from TSPLIB [3]. The results are summarized in Table 1. Here, the number of iterations is 100times. The results are average values of 10 trials. The
Table 1 shows the Or-opt algorithm without chaos (conventional method), the Or-opt algorithm with chaos noiseof the bifurcation parameter α = 3.828 (proposed method1), α = 3.5 (proposed method 2), and α = 4.0 (proposedmthod 3).

Table 1: The results of conventional method, proposed
method 1, proposed method 2 and proposed mthod 3.
Problem
Optimalsolution
Conventional
methodProposedmethod 1
Proposedmethod 2
Proposedmethod 3

bayg29lin105

rat575

9047

14379

6773

9141

14790

7150

9074

14425

7111

9107

14459

7101

9074

14535

7116

From this table, we can conﬁrm that the proposed algorithms with chaos exhibit better performance than theconventional method without chaos. Although the averaged values are similar for all three proposed methods, theintermitency chaos seems to be more eﬀective to ﬁnd thebest solution.

5 Conclusions
We have investigated the eﬀect of chaos noise poured in
the city placement with Or-opt algorithm for the TSPs. By
carrying out computer simulations for various problems, wehave conﬁrmed that the chaos noise had a good eﬀect toavoid local minimum problems and achieved a good performance to ﬁnd good solutions of the TSPs.
As the future subject, we will investigate the eﬀect topour diﬀerent noises to the city placement.

(1)

References(2)[1] Y. Yoshida, S. Aono and Y. Nishio, “Eﬀect of chaosnoise on city placement by using 2-Opt algorithm forTSPs,” Proc. of NCSP’09, pp.357-359, Mar. 2009.

where x̄ is the average of xn and σx is the standard devision of xn . In this study, we use the bifurcation parameter
α = 3.5, 3.828, 4.0. The bifurcation parameter α = 3.828
is the intermittency chaos near the three-periodic window
obtained from the logistic map. It is reported that the intermittency chaos near the three-periodic window obtained[2] Y. Hayakawa and Y. Sawada, “Eﬀects of the chaotic
noise on the performance of a neural network model for
optimization problems,” Physical Review E, vol.51, no.4,
pp.2693-2696, 1995.
[3] “TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/