Gravitational swarm for graph coloring
- REBOLLO RUIZ, ISRAEL CARLOS
- Manuel Graña Romay Director
Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea
Fecha de defensa: 27 de julio de 2012
- Juan Luis Pavón Mestras Presidente/a
- Ana Isabel González Acuña Secretaria
- Javier de Lope Asiaín Vocal
- Richard J. Duro Fernández Vocal
- Diego Andina de la Fuente Vocal
Tipo: Tesis
Resumen
Abstract:This Thesis deals with the development of a Swarm Intelligence algorithm to solve theclassical problem of Graph Coloring. The Gravitational Swarm for Graph Coloring(GS-GC) algorithm maps the GCP problem into a collection of autonomous agents thatmove in a space following a global gravitational attraction to the color goals andattraction-repulsion local forces corresponding to the graph topology. The Thesisprovides formal asymptotic convergence proofs showing that the GS-GC stationarystates correspond to GCP solutions. The Thesis provides also extensive empiricalsupport of the GS-GC comparing it with state of the art algorithms.