Name
Abstract | ||
|---|---|---|
This correspondence describes a hybrid genetic algorithm (GA) to find high-quality solutions for the traveling salesman problem (TSP). The proposed method is based on a parallel implementation of a multipopulation steady-state GA involving local search heuristics. It uses a variant of the maximal preservative crossover and the double-bridge move mutation. An effective implementation of the Lin-Kernighan heuristic (LK) is incorporated into the method to compensate for the GA's lack of local search ability. The method is validated by comparing it with the LK-Helsgaun method (LKH), which is one of the most effective methods for the TSP. Experimental results with benchmarks having up to 316 228 cities show that the proposed method works more effectively and efficiently than LKH when solving large-scale problems. Finally, the method is used together with the implementation of the iterated LK to find a new best tour (as of June 2, 2003) for a 1 904 711-city TSP challenge |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/TSMCB.2006.880136 | IEEE Transactions on Systems, Man, and Cybernetics, Part B |
Keywords | Field | DocType |
memetic algorithm,steady state,traveling salesman problem,local search,genetic algorithms | Memetic algorithm,Computer science,Travelling salesman problem,Heuristics,Artificial intelligence,Genetic algorithm,Mathematical optimization,Heuristic,Crossover,Algorithm,Local search (optimization),Iterated function,Machine learning | Journal |
Volume | Issue | ISSN |
37 | 1 | 1083-4419 |
Citations | PageRank | References |
73 | 2.73 | 26 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hung Dinh Nguyen | 1 | 75 | 3.11 |
| Ikuo Yoshihara | 2 | 120 | 18.53 |
| Kunihito Yamamori | 3 | 74 | 3.11 |
| Moritoshi Yasunaga | 4 | 78 | 3.40 |