Gravitational swarm for graph coloring

  1. REBOLLO RUIZ, ISRAEL CARLOS
unter der Leitung von:
  1. Manuel Graña Romay Doktorvater/Doktormutter

Universität der Verteidigung: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 27 von Juli von 2012

Gericht:
  1. Juan Luis Pavón Mestras Präsident/in
  2. Ana Isabel González Acuña Sekretär/in
  3. Javier de Lope Asiaín Vocal
  4. Richard J. Duro Fernández Vocal
  5. Diego Andina de la Fuente Vocal
Fachbereiche:
  1. Ciencia de la Computación e Inteligencia Artificial

Art: Dissertation

Teseo: 115421 DIALNET

Zusammenfassung

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.