23-09-2016, 11:02 AM
Solving Traveling Salesman Problem by Using Improved
Ant Colony Optimization Algorithm
[attachment=71519]
Abstract—Ant colony optimization (ACO) is a heuristic
algorithm which has been proven a successful technique and
applied to a number of combinatorial optimization problems
and is taken as one of the high performance computing methods
for Traveling salesman problem (TSP). TSP is one of the most
famous combinatorial optimization (CO) problems and which
has wide application background.. ACO has very good search
capability for optimization problems, but it still remains a
computational bottleneck that the ACO algorithm costs too
much time to convergence and traps in local optima in order to
find an optimal solution for TSP problems. The presented paper
proposes an improved ant colony optimization algorithm with
two highlights. First, candidate set strategy is adopted to rapid
convergence speed. Second, a dynamic updating rule for
heuristic parameter based on entropy to improve the
performance in solving TSP. Algorithms are tested on
benchmark problems from TSPLIB and test results are
presented. From our experiments, the proposed algorithm has
better performance than the conventional ACO algorithm and
the results of the proposed algorithms are found to be
satisfactory.
INTRODUCTION
Swarm intelligence is a relatively new approach to
problem solving that takes inspiration from the social
behaviors of insects and of other animals. The attempt in the
research of computer technology is to develop algorithms
inspired by insect behavior to solve optimization problems.
ant colony optimization (ACO) is one of the most successful
techniques in the wider field of swarm intelligence. Many
research works have been devoted to ant colony optimization
techniques in different areas. It is a relatively novel
meta-heuristic technique and has been successfully used in
many applications especially problems that belong to the
combinatorial optimization. ACO inspired by the foraging
behavior of real ant was first introduced by dorigo and his
colleagues ([1], [2]) in early 1990s and has become one of the
most efficient algorithms for TSP. ACO is based on the
pheromone trail laying and following behavior of some ant
species, a behavior that was shown to allow real ant colonies
to find shortest paths between their colony and food sources.
These ants deposit pheromone on the ground in order to mark
some favorable path that should be followed by other
members of the colony. The ants move according to the amount of pheromones, the richer the pheromone trail on a
path is, the more likely it would be followed by other ants. So
a shorter path has a higher amount of pheromone in
probability, ants will tend to choose a shorter path. Artificial
ants imitate the behavior of real ants how they forage the food,
but can solve much more complicated problem than real ants
can. Ant colony optimization exploits a similar mechanism
for solving optimization problems.
From the early nineties, when the first ant colony
optimization algorithm was proposed, ACO attracted the
attention of increasing numbers of researchers and many
successful applications are now available. ACO has been
widely applied to solving various combinatorial optimization
problems such as traveling salesman problem (TSP),
job-shop scheduling problem (JSP), vehicle routing problem
(VRP), quadratic assignment problem (QAP),
Weapon-Target Assignment problems (WTA), etc.
ACO can be used to find the solutions of difficult
combinatorial optimization problems and it enjoys a rapidly
growing popularity. Although ACO has a powerful capacity
to find out solutions to combinatorial optimization problems,
it has the problems of stagnation and premature convergence
and the convergence speed of ACO is always slow. Those
problems will be more obvious when the problem size
increases. Therefore, several extensions and improvements
versions of the original ACO algorithm were introduced over
the years. Various adaptations: an algorithm based on the
basis of the ant evolution rules [3], dynamic control of
solution construction and mergence of local search ([4], [5],
[6]), new pheromone updating strategies [7], max-min ant
system [8], a strategy is to partition artificial ants into two
groups: scout ants and common ants [9], using candidate lists
strategies ([10], [11]), dynamic ant colony system with three
level updates ([12-13]) and using the path selection
controlled by information entropy [15] are studied to improve
the quality of the final solution and lead to speedup of the
algorithm. All these studies have contributed to the
improvement of the ACO to some extent, but they have little
obvious effect on increasing the convergence speed and
obtaining the global optimal solution. In the proposed system,
the main modifications introduced by ACO are the following.
First, ACO is more effective as the candidate set strategy is
adopted. This modification reduces the size of the search
space for the ant colony algorithm. Second, information
entropy is introduced which is adjust the algorithm’s
parameters. Additionally, the best performing ACO
algorithms for the TSP improve the solutions generated by
the ants using local search algorithms. The experiment results
show that the algorithm proposed in this study can
substantially increase the convergence speed of the ACO In this paper, a modified ant colony system for solving
TSP using candidate set strategy and dynamic updating of
heuristic parameter is developed. This algorithm is used to
produce near-optimal solutions to the TSP. The paper is
organized as follows: Section 2 describes traveling salesman
problem. Section 3 and 4 illustrates the algorithm of ant
colony system. Section 5 presents candidate list strategy
approach to ACO and the other is analysis of heuristic
parameter to be updated in the algorithm. Section 6presents
the proposed algorithm for TSP. In Section 7, the proposed
method is employed into several TSP problems and the
results of our approach and of traditional ACO are reported.
Finally, Section 8 makes the conclusion.
II. TRAVELING SALESMAN PROBLEM
Traveling salesman problem (TSP) is a well known,
popular and extensively studied problem in the field of
combinatorial optimization and attracts computer scientists,
mathematicians and others. Its statement is deceptively
simple, but yet it remains one of the most challenging
problems in operational research. It also an optimization
problem of finding a shortest closed tour that visits all the
given cities. It is known as a classical NP-complete problem,
which has extremely large search spaces and is very difficult
to solve.
The definition of a TSP is: given N cities, if a salesman
starting from his home city is to visit each city exactly once
and then return home, find the order of a tour such that the
total distances (cost) traveled is minimum. Cost can be
distance, time, money, energy, etc. TSP is an NP-hard
problem and researchers especially mathematicians and
scientists have been studying to develop efficient solving
methods since 1950’s. Because it is so easy to describe and so
difficult to solve. Graph theory defines the problem as
finding the Hamiltonian cycle with the least weight for a
given complete weighted graph.
The traveling salesman problem is widespread in
engineering applications. It has been employed in designing
hardware devices and radio electronic devices, in
communications, in the architecture of computational
networks, etc. In addition, some industrial problems such as
machine scheduling, cellular manufacturing and frequency
assignment problems can be formulated as a TSP.
A complete weighted graph G=(N, E) can be used to
represent a TSP, where N is the set of n cities and E is the set
of edges (paths) fully connecting all cities. Each edge(i,j)∈E
is assigned a cost dij, which is the distance between cities i
and j. dij can be defined in the Euclidean space and is given as
follows:
(1)
One direct solving method is to select the route which has
minimum total cost for all possible permutations of N cities.
The number of permutations can be very large for even 40
cities. Every tour is represented in 2n different ways (for
symmetrical TSP). Since there are n! possible ways to
permute n numbers, the size of the search space is then THEORY AND MATHEMATICAL MODEL OF ANT
ALGORITHM
A. The Theory of Ant Algorithm
The Ant Colony Optimization techniques has emerged
recently as a relatively novel meta-heuristic for hard
combinational optimization problems. It is designed to
simulate the ability of ant colonies to determine shortest paths
to food. Although individual ants posses few capabilities,
their operation as a colony is capable of complex behavior.
Real ants can indirectly communicate by pheromone
information without using visual cues and are capable of
finding the shortest path between food sources and their nests.
The ant deposits pheromone on the trail while walking, and
the other ants follow the pheromone trails with some
probability which are proportioned to the density of the
pheromone. The more ants walk on a trail, the more
pheromone is deposited on it and more and more ants follow
the trail. Through this mechanism, ants will eventually find
the shortest path. Artificial ants imitate the behavior of real
ants how they forage the food, but can solve much more
complicated problems than real ants can. A search algorithm
with such concept is called Ant Colony Optimization. Figure
1 shows how the ants find the shortest path
Ant Colony Optimization Algorithm
[attachment=71519]
Abstract—Ant colony optimization (ACO) is a heuristic
algorithm which has been proven a successful technique and
applied to a number of combinatorial optimization problems
and is taken as one of the high performance computing methods
for Traveling salesman problem (TSP). TSP is one of the most
famous combinatorial optimization (CO) problems and which
has wide application background.. ACO has very good search
capability for optimization problems, but it still remains a
computational bottleneck that the ACO algorithm costs too
much time to convergence and traps in local optima in order to
find an optimal solution for TSP problems. The presented paper
proposes an improved ant colony optimization algorithm with
two highlights. First, candidate set strategy is adopted to rapid
convergence speed. Second, a dynamic updating rule for
heuristic parameter based on entropy to improve the
performance in solving TSP. Algorithms are tested on
benchmark problems from TSPLIB and test results are
presented. From our experiments, the proposed algorithm has
better performance than the conventional ACO algorithm and
the results of the proposed algorithms are found to be
satisfactory.
INTRODUCTION
Swarm intelligence is a relatively new approach to
problem solving that takes inspiration from the social
behaviors of insects and of other animals. The attempt in the
research of computer technology is to develop algorithms
inspired by insect behavior to solve optimization problems.
ant colony optimization (ACO) is one of the most successful
techniques in the wider field of swarm intelligence. Many
research works have been devoted to ant colony optimization
techniques in different areas. It is a relatively novel
meta-heuristic technique and has been successfully used in
many applications especially problems that belong to the
combinatorial optimization. ACO inspired by the foraging
behavior of real ant was first introduced by dorigo and his
colleagues ([1], [2]) in early 1990s and has become one of the
most efficient algorithms for TSP. ACO is based on the
pheromone trail laying and following behavior of some ant
species, a behavior that was shown to allow real ant colonies
to find shortest paths between their colony and food sources.
These ants deposit pheromone on the ground in order to mark
some favorable path that should be followed by other
members of the colony. The ants move according to the amount of pheromones, the richer the pheromone trail on a
path is, the more likely it would be followed by other ants. So
a shorter path has a higher amount of pheromone in
probability, ants will tend to choose a shorter path. Artificial
ants imitate the behavior of real ants how they forage the food,
but can solve much more complicated problem than real ants
can. Ant colony optimization exploits a similar mechanism
for solving optimization problems.
From the early nineties, when the first ant colony
optimization algorithm was proposed, ACO attracted the
attention of increasing numbers of researchers and many
successful applications are now available. ACO has been
widely applied to solving various combinatorial optimization
problems such as traveling salesman problem (TSP),
job-shop scheduling problem (JSP), vehicle routing problem
(VRP), quadratic assignment problem (QAP),
Weapon-Target Assignment problems (WTA), etc.
ACO can be used to find the solutions of difficult
combinatorial optimization problems and it enjoys a rapidly
growing popularity. Although ACO has a powerful capacity
to find out solutions to combinatorial optimization problems,
it has the problems of stagnation and premature convergence
and the convergence speed of ACO is always slow. Those
problems will be more obvious when the problem size
increases. Therefore, several extensions and improvements
versions of the original ACO algorithm were introduced over
the years. Various adaptations: an algorithm based on the
basis of the ant evolution rules [3], dynamic control of
solution construction and mergence of local search ([4], [5],
[6]), new pheromone updating strategies [7], max-min ant
system [8], a strategy is to partition artificial ants into two
groups: scout ants and common ants [9], using candidate lists
strategies ([10], [11]), dynamic ant colony system with three
level updates ([12-13]) and using the path selection
controlled by information entropy [15] are studied to improve
the quality of the final solution and lead to speedup of the
algorithm. All these studies have contributed to the
improvement of the ACO to some extent, but they have little
obvious effect on increasing the convergence speed and
obtaining the global optimal solution. In the proposed system,
the main modifications introduced by ACO are the following.
First, ACO is more effective as the candidate set strategy is
adopted. This modification reduces the size of the search
space for the ant colony algorithm. Second, information
entropy is introduced which is adjust the algorithm’s
parameters. Additionally, the best performing ACO
algorithms for the TSP improve the solutions generated by
the ants using local search algorithms. The experiment results
show that the algorithm proposed in this study can
substantially increase the convergence speed of the ACO In this paper, a modified ant colony system for solving
TSP using candidate set strategy and dynamic updating of
heuristic parameter is developed. This algorithm is used to
produce near-optimal solutions to the TSP. The paper is
organized as follows: Section 2 describes traveling salesman
problem. Section 3 and 4 illustrates the algorithm of ant
colony system. Section 5 presents candidate list strategy
approach to ACO and the other is analysis of heuristic
parameter to be updated in the algorithm. Section 6presents
the proposed algorithm for TSP. In Section 7, the proposed
method is employed into several TSP problems and the
results of our approach and of traditional ACO are reported.
Finally, Section 8 makes the conclusion.
II. TRAVELING SALESMAN PROBLEM
Traveling salesman problem (TSP) is a well known,
popular and extensively studied problem in the field of
combinatorial optimization and attracts computer scientists,
mathematicians and others. Its statement is deceptively
simple, but yet it remains one of the most challenging
problems in operational research. It also an optimization
problem of finding a shortest closed tour that visits all the
given cities. It is known as a classical NP-complete problem,
which has extremely large search spaces and is very difficult
to solve.
The definition of a TSP is: given N cities, if a salesman
starting from his home city is to visit each city exactly once
and then return home, find the order of a tour such that the
total distances (cost) traveled is minimum. Cost can be
distance, time, money, energy, etc. TSP is an NP-hard
problem and researchers especially mathematicians and
scientists have been studying to develop efficient solving
methods since 1950’s. Because it is so easy to describe and so
difficult to solve. Graph theory defines the problem as
finding the Hamiltonian cycle with the least weight for a
given complete weighted graph.
The traveling salesman problem is widespread in
engineering applications. It has been employed in designing
hardware devices and radio electronic devices, in
communications, in the architecture of computational
networks, etc. In addition, some industrial problems such as
machine scheduling, cellular manufacturing and frequency
assignment problems can be formulated as a TSP.
A complete weighted graph G=(N, E) can be used to
represent a TSP, where N is the set of n cities and E is the set
of edges (paths) fully connecting all cities. Each edge(i,j)∈E
is assigned a cost dij, which is the distance between cities i
and j. dij can be defined in the Euclidean space and is given as
follows:
(1)
One direct solving method is to select the route which has
minimum total cost for all possible permutations of N cities.
The number of permutations can be very large for even 40
cities. Every tour is represented in 2n different ways (for
symmetrical TSP). Since there are n! possible ways to
permute n numbers, the size of the search space is then THEORY AND MATHEMATICAL MODEL OF ANT
ALGORITHM
A. The Theory of Ant Algorithm
The Ant Colony Optimization techniques has emerged
recently as a relatively novel meta-heuristic for hard
combinational optimization problems. It is designed to
simulate the ability of ant colonies to determine shortest paths
to food. Although individual ants posses few capabilities,
their operation as a colony is capable of complex behavior.
Real ants can indirectly communicate by pheromone
information without using visual cues and are capable of
finding the shortest path between food sources and their nests.
The ant deposits pheromone on the trail while walking, and
the other ants follow the pheromone trails with some
probability which are proportioned to the density of the
pheromone. The more ants walk on a trail, the more
pheromone is deposited on it and more and more ants follow
the trail. Through this mechanism, ants will eventually find
the shortest path. Artificial ants imitate the behavior of real
ants how they forage the food, but can solve much more
complicated problems than real ants can. A search algorithm
with such concept is called Ant Colony Optimization. Figure
1 shows how the ants find the shortest path