NP - hard problem which cannot be solved in polynomial time for asymptotically large values of n and travelling salesman problem (TSP) is important in operations research and theoretical computer science. In this pape...
详细信息
NP - hard problem which cannot be solved in polynomial time for asymptotically large values of n and travelling salesman problem (TSP) is important in operations research and theoretical computer science. In this paper a balanced combination of genetic algorithm and simulated annealing has been applied. To improve the performance of finding an optimal solution from huge search space, we have incorporated the use of tournament and rank as selection operators, and inver-over operator mechanism for crossover and mutation. This proposed technique is applied for some routing resource problems in a chip design process and a best optimal solution was obtained, and the TSP appears as a sub-problem in many areas and is used as a benchmark for many optimisation methods.
We study the empirical scaling of the running time required by state-of-theart exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, w...
详细信息
We study the empirical scaling of the running time required by state-of-theart exact and inexact TSP algorithms for finding optimal solutions to Euclidean TSP instances as a function of instance size. In particular, we use a recently introduced statistical approach to obtain scaling models from observed performance data and to assess the accuracy of these models. For Concorde, the long-standing state-of-the-art exact TSP solver, we compare the scaling of the running time until an optimal solution is first encountered (the finding time) and that of the overall running time, which adds to the finding time the additional time needed to complete the proof of optimality. For two state-of-the-art inexact TSP solvers, LKH and EAX, we compare the scaling of their running time for finding an optimal solution to a given instance;we also compare the resulting models to that for the scaling of Concorde's finding time, presenting evidence that both inexact TSP solvers show significantly better scaling behaviour than Concorde.
The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact ge...
详细信息
The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact genetic algorithm in order to generate high-quality tours, which are then refined by means of the lin-kernighan (LK) local search. Local optima found by the LK local search are in turn exploited by the evolutionary part of the algorithm in order to improve the quality of its simulated population. The results of several experiments conducted on different TSP instances with up to 13509 cities show the efficacy of the symbiosis between the two heuristics.
作者：
Mulder, SAWunsch, DCUniv Missouri
Dept Comp Sci Appl Computat Intelligence Lab Rolla MO 65401 USA Univ Missouri
Dept Elect & Comp Engn Appl Computat Intelligence Lab Rolla MO 65401 USA
The Traveling Salesman Problem (TSP) is a very hard optimization problem in the field of operations research. It has been shown to be NP-complete, and is an often-used benchmark for new optimization techniques. One of...
详细信息
The Traveling Salesman Problem (TSP) is a very hard optimization problem in the field of operations research. It has been shown to be NP-complete, and is an often-used benchmark for new optimization techniques. One of the main challenges with this problem is that standard, non-AI heuristic approaches such as the lin-kernighan algorithm (LK) and the chained LK variant are currently very effective and in wide use for the common fully connected, Euclidean variant that is considered here. This paper presents an algorithm that uses adaptive resonance theory (ART) in combination with a variation of the lin-kernighan local optimization algorithm to solve very large instances of the TSP. The primary advantage of this algorithm over traditional LK and chained-LK approaches is the increased scalability and parallelism allowed by the divide-and-conquer clustering paradigm. Tours obtained by the algorithm are lower quality, but scaling is much better and there is a high potential for increasing performance using parallel hardware. (C) 2003 Elsevier Science Ltd. All rights reserved.
作者：
Mulder, SAWunsch, DCUniv Missouri
Dept Comp Sci Appl Computat Intelligence Lab Rolla MO 65401 USA Univ Missouri
Dept Elect & Comp Engn Appl Computat Intelligence Lab Rolla MO 65401 USA
The Traveling Salesman Problem (TSP) is a very hard optimization problem in the field of operations research. It has been shown to be NP-complete, and is an often-used benchmark for new optimization techniques. One of...
详细信息
The Traveling Salesman Problem (TSP) is a very hard optimization problem in the field of operations research. It has been shown to be NP-complete, and is an often-used benchmark for new optimization techniques. One of the main challenges with this problem is that standard, non-AI heuristic approaches such as the lin-kernighan algorithm (LK) and the chained LK variant are currently very effective and in wide use for the common fully connected, Euclidean variant that is considered here. This paper presents an algorithm that uses adaptive resonance theory (ART) in combination with a variation of the lin-kernighan local optimization algorithm to solve very large instances of the TSP. The primary advantage of this algorithm over traditional LK and chained-LK approaches is the increased scalability and parallelism allowed by the divide-and-conquer clustering paradigm. Tours obtained by the algorithm are lower quality, but scaling is much better and there is a high potential for increasing performance using parallel hardware. (C) 2003 Elsevier Science Ltd. All rights reserved.
The nested partitions method (NPM) is a global optimization method, which can be applied to solve many large-scale discrete optimization problems. The basic procedure of this method for solving the traveling salesman ...
详细信息
ISBN:
(数字)9783642549243
ISBN:
(纸本)9783642549243;9783642549236
The nested partitions method (NPM) is a global optimization method, which can be applied to solve many large-scale discrete optimization problems. The basic procedure of this method for solving the traveling salesman problem (TSP) was introduced. Based on the analysis and determination of the strategy of the four arithmetic operators of NPM, an improved NPM was proposed. The initial most promising region was improved by weighted sampling method;The historical optimal solution of every region was recorded in a global array;the 3-opt algorithm was combined in the local search for improving the quality of solution for every subregion;the improved lin-kernighan algorithm was used in the search for improving the quality of solution for surrounding region. Some experimental results of TSPLIB (TSP Library) show that the proposed improved NPM can find solutions of high quality efficiently when applied to the TSP.
暂无评论