nach oben

Soft Computing

Erschienen in:

29.01.2016 | Methodologies and Application

Improving the Hopfield model performance when applied to the traveling salesman problem

A divide-and-conquer scheme

verfasst von: Lucas García, Pedro M. Talaván, Javier Yáñez

Erschienen in: Soft Computing | Ausgabe 14/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The continuous Hopfield network (CHN) can be used to solve, among other combinatorial optimization problems, the traveling salesman problem (TSP). In order to improve the performance of this heuristic technique, a divide-and-conquer strategy based on two phases is proposed. The first phase involves linking cities with the most neighbors to define a set of chains of cities and, secondly, to join these with isolated cities to define the final tour. Both problems are solved by mapping the two TSPs onto their respective CHNs. The associated parameter-setting procedures are deduced; these procedures ensure the feasibility of the obtained tours, and the quality of the solutions is compared with the pure CHN approach using some traveling salesman problem library (TSPLIB) instances. By means of this strategy, solving TSP instances with sizes of up to 13,509 cities are allowed with the computational resources we had available. Finally, the new divide-and-conquer procedure is improved by tuning the parameter which controls the first phase.

Vorheriger Artikel Application of bivariate fuzzy Bernstein polynomials to solve two-dimensional fuzzy integral equations

Nächster Artikel An incentive mechanism for K-anonymity in LBS privacy protection based on credit mechanism

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

A city can have \(\tau \) neighbors but may be chosen as a neighbor by more than \(\tau \) cities. This definition guarantees that the distance matrix is symmetric.

All simulations have been accomplished using a workstation equipped with an Intel Xeon E5-2620 @ 2 GHz with 64 GB RAM.

MATLAB code can be made available upon direct request to the authors.

Di Marco M, Forti M, Grazzini M, Pancioni L (2014) Necessary and sufficient condition for multistability of neural networks evolving on a closed hypercube. Neural Netw 54:38–48CrossRefMATH

Hopfield JJ (1984) Neurons with graded response have collective computational properties like those of two-state neurons. Proc Natl Acad Sci 81(10):3088–3092CrossRef

Hopfield JJ, Tank DW (1985) “Neural” computation of decisions in optimization problems. Biol Cybern 52(3):141–152MATH

Jolai F, Ghanbari A (2010) Integrating data transformation techniques with Hopfield neural networks for solving travelling salesman problem. Expert Syst Appl 37(7):5331–5335CrossRef

Lawler EL (1985) The traveling salesman problem: a guided tour of combinatorial optimization. In: Wiley-Interscience series in discrete mathematics. Wiley, New York

Mérida-Casermeiro E, Galán-Marín G, Munoz-Perez J (2001) An efficient multivalued Hopfield network for the traveling salesman problem. Neural Process Lett 14(3):203–216CrossRefMATH

Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237–244CrossRefMATH

Reinelt G (1991) TSPLIB. A traveling salesman problem library. ORSA J Comput 3(4):376–384CrossRefMATH

Reinelt G (1994) The traveling salesman: computational solutions for TSP applications. Springer, New York

Salcedo-Sanz S, Ortiz-García EG, Pérez-Bellido ÁM, Portilla-Figueras A, López-Ferreras F (2009) On the performance of the LP-guided Hopfield network-genetic algorithm. Comput Oper Res 36(7):2210–2216MathSciNetCrossRefMATH

Schmidhuber J (2015) Deep learning in neural networks: an overview. Neural Netw 61:85–117CrossRef

Suh T, Esat II (1998) Solving large scale combinatorial optimisation problems based on a divide and conquer strategy. Neural Comput Appl 7(2):166–179

Talaván PM, Yáñez J (2002) Parameter setting of the Hopfield network applied to TSP. Neural Netw 15(3):363–373CrossRef

Talaván PM, Yáñez J (2005) A continuous Hopfield network equilibrium points algorithm. Comput Oper Res 32(8):2179–2196MathSciNetCrossRefMATH

Talaván PM, Yáñez J (2006) The generalized quadratic knapsack problem. A neuronal network approach. Neural Netw 19(4):416–428CrossRefMATH

Tan K, Tang H, Ge S (2005) On parameter settings of Hopfield networks applied to traveling salesman problems. IEEE Trans Circuits Syst I Regul Pap 52(5):994–1002MathSciNetCrossRef

Tang H, Tan KC, Zhang Y (2007) Neural networks: computational models and applications. Studies in Computational Intelligence, vol 53, Springer, Berlin, Heidelberg

Wang RL, Tang Z, Cao QP (2002) A learning method in Hopfield neural network for combinatorial optimization problem. Neurocomputing 48(1):1021–1024CrossRefMATH

Wen U-P, Lan K-M, Shih H-S (2009) A review of Hopfield neural networks for solving mathematical programming problems. Eur J Oper Res 198(3):675–687MathSciNetCrossRefMATH

Wilson G, Pawley G (1988) On the stability of the travelling salesman problem algorithm of Hopfield and tank. Biol Cybern 58(1):63–70MathSciNetCrossRefMATH

Woeginger GJ (2003) Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization Eureka, You Shrink!. Springer, New York, pp 185–207

Titel: Improving the Hopfield model performance when applied to the traveling salesman problem
A divide-and-conquer scheme
verfasst von: Lucas García
Pedro M. Talaván
Javier Yáñez
Publikationsdatum: 29.01.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 14/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2039-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 14/2017

Discussion on semi-immune algorithm behaviour based on fractal analysis

Multilevel framework for large-scale global optimization

A novel evolutionary technique based on electrolocation principle of elephant nose fish and shark: fish electrolocation optimization

An online and incremental GRLVQ algorithm for prototype generation based on granular computing

Interval fuzzy sliding-mode formation controller design

Energy-efficient resource allocation for multiuser OFDMA system based on hybrid genetic simulated annealing