Издательство InTech, 2010, -336 pp.
Computational complexity theory is a core branch of study in theoretical computing science and mathematics, which is generally conceed with classifying computational problems with their inherent diffi culties. One of the core open problems is the resolution of P and NP problems. These are problems which are very important, however, for which no effi cient algorithm is known. The Traveling Salesman Problem (TSP) is one of these problems, which is generally regarded as the most intensively studied problem in computational mathematics.
Assuming a traveling salesman has to visit a number of given cities, starting and ending at the same city. This tour, which represents the length of the travelled path, is the TSP formulation. As the number of cities increases, the determination of the optimal tour (in this case a Hamiltonian tour), becomes inexorably complex. A TSP decision problem is generally classifi ed as NP-Complete problem.
One of the current and best-known approaches to solving TSP problems is with the application of Evolutionary algorithms. These algorithms are generally based on naturally occurring phenomena in nature, which are used to model computer algorithms. A number of such algorithms exists; namely, Artifi cial Immune System, Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization and Self Organising Migrating Algorithm. Algorithms based on mathematical formulations such as Differential Evolution, Tabu Search and Scatt er Search have also been proven to be very robust.
Evolutionary Algorithms generally work on a pool of solutions, where the underlying paradigm att empts to obtain the optimal solution. These problems are hence classifi ed as optimization problems. TSP, when resolved as an optimization problem, is classifi ed as a NP-Hard problem.
This book is a collection of current research in the application of evolutionary algorithms and other optimal algorithms to solving the TSP problem. It brings together researchers with applications in Artifi cial Immune Systems, Genetic Algorithms, Neural Networks and Diff erential Evolution Algorithm. Hybrid systems, like Fuzzy Maps, Chaotic Maps and Parallelized TSP are also presented. Most importantly, this book presents both theoretical as well as practical applications of TSP, which will be a vital tool for researchers and graduate entry students in the fi eld of applied Mathematics, Computing Science and Engineering.
Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches.
The Advantage of Intelligent Algorithms for TSP.
Privacy-Preserving Local Search for the Traveling Salesman Problem.
Chaos Driven Evolutionary Algorithm for the Traveling Salesman Problem.
A Fast Evolutionary Algorithm for Traveling Salesman Problem.
Immune-Genetic Algorithm for Traveling Salesman Problem.
The Method of Solving for Travelling Salesman Problem Using Genetic Algorithm with Immune Adjustment Mechanism.
A High Performance Immune Clonal Algorithm for Solving Large Scale TSP.
A Multi-World Intelligent Genetic Algorithm to Optimize Delivery Problem with Interactive-Time.
An Effi cient Solving the Travelling Salesman Problem: Global Optimization of Neural Networks by Using Hybrid Method.
Recurrent Neural Networks with the Soft ‘Winner Takes All’ Principle Applied to the Traveling Salesman Problem.
A Study of Traveling Salesman Problem Using Fuzzy Self Organizing Map.
Hybrid Metaheuristics Using Reinforcement Leaing Applied to Salesman Traveling Problem.
Predicting Parallel TSP Performance: A Computational Approach.
Linear Programming Formulation of the Multi-Depot Multiple Traveling Salesman Problem with Differentiated Travel Costs.
A Sociophysical Application of TSP: The Corporate Vote.
Some Special Traveling Salesman Problems with Applications in Health Economics.
Computational complexity theory is a core branch of study in theoretical computing science and mathematics, which is generally conceed with classifying computational problems with their inherent diffi culties. One of the core open problems is the resolution of P and NP problems. These are problems which are very important, however, for which no effi cient algorithm is known. The Traveling Salesman Problem (TSP) is one of these problems, which is generally regarded as the most intensively studied problem in computational mathematics.
Assuming a traveling salesman has to visit a number of given cities, starting and ending at the same city. This tour, which represents the length of the travelled path, is the TSP formulation. As the number of cities increases, the determination of the optimal tour (in this case a Hamiltonian tour), becomes inexorably complex. A TSP decision problem is generally classifi ed as NP-Complete problem.
One of the current and best-known approaches to solving TSP problems is with the application of Evolutionary algorithms. These algorithms are generally based on naturally occurring phenomena in nature, which are used to model computer algorithms. A number of such algorithms exists; namely, Artifi cial Immune System, Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization and Self Organising Migrating Algorithm. Algorithms based on mathematical formulations such as Differential Evolution, Tabu Search and Scatt er Search have also been proven to be very robust.
Evolutionary Algorithms generally work on a pool of solutions, where the underlying paradigm att empts to obtain the optimal solution. These problems are hence classifi ed as optimization problems. TSP, when resolved as an optimization problem, is classifi ed as a NP-Hard problem.
This book is a collection of current research in the application of evolutionary algorithms and other optimal algorithms to solving the TSP problem. It brings together researchers with applications in Artifi cial Immune Systems, Genetic Algorithms, Neural Networks and Diff erential Evolution Algorithm. Hybrid systems, like Fuzzy Maps, Chaotic Maps and Parallelized TSP are also presented. Most importantly, this book presents both theoretical as well as practical applications of TSP, which will be a vital tool for researchers and graduate entry students in the fi eld of applied Mathematics, Computing Science and Engineering.
Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches.
The Advantage of Intelligent Algorithms for TSP.
Privacy-Preserving Local Search for the Traveling Salesman Problem.
Chaos Driven Evolutionary Algorithm for the Traveling Salesman Problem.
A Fast Evolutionary Algorithm for Traveling Salesman Problem.
Immune-Genetic Algorithm for Traveling Salesman Problem.
The Method of Solving for Travelling Salesman Problem Using Genetic Algorithm with Immune Adjustment Mechanism.
A High Performance Immune Clonal Algorithm for Solving Large Scale TSP.
A Multi-World Intelligent Genetic Algorithm to Optimize Delivery Problem with Interactive-Time.
An Effi cient Solving the Travelling Salesman Problem: Global Optimization of Neural Networks by Using Hybrid Method.
Recurrent Neural Networks with the Soft ‘Winner Takes All’ Principle Applied to the Traveling Salesman Problem.
A Study of Traveling Salesman Problem Using Fuzzy Self Organizing Map.
Hybrid Metaheuristics Using Reinforcement Leaing Applied to Salesman Traveling Problem.
Predicting Parallel TSP Performance: A Computational Approach.
Linear Programming Formulation of the Multi-Depot Multiple Traveling Salesman Problem with Differentiated Travel Costs.
A Sociophysical Application of TSP: The Corporate Vote.
Some Special Traveling Salesman Problems with Applications in Health Economics.