Algorithms for the graph coloring problem based on swarm intelligence

摘要

In this paper, we tailor the Artificial Bee Colony (ABC) algorithm to solve the Graph Coloring Problem (GCP). We call this algorithm as the ABC-GCP. In the proposed ABC-GCP, a sequence of nodes of the given graph is generated. Then, based on this order of nodes, a color assignment algorithm is executed on the graph to color it. The sequence generation is implemented by the ABC algorithm in which a vector of continuous components is mapped to a sequence of integer numbers. The color assignment is based on a known heuristic called “Recursive Largest First (RLF)”, which gets the generated sequence and tries to color it with a least amount of colors. The proposed ABC-GCP is tested with randomly gated graphs with different densities, and it is compared with some other relevant algorithms. The experimental results demonstrate the superiority of the proposed algorithm in comparison with the other algorithms.