Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Soft Computing
Erschienen in: Soft Computing 23/2020

10.06.2020 | Methodologies and Application

Evolutionary operators for the Hamiltonian completion problem

verfasst von: Krunoslav Puljić, Robert Manger

Erschienen in: Soft Computing | Ausgabe 23/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper deals with evolutionary algorithms for solving the Hamiltonian completion problem. More precisely, the paper is concerned with a collection of crossover and mutation operators, which mostly originate from the traveling salesman problem, but have further on been modified or customized for Hamiltonian completion. The considered crossovers and mutations are tested on a set of randomly generated problem instances. The obtained experimental results clearly show that the behavior and relative ranking of the operators within the Hamiltonian completion environment are different than within the traveling salesman environment. Moreover, it is shown that our modified or custom-designed operator variants accomplish much better results for Hamiltonian completion than the standard variants.
Vorheriger Artikel The use of local information sharing on soccer game optimization
Nächster Artikel CALA-FOMF: a continuous action-set learning automata-based approach to finding optimized membership functions for fuzzy association rules in web usage data

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
Agnetis A, Detti P, Meloni C, Pacciarelli D (2001) A linear algorithm for the Hamiltonian completion number of the line graph of a tree. Inf Process Lett 79:17–24MathSciNetCrossRef
Ahmed ZH (2014) Improved genetic algorithms for the traveling salesman problem. Int J Process Manag Benchmark 4:109–124CrossRef
Choi I, Kim S, Kim H (2003) A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem. Comput Oper Res 30:773–786MathSciNetCrossRef
Cook WJ (2012) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, PrincetonMATH
Cook WJ (2015) Concorde TSP solver. University od Waterloo, Ontario, Canada. http://​www.​math.​uwaterloo.​ca/​tsp/​concorde/​index.​html.​ Accessed 5 January 2020
Detti P, Meloni C (2004) A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. Discrete Appl Math 136:197–215MathSciNetCrossRef
Detti P, Meloni C, Pranzo M (2007) Local search algorithms for finding the Hamiltonian completion number of line graphs. Ann Oper Res 156:5–24MathSciNetCrossRef
Detti P, Meloni C, Pranzo M (2013) A lower bound on the Hamiltonian path completion number of a line graph. Appl Math Comput 220:296–304MathSciNetMATH
Eiben AE, Smith JE (2015) Introduction to evolutionary computing. Natural computing series, 2nd edn. Springer, BerlinCrossRef
Franzblau DS, Raychaudhuri A (2002) Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow. ANZIAM J 44:193–204MathSciNetCrossRef
Gamarnik D, Sviridenko M (2005) Hamiltonian completions of sparse random graphs. Discrete Appl Math 152:139–158MathSciNetCrossRef
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completness. W.H Freeman, San FranciscoMATH
Gog A, Chira C (2011) Comparative analysis of recombination operators in genetic algorithms for the traveling salesman problem. In: Corchado E, Kurzynski M, Wozniak M (eds) Hybrid artificial intelligent systems—6th international conference, HAIS 2011, Wroclaw, Poland, May 23–25, 2011, Proceedings part II. LNCS vol 6679. Springer, Berlin, pp 10–17
Grefenstette JJ, Gopal R, Rosmaita BJ, Van Gucht D (1985) Genetic algorithms for the traveling salesman problem. In: Grefenstette JJ (ed) Proceedings of the 1st international conference on genetic algorithms, Pittsburgh PA, July 1985. Lawrence Erlbaum Associates, Mahwah NJ, pp 160–168
Gutin G, Punnen AP (2007) The traveling salesman problem and its variations. Springer, New YorkCrossRef
Helsgaun K (2018) LKH Version 2.0.9. Roskilde University, Denmark. http://​akira.​ruc.​dk/​ keld/research/LKH. Accessed 5 January 2020
Jungnickel D (2013) Graphs, networks and algorithms, 4th edn. Springer, BerlinCrossRef
Komlos J, Szeweredi E (2006) Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math 306:1032–1038CrossRef
Korte B, Wygen J (2012) Combinatorial optimization—theory and algorithms, 5th edn. Springer, BerlinCrossRef
Larranaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S (1999) Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif Intell Rev 13:129–170CrossRef
Li C, Zhan W, Xu J, Yang L (2011) Development of two assistant crossover operators to solve the traveling salesman problem. Int J Adv Comput Technol 3:178–184
Maretić HP, Grbić A (2015) A heuristic approach to Hamiltonian completion problem (HCP). In: Biljanović P (ed) Proceedings of the 38th international convention on information and communication technology, electronics and microelectronics, MIPRO 2015, Opatija, Croatia, May 25-29, 2015. MIPRO Society, Rijeka, Croatia, pp 1607-1612
Mchedlidze T, Symvonis A (2009) Crossing-optimal acyclic Hamiltonian path completion and its application to upward topological book embeddings. In: Das S, Uchara R (eds) Proceedings of the third international workshop on algorithms and computation, WALCOM 2009, Kolkata, India, February 18–20 (2009) LNCS, vol 5431. Springer, Berlin, pp 250–261
Mchedlidze T, Symvonis A (2009) Crossing-free acyclic Hamiltonian path completion for planar st-digraphs. In: Dong Y, Du D-Z, Ibarra O (eds) Proceedings of the 20th international symposium on algorithms and computation, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18 (2009) LNCS, vol 5878. Springer, Berlin, pp 882–891
Meloni C, Naso D, Turchiano B (2006) Setup coordination between two stages of a production system: a multi-objective evolutionary approach. Ann Oper Res 147:175–198MathSciNetCrossRef
Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs, 3rd edn. Springer, New YorkCrossRef
Nagata Y, Kobayashi S (2013) A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS J Comput 25:346–363MathSciNetCrossRef
Naso D, Turchiano B, Meloni C (2006) Single and multi-objective evolutionary algorithms for the coordination of serial manufacturing operations. J Intell Manuf 17:251–270CrossRef
Nikolopolous SD (2004) Parallel algorithms for Hamiltonian problems on quasi-threshold graphs. J Parallel Distrib Comput 64:48–67CrossRef
Papadimitrou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Dover Publications, Mineola
Pongcharoen P, Stewardson DJ, Hicks C, Braiden PM (2001) Applying designed experiments to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry. J Appl Stat 28:441–455MathSciNetCrossRef
Raychaudhuri A (1995) The total interval number of a tree and the Hamiltonian completion number of its line graph. Inf Process Lett 56:299–306MathSciNetCrossRef
Raychaudhuri A (1999) On Hamiltonian path completion number of an interval graph. In: Stanton RG, Allston JL (eds) Proceedings of the 30th southeastern international conference on combinatorics, graph theory and computing, Boca Raton, FL, March 8–12, 1999. Utilitas Mathematica Publishing, Winnipeg, Manitoba, Canada, pp 193–198
Spiegel M, Stephens L (2014) Schaum’s outline of statistics, 5th edn. McGraw-Hill, New York
Starkweather T, McDaniel S, Mathias KE, Whitley LD, Whitley C (1991) A comparison of genetic sequencing operators. In: Belew RK, Booker LB (eds) Proceedings of the 4th international conference on genetic algorithms, San Diego CA, July 1991. Morgan Kaufmann, San Francisco CA, pp 69–76
Tsai HK, Yang J-M, Tsai Y-F, Kao C-Y (2004) An evolutionary algorithm for large traveling salesman problems. IEEE Trans Syst Man Cybern B Cybern 34:1718–1729CrossRef
Wang J, Ersoy OK, He M, Wang F (2016) Multi-offspring genetic algorithm and its application to the traveling salesman problem. Appl Soft Comput 43:415–423CrossRef
Wu Q, Lu CL, Lee RC-T (2005) The approximability of the weighted Hamiltonian path completion problem on a tree. Theor Comput Sci 341:385–397MathSciNetCrossRef
Zhao Z, Chen Y, Zhao Z (2016) A study on the traveling salesman problem using genetic algorithms. Int J Simul Syst Sci Technol 17:1–6
Metadaten
Titel
Evolutionary operators for the Hamiltonian completion problem
verfasst von
Krunoslav Puljić
Robert Manger
Publikationsdatum
10.06.2020
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 23/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-020-05063-8

Weitere Artikel der Ausgabe 23/2020

Soft Computing 23/2020 Zur Ausgabe

Methodologies and Application

Multi-label charge predictions leveraging label co-occurrence in imbalanced data scenario

Methodologies and Application

Weight convergence analysis of DV-hop localization algorithm with GA

Focus

Artificial neural networks training acceleration through network science strategies

Preface

To the special issue dedicated to the 3rd international conference “Numerical Computations: Theory and Algorithms—NUMTA 2019” June 15–21, 2019, Isola Capo Rizzuto, Italy

Focus

Comparison of active-set and gradient projection-based algorithms for box-constrained quadratic programming

Methodologies and Application

Analysis of slump and surge phenomenon in Chinese stock market based on sequence alignment method

Premium Partner

    Bildnachweise