Sept 16' 2013 - Sept 20' 2013
After going through the last research paper by Nishida, analyzing it, understanding the concepts mentioned, This week i took to a new document, which is:
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 return 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 born.
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 returns 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 returned solution is always less than k times the least possible cost, for some real number k>1, the heuristic is called a k-approximation algorithm.
Unfortunately, k-approximation algorithm for TSP are not known, for any k>1.
Moreover, in a paper appeared in 2000, Papadimitriou, and Vempala have shown that a k approximation algorithm for TSP for any 97/96>k>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.
In chapter 1 [Population-Based Optimization Algorithms for Solving the Travelling Salesman Problem] the following bio-inspired algorithmic techniques are considered:
Genetic Algorithms, Ant Colon Optimization, Particle Swarm Optimization, Intelligent Water Drops, Artificial Immune Systems, Bee Colony Optimization, and Electromagnetism like Mechanisms. Every section briefly introduces one of these techniques and an algorithm applying it for solving TSP. In the last section the obtained experimental results are compared.
Chapter 2 [Bio-inspired Algorithms for TSP and Generalized TSP] is divided into two parts. In the first part, a new algorithm using the Ant Colon Optimization technique is considered. The obtained experimental results are then compared with other two algorithms using the same technique. In the second part, the combinatorial optimization problem called Generalized TSP (GTSP) is introduced, and a Genetic Algorithm for solving is proposed. We recall that a GSTP instance provides a complete graph G = (V,E), and a cost function (as in a TSP instance), together with a partition of the node set V into p subsets. A feasible solution for GTSP is a tour passing at least once from each one of the p subsets of V. Clearly, GTSP is a generalization of TSP.
In Chapter 3 [Approaches to the Travelling Salesman Problem Using Evolutionary Computing Algorithms] an algorithm for TSP using the Genetic Local Search is considered.
It is a hybrid technique, as it combines a genetic algorithm approach by a local search technique: As in a genetic algorithm the fitness of a population is the target, but a local search optimization phase is applied whenever a new individual is created during the evolutionary process. At the end of the chapter some experimental results are discussed.
Chapter 4 [Particle Swarm Optimization Algorithm for the Traveling Salesman Problem] and Chapter 5 [A Modified Discrete Particle Swarm Optimization Algorithm for the Generalized Traveling Salesman Problem] deals with the Particle Swarm Optimization (PSO) technique. In a PSO algorithm the current solution is seen as a particle whose movement in the solution space is controlled by a certain velocity operator. As the solution space of a TSP instance is discrete, it is more correct referring to discrete PSO approach for TSP.
In Chapter 4 the authors propose some velocity operators for a discrete PSO algorithm for TSP, and compare by computational experiments the results of the proposed approach with other known PSO heuristics for TSP.
In Chapter 5 a discrete PSO approach is considered for Generalized TSP. Afterwards, the proposed algorithm is hybridized with a local search improvement heuristic. In the last section some the computational results compare the proposed algorithm, and its improvement with other known discrete PSO algorithm for GTSP.
In Chapter 6 [Solving TSP via Neural Networks] and in Chapter 7 [A Recurrent Neural Network to Traveling Salesman Problem] Neural Network techniques for solving TSP are considered.
In particular, Chapter 6 is devoted to the recent progress in the transiently chaotic neural network (TCNN), a discrete-time neural network model, are presented. An algorithm for TSP using such technique is then introduced, and the obtained results are compared with other neural networks algorithms.
In Chapter 7 a technique based on the Wang’s Recurrent Neural Networks with the “Winner Takes All” principle is used to solve the Assignment Problem (AP). By lightly modifying such technique, an algorithm for TSP is derived. Finally, some TSP instances taken from the TSP library are chosen for comparing the proposed algorithm with some other algorithms using different techniques.
Chapter 8 [Solving the Probabilistic Travelling Salesman Problem Based on Genetic Algorithm with Queen Selection Scheme] treats an extension of TSP, the Probabilistic TSP (PTSP). A PTSP instance provides a complete graph G=(V,E), and a cost function (as in a TSP instance), together with a real number 0 ≤ Pi ≤ 1 for each node i in V. Pi represents the probability of the node i to be visited by a tour. Clearly, the goal of PTSP is to find a tour of minimal expected cost. In this chapter an optimization procedure based on a Genetic Algorithm framework is presented.
In Chapter 9 [Niche Pseudo-Parallel Genetic Algorithms for Path Optimization of Autonomous Mobile Robot - A Specific Application of TSP] an application of TSP to the Path Optimization of Autonomous Mobile Robot is considered. An autonomous mobile robot has to find a non-collision path from initial position to objective position in an obstacle space trying to minimize the path cost. This problem can be modelled as a TSP instance. The authors consider a genetic algorithm, called Niche Pseudo-Parallel Genetic Algorithm, for solving TSP.
The last Chapter [The Symmetric Circulant Traveling Salesman Problem] gives an example of a theoretical research on TSP. Actually, it is interesting to investigate if TSP becomes easier or remains hard (from a computational complexity point of view) when it is restricted to a particular class of graphs. In this chapter the case in which the graph in the instance is symmetric, and circulant is deeply analyzed, and an overview on the most recent results is given. By summing up, in this book the problem of finding algorithmic technique leading to good/optimal solutions for TSP (or for some other strictly related problems) is considered.
An important thing has to be outlined here. As already said, TSP is a very attractive problem for the research community. Anyway, it arises as a natural subproblem in many applications concerning the every day life. Indeed, each application, in which an optimal ordering of a number of items has to be chosen in a way that the total cost of a solution is determined by adding up the costs arising from two successively items, can be modelled as a TSP instance.
Thus, studying TSP can be never considered as an abstract research with no real importance.
Following were the algorithms mentioned in this document :
