08-05-2013, 12:42 PM
Ant Colony Optimization
Ant Colony Optimization.docx (Size: 335.62 KB / Downloads: 53)
INTRODUCTION
In this month’s column I present C# code that implements an Ant Colony Optimization (ACO) algorithm to solve the Traveling Salesman Problem (TSP). An ACO algorithm is an artificial intelligence technique based on the pheromone-laying behavior of ants; it can be used to find solutions to exceedingly complex problems that seek the optimal path through a graph. The best way to see where I’m headed is to take a look at the screenshot in Figure 1. In this case, the demo is solving an instance of the TSP with the goal of finding the shortest path that visits each of 60 cities exactly once. The demo program uses four ants; each ant represents a potential solution. ACO requires the specification of several parameters such as the pheromone influence factor (alpha) and the pheromone evaporation coefficient (rho), which I’ll explain later. The four ants are initialized to random trails through the 60 cities; after initialization, the best ant has a shortest trail length of 245.0 units. The key idea of ACO is the use of simulated pheromones, which attract ants to better trails through the graph. The main processing loop alternates between updating the ant trails based on the current pheromone values and updating the pheromones based on the new ant trails. After the maximum number of times (1,000) through the main processing loop, the program displays the best trail found and its corresponding length (61.0 units).
The 60-city graph is artificially constructed so that every city is connected to every other city, and the distance between any two cities is a random value between 1.0 and 8.0 arbitrary units (miles, km and so forth). There’s no easy way to solve the TSP. With 60 cities, assuming you can start at any city and go either forward or backward, and that all cities are connected, there are a total of (60 - 1)! / 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 possible solutions. Even if you could evaluate 1 billion possible solutions per second, it would take about 2.2 * 1063 years to check them all, which is many times longer than the estimated age of the universe.
ACO is a meta-heuristic, meaning that it’s a general framework that can be used to create a specific algorithm to solve a specific graph path problem. Although ACO was proposed in a 1991 doctoral thesis by M. Dorigo, the first detailed description of the algorithm is generally attributed to a 1996 follow-up paper by M. Dorigo, V. Maniezzo and A. Colorni. Since then, ACO has been widely studied and modified, but, somewhat curiously, very few complete and correct implementations are available online.
Updating the Ants
The key to the ACO algorithm is the process that updates each ant and trail by constructing a new—we hope better—trail based on the pheromone and distance information. Take a look at Figure 3. Suppose we have a small graph with just five cities. In Figure 3 the new trail for an ant is under construction. The trail starts at city 1, then goes to city 3, and the update algorithm is determining the next city. Now suppose the pheromone and distance information is as shown in the image. The first step in determining the next city is constructing an array I’ve called “taueta” (because the original research paper used the Greek letters tau and eta). The taueta value is the value of the pheromone on the edge raised to the alpha power, times one over the distance value raised to the beta power. Recall that alpha and beta are global constants that must be specified. Here I’ll assume that alpha is 3 and beta is 2. The taueta values for city 1 and city 3 aren’t computed because they’re already in the current trail. Notice that larger values of the pheromone increase taueta, but larger distances decrease taueta.
Wrapping Up
Let me emphasize that there are many variations of ACO; the version I’ve presented here is just one of many possible approaches. ACO advocates have applied the algorithm to a wide range of combinatorial optimization problems. Other combinatorial opti¬mization algorithms based on the behavior of natural systems include Simulated Annealing (SA), which I covered last month (msdn.microsoftmagazine/hh708758), and Simulated Bee Colony (SBC), which I covered in my April 2011 column (msdn.microsoftmagazine/gg983491). Each approach has strengths and weaknesses. In my opinion, ACO is best-suited for problems that closely resemble the Traveling Salesman Problem, while SA and SBC are better for more general combinatorial optimization problems, such as scheduling.
ACO, in common with other meta-heuristics based on natural systems, is quite sensitive to your choice of free global parameters—alpha, beta and so on. Although there has been quite a bit of research on ACO parameters, the general consensus is that you must experiment a bit with free parameters to get the best combination of performance and solution quality.
Ant Colony Optimization.docx (Size: 335.62 KB / Downloads: 53)
INTRODUCTION
In this month’s column I present C# code that implements an Ant Colony Optimization (ACO) algorithm to solve the Traveling Salesman Problem (TSP). An ACO algorithm is an artificial intelligence technique based on the pheromone-laying behavior of ants; it can be used to find solutions to exceedingly complex problems that seek the optimal path through a graph. The best way to see where I’m headed is to take a look at the screenshot in Figure 1. In this case, the demo is solving an instance of the TSP with the goal of finding the shortest path that visits each of 60 cities exactly once. The demo program uses four ants; each ant represents a potential solution. ACO requires the specification of several parameters such as the pheromone influence factor (alpha) and the pheromone evaporation coefficient (rho), which I’ll explain later. The four ants are initialized to random trails through the 60 cities; after initialization, the best ant has a shortest trail length of 245.0 units. The key idea of ACO is the use of simulated pheromones, which attract ants to better trails through the graph. The main processing loop alternates between updating the ant trails based on the current pheromone values and updating the pheromones based on the new ant trails. After the maximum number of times (1,000) through the main processing loop, the program displays the best trail found and its corresponding length (61.0 units).
The 60-city graph is artificially constructed so that every city is connected to every other city, and the distance between any two cities is a random value between 1.0 and 8.0 arbitrary units (miles, km and so forth). There’s no easy way to solve the TSP. With 60 cities, assuming you can start at any city and go either forward or backward, and that all cities are connected, there are a total of (60 - 1)! / 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 possible solutions. Even if you could evaluate 1 billion possible solutions per second, it would take about 2.2 * 1063 years to check them all, which is many times longer than the estimated age of the universe.
ACO is a meta-heuristic, meaning that it’s a general framework that can be used to create a specific algorithm to solve a specific graph path problem. Although ACO was proposed in a 1991 doctoral thesis by M. Dorigo, the first detailed description of the algorithm is generally attributed to a 1996 follow-up paper by M. Dorigo, V. Maniezzo and A. Colorni. Since then, ACO has been widely studied and modified, but, somewhat curiously, very few complete and correct implementations are available online.
Updating the Ants
The key to the ACO algorithm is the process that updates each ant and trail by constructing a new—we hope better—trail based on the pheromone and distance information. Take a look at Figure 3. Suppose we have a small graph with just five cities. In Figure 3 the new trail for an ant is under construction. The trail starts at city 1, then goes to city 3, and the update algorithm is determining the next city. Now suppose the pheromone and distance information is as shown in the image. The first step in determining the next city is constructing an array I’ve called “taueta” (because the original research paper used the Greek letters tau and eta). The taueta value is the value of the pheromone on the edge raised to the alpha power, times one over the distance value raised to the beta power. Recall that alpha and beta are global constants that must be specified. Here I’ll assume that alpha is 3 and beta is 2. The taueta values for city 1 and city 3 aren’t computed because they’re already in the current trail. Notice that larger values of the pheromone increase taueta, but larger distances decrease taueta.
Wrapping Up
Let me emphasize that there are many variations of ACO; the version I’ve presented here is just one of many possible approaches. ACO advocates have applied the algorithm to a wide range of combinatorial optimization problems. Other combinatorial opti¬mization algorithms based on the behavior of natural systems include Simulated Annealing (SA), which I covered last month (msdn.microsoftmagazine/hh708758), and Simulated Bee Colony (SBC), which I covered in my April 2011 column (msdn.microsoftmagazine/gg983491). Each approach has strengths and weaknesses. In my opinion, ACO is best-suited for problems that closely resemble the Traveling Salesman Problem, while SA and SBC are better for more general combinatorial optimization problems, such as scheduling.
ACO, in common with other meta-heuristics based on natural systems, is quite sensitive to your choice of free global parameters—alpha, beta and so on. Although there has been quite a bit of research on ACO parameters, the general consensus is that you must experiment a bit with free parameters to get the best combination of performance and solution quality.