Algorithm To Solve Travelling Salesman Problem Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Ant colony optimization, which is a combination of Swarm Intelligence and Bio-inspired Artificial Intelligence, is an algorithm that simulates the behavior of ants to solve complex problems. Ants are able to solve these problems by communicating through pheromones. The intelligence is due to the self-organizational capabilities of the ants, which in turn arises from these very pheromone levels. Drawing an analogy, the travelling salesman problem can be solved using ACO algorithm since it is dynamic in nature and preferably should be solved using self-organizational algorithms. ACO can be used to describe the different travelling cases. The problem with the application of ACO in TSP solution is that it becomes prone to long execution time, stagnation and early convergence as the size of the problem set increases. These limitations can be overcome using two methods - one, to use a defined and a lower bound value of the pheromone levels and second, to facilitate dynamic update of heuristics. The improved ACO proves to be quite more efficient in its solution search when compared to its traditional counterpart while solving NP Hard problems like the TSP.

Introduction: It has long been a matter of research in the field of Computational Mathematics to implement an algorithm that emulates the social behavior of insects like ants which have self-organizational and optimization capabilities in order to solve combinatorial and optimization problems[1]. Ants, while walking from their nest to food and back, release pheromone and the other ants follow these trails to choose their paths. Since a shorter path has a higher probability of greater pheromone trail level, over a period of time, ants tend to choose this optimal path. Analogous to this, the ACO has artificial ants that walk on the problem graph, building solutions and depositing artificial pheromone on the graph in such a way that the following artificial ants can construct better solutions using the pheromone trail[3]. But this algorithm, as already mentioned, is prone to long computation time, stagnation and premature convergence[3,5]. This paper attempts to overcome these drawbacks and improve the traditional ACO by differing in that it uses lower value of pheromone trail and the heuristic parameter is not a predefined value rather gets updated dynamically.

The problem of stagnation occurs because of the following reason - the evaporation of pheromone over time leads to its concentration on the path close to zero which causes the algorithm to stop and explore for new possibility and it cannot find a better traversal[2,3]. This problem can be solved by using a lower value of pheromone trail bound, that is, by increasing the sensitivity of the ants towards what level of pheromone can still be treated as considerable to proceed. The second problem of poor heuristics arises due to the fact that the pheromone gets deposited only on the paths after the ants walk through points on the paths and since the paths chosen by ants in the initial stages are not necessarily the optimal ones but still having higher concentration of pheromone due to the ants walking initially, the following ants tend to proceed similarly[2,3,4]. Thus, to introduce diversity in paths, it is necessary to suppress the effect of the pheromone or the sensitivity towards its levels for paths traversed during the early stages of the problem in contrast to emphasis on these levels for the later stages since by then, the optimal paths must have been indicated by greater levels of pheromone.

Travelling Salesman Problem: The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

The network of cities can be considered as a graph G (V, E) where V indicates the set of all vertices or cities and E indicates the set of all edges or paths between the cities[1,5]. Each edge (i,j) between vertices or cities we and j, is assigned a weight or a cost d(we,j) = |v(i)-v(j)| or |v(j)-v(i)|, where v(i) and v(j) represent the position vectors of the cities we and j respectively. The solution of the TSP is a Hamiltonian circuit as it visits the cities (vertices) exactly once and forms a cycle, which is the definition of a Hamiltonian circuit. Mathematically, we must find f(π) = Σn-1i=1 d π(i) π(i+1) + d π(n) π(1), where f(π) is the traveling length of the permutation π of the cities. In a symmetric TSP, d(Ij)=d(ji) for each pair we,j, that is, the length of the edge connecting cities we, j is independent of whether one goes from we to j or vice versa. In an asymmetric TSP, this is not the case.

