| On 2010-04-23 at 14:00:00 (Brussels Time) |
Abstract
We present two "position-guided" algorithms that work on top of a local search process. The objective is to employ positional information so as to guide the underlying local search toward the most appropriate search space regions. The search space regions are delimited using the notion of sphere: given a search space distance metric, a sphere is the set of potential solutions situated within a distance R from its center.The diversification algorithm performs a coarse-grained recording of its own trajectory by recording a limited number of spheres. Even if the total number of visited solutions is enormous, the number of visited spheres is always considerably smaller. The objective is to continually guide the exploration toward as-yet-unvisited R-spheres, and so, to ensure diversification. A second intensification algorithm performs deep investigations only within a "limited perimeter", in the proximity of a given (chosen) solution. 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. By coupling the two algorithms, we reached very competitive results for graph coloring. For example, we found for the first time the upper bound k=223 for the DIMACS graph djsc1000.9 (available in the literature since 1991).
Keywords
Local search, Graph coloring, Distance metric, Guided exploration
