A Study into the Improvement of Binary Hopfield Networks for Map Coloring

Authors

Gloria Galán-Marín , Enrique Mérida-Casermeiro , Domingo López-Rodríguez , Juan Miguel Ortiz-De-Lazcano-Lobato

Published

1 January 2007

Publication details

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), (4432 LNCS), PART 2, pp. 98-106

Links

DOI PDF

 

Abstract

The map-coloring problem is a well known combinatorial optimization problem which frequently appears in mathematics, graph theory and artificial intelligence. This paper presents a study into the performance of some binary Hopfield networks with discrete dynamics for this classic problem. A number of instances have been simulated to demonstrate that only the proposed binary model provides optimal solutions. In addition, for large-scale maps an algorithm is presented to improve the local minima of the network by solving gradually growing submaps of the considered map. Simulation results for several n-region 4-color maps showed that the proposed neural algorithm converged to a correct colouring from at least 90% of initial states without the fine-tuning of parameters required in another Hopfield models. © Springer-Verlag Berlin Heidelberg 2007.

Citation

How to cite

G. Galán-Marín, E. Mérida-Casermeiro, D. López-Rodríguez, et al. “A Study into the Improvement of Binary Hopfield Networks for Map Coloring”. In: Adaptive and Natural Computing Algorithms, 8th International Conference, ICANNGA 2007, Warsaw, Poland, April 11-14, 2007, Proceedings, Part II. Ed. by B. Beliczynski, A. Dzielinski, M. Iwanowski and B. Ribeiro. Vol. 4432 LNCS. Lecture Notes in Computer Science PART 2. cited By 3; Conference of 8th International Conference on Adaptive and Natural Computing Algorithms, ICANNGA 2007 ; Conference Date: 11 April 2007 Through 14 April 2007; Conference Code:71057. Warsaw: Springer Verlag, 2007, pp. 98-106. DOI: 10.1007/978-3-540-71629-7_12. URL: https://doi.org/10.1007/978-3-540-71629-7_12.

BibTeX

<pre><code>

@InProceedings{GalanMarin2007a, author = {G. Galán-Marín and E. Mérida-Casermeiro and D. López-Rodríguez and J.M. Ortiz-De-Lazcano-Lobato}, booktitle = {Adaptive and Natural Computing Algorithms, 8th International Conference, {ICANNGA} 2007, Warsaw, Poland, April 11-14, 2007, Proceedings, Part {II}}, title = {A Study into the Improvement of Binary Hopfield Networks for Map Coloring}, year = {2007}, address = {Warsaw}, editor = {Bartlomiej Beliczynski and Andrzej Dzielinski and Marcin Iwanowski and Bernardete Ribeiro}, note = {cited By 3; Conference of 8th International Conference on Adaptive and Natural Computing Algorithms, ICANNGA 2007 ; Conference Date: 11 April 2007 Through 14 April 2007; Conference Code:71057}, number = {PART 2}, pages = {98-106}, publisher = {Springer Verlag}, series = {Lecture Notes in Computer Science}, volume = {4432 LNCS}, abstract = {The map-coloring problem is a well known combinatorial optimization problem which frequently appears in mathematics, graph theory and artificial intelligence. This paper presents a study into the performance of some binary Hopfield networks with discrete dynamics for this classic problem. A number of instances have been simulated to demonstrate that only the proposed binary model provides optimal solutions. In addition, for large-scale maps an algorithm is presented to improve the local minima of the network by solving gradually growing submaps of the considered map. Simulation results for several n-region 4-color maps showed that the proposed neural algorithm converged to a correct colouring from at least 90% of initial states without the fine-tuning of parameters required in another Hopfield models. © Springer-Verlag Berlin Heidelberg 2007.}, bibsource = {dblp computer science bibliography, https://dblp.org}, biburl = {https://dblp.org/rec/conf/icannga/MarinCLO07.bib}, document_type = {Conference Paper}, doi = {10.1007/978-3-540-71629-7_12}, journal = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}, keywords = {Coloring; Graph theory; Large scale systems; Optimization; Problem solving, Classic problems; Large-scale maps; Map coloring, Hopfield neural networks}, source = {Scopus}, url = {https://doi.org/10.1007/978-3-540-71629-7_12}, }

<button class='copy-bib-btn' id='copy-bib-btn'><i class='bi bi-clipboard'></i> Copy BibTeX</button>

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

A Study into the Improvement of Binary Hopfield Networks for Map Coloring

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

1. Yuxin Ding (2012). Artificial Higher Order Neural Networks for Modeling Combinatorial Optimization Problems. IGI Global eBooks DOI
2. Yuxin Ding, Dong Li, Bin Zhao, et al. (2011). High Order Hopfield Network with Self-feedback to Solve Crossbar Switch Problem. Lecture notes in computer science DOI
3. Yuxin Ding, Dong Li, Ling Wang, et al. (2010). A High Order Neural Network to Solve Crossbar Switch Problem. Lecture notes in computer science DOI
4. Yuxin Ding, Ye Li, Min Xiao, et al. (2010). A high order neural network to solve N-queens problem. DOI