The space complexity increases factorially with the number of cities in a TSP and the relation is given by: n(S)=(c-1)! Where n(S) is the cardinality of the solution set and c is the number of cities[2-4]. Since for large values of c, an exhaustive search algorithm would prove to be infeasible, we employ approximate heuristic algorithms to solve problems involving such great problem set size at low execution time and space consumption. The heuristic approaches applied to the TSP are of two types - one, tour construction heuristics and two, tour optimization heuristics. While the former attempts to construct optimal and feasible tours using certain heuristic rules by choosing a random city as the starting point without trying to improve upon or optimize this constructed tour, the latter aims to achieve optimization of the tour by exchanging the edges until an optimal length of the tour is achieved. Typical tour construction algorithms include ACO, nearest-neighbour and greedy while the optimization heuristics include 2-opt, 3-opt.

Ant Colony Optimization: ACO algorithms were firstly introduced by Dorigo and are novel meta-heuristic optimization algorithms[2-5]. ACO can be applied to solve distributed optimization problems among many cooperating simple agents that are not aware of their cooperative behavior. The study of ACO is to investigate the patterns derived from the observation of real ants' 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 ants release pheromone on the ground while walking through a path. Thus, a pheromone trail is formed on the traversed way. Supposedly, a shorter path should have a higher amount of pheromone in probability. As a consequence, ants may 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 problems than real ants can. A search algorithm with such concept is called Ant Colony Optimization (ACO)

ACO is a meta-heuristic in which a colony of artificial ants cooperates in finding good solutions of discrete optimization problems. Cooperation is a key design component of ACO algorithms because the choice is to allocate the computational resources to a set of relatively simple agents (artificial ants) that communicate indirectly by pheromone information.

Procedure: ACO metaheuristic

while (not in termination condition)

Construct Ant solutions

Pheromone Update

Daemon Actions {optional}

end while

end procedure

"Construction of Ants Solutions" manages a colony of ants that cooperatively and interactively visit adjacent states of the considered problem by moving through feasible neighbour nodes of the graph. The movements are based on a local ant-decision rule that makes use of pheromone trails and heuristic information. In this way, ants incrementally build solutions to the problem.

Pheromone Update consists of pheromone evaporation and new pheromone deposition. Pheromone evaporation is a process of decreasing the intensity of pheromone trails over time. This process guides ants to explore possible paths, and it avoids too rapid convergence of the algorithm towards a suboptimal region. Pheromone Update is used to implement a useful form of forgetting which enables the ants to forage the promising area of the search space.

The Daemon Actions procedure is used to implement centralized actions which cannot be performed by a single ant. Daemon Actions are optional for ACO algorithms. The idea is to collect useful global information that can be used to decide whether it is useful or not and to deposit additional pheromone to bias the search process from a non-local perspective.

In ACO, when located at city i, ant k chooses the next city j according to the so-called pseudorandom proportional (ant-decision) rule given by

where q is a random variable uniformly distributed in [0,1], q0 (0≤ q0≤1) is a pre-defined parameter, τiu is the pheromone trail, ηiu = 1/diu is the heuristic information (heuristic visibility), α and β are referred to as the visibility and the trail intensity and are two adjustable positive parameters that control the relative weights of the pheromone trail and of the heuristic information, and allowedk(i) is the set of unvisited cities yet when ant k is located at city i. J is a random variable and is a tradeoff between visibility and trail intensity at iteration t. J is selected according to the transition probability given by

Global update is performed after iteration. When all ants have completed their tours, only the shortest tour is allowed to increase pheromone by the following equation:

where 0≤ψ≤ 1 is a decay parameter, Δτ elitist i j =(Lelitist) -1, and Lelitist is the length of the globally best tour. In above eqn, the deposited pheromone is discounted by a factor ψ. Global update gives the best tour higher reinforcement for the pheromone trails and the amount of the pheromone increases on the edges of the tour.

While constructing a tour, ant k is located at city i and selects city j  allowedk(t), the local update is performed by the following equation:

τi j (t)=(1-ρ)τi j(t)+ρτ0 . . . . . . . (6)

where 0≤ρ≤1 is a decay parameter, τ0=(n. Lnn )-1

