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

 

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

Please, cite this work as:

[Gal+07] 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

@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},
}

Bibliometric data

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

4

CITATIONS

4 Total citations

0 Recent citations

0.71 Field Citation Ratio

n/a Relative Citation Ratio

• Citations
• CrossRef - Citation Indexes: 4
• Scopus - Citation Indexes: 4

• Captures
• Mendeley - Readers: 4

-

see details

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] Y. Ding. “Artificial Higher Order Neural Networks for Modeling Combinatorial Optimization Problems”. In: Artificial Higher Order Neural Networks for Modeling and Simulation. IGI Global, 2013, p. 44–57. ISBN: 9781466621763. DOI: 10.4018/978-1-4666-2175-6.ch003. URL: http://dx.doi.org/10.4018/978-1-4666-2175-6.ch003.

[2] Y. Ding, L. Dong, L. Wang, et al. “A High Order Neural Network to Solve Crossbar Switch Problem”. In: Neural Information Processing. Models and Applications. Springer Berlin Heidelberg, 2010, p. 692–699. ISBN: 9783642175343. DOI: 10.1007/978-3-642-17534-3_85. URL: http://dx.doi.org/10.1007/978-3-642-17534-3_85.

[3] Y. Ding, L. Dong, B. Zhao, et al. “High Order Hopfield Network with Self-feedback to Solve Crossbar Switch Problem”. In: Neural Information Processing. Springer Berlin Heidelberg, 2011, p. 315–322. ISBN: 9783642249655. DOI: 10.1007/978-3-642-24965-5_35. URL: http://dx.doi.org/10.1007/978-3-642-24965-5_35.

[4] Y. Ding, Y. Li, M. Xiao, et al. “A high order neural network to solve N-queens problem”. In: The 2010 International Joint Conference on Neural Networks (IJCNN). IEEE, Jul. 2010, p. 1–6. DOI: 10.1109/ijcnn.2010.5596706. URL: http://dx.doi.org/10.1109/ijcnn.2010.5596706.