Computer experiments with a parallel clonal selection algorithm for the Graph Coloring Problem

Artificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of the algorithm over a set of well-established benchmark graphs and random graphs is compared with a parallel Tabu Search algorithm.