Position-guided diversification and intensification for graph coloring local search

Daniel Porumbel

We present two position-guided algorithms that work on top of a local search process (Tabu Search) so as to guide it toward certain targeted regions of the search space. For this, the search space is structured in spheres, and, using evidence from a search space “cartography”, we take profit from the following clustering hypothesis: the high quality configurations are not randomly scattered in the search space, but rather grouped in clusters within spheres of diameter R=0.1|V|.

The diversification algorithm uses a learning process so as to guide the underlying local search toward as-yet-unvisited R-spheres. The intensification algorithm makes deep investigations within a ``limited perimeter'' around a given (promising) configuration. For this, it employs a breath-first-search routine to enumerate all R-spheres from this ``limited perimeter'', and, each of these spheres is thoroughly explored by numerous independent local search processes. We experimentally observed that if such a ``limited perimeter'' contains a global optimum, the intensification algorithm does not fail in eventually finding it. This pair of algorithms reached very competitive results, in particular they colored for the first time the well-studied DIMACS instance djsc1000.9 with k=223 colors.