is the initial values of the pheromone trails, where n is the number of cities in the TSP and Lnn is the cost produced by the nearest neighbor heuristic [4]. Eq. (6) is mainly to avoid very strong pheromone paths to be chosen by other ants and to increase the explorative probability for other paths. Once the edge between city i and city j has been visited by all ants, the local updating rule makes pheromone level diminish on the edge. This rule enables the visited edges less and less attractive when ants traverse the edges and also indirectly increases the exploration of not yet visited edges. In other words, the role of the local updating rule is to shuffle the tours so that the early visited cities in one ant's tour may be possibly explored later in other ants' tours.

The Proposed Mechanisms:

Although ACO has very good search capability for optimization problems, it may have the problems of stagnation and premature convergence. Those problems will be more evident when the complexities of the considered problems increase. In this research, two issues in ACO have been studied. The first one is to analyze the local update effects and the initial pheromone values. A lower pheromone trail bound is proposed in this research. The other is to investigate the characteristics of one heuristic parameter required in ACO. we then propose a way of dynamically modifying that parameter. This approach is based on the entropy measure of the pheromone in ACO.

Analysis of Pheromone Trail Limit

In ACO, the elitist strategy of global update enables that the pheromone trails of the currently best tour will continuously obtain positive feedback and other trails in the pheromone matrix evaporate in the process. It is easy to see that such an elitist strategy may lead to a stagnation behavior because the currently best tour may be a suboptimal tour and thus, the edges of this suboptimal tour will have an excessive growth of pheromone. Because the evaporation of the pheromone trails is in an exponential speed, the amount of pheromone for some unvisited edges will decrease to close to zero after iterations. If those unvisited paths edges are in the optimal path, the algorithm may not be able to visit them in the later search process. In that case, we may say that the search is trapped into suboptimal solutions.

In this study, in order to avoid such cases, a value Ï„min is considered as the minimal. we analyze two conditions for the selection of Ï„min in the following. First, the initial values of pheromone are set to Ï„0= (n.Lnn )-1, where Lnn is produced by the nearest neighbour algorithm. Because the initial values of pheromone are the same for all trails, the tour length of the first iteration is close to Lnn. When the algorithm continues, Lelitist will be shorter and may exceed Lnn. As the number of cities increases, ants find it very hard to find the optimal solution in relatively short iterations. However, if we set the minimal bound to Ï„min =(nïƒ-Lelitist) -1, which is close to the initial pheromone values, this bound will not fulfill the principle of positive feedback because edges in poor solutions are also bounded to close to the initial value.

Secondly, the effects of the local updating rule are to

make visited edges less and less attractive. In fact, for any Ï„i j, it will satisfy

lim k→∞ τi j (k) = τ0

where k is the number of ants, Ï„0 is the initial values of pheromone.

Ï„0 is the lowest bound and is asymptotically converged when using the local updating rule. From this viewpoint, it strengthens our assertion about the minimal bound of the pheromone trails will rapidly reach Ï„0 in the first selection of Ï„min. In our implementation, Ï„min is selected as:

Ï„min = 1/(c.n2.Lelitist )

where Lelitist is the length of the currently best tour, n is the number of cities, and c is a constant and is determined heuristically. In our selection, we only give a value greater than zero and the minimal value of trails will decrease as the number of cities increases in order to ensure complete search. In order to see which value for c is proper, three TSP instances KoA100, KroB150, and KroA200 taken from TSPLIB [5] are used as the benchmarks. The experimental results are shown in Table 1 and a good value for c is found to be 2. It should be notice that the value of c makes no significant influence on the search performance as shown in the table. Figure 1 shows the change history of the pheromone value on an edge (edge(1,2)) in the KroA100 TSP instance while using different values for the minimal bound. The solid red line is the initial pheromone value Ï„0 and the bold dotted light-blue line is the lower pheromone trail bound Ï„min = (2ïƒ- n2ïƒ-Llitist )-1. The purple, green and bold dotted blue lines are the variation of pheromone on edge (1,2) while using a lower bound, Ï„min = (2. n2.Llitist )-1, and Ï„min =0 (i.e., no bound is used), Ï„min = (nïƒ-Llitist )-1, respectively. It can be found that when we set a suitably minimal bound, the pheromone amount (the purple line) is always higher than that of without a minimal bound (the green line) especially the portion marked in the figure (after 500 iterations). The pheromone trail will become very small

In this implementation of the use of lower trail bounds, an interesting phenomenon exists. Table 3 shows the executing times for two TSP instances with the lower bound and without the lower bound. Their search performances

Dynamic Heuristic Parameter:

In ACO algorithms, Eq. (3) or (4) plays an important role in selecting solution paths. In the equation, there are two terms, the pheromone trail (τiu) and the heuristic information (ηiu). α and β are two adjustable positive parameters controlling the relative weights of the pheromone trail and of the heuristic information. The heuristic information is essential in generating superior quality tours in the initial search stages. It is because the values of the pheromone trails do not have much information in the early stage of learning and cannot guide the artificial ants in constructing good tours. In this situation, the heuristic parameter may be set to a large value. On the other hand, in the later stage, the heuristic parameter may need a small value because the pheromone trails may have collected enough information to behavior as required and the heuristic information may mislead the search due to its locality. Thus, in this situation, we may need a small value for the heuristic parameter. As mentioned earlier,

the heuristic parameter is set as a constant in traditional ACO algorithms. In order to show the above phenomena, we consider several TSP instances for different fixed heuristic parameters. Fig. 2 shows the results from several TSP instances for different fixed heuristic parameters. Here, we have taken the average of 30 runs. In the initial phases of the search, a high value of heuristic parameter can always provide high quality tours. This means that the influence of pheromone is greatly reduced, and ants are able to search other paths in constructing feasible solutions. It is evident that a small value of the heuristic parameter may result in bad performance in the early stage of learning. Nevertheless, a small value of the heuristic parameter can have good performance when the search process lasts long enough. Thus, it is intuitive to use an adaptive heuristic parameter for ACO. In this study, we intend to propose a way of designing an adaptive heuristic parameter for ACO such that the search performance can be better.

Now, the problem is how the heuristic parameter

adapts. Traditionally, parameters required in learning are adapted based on iteration numbers [3]. However, the iteration number may not truly reflect the learning effects. In our study, we propose to use the concept of entropy of the pheromone trails to measure the learning status and then the heuristic parameter is adapted according to this entropy measure.

The concept of entropy is known from Shannon's information theory [4,5]. It is a measure of uncertainty concerning an event and is used to denote the degree of disorder in a system. Shannon's entropy represents the information regarding the probability of occurrence of an event. In ACO, pheromone is the basis of path selection, and the selection is uncertain in nature. Thus, we propose to consider the entropy information in ACO to estimate the variation of the pheromone matrix. Each trail is a discrete random variable in the pheromone matrix. The entropy of a random variable X is defined as

where X represents the trails in the pheromone matrix.

For a symmetric n cities TSP, there are nïƒ-(n-1)/2 distinct pheromone trails and r = nïƒ-(n-1)/2. It is easy to see that when the probability of each trail is the same, H will be the maximum (denoted as Hmax) and is given by

4.3. The Proposed Algorithm

By combining the use of a lower limit bound and the

entropy based adaptive heuristic parameter, the proposed ACO algorithm is given as follows:


In this paper, we have proposed a dynamic updating rule for the heuristic parameters based on entropy to improve the efficiency of ACO. we have also proposed to use a lower pheromone trail bound in the algorithm. Various analyses are conducted our study and reported in this paper. From our experimental results, the proposed method demonstrates excellent performance and is much better than traditional ACO algorithms. It can also be found that the proposed dynamic update of the heuristic parameters based on entropy will generate high quality tours and it can guide ants toward the effective solutions space in the initial search stages.