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:
Parallel Collaborative Filtering Recommendation Model Based on Two-Phase Similarity Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Water Wave Optimization for the Traveling Salesman Problem

Authors : Xiao-Bei Wu, Jie Liao, Zhi-Cheng Wang

Published in: Intelligent Computing Theories and Methodologies

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

Water wave optimization (WWO) is a novel evolutionary algorithm borrowing ideas from shallow water wave models for global optimization problems. This paper presents a first study on WWO for a combinatorial optimization problem — the traveling salesman problem (TSP). We adapt the operators in the original WWO so as to effectively exploring in a discrete solution space. The results of simulation experiments on a set of test instances from TSPLIB show that the proposed WWO algorithm is not only applicable and efficient for TSP, but also has significant performance advantage in comparison with two other methods, genetic algorithm (GA) and biogeography-based optimization (BBO).

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 A Water Wave Optimization Algorithm with Variable Population Size and Comprehensive Learning
next chapter Improved Dendritic Cell Algorithm with False Positives and False Negatives Adjustable
Literature
1.
Holland, J.H.: Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence. U Michigan Press (1975)
2.
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948. IEEE Press, New York (1995)
3.
Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997)MathSciNetCrossRefMATH
4.
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)CrossRef
5.
Simon, D.: Biogeography-based optimization. IEEE Trans. Evol. Comput. 12(6), 702–713 (2008)CrossRef
6.
Yang, X.S.: Hossein Gandomi, A.: Bat algorithm: a novel approach for global engineering optimization. Eng. Comput. 29(5), 464–483 (2012)CrossRef
7.
Mei, C.C., Liu, P.L.: Surface waves and coastal dynamics. Annu. Rev. Fluid Mech. 25(1), 215–240 (1993)CrossRef
8.
9.
Banks, A., Vincent, J., Anyakoha, C.: A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Nat. Comput. 7(1), 109–124 (2008)MathSciNetCrossRefMATH
10.
Prado, R.S., Silva, R.C., Guimarães, F.G., Neto, O.M.: Using differential evolution for combinatorial optimization: a general approach. In: 2010 IEEE International Conference on Systems Man and Cybernetics, pp. 11–18. IEEE Press, New York (2010)
11.
Lawler, E.L., Lenstra, J.K., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley and Sons, New York (1985)MATH
12.
Wang, H.F., Wu, K.Y.: Hybrid genetic algorithm for optimization problems with permutation property. Comput. Oper. Res. 31(14), 2453–2471 (2004)MathSciNetCrossRef
13.
Smith, T.H.C., Thompson, G.L.: A LIFO implicit enumeration search algorithm for the symmetric traveling salesman problem using Held and Karp’s 1-tree relaxation. Ann. Discret. Math. 1, 479–493 (1977)MathSciNetCrossRef
14.
Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)CrossRef
15.
Potvin, J.Y.: Genetic algorithms for the traveling salesman problem. Ann. Oper. Res. 63(3), 337–370 (1996)CrossRef
16.
Wu, J.: Genetic Algorithm for the Traveling Salesman Problem. PhD Thesis, Oklahoma State University, Stillwater, Oklahoma (2000)
17.
Shi, X.H., Liang, Y.C., Lee, H.P., et al.: Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf. Process. Lett. 103(5), 169–176 (2007)MathSciNetCrossRef
18.
Song, Y., Liu, M., Wang, Z.: Biogeography-based optimization for the traveling salesman problems. In: Third International Joint Conference on Computational Science and Optimization, vol. 1, pp. 295–299. IEEE, New York (2010)
19.
Huang, H.: Dynamics of Surface Waves in Coastal Waters: Wave-current-bottom Interactions. Springer, Berlin-Heidelberg (2009)CrossRefMATH
20.
Reinelt, G.: TSPLIB—A traveling salesman problem library. ORSA Journal on Computing 3(4), 376–384 (1991)CrossRefMATH
21.
Eshelman, L.J.: The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination. In: Rawlins, G.J.E. (ed.) Foundations of Genetic Algorithms, pp. 265–283. Morgan Kauffman, Los Altos (1991)
Metadata
Title
Water Wave Optimization for the Traveling Salesman Problem
Authors
Xiao-Bei Wu
Jie Liao
Zhi-Cheng Wang
Copyright Year
2015
Book
Intelligent Computing Theories and Methodologies

Print ISBN: 978-3-319-22179-3

Electronic ISBN: 978-3-319-22180-9

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-22180-9_14

Premium Partner

    Image Credits