Abstract
We briefly review previous attempts to generate near-optimal solutions of the Traveling Salesman Problem by applying Genetic Algorithms. Following the lines of Johnson [1990] we discuss some possibilities for speeding up classical Local Search algorithms by casting them into a genetic frame. In an experimental study two such approaches, viz. Genetic Local Search with 2-Opt neighbourhoods and Lin-Kernighan neighbourhoods, respectively, are compared with the corresponding classical multi-start Local Search algorithms, as well as with Simulated Annealing and Threshold Accepting, using 2-Opt neighbourhoods. As to be expected a genetic organization of Local Search algorithms can considerably improve upon performance though the genetic components alone can hardly counterbalance a poor choice of the neighbourhoods.
This is a preview of subscription content, log in via an institution.
Preview
Unable to display preview. Download preview PDF.
References
Aarts, E. H. L. and P.J.M. van Laarhoven [1985], A New Polynomial-Time Cooling Schedule, Proc. IEEE Int. Conf. Computer-Aided Design, Santa Clara, pp. 206–208.
Ablay, P. [1987], Optimieren mit Evolutionsstrategien, Spektrum der Wissenschaft 7, 162–173.
Ackley, D.H. [1987], A Connectionist Machine for Genetic Hillclimbing, Kluwer Academic Publishers.
Dueck, G. and T. Scheuer [1988], Threshold Accepting. A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing, TR 88.10.011, IBM Heidelberg Scientific Center.
Goldberg, D.E. [1989a], Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley.
Goldberg, D.E. [1989b], Zen and the Art of Genetic Algorithms, Proc. 3rd Int. Conf. Genetic Algorithms, Morgan Kaufmann Publishers, pp. 80–85.
Gorges-Schleuter, M. [1989], ASPARAGOS, A Parallel Genetic Algorithm and Population Genetics, Proc. 3rd Int. Conf. Genetic Algorithms, Morgan Kaufmann publishers, pp. 422–427.
Grefenstette, J.J. [1986], Optimization of Control Parameters for Genetic Algorithms, IEEE Trans. Systems Man Cybernetics 16, 122–128.
Grefenstette, J.J. [1987], Incorporating Problem Specific Knowledge into Genetic Algorithms, in L. Davis, Genetic Algorithms and Simulated Annealing, Pitman, pp. 42–60.
Grefenstette, J.J., R. Gopal, B. Rosmaita, and D. Van Gucht [1985], Genetic Algorithms for the Traveling Salesman Problem, Proc. 1st Int. Conf. Genetic Algorithms and Their Applications, Lawrence Erlbaum Ass., pp. 160–168.
Jog, P., J.Y. Suh, and D. Van Gucht [1989], The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Traveling Salesman Problem. Proc. 3rd Int. Conf. Genetic Algorithms, Morgan Kaufmann Publishers, pp. 110–115.
Johnson, D.S. [1990], Local Optimization and the Traveling Salesman Problem, Proc. 17th Colloq. Automata, Languages, Programming, Springer-Verlag (in press).
Johnson, D.S., C.H. Papadimitriou, and M. Yannakakis [1985], How Easy is Local Search?, Journal of Computer and System Science 37, 79–100.
Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys [1985], The Traveling Salesman Problem, John Wiley & Sons.
Lin, S., and B.W. Kernighan [1973], An Effective Heuristic Algorithm for the Traveling Salesman Problem, Operations Research 21, 498–516.
Mühlenbein, H. [1989], Parallel Genetic Algorithms, Population Genetics and Combinatorial Optimization, Proc. 3rd Int. Conf. Genetic Algorithms, Morgan Kaufmann Publishers, pp. 416–421.
Mühlenbein, H., M. Gorges-Schleuter, and O. Krämer [1987], New Solutions to the Mapping Problem of Parallel Systems: the Evolution Approach, Parallel Computing 4, 269–279.
Mühlenbein, H., M. Gorges-Schleuter, and O. Krämer [1988], Evolution Algorithms in Combinatorial Optimization, Parallel Computing 7, 65–85
Mühlenbein, H., and J. Kindermann [1989], Dynamics of Evolution and Learning — Towards Genetic Neural Networks, in R. Pfeiffer, Connectionism in Perspective, Elsevier (in press).
Rechenberg, I. [1973], Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution, Problemata, Fromann-Holzboog.
Reinelt, G. [1989], Fast Heuristics for Large Geometric Traveling Salesman Problems, Report nr. 185, Institut für Mathematik, Universität Augsburg.
Schwefel, H.-P. [1977], Numerische Optimierung von Computer-Modellen Mittels der Evolutionsstrategie, Birkhäuser Verlag.
Suh, J.Y., and D. Van Gucht [1987], Incorporating Heuristic Information into Genetic Search, Proc. 2rd Int. Conf. Genetic Algorithms, Lawrence Erlbaum Associates, pp. 100–107.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ulder, N.L.J., Aarts, E.H.L., Bandelt, HJ., van Laarhoven, P.J.M., Pesch, E. (1991). Genetic local search algorithms for the traveling salesman problem. In: Schwefel, HP., Männer, R. (eds) Parallel Problem Solving from Nature. PPSN 1990. Lecture Notes in Computer Science, vol 496. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029740
Download citation
DOI: https://doi.org/10.1007/BFb0029740
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54148-6
Online ISBN: 978-3-540-70652-6
eBook Packages: Springer Book Archive