Gravitational swarm for graph coloring

  1. REBOLLO RUIZ, ISRAEL CARLOS
Zuzendaria:
  1. Manuel Graña Romay Zuzendaria

Defentsa unibertsitatea: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Fecha de defensa: 2012(e)ko uztaila-(a)k 27

Epaimahaia:
  1. Juan Luis Pavón Mestras Presidentea
  2. Ana Isabel González Acuña Idazkaria
  3. Javier de Lope Asiaín Kidea
  4. Richard J. Duro Fernández Kidea
  5. Diego Andina de la Fuente Kidea
Saila:
  1. Konputazio Zientzia eta Adimen Artifiziala

Mota: Tesia

Teseo: 115421 DIALNET

Laburpena

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.