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

382

17-13
Eﬀect of Chaos Noise on City Placement with2-Opt Algorithm for Traveling Salesman Problems
Yasuyuki Yoshida

Shuichi Aono
(Tokushima University)

1 Introduction

1.5

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

cac

10.5x(t)Although it would be possible to solve combinationaloptimization problems with a huge number of elements if
we have inﬁnite long time, it does not make any sense forpractical problems. In the approximation method, the solutions get into local minima. Therefore, the solutions needto avoid the local minima. It is possible that the solutions
become close to a good solution by avoiding the local minima.
In this study, we investigate the eﬀect of chaos noise
poured in the city placement with 2-opt algorithm for thetraveling salesman problems (TSPs). By carrying out computer simulations for various problems, we conﬁrm thatthe chaos noise has a good eﬀect to avoid local minimum
problems and achieves a good performance to ﬁnd a goodsolution of the TSPs.

aYoshifumi Nishio

0-0.5-1-1.50bd

Figure 1: Example of 2-opt exchange.
After the 2-opt algorithm, the chaos noise is poured in
the city placement. The city placement is changed by thechaos noise. Therefore, the 2-opt algorithm ﬁnds new candidates for exchange. These processes are iterated severaltimes.

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))(1)

The chaotic sequence is normalized byx̂n (t) =xn (t) − x̄
σx300

400500

600

700

800

9001000

Figure 2: Intermittency chaos (α = 3.828).

4 Simulated results
In this study, we use three problems, “bayg29”, “lin105”
and “kroE100” from TSPLIB[2]. The results are summarized in Table 1. Here, the number of iterations is 100times. The results are average values of 10 trials.

Table 1: The results of the 2-opt algorithm (conventional method) and the 2-opt algorithm with chaosnoise (proposed method).

bayg29lin105
kroE100b200

t

Problemd100

Optimalsolution
9074
14379
59030

Conventional
method
9416
15596
62950

Proposedmethod
9148
14728
59847

From this table, we can conﬁrm that the 2-opt algorithmwith chaos noise exhibits better performance than the 2opt algorithm.

5 Conclusions
We have investigated the eﬀect of chaos noise poured in
the city placement with 2-opt algorithms for the TSPs. Bycarrying out computer simulations for various problems,
we have conﬁrmed that the chaos noise had a good eﬀect
to avoid 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.

(2)

where x̄ is the average of xn and σx is the standard devision of xn . In this study, we use the intermittency chaos
near the three-periodic window obtained from the logistic
map with α = 3.828. It is reported that the intermittencychaos near the three-periodic window obtained from thelogistic map gains good performance for combinational optimization problems [1]. The chaotic sequence is shown inFig. 2.

References[1] 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.
[2] “TSPLIB,” http://www.iwr.uni-heidelberg.de/groups/
comopt/software/TSPLIB95/