Published in Volume XV, 2005, pages 110-123

Authors: Cornelius CROITORU, Gabriel NEGARA

Abstract

In this paper, we introduce a new ant-like algorithm for the graph coloring problem, based on an ant system meta-heuristic. EAC (Experience-based Ant Coloring) uses an ant system paradigm in which a number of agents (ants) perform specific colorings during a number of iterations. The colorings are performed using algorithms adapted to the ant system paradigm and are based on the experience from the previous iterations. After each iteration, the agents update the system memory. EAC introduces a new type of graph adjacency matrix and uses a new ant system approach for the graph coloring problem. We have experimented the implementation of the algorithm on graphs from the DIMACS Computational Challenge, obtaining good results.

Bibtex

@article{sacscuza:croitoru2005eac(-anaga,
  title={Experience-based Ant Coloring (EAC) - A new ant-like graph-coloring algoritm.},
  author={Cornelius CROITORU and Gabriel NEGARA},
  journal={Scientific Annals of Computer Science},
  volume={15},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2005},
  pages={110--123},
  publisher={``A.I. Cuza'' University Press}
}