An empirical evaluation of Gravitational Swarm Intelligence for graph coloring algorithm

This paper gives an extensive empirical evaluation of the innovative nature inspired Gravitational Swarm Intelligence (GSI) algorithm solving the Graph Coloring Problem (GCP). GSI follows the Swarm Intelligence problem solving approach, where the spatial position of agents is interpreted as problem solution and agent motion is determined solely by local information, avoiding any central control system. To apply GSI to search for solutions of GCP, we map agents to graph's nodes. Agents move as particles in the gravitational field defined by goal objects corresponding to colors. When the agents fall in the gravitational well of the color goal, their corresponding nodes are colored by this color. Graph's connectivity is mapped into a repulsive force between agents corresponding to adjacent nodes. We discuss the convergence of the algorithm, testing it over an extensive suite of well-known benchmarking graphs. Comparison of this approach to state-of-the-art approaches in the literature shows improvements in many of the benchmark graphs.