Name
Title | ||
|---|---|---|
A proposal for Zoning Crossover of Hybrid Genetic Algorithms for large-scale traveling salesman problems |
Abstract | ||
|---|---|---|
This paper proposes a novel crossover operator for solving large-scale traveling salesman problems (TSPs) by using a Hybrid Genetic Algorithm (HGA) with Lin-Kernighan heuristic for local search and we tentatively name Zoning Crossover (Z-Cross). The outline of Z-Cross is firstly to set a zone in the travelling area according to some rules, secondly to cut edges connecting cities between inside and outside the zone, thirdly to exchange edges inside the zone of one parent and those of the other parent, and lastly to reconnect sub-tours and isolated cities, which come about in the 3rd step mentioned above, so as to construct a new tour of TSP. The method is compared with conventional three crossovers; those are the Maximal Preservative Crossover, the Greedy Sub-tour Crossover and the Edge Recombination Crossover, and evaluated from the viewpoints of tour quality and CPU time. Ten benchmarks are selected from the well-known TSP website of Georgia Institute of Technology, whose names are xqf131, xqg237, ..., sra104815. The experiments are performed ten times for each crossover and each benchmark and show that the Z-Cross succeeds in finding better solution and running faster than the conventional methods. Six benchmarks with size from 39,603 to 104,815 cities are selected from the TSP website and challenged the records of tour lengths. The Z-Cross betters the record of the problem rbz43748 and approaches to solutions less than only 0.02% over the known best solutions for five instances. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/CEC.2010.5586061 | IEEE Congress on Evolutionary Computation |
Keywords | Field | DocType |
genetic algorithms,search problems,travelling salesman problems,Lin Kernighan heuristic,crossover operator,edge recombination crossover,greedy sub-tour crossover,hybrid genetic algorithms,large scale traveling salesman problems,local search,maximal preservative crossover,zoning crossover | Heuristic,Mathematical optimization,Crossover,Computer science,Edge recombination operator,Travelling salesman problem,Artificial intelligence,Local search (optimization),Machine learning,Benchmark (computing),Genetic algorithm,Lin–Kernighan heuristic | Conference |
ISBN | Citations | PageRank |
978-1-4244-6909-3 | 2 | 0.44 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masafumi Kuroda | 1 | 2 | 0.78 |
| Yamamori, K. | 2 | 2 | 0.44 |
| Masaharu Munetomo | 3 | 253 | 35.01 |
| Moritoshi Yasunaga | 4 | 178 | 33.03 |