Издательство InTech, 2008, -212 pp.
In the middle 1930s computer science was yet a not well defined academic discipline. Actually, fundamental concepts, such as ‘algorithm’, or ‘computational problem’, has been formalized just some year before.
In these years the Austrian mathematician Karl Menger invited the research community to consider from a mathematical point of view the following problem taken from the every day life. A traveling salesman has to visit exactly once each one of a list of m cities and then retu to the home city. He knows the cost of traveling from any city i to any other city j. Thus, which is the tour of least possible cost the salesman can take?
The Traveling Salesman Problem (for short, TSP) was bo.
More formally, a TSP instance is given by a complete graph G on a node set V={1,2,…m}, for some integer m, and by a cost function assigning a cost cij to the arc (i,j) , for any i,j in V.
TSP is a representative of a large class of problems known as combinatorial optimization problems. Among them, TSP is one of the most important, since it is very easy to describe, but very difficult to solve.
Actually, TSP belongs to the NP-hard class. Hence, an efficient algorithm for TSP (that is, an algorithm computing, for any TSP instance with m nodes, the tour of least possible cost in polynomial time with respect to m) probably does not exist. More precisely, such an algorithm exists if and only if the two computational classes P and NP coincide, a very improbable hypothesis, according to the last years research developments.
From a practical point of view, it means that it is quite impossible finding an exact algorithm for any TSP instance with m nodes, for large m, that has a behaviour considerably better than the algorithm which computes any of the (m-1)! possible distinct tours, and then retus the least costly one.
If we are looking for applications, a different approach can be used. Given a TSP instance with m nodes, any tour passing once through any city is a feasible solution, and its cost leads to an upper bound to the least possible cost. Algorithms that construct in polynomial time with respect to m feasible solutions, and thus upper bounds for the optimum value, are called heuristics. In general, these algorithms produce solutions but without any quality guarantee as to how far is their cost from the least possible one. If it can be shown that the cost of the retued solution is always less than k times the least possible cost, for some real number k GT 1, the heuristic is called a k-approximation algorithm.
Unfortunately, k-approximation algorithm for TSP are not known, for any k GT
1. Moreover, in a paper appeared in 2000, Papadimitriou, and Vempala have shown that a k-approximation algorithm for TSP for any 97/96 GT k GT 1 exists if and only if P=NP. Hence, also finding a good heuristic for TSP seems very hard.
Better results are known for NP-Hard subproblem of TSP. For example, a 3/2- approximation algorithm is known for Metric TSP (in a metric TSP instance the cost function verifies the triangular inequality).
Anyway, the extreme intractability of TSP has invited many researchers to test new heuristic technique on this problem. The harder is the problem you test on, the more significant are the result you obtain.
A large part of this book is devoted to some bio-inspired heuristic techniques that have been developed in the last years. Such techniques take inspiration from the nature. Actually, the animals that usually form great groups behave by instinct trying to satisfy the group necessity in the best possible way. Similarly, the natural systems develop in order to (locally) minimize their potential by finding a stationary point.
Population-Based Optimization Algorithms for Solving the Travelling Salesman Problem.
Bio-inspired Algorithms for TSP and Generalized TSP.
Approaches to the Travelling Salesman Problem Using Evolutionary Computing Algorithms.
Particle Swarm Optimization Algorithm for the Traveling Salesman Problem.
A Modified Discrete Particle Swarm Optimization Algorithm for the Generalized Traveling Salesman Problem.
Solving TSP by Transiently Chaotic Neural Networks.
A Recurrent Neural Network to Traveling Salesman Problem.
Solving the Probabilistic Travelling Salesman Problem Based on Genetic Algorithm with Queen Selection Scheme.
Niche Pseudo-Parallel Genetic Algorithms for Path Optimization of Autonomous Mobile Robot - A Specific Application of TSP.
The Symmetric Circulant Traveling Salesman Problem.
In the middle 1930s computer science was yet a not well defined academic discipline. Actually, fundamental concepts, such as ‘algorithm’, or ‘computational problem’, has been formalized just some year before.
In these years the Austrian mathematician Karl Menger invited the research community to consider from a mathematical point of view the following problem taken from the every day life. A traveling salesman has to visit exactly once each one of a list of m cities and then retu to the home city. He knows the cost of traveling from any city i to any other city j. Thus, which is the tour of least possible cost the salesman can take?
The Traveling Salesman Problem (for short, TSP) was bo.
More formally, a TSP instance is given by a complete graph G on a node set V={1,2,…m}, for some integer m, and by a cost function assigning a cost cij to the arc (i,j) , for any i,j in V.
TSP is a representative of a large class of problems known as combinatorial optimization problems. Among them, TSP is one of the most important, since it is very easy to describe, but very difficult to solve.
Actually, TSP belongs to the NP-hard class. Hence, an efficient algorithm for TSP (that is, an algorithm computing, for any TSP instance with m nodes, the tour of least possible cost in polynomial time with respect to m) probably does not exist. More precisely, such an algorithm exists if and only if the two computational classes P and NP coincide, a very improbable hypothesis, according to the last years research developments.
From a practical point of view, it means that it is quite impossible finding an exact algorithm for any TSP instance with m nodes, for large m, that has a behaviour considerably better than the algorithm which computes any of the (m-1)! possible distinct tours, and then retus the least costly one.
If we are looking for applications, a different approach can be used. Given a TSP instance with m nodes, any tour passing once through any city is a feasible solution, and its cost leads to an upper bound to the least possible cost. Algorithms that construct in polynomial time with respect to m feasible solutions, and thus upper bounds for the optimum value, are called heuristics. In general, these algorithms produce solutions but without any quality guarantee as to how far is their cost from the least possible one. If it can be shown that the cost of the retued solution is always less than k times the least possible cost, for some real number k GT 1, the heuristic is called a k-approximation algorithm.
Unfortunately, k-approximation algorithm for TSP are not known, for any k GT
1. Moreover, in a paper appeared in 2000, Papadimitriou, and Vempala have shown that a k-approximation algorithm for TSP for any 97/96 GT k GT 1 exists if and only if P=NP. Hence, also finding a good heuristic for TSP seems very hard.
Better results are known for NP-Hard subproblem of TSP. For example, a 3/2- approximation algorithm is known for Metric TSP (in a metric TSP instance the cost function verifies the triangular inequality).
Anyway, the extreme intractability of TSP has invited many researchers to test new heuristic technique on this problem. The harder is the problem you test on, the more significant are the result you obtain.
A large part of this book is devoted to some bio-inspired heuristic techniques that have been developed in the last years. Such techniques take inspiration from the nature. Actually, the animals that usually form great groups behave by instinct trying to satisfy the group necessity in the best possible way. Similarly, the natural systems develop in order to (locally) minimize their potential by finding a stationary point.
Population-Based Optimization Algorithms for Solving the Travelling Salesman Problem.
Bio-inspired Algorithms for TSP and Generalized TSP.
Approaches to the Travelling Salesman Problem Using Evolutionary Computing Algorithms.
Particle Swarm Optimization Algorithm for the Traveling Salesman Problem.
A Modified Discrete Particle Swarm Optimization Algorithm for the Generalized Traveling Salesman Problem.
Solving TSP by Transiently Chaotic Neural Networks.
A Recurrent Neural Network to Traveling Salesman Problem.
Solving the Probabilistic Travelling Salesman Problem Based on Genetic Algorithm with Queen Selection Scheme.
Niche Pseudo-Parallel Genetic Algorithms for Path Optimization of Autonomous Mobile Robot - A Specific Application of TSP.
The Symmetric Circulant Traveling Salesman Problem.