Gravitational swarm for graph coloring

  1. REBOLLO RUIZ, ISRAEL CARLOS
Dirigida por:
  1. Manuel Graña Romay Director

Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 27 de julio de 2012

Tribunal:
  1. Juan Luis Pavón Mestras Presidente/a
  2. Ana Isabel González Acuña Secretaria
  3. Javier de Lope Asiaín Vocal
  4. Richard J. Duro Fernández Vocal
  5. Diego Andina de la Fuente Vocal

Tipo: Tesis

Teseo: 115421 DIALNET

Resumen

Resumen:Esta tesis aborda el desarrollo de un algoritmo Swarm Intelligence para resolver elproblema clásico del coloreado de grafos. El algoritmo Gravitational Swarm for GraphColoring (GS-GC) mapea el problema GCP en una colección de agentes autónomosque se mueven en un espacio siguiendo una atracción gravitacional global hacia lasmetas de color y unas fuerzas de atracción-repulsión locales que corresponden a latopología del grafo. La Tesis ofrece pruebas formales de convergencia asintótica quemuestran que los estados estacionarios del GS-GC corresponden a soluciones de GCP.La tesis ofrece también un amplio soporte empírico al GS-GC comparado conalgoritmos avanzados del estado del arte.