Ant Colony Optimization - Tsp

ABSTRACT

The purpose of this paper is to analyze and implement Ant Colony Optimization (ACO) framework to solve traveling sales man (TSP) problem. TSP is known to be a NP-hard problem and therefore it draws the attention of many algorithm designers and researchers in computer science. Given n cities, traveling sales man must visit each city exactly once, without repeating any cities in the most cost effective (i.e. shortest path) way is the theme of TSP. As n gets larger, it is virtually impossible to solve with current computing devices, algorithms, OR combination of both.

Metaheuristic family member of algorithms such as ACO, however can be use to find optimal solution (or) best possible answer by using intelligent guesses based on high probability. ACO was designed by inspiring behavior of ants in finding paths from colony for food. ACO will be introduced in a fashion to be easily understandable by non technical readers, but mathematics and advanced algorithm design techniques will also be presented for technical audience.

INTRODUCTION

As a kid grown up in Myanmar (formerly know as Burma), it was always interesting to observe and play1with insects, especially ants. As a rainy season approaches, somewhere between May and August, ants always seemed to know that it was coming and they were all rushing to forage food. Relationship between ants and their anticipation of a rain was a mystery. How did those ants know that rain was coming? They didn't seem to be much intelligent.

Occasionally, a small piece of meat was placed on the floor to see how ants would react. Few minutes later, several ants would magically show up and they would start to carry a meat, probably into their nest. As they started to move a piece of meat, other ants would show up and help. Ants doesn't seem to be talking (OR) has a vision, but how did they know that they their fellow ants were in need of help. I had an impression that the ants communicated via some sort of scent as a kid.

Fast forward 20 years, something about the ants came up again in Professor Lucci's2class, in one of his lectures for Ant Colony Optimization(ACO). ACO is an algorithm designed for discrete optimization problems developed with inspiration from observations of how some ant species forage for food.

Although individual ants performs relatively simple tasks, as a collection of agents however, they can perform quite complicated tasks efficiently. For example, ants are very efficient at clustering of dead bodies and building sophisticated ventilation systems collectively as if they were following orders from someone. Ants coordinated their activity via stigmergy, a form of indirect communication by depositing chemicals known as pheromones.

ACO and other "ant algorithms" uses models from the observation of ant's behavior, and uses these models as a source of inspiration for the design of novel algorithms for the solution of optimization and distributed control problems. ACO is one of the successful algorithms based on the ants model and it is the subject of this paper to use ACO to solve Traveling Sales Man problem.

TRAVELING SALES PROBLEM

A brief introduction of TSP will be presented for readers who does not have technical background in the area. Given a number of cities and travel cost, traveling sales man must visit each city exactly once, with any repetition, by choosing most cost effective route. More formally, the TSP can be represented by a complete weighted graph G = (N,E) with N being the set of nodes representing the cities and E being the set of edges (or) lines connecting between the cities. One can also think of TSP as finding a minimum Hamiltonian circuit of a graph, where a Hamiltonian circuit is a closed path visiting each of the n = |N| nodes of G exactly once. Thus, an optimal solution to the TSP is a permutation of the node indices {1, 2, . . . n} such that the length is minimal, where is given by

TSP was chosen to optimize with ACO for very simple reason. It is an important NP-hard problem. Therefore, if an algorithms performs well on known NP problem then it is very likely that it will perform well on other class of NP complete problems. Marco Dorigo [Ant Colony Optimization 2004] said, "the history of ACO shows that very often the most efficient ACO algorithms for the TSP were also found to be among the most efficient ones for a wide variety of other problems."

POSITIVE REINFORCEMENT

Before getting deep into algorithms lets analyze why there is such a hype (or) noise among scientists and researchers who came up with algorithms by inspiring behavior of ants. What make ants so inspiring? In part 1 of the picture below, a green arrow (a)indicates that an ant is in exploration mode. For example, ants will always explore their neighborhood in an anticipation to find more food. Once the source of food is found, the ant is headed back to the nest to recruit more ants as shown in yellow arrow (b). After the recruit, ants would follow random paths at branches as shown in part 2. Eventually ants have managed to find the shortest path as shown in part 3. In the final stage ants started to exploit, following congested path by avoiding longer paths. Notice there is one still exploring! Why?

Fig. 1: Selection of short path as time progresses (image source wikipedia.com)

At this time it is reasonable to start thinking how did the ant's managed to find the shortest path. Apparently, they do so by depositing a chemical from their body known as pheromones, while traveling back and forth between the food and the nest. In the beginning of the tour there is no pheromone on the branches. Therefore, the ants do not have any preference over one branch for another and they select with the same probability for any of the branches. Yet, because of random fluctuations, a few more ants will select one branch over the other. Because ants deposit pheromone while walking, a larger number of ants on