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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Cuckoo Search and Firefly Algorithm: Overview and Analysis Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

Improved and Discrete Cuckoo Search for Solving the Travelling Salesman Problem

verfasst von : Aziz Ouaarab, Belaïd Ahiod, Xin-She Yang

Erschienen in: Cuckoo Search and Firefly Algorithm

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Improved and Discrete Cuckoo Search (DCS) algorithm for solving the famous travelling salesman problem (TSP), an NP-hard combinatorial optimization problem, is recently developed by Ouaarab, Ahiod, and Yang in 2013, based on the cuckoo search (CS), developed by Yang and Deb in 2009. DCS first reconstructs the population of CS by introducing a new category of cuckoos in order to improve its search efficiency, and adapts it to TSP based on the terminology used either in inspiration source of CS or in its continuous search space. The performance of the proposed DCS is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that DCS is superior to some other metaheuristics.

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 "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

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
Vorheriges Kapitel Cuckoo Search: A Brief Literature Review
Nächstes Kapitel Comparative Analysis of the Cuckoo Search Algorithm
Literatur
1.
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM (JACM) 45(5), 753–782 (1998)CrossRefMATH
2.
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. (CSUR) 35(3), 268–308 (2003)CrossRef
3.
Brown, C.T., Liebovitch, L.S., Glendon, R.: Lévy flights in dobe ju/’hoansi foraging patterns. Hum Ecol 35(1), 129–138 (2007)CrossRef
4.
Chen, S.M., Chien, C.Y.: Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Syst. Appl. 38(12), 14439–14450 (2011)CrossRef
5.
Clerc, M.: Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: Babu, B.V, Onwubolu, G.C. (Eds.) New optimization techniques in engineering, pp. 219–239. Springer, Berlin (2004)
6.
7.
Davendra, D.: Traveling Salesman Problem, Theory and Applications. InTech Publisher, Rijeka (2010)CrossRefMATH
8.
Dorigo, M., Maniezzo, V., Colorni, A.: Positive feedback as a search strategy. Technical report. pp. 99–016. Dipartimento di Electtonica, Polotecnico di Milano, Italy (1992)
9.
Dorigo, M., Di Caro, G.: Ant colony optimization: a new metaheuristic. In: Proceedings of the 1999 Congress on Evolutionary Computation, 1999, CEC 99, (Vol. 2). IEEE (1999)
10.
Gandomi, A.H., Yang, X.S., Alavi, A.H.: Mixed variable structural optimization using firefly algorithm. Comput. Struct. 89(23–24), 2325–2336 (2011)CrossRef
11.
Gandomi, A.H., Talatahari, S., Yang, X.S., Deb, S.: Design optimization of truss structures using cuckoo search algorithm. Struct. Des Tall Special Build. (2012). doi:10.​1002/​tal.​1033
12.
Gandomi, A.H., Yang, X.S., Alavi, A.H.: Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems. Eng. Comput. 29(1), 17–35 (2013)MathSciNetCrossRef
13.
Geem, Z.W., Kim, J.H., Loganathan, G.V.: A new heuristic optimization algorithm: harmony search. Simulation 76(2), 60–68 (2001)CrossRef
14.
Glover, F., Laguna, M.: Tabu Search, vol. 22. Kluwer academic publishers, Boston (1997)
15.
Glover, F., Kochenberger, G.A.: Handbook of Metaheuristics. Springer, New York (2003)MATH
16.
Grefenstette, J.J., Gopal, R., Rosmaita, B.J., Gucht, D.V.: Genetic algorithms for the traveling salesman problem. In: Proceedings of the 1st international conference on genetic algorithms, pp. 160–168. L. Erlbaum Associates Inc. (1985)
17.
Hochbaum, D.S.: Approximation Algorithms for NP-Hard Problems. PWS Publishing Co, Boston (1996)
18.
Jati, G.K.: Evolutionary discrete firefly algorithm for travelling salesman problem. In Adaptive and Intelligent Systems, pp. 393–403. Springer, Berlin (2011)
19.
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks, IEEE 1995, vol. 4, pp. 1942–1948 (1995)
20.
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291–307 (1970)CrossRefMATH
21.
22.
Kochenberger, G.A.: Handbook of Metaheuristics. Springer, New York (2003)
23.
Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)CrossRefMATH
24.
Lawler, E.L., Lenstra, J.K., Kan, A.R., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Vol. 3. Wiley, Chichester (1985)
25.
Lenstra, J.K., Rinnooy, K.A.: Some simple applications of the travelling salesman problem. Oper. Res. Quart. 26(5), 717–733 (1975)CrossRefMATH
26.
Malek, M., Guruswamy, M., Pandya, M., Owens, H.: Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Ann. Oper. Res. 21(1), 59–84 (1989)MathSciNetCrossRefMATH
27.
Martin, O., Otto, S.W., Felten, E.W.: Large-step markov chains for the traveling salesman problem. Complex Syst. 5(3), 299–326 (1991)MathSciNetMATH
28.
Melanie, M.: An Introduction to Genetic Algorithms. MIT Press, Massachusetts (1999). (Fifth printing)
29.
30.
31.
Payne, R.B., Sorenson, M.D.: The Cuckoos, vol. 15. Oxford University Press, Oxford (2005)
32.
Potvin, J.Y.: Genetic algorithms for the traveling salesman problem. Ann. Oper. Res. 63(3), 337–370 (1996)CrossRef
33.
Reinelt, G.: Tsplib a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)CrossRefMATH
34.
Reinelt, G.: The Traveling Salesman: Computational Solutions for TSP Applications, vol. 15. Springer, New York (1994)
35.
36.
Shi, X.H., Liang, Y.C., Lee, H.P., Lu, C., Wang, Q.X.: Particle swarm optimization-based algorithms for tsp and generalized tsp. Inf. Process. Lett. 103(5), 169–176 (2007)MathSciNetCrossRefMATH
37.
Shlesinger, M.F., Zaslavsky, G.M., Frisch, U.: Lévy Flights and Related Topics in physics:(Nice, 27–30 June 1994). Springer, New York (1995)CrossRef
38.
Talbi, E.G.: Metaheuristics: From Design to Implementation, vol. 74. Wiley, Hoboken (2009)
39.
Teodorovic, D., Lucic, P., Markovic, G., Orco, M.D.: Bee colony optimization: principles and applications. In: 2006 8th Seminar on Neural Network Applications in Electrical Engineering (NEUREL 2006), IEEE, pp. 151–156 (2006)
40.
Teodorovic, D.: Bee colony optimization (BCO). In: Lim, C.P., Jain, L.C., Dehuri, S. (eds.) Innovations in Swarm Intelligence, pp. 39–60. Springer Berlin (2009)
41.
Tucker, A.W. Letter to David Shmoys, 17 Feb 1983. [1:3].
42.
Wang, K.P., Huang, L., Zhou, C.G., Pang, W.: Particle swarm optimization for traveling salesman problem. In: 2003 International Conference on Machine Learning and Cybernetics, vol. 3, pp. 1583–1585. IEEE (2003)
43.
Wong, L.P., Low, M.Y.H., Chong, C.S.: A bee colony optimization algorithm for traveling salesman problem. In: Second Asia International Conference on Modeling and Simulation, 2008. AICMS 08, pp. 818–823. IEEE (2008)
44.
Yang, X.S.: Firefly algorithms for multimodal optimization. In: Stochastic Algorithms: Foundations and Applications, pp. 169–178. Springer, Berlin (2009)
45.
Yang, X.S., Deb, S., (2009) Cuckoo search via lévy flights. In: World congress on Nature and biologically inspired computing, NaBIC 2009, pp. 210–214. IEEE (2009)
46.
Yang, X.S., Deb, S.: Engineering optimisation by cuckoo search. Int. J. Math. Modell. Numer. Optim. 1(4), 330–343 (2010)MATH
47.
Yang, X.S.: Engineering Optimization: An Introdubtion with Metaheuristic Applications. Wiley, Hoboken (2010)CrossRef
48.
Yang, X.S., Gandomi, A.H.: Bat algorithm: a novel approach for global engineering optimization. Eng. Comput. 29(5), 464–483 (2012)CrossRef
49.
Yang, X.S., Cui, Z.H., Xiao, R.B., Gandomi, A.H., Karamanoglu, M.: Swarm Intelligence and Bio-Inspired Computation: Theory and Applications. Elsevier, Waltham (2013)
Metadaten
Titel
Improved and Discrete Cuckoo Search for Solving the Travelling Salesman Problem
verfasst von
Aziz Ouaarab
Belaïd Ahiod
Xin-She Yang
Copyright-Jahr
2014
Buch
Cuckoo Search and Firefly Algorithm

Print ISBN: 978-3-319-02140-9

Electronic ISBN: 978-3-319-02141-6

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-02141-6_4