![](https://csdnimg.cn/release/download_crawler_static/15736775/bg4.jpg)
Volume 8 • Issue 4 • October-December 2017
4
of binary encoding (Gutjahr, 2008; Doerr & Johannsen, 2007; Doerr et al., 2011) to derive a tighter
upper bound of running time for RTSP than that obtained in (Nallaperuma et al., 2013).
This section introduces a special ACO algorithm, i.e., ant system algorithm (AS) (Dorigo et al.,
1996), for solving traveling salesman problems (TSPs). We describe the TSP, and then present the
AS algorithm as well as its absorbing Markov chain model.
We begin by stating some notations which will be used in the remaining sections of the present paper.
Definition 1. Traveling Salesman Problem (TSP): A traveling salesman wants to visit each of n
cities exactly once and return to his/her starting point. The problem is to find an order of cities
for the salesman such that the total travel distance is minimized.
Actually, the TSP is to seek a Hamiltonian cycle with the lowest cost in a connected weighted
graph. Specifically, let G V E D= ( , , ) be a connected weighted graph with V = { , ,..., }1 2 n ,
E V= < > ∈{ , | , }i j i j , and D V= ≥ ∈{ | ; , }d d i j
ij ij
0 as vertex set, edge set, and cost set,
respectively, where d
ij
denotes the cost (length) of edge < >i j, . Note that a Hamiltonian cycle is
required to pass through all of the vertices exactly once. Hence, each Hamiltonian cycle is a candidate
solution of TSP. Let x = ( , ,..., )v v v
n1 2
be a Hamiltonian cycle where v
i
∈ V denotes a vertex in
and v
1
is the starting point. The cost of the cycle is the total length of the edges at
, so the value
of objective function f d d
v v
i
n
v v
i i n
( )x = +
−
=
∑
1 1
2
is the length of
.
The TSP is an NP-complete combinatorial problem and it is often used as benchmark to verify
the efficiency of ACO (Dorigo et al., 2006; Dorigo & Stützle, 1999). Recently, running-time analysis
of ACO algorithms for TSPs (Zhou, 2009; Kötzing et al., 2010) has become an important topic in
theoretical research of evolutionary computation. Our work is also along this line with focus on the
running-time analysis of AS algorithm for regular-polygon TSPs.
We now introduce the ant system algorithm (AS) for solving TSPs. We note that most of the previous
studies (Zhou, 2009; Kötzing et al., 2010; Kötzing et al., 2012) focused on the ACO variants that
were never designed for solving Euclidean TSPs. The AS algorithm (Dorigo et al., 1996), however,
is one of the earliest published ACO variants which aim at solving TSPs. This is why we choose the
AS algorithm to analyze its running-time for solving TSPs.
We present the framework of AS in Figure 1 and explain its implementation details as follows.
Let τ( )t be the pheromone matrix at the
-th iteration and τ
ij
t( ) be the pheromone trail value
of edge < >i j, , where t ∈
+
Z ∪ { }0 . At the first step of Figure 1, the initialization of pheromone
runs by τ
ij
n( ) / ( )0 1 1= − , where i j n, , ,...,
1 2 and
is the problem size of TSP.
At the second step of Figure 1, the sole artificial ant selects an arbitrary city as the first city of
TSP tour, and chooses the next city one by one to generate a complete solution with a probability,
defined in Expression (1). Specifically, if we assume X
t
t t
n
t
v v v= ( , ,..., )
1 2
is the solution found by