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.

Cites

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

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