|
|
|
Solving The Traveling Salesman Problem - Nature's Way by Mike
TSP BackgroundThe origin of the traveling salesman problem can be traced back to mathematician and economist Karl Menger in Austria in the 1920's and has since gained notoriety as a difficult problem in combinatorial optimization. The puzzle stated more formally is: given a number of cities and the cost to travel between any two, find the least expensive tour for visiting each of the cities once and returning to the city of origin. For all but the smallest number of cities to visit, examining all possible tours one by one is out of the question because of their large number. For n cities, the number of possible tours is n factorial (n!). So for example, a small TSP problem with only 13 cities has over 6 billion possible tours. Mathematicians and computer scientists have developed many algorithms for efficiently searching the TSP solution space for the shortest path without having to perform an exhaustive search. In addition to its importance in mathematics, the TSP problem has application in many scheduling problems including network routing, urban transportation systems, and printed circuit manufacturing. Simulated AnnealingSimulated annealing (SA) is a search algorithm for finding a good approximation to the global minimum or maximum of a function in a large search space. As applied to the TSP, the function is the cost of the round-trip tour, the search space is the set of all possible tours, and the optimization objective is to find a minimum cost tour. SA is based on the way in which liquids crystallize in the process of annealing. In the annealing process a liquid, initially at high temperature, is slowly cooled. As cooling proceeds, the system becomes more ordered and approaches a frozen state with minimum energy. If the initial temperature of the system is too low or cooling is done too rapidly then the system may not reach a minimum energy state, creating poorly formed crystals. Slow cooling near thermodynamic equilibrium gives the molecules of the liquid more chances of finding optimum configurations with lower internal energy.
In my simulation, I used Bot objects to represent cities and a Group object to represent a tour. Cities are ordered within the tour according to the sequence in which they would be visited. The important controlling parameters are the annealing schedule (initial temperature and rate of reduction) and number of trials to perform for each temperature. The following pseudo code gives the overall logic of the simulation: Create and locate a number of city (Bot) objects
on the screen Genetic AlgorithmLike Simulated annealing, a genetic algorithm (GA) is a search technique used to find approximate solutions to optimization problems. Genetic algorithms are inspired by evolutionary biology and simulate the strategies of natural selection, inheritance, recombination (or crossover) and mutation for evolving optimal solutions.
In my TSP GA algorithm, the population of TSP solutions is maintained in an array, sorted from most fit to least fit. Fitness is assessed based on the inverse of tour distance (1/distance). During each iteration, a probabilistic rule called the "roulette wheel" method is used to decide which tours to select for mating - the higher a tour's fitness the higher probability that it will be selected. Mating pairs of solutions bear two offspring, each inheriting pieces of their parent's tours in a process called recombination. Recombination is performed by splicing a "piece" of one parent's tour into a copy of the other parent's tour, taking care to avoid duplicate cities. After recombination, the offspring tours are mutated, typically with a small probability (less than 20%). There are two options for mutation: the tour positions of two randomly chosen cities are swapped (called inversion), or the position of one randomly chosen city is moved to another randomly chosen position in the tour. After the new offspring are created, they replace the least fittest solutions from the previous iteration, and then the population array is resorted based on fitness. The simulation ends after a specified number of iterations. Important controlling parameters are the population size, the number
of mating pairs per iteration, crossover type, mutation type, and mutation
rate.
The
following pseudo code gives the overall logic of the simulation: Ant Colony Optimization
In my ACO simulation, three large arrays (with dimensions n by n where n is the number of cities) are used. A distance array for precalculating all city to city distances, a pheromone array for keeping track of the amount of pheromone trail between all cities, and a delta pheromone array for temporarily storing the pheromone to add to the pheromone array at the end of a simulation iteration. The delta pheromone array is needed so that all ants sense the results of the previous iteration simultaneously. Important controlling parameters are the number of ants, parameters for computing an ant's next move probability, the amount of pheromone to add per tour, and the pheromone evaporation rate. The following pseudo code gives the overall logic of the simulation: Create and locate a number of city (bot) objects
on the screen Summary of What I LearnedI tested the three algorithms on three geometric patterns of increasing number of cities. The three patterns had 16, 44, and 91 cities respectively. Here are some of my observations:
PerformanceIt is difficult to judge performance of the three techniques based on convergence time because I opted to code these for clarity of understanding rather than for efficiency. For example, there are improvements to be made in the way the cost function is calculated for SA, where I calculate the cost by summing distances over the entire tour, rather than considering only those segments that are affected by the perturbation. Also, the SA and ACO draw both intermediate tours (blue) as well as the best tour (red), and so must update the screen far more often than GA, which only draws the best tour. For a large number of cities, these inefficiencies are probably significant. However, a couple of observations about performance seem obvious, the above not withstanding. For the 16 city problem, the GA seems to converge on an answer significantly faster than SA and ACO, with convergence resulting in an optimum solution most of the time. For the 44 and 91 city cases, it was no contest - the ACO solved these as fast as it did the 16 city problem. I think this is because ACO optimizes the traversal locally, based on a local cost measure (visibility and trail to the next city on the tour), whereas the SA and GA judge each potential solution using a global cost measure (length of the entire tour). For large number of cities, improving the solution via global cost measures can require a very large number of perturbation attempts.
MemoryThere are large differences in the amount of memory utilized by each of the algorithms. SA needs the least as it does not require any arrays. GA requires several population arrays dimensioned to up to about 5 times the number of cities. However, ACO requires a substantial amount of memory above what is required by the other two techniques - about 2 or 3 times the number of cities squared in order to store pheromone trails and precalculated city to city distances. The distance array is actually not needed, as the distances between cities can be computed on the fly (but less efficiently).
Ease of UseMy favorite of the three techniques is SA because of its simplicity. This simplicity leads to more flexibility, making it very easy to adapt SA to a wide range of optimization problems, not just TSP. All you need for SA is a cost function and some reasonable way of making perturbations. On the other extreme is ACO, which because of its structure, is difficult to adapt to problems other than those which can be formulated in terms of a graph traversal problem. Both GA and ACO have more parameters than SA and a considerable amount of tweaking is needed to find optimal settings for each problem.
On a Philosophical Note...I'd like to share a realization that occurred to me while I was working on this project. During my almost 25 years working as a scientist in a large corporation, there has been much discussion about the seemingly competing roles of process standardization versus the fostering of creativity and ingenuity - or freedom to act "outside the box". I believe there is something to learn from a common underpinning in these nature-inspired optimization algorithms. In all three, agents dutifully follow a common set of rules for decision making. The fact that they can rely on each other to abide by the same set of rules is in part why they are able to collectively reach a global optimum. If on the other hand, each selfishly sought their own local optimum at the expense of their teammates, failure in a global sense would surely be guaranteed. Yet, a critically important aspect of all of these algorithms is their heavy reliance on the occasional "errant" departure from the norm. In the case of GA, the departure takes place in the form of mutation, in SA, the acceptance of a larger cost solution at high temperatures, and in ACO, the occasional mis-wandering by the ant off the beaten path. These departures are critical for preventing the system from becoming trapped in local minimums - like ants following each other in an endless circle, or not unlike corporate drones faithfully reinforcing a sub-optimal behavior because "its the way we have always done it". What may seem like an errant departure from the norm at the time, may eventually lead to a better solution in the long run. So the moral of the story - both process standardization AND "ingenuity" are necessary to move towards a global optimum and in this sense, they are not competing mantras, but integral components of a nature-tested winning strategy. The TSP simulations discussed on this page are included with the VisualBots software download. References:http://www.tsp.gatech.edu - The best site on the web for information on the TSP. http://www.tsplib.com - A source for TSP problem sets. Ant Colony Optimization, Genetic Algorithm, and Simulated Annealing on Wikipedia - the free encyclopedia. Back to projects main page <<prev project next project>>
|
|||||||||||||||||||||||
|
|||||||||||||||||||||||||
| Copyright © | This sited last updated Jan 05, 2008 |
