An Efficient Solving the Travelling Salesman Problem : Global Optimization of Neural Networks by Using Hybrid Method
Yong-Hyun Cho · InTech eBooks · 2010
The travelling salesman problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science.Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once (Aarts & Laarhoven, 1985;Beale & Jackson, 1990;Bout & Miller, 1988;Cichock & Unbehaun, 1993;Lin, 1965;Zurada, 1992).The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization.It is used as a benchmark for many optimization methods.Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved (Beale & Jackson, 1990;Freeman & Skapura, 1991;Lin, 1965).The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips.Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing.In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments (Beale & Jackson, 1990;Cichock & Unbehaun, 1993;Freeman & Skapura, 1991;Zurada, 1992).In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.In the theory of computational complexity, the decision version of TSP belongs to the class of NP-complete problems (Aarts & Laarhoven, 1985;Abe et al., 1992;Burke, 1994;Freeman & Skapura, 1991;Hopfield & Tank, 1985).Thus, it is assumed that there is no efficient algorithm for solving TSPs.In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly.The travelling salesman problem is regarded as difficult to solve.If there is a way to break this problem into smaller component problems, the components will be at least as complex as the original one.This is what computer scientists call NP-hard problems (Aarts & Laarhoven, 1985;Abe et al., 1992;Freeman & Skapura, 1991). www.intechopen.com Traveling Salesman Problem, Theory and Applications 156Many people have studied this problem.The easiest (and most expensive solution) is to simply try all possibilities.The problem with this is that for n cities you have (n-1)!possibilities.This means that for only 11 cities there are about 3.5 million combinations to try (Freeman & Skapura, 1991).In recent years, many algorithms for solving the TSP have been proposed (Cichock & Unbehaun, 1993;Dorigo et al., 1991;Goldberg, 1989;Lin & Kernighan, 1971;Mascato, 1989;Szu & Hartley, 1987).However, these algorithms sustain several disadvantages.First, some of these algorithms are not optimal in a way that the solution they obtain may not be the best one.Second, their runtime is not always defined in advance, since for every problem there are certain cases for which the computation time is very long due to unsuccessful attempts for optimization.They will often consistently find good solutions to the problem.These good solutions are typically considered to be good enough simply because they are the best that can be found in a reasonable amount of time.Therefore, optimization often takes the role of finding the best solution possible in a reasonable amount of time.There have been several types of approaches taken to solving the TSP [10-30] of the numerical methods and the neural networks (NNs) (Beale & Jackson, 1990;Cichock & Unbehaun, 1993;Freeman & Skapura, 1991;Goldberg, 1989;Zurada, 1992).Recently, NN is well suited for this type of problems.An NN, also known as a parallel distributed processing network, is a computing paradigm that is loosely modeled after cortical structures of the brain (Beale & Jackson, 1990;Cichock & Unbehaun, 1993;Freeman & Skapura, 1991;Zurada, 1992).It consists of interconnected processing elements called nodes or neurons (Beale & Jackson, 1990;Zurada, 1992).NN, due to its massive parallelism, has been rigorously studied as an alternative to the conventional numerical approach for fast solving of the combinatorial optimization or the pattern recognition problems.The optimization is to find the neuron that lead to the energy minimum by applying repeatedly the optimization algorithm.Hopfield model is energy-minimizing network, and is useful as a content addressable memory or an analog computer for solving combinatorial optimization problems (Abe et al., 1992;