Abstract
In this paper we investigate the design of a coarse-grained parallel implementation of Cga-LK, a hybrid heuristic for the Traveling Salesman Problem (TSP). Cga-LK exploits a compact genetic algorithm in order to generate high-quality tours which are then refined by means of an efficient implementation of the Lin-Kernighan local search heuristic. The results of several experiments conducted on a cluster of workstations with different TSP instances show the efficacy of the parallelism exploitation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Optimization by simulated annealing. Science, 220:671–680, 1983.
J. Grefenstette, R. Gopal, B. Rosimaita, and D. van Gucht. Genetic algorithms for the traveling salesman problem. In Proceedings of the International Conference on Genetics Algorithms and their Applications, pages 160–168, 1985.
H.C. Braun. On solving traveling salesman problems by genetic algorithm. In H.P. Schwefel and R. Männer, editors, Parallel Problem Solving from Nature, volume 496 of Lecture Notes in Computer Science, pages 129–133, Berlin, 1991. Springer-Verlag.
G.A. Croes. A method for solving traveling salesman problems. Operations Research, 6:791–812, 1958.
S. Lin. Computer solution of the traveling salesman problem. Bell System Technical Journal, 44:2245–2269, 1965.
S. Lin and B.W. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21:498–516, 1973.
D.S. Johnson and L.A. McGeoch. Local Search in Combinatorial Optimization, chapter The Traveling Salesman Problem: A Case Study in Local Optimization. John Wiley and Sons, New York, 1996.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook. Finding tours in the tsp. Preliminary chapter of a planned monograph on the TSP, available at URL: http://www.caam.rice.edu/~keck/reports/lk_report.ps, 1999.
O. Martin and S.W. Otto. Combining simulated annealing with local search heuristic. To appear on Annals of Operation Research.
P. Merz and B. Freisleben. Genetic local search for the TSP: New results. In Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, pages 159–163, Indianapolis, USA, 1997. IEEE press.
M. Gorges-Schleuter. Asparagos96 and the travelling salesman problem. In T. Bäck, editor, Proceedings of the Fourth International Conference on Evolutionary Computation, pages 171–174, New York, EEE Press, 1997.
R. Perego R. Baraglia, J.I. Hidalgo. A hybrid approach for the TSP combining genetics and the Lin-Kerninghan local search. Technical Report CNUCE-B4-2000-007, CNUCE-Institute of the Italian National Research Council, 2000.
R. Perego R. Baraglia, J.I. Hidalgo. A hybrid approach for the Traveling Salesman Problem. submitted paper.
G. Harik, F. Lobo, and D. Goldberg. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation, 3(4):287–297, 1999.
D. Thierens and D. Goldberg. Mixing in genetic algorithms. In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 38–45, San Mateo, CA, 1993. Morgan Kaufmann.
E. Cantu-Paz. A survey of parallel genetic algoritms. Technical Report 97003, University of Illinois at Urbana-Champaign, Genetic Algoritms Lab. (IlliGAL), http://www.gal4.ge.uiuc.edu/illigal.home.html, July 1997.
M. Tomassini. A survey of genetic algorithms. Technical Report 95/137, Department of Computer Science, Swiss Federal Institute of Technology, Lausanne, Switzerland, July 1995.
P. Grosso. Computer Simulations of Genetic Adaptation: Parallel Subcomponent Interaction in a Multilocus Model. PhD thesis, University of Michigan, 1985.
R. Tanese. Parallel genetic algorithms for a hypercube. In Proceedings of the Second International Conference on Genetic Algorithms, pages 177–183. L. Erlbaum Associates, 1987.
R. Tanese. Distribuited genetic algorithms. In Proceedings of the Third International Conference on Genetic Algorithms, pages 434–440. M. Kaufmann, 1989.
S. Cohoon, J. Hedge, S. Martin, and D. Richards. Punctuated equilibria: a parallel genetic algorithm. IEEE Transaction on CAD, 10(4):483–491, April 1991.
C. Pettey, M. Lenze, and J. Grefenstette. A parallel genetic algorithm. In Proceedings of the Second International Conference on Genetic Algorithms, pages 155–161. L. Erlbaum Associates, 1987.
H. Muhlenbein, M. Schomisch, and J. Born. The parallel genetic algorithm as function optimizer. Parallel Computing, 17:619–632, 1991.
W. Gropp, E. Lusk, and A. Skjellum. Using MPI. Massachusetts Institute of Technology, 1999.
D.E. Culler and J.P. Singh. Parallel Computer Architecture a Harware/Sotware Approach. Morgan Kaufmann Publishers, Inc., 1999.
G. Reinelt. TSPLIB-A traveling salesman problem library. ORSA Journal on Computing, 3:376–384, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baraglia, R., Ignacio Hidalgo, J., Perego, R. (2001). A Parallel Hybrid Heuristic for the TSP. In: Boers, E.J.W. (eds) Applications of Evolutionary Computing. EvoWorkshops 2001. Lecture Notes in Computer Science, vol 2037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45365-2_20
Download citation
DOI: https://doi.org/10.1007/3-540-45365-2_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41920-4
Online ISBN: 978-3-540-45365-9
eBook Packages: Springer Book Archive