Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Discrete Energy Laws for the First-Order System Least-Squares Finite-Element Approach Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem

Authors : Anton V. Eremeev, Yulia V. Kovalenko

Published in: Large-Scale Scientific Computing

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We propose a new genetic algorithm with optimal recombination for the asymmetric instances of travelling salesman problem. The algorithm incorporates several new features that contribute to its effectiveness: 1. Optimal recombination problem is solved within crossover operator. 2. A new mutation operator performs a random jump within 3-opt or 4-opt neighborhood. 3. Greedy constructive heuristic of Zhang and 3-opt local search heuristic are used to generate the initial population. A computational experiment on TSPLIB instances shows that the proposed algorithm yields competitive results to other well-known memetic algorithms for asymmetric travelling salesman problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Intercriteria Analysis over Intuitionistic Fuzzy Data
next chapter Heuristic Algorithm for 2D Cutting Stock Problem
Literature
1.
Brown, B.W., Hollander, M.: Statistics: A Biomedical Introduction. Wiley Inc., New York (1977)CrossRefMATH
2.
Buriol, L.S., Franca, P.M., Moscato, P.: A new memetic algorithm for the asymmetric traveling salesman problem. J. Heuristics 10, 483–506 (2004)CrossRefMATH
3.
4.
Dongarra, J.J.: Performance of various computers using standard linear equations software. Technical Report CS-89-85, 110 p. University of Manchester (2014)
5.
6.
Eremeev, A.V., Kovalenko, J.V.: Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II. Yugoslav J. Oper. Res. 24(2), 165–186 (2014)MathSciNetCrossRefMATH
7.
8.
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco (1979)MATH
9.
Goldberg, D., Thierens, D.: Elitist recombination: An integrated selection recombination GA. In: First IEEE World Congress on Computational Intelligence, vol. 1, pp. 508–512. IEEE Service Center, Piscataway, New Jersey (1994)
10.
Johnson, D.S., McGeorch, L.A.: The traveling salesman problem: a case study. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215–336. Wiley Ltd. (1997)
11.
Kanellakis, P.C., Papadimitriou, C.H.: Local search for the asymmetric traveling salesman problem. Oper. Res. 28, 1086–1099 (1980)MathSciNetCrossRefMATH
12.
13.
14.
15.
16.
Tinós, R., Whitley, D., Ochoa, G.: Generalized asymmetric partition crossover (GAPX) for the asymmetric TSP. In: The 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 501–508. ACM, New York (2014)
17.
Whitley, D., Starkweather, T., Shaner, D.: The traveling salesman and sequence scheduling: Quality solutions using genetic edge recombination. In: Davis, L. (ed.) Handbook of Genetic Algorithms, pp. 350–372. Van Nostrand Reinhold (1991)
18.
Yagiura, M., Ibaraki, T.: The use of dynamic programming in genetic algorithms for permutation problems. Eur. J. Oper. Res. 92, 387–401 (1996)CrossRefMATH
19.
Zhang, W.: Depth-first branch-and-bound versus local search: A case study. In: 17th National Conference on Artificial Intelligence, Austin, pp. 930–935 (2000)
Metadata
Title
Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
Authors
Anton V. Eremeev
Yulia V. Kovalenko
Copyright Year
2018
Book
Large-Scale Scientific Computing

Print ISBN: 978-3-319-73440-8

Electronic ISBN: 978-3-319-73441-5

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-73441-5_36

Premium Partner

    Image Credits