Discrete Flower Pollination Algorithm for the Graph Coloring Problem

Sammanfattning

The graph coloring problem (GCP) is a famous NP-hard problem applicable to many real-world problems. The Flower Pollination Algorithm (FPA) is a relatively recently developed algorithm based on the pollination-behaviors of flowers. It has seen great results in single- and multi-objective optimization in continuous search spaces. This paper aims to develop and evaluate a discrete version of the FPA for solving the GCP. We propose an algorithm, the DFPA, that manages to translate the continuous search space of the original FPA to the combinatorial search space of the GCP. Results show that the DFPA performs consistently on small to medium sized graphs and performs better than previous attempts at discretizing the FPA. The DFPA however, performs significantly worse on larger graphs when compared to the state of the art algorithm HEAD.