Daniel Cosmin Porumbel

Jin Kao Hao

Pascale Kuntz

A Search Space "Cartography" for Guiding Graph Coloring Heuristics

Keywords: graph coloring, local optima distribution, search by learning

We present a search space analysis and its application in improving local search algorithms for the graph coloring problem. Using a classical distance measure between colorings, we introduce the following clustering hypothesis: the high quality solutions are not randomly scattered in the search space, but rather grouped in clusters within spheres of specific diameter. We first provide intuitive evidence for this hypothesis by presenting a projection of a large set of local minima in the 3D space. An experimental confirmation is also presented: we introduce two algorithms that exploit the hypothesis by guiding an underlying Tabu Search (TS) process. The first algorithm (TS-Div) uses a learning process to guide the basic TS process toward as-yet-unvisited spheres. The second algorithm (TS-Int) makes deep investigations within a bounded region by organizing it as a tree-like structure of connected spheres. We experimentally demonstrate that if such a region contains a global optimum, TS-Int does not fail in eventually finding it. This pair of algorithms significantly outperforms the underlying basic TS algorithm; it can even improve some of the best-known solutions ever reported in the literature (e.g. for dsjc1000.9).

Introduction

The graph coloring problem (COL) is a well-known problem in Combinatorial Optimization. It is one of the 21 fundamental problems proved to be NP-Complete by Richard Karp in 1972 [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Given a graph G, COL asks to find the minimum number of colors (the chromatic number χ(G)) necessary to color the vertices of G such that no two adjacent vertices share the same color. Due to its simplicity and generality, many practical applications have been modeled using coloring problems: timetabling [START_REF] Burke | A university timetabling system based on graph colouring and constraint manipulation[END_REF][START_REF] De Werra | An introduction to timetabling[END_REF], scheduling [START_REF] Gamache | A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding[END_REF][START_REF] Leighton | A graph coloring algorithm for large scheduling problems[END_REF][START_REF] Lewandowski | Experiments with parallel graph coloring heuristics and applications of graph coloring[END_REF], register allocation in compilers [START_REF] Chaitin | Register allocation & spilling via graph coloring[END_REF][START_REF] Lewandowski | Experiments with parallel graph coloring heuristics and applications of graph coloring[END_REF], frequency assignment in cellular networks [START_REF] Hale | Frequency assignment: Theory and applications[END_REF], air traffic flow management [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF], supply chain management [START_REF] Lim | Robust Graph Coloring for Uncertain Supply Chain Management[END_REF], etc.

The first algorithms for graph coloring were developed in the 1960s [START_REF] Brown | Chromatic scheduling and the chromatic number problem[END_REF][START_REF] Christofides | An algorithm for the chromatic number of a graph[END_REF][START_REF] Welsh | An upper bound for the chromatic number of a graph and its application to timetabling problems[END_REF]. Since then, a considerable number of new methods have been developed and important progress has been made. The second DIMACS Implementation Challenge [START_REF] Johnson | Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge[END_REF] collected a large set of graphs that was used extensively since 1996 for benchmarking coloring algorithms.

Existing heuristic and metaheuristic coloring algorithms belong to three main solution approaches: sequential construction (algorithms like Dsatur [START_REF] Brelaz | New methods to color the vertices of a graph[END_REF], Iterated Greedy IG [START_REF] Culberson | Exploring the k-colorable landscape with iterated greedy[END_REF], RLX and XRLF [START_REF] Johnson | Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning[END_REF]-very fast methods but not particularly efficient), local search (Tabu Search [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Dorne | Tabu search for graph coloring, T-colorings and set T-colorings[END_REF][START_REF] Fleurent | Genetic and hybrid algorithms for graph coloring[END_REF][START_REF] Galinier | Hybrid Evolutionary Algorithms for Graph Coloring[END_REF][START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF], Simulated Annealing [START_REF] Chams | Some experiments with simulated annealing for coloring graphs[END_REF][START_REF] Johnson | Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning[END_REF], Iterated Local Search [START_REF] Chiarandini | An application of iterated local search to graph coloring[END_REF][START_REF] Paquete | An experimental investigation of iterated local search for coloring graphs[END_REF], Variable Neighborhood Search [START_REF] Avanthay | A variable neighborhood search for graph coloring[END_REF][START_REF] Hertz | Variable space search for graph coloring[END_REF][START_REF] Trick | A large neighborhood search heuristic for graph coloring[END_REF]) and evolutionary hybrid or population based search [START_REF] Dorne | A new genetic local search algorithm for graph coloring[END_REF][START_REF] Fleurent | Genetic and hybrid algorithms for graph coloring[END_REF][START_REF] Galinier | Hybrid Evolutionary Algorithms for Graph Coloring[END_REF][START_REF] Galinier | An adaptive memory algorithm for the k-coloring problem[END_REF][START_REF] Malaguti | A Metaheuristic Approach for the Vertex Coloring Problem[END_REF]. A recent survey, especially for the local search methods, is provided in [START_REF] Galinier | A survey of local search methods for graph coloring[END_REF].

We note that, very recently, two less-traditional local search algorithms proved surprisingly competitive [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Hertz | Variable space search for graph coloring[END_REF] and they matched many of the best results found so far in two decades. These local search algorithms focus on local level improvements-i.e. more powerful neighborhood relations [START_REF] Hertz | Variable space search for graph coloring[END_REF] or alternative solution encodings [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF]. Generally speaking, there are numerous local-level techniques that can enhance the performance of any local search heuristic.

However, local searches are also often substantially limited by the fact that they do not exploit enough global information about the search process. In most combinatorial optimization problems, local search methods are not typically very concerned about the relations between potential solutions (configurations) visited at different stages of the search. Moreover, most studies that analyze the search space structure (for example [START_REF] Culberson | Frozen development in graph coloring[END_REF][START_REF] Hamiez | An analysis of solution properties of the graph coloring problem[END_REF][START_REF] Hertz | Local optima topology for the k-coloring problem[END_REF] for graph coloring) focus more on providing theoretical information than on effectively using such information to improve an algorithm.

Given any local search process searching through a search space, some important questions might be:

• what does the exploration path look like ?

• which regions is the process more likely to explore?

• can we be sure the search process does not explore only a limited number of regions?

• what is the spatial distribution of high quality solutions?

• are they randomly scattered or are they grouped in structures?

Our study consists in an exploration of these issues. The paper can be divided in two parts: the first one deals with search space analysis, and the second one effectively exploits the information from this analysis for the purpose of developing two new algorithms.

We analyze the spatial distribution of the high quality configurations (local optima) discovered by a classical Tabu Search (TS) algorithm for graph coloring (Tabucol) in a given period. The high quality configurations are compared with a distance measurecomputed with a fast algorithm-and the resulting distance matrix is embedded in IR 3 (see Section 3.1) with a Multidimensional Scaling (MDS) procedure [START_REF] Kruskal | Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis[END_REF]. In the 3D representation, points represent colorings and the basic Euclidean distance between these points is an approximation of the computed distance between the associated colorings. The representations show that the high quality configurations are not randomly scattered in the space, but they form clusters that can be covered by spheres of specific diameter.

In the second part of the paper, we develop two algorithms that use a sphere-based search space organization. The first (TS-Div) is a classical Tabu Search (TS) algorithm that keeps track of all the visited configurations by recording all visited spheres (Section 4). It also uses an additional learning process that guides the underlying Tabu Search process toward as-yet-unexplored spheres. TS-Int (Section 5) is a second-stage algorithm that performs in-depth explorations in the proximity of the high quality colorings provided by TS-Div.

The next section briefly outlines the formal details of the problem formulation, the local search algorithm (Tabu Search) and the test graphs. Section 3 presents the formal analysis of the spatial distribution of high quality colorings in the search space. Next, in Section 4 and Section 5, we present the two algorithms: TS-Div (assuring diversification) and TS-Int (assuring intensification). Numerical results and discussions are presented in Section 6, followed by conclusions in the last section.

2 Preliminary definitions and the general setting

Problem formulation and coloring representation

Let G = (V, E) be a graph with vertex set V and edge set E. The general graph coloring problem is to determine the chromatic number χ(G) of G, i.e. the minimum value of k for which there is k-coloring (i.e. a function c :

V → {1, 2, • • • , k}) with no conflicts (i.e. with no {i, j} ∈ E such that c(i) = c(j)).
In this study, we directly deal with the k-coloring problem: given a number of colors k, decide if G has a k-coloring with no conflicts. We start with a very large k (e.g. k = |V |) and we decrease k each time the corresponding k-coloring problem is solved. We recall the following definitions. Moreover, C is said to be a legal coloring if and only if c(i) = c(j), ∀{i, j} ∈ E. A legal coloring represents a solution to the k-coloring problem. All colorings, both proper and improper, form the search space Ω of the problem.

Definition 2 (Partition representation)

A k-coloring C = [c(1) ,c(2), . . . , c(|V |)] of G is denoted as a partition {C 1 , C 2 , . . . , C k } of V (i.e. a set of k disjoint subsets of V covering V ) such that ∀x, y ∈ V , x, y ∈ C i ⇔ c(x) = c(y) = i.
We say that C i is the class color i induced by the coloring C, i.e. the set of vertices having color i in C. This partition definition is particularly relevant to avoid symmetry issues arising from the color based encoding. It is consistent with the set-theoretic partition distance (see Section 4.2). A (G, k) problem is considered solved if and only if the algorithm finds a coloring such that f (C) = 0. A conflicting vertex is any v ∈ V , that has a neighbor of the same color.

Tabu Search for Graph Coloring

The search space analysis and the resolution methods from this paper are based on Tabucol [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF], a classical Tabu Search for graph coloring [START_REF] Glover | Tabu Search[END_REF]. Basically, Tabucol just passes from one configuration to another by modifying the color of a conflicting vertex, but it imposes the condition that each color change has to be not-Tabu, i.e. not performed in the near past. The general description of our TS version is presented in Algorithm 1; the stopping condition is to find a legal coloring or to reach a maximum number of iterations. The most important details that need to be filled are the neighborhood relation N and the Tabu list management.

Algorithm 1 Pseudocode General Tabu Search

Input: graph G, color number k, (optional) the start configuration Cst Return value: f (C * ) (i.e. 0 if a legal coloring is found) C: the current coloring; C * : the best coloring ever found Begin

1. C:=Cst (choose C = random configuration if Cst is not specified.) 2. while a stopping condition is not met (a) find the best C ′ ∈ N (C) so that move C <i,i ′ > -→ C ′ is not Tabu (b) C = C ′ (i.e. perform move < i, i ′ >; C(i) := i ′ ) (c) if (f (C) < f (C * )) • C * = C (d) make the pair (i, i ′ ) Tabu for T ℓ iterations

End

Neighborhood N Given a coloring problem (G(V, E),k), the search space Ω consists of all possible colorings of G; thus |Ω| = |V | k . A simple neighborhood function N : Ω → 2 Ω -{∅} can be defined as follows. For any configuration C ∈ Ω, a neighbor C ′ is obtained by changing the color of a single conflicting vertex in C. Definition 4 (Plateau) We say subset P ⊂ Ω is a plateau of Ω if and only if: (i) all configurations in P have the same conflict number and (ii) for any C a , C b ∈ P , there exist configurations C 1 , C 2 , . . . , C n ∈ P such that:

C 1 ∈ N (C a ), C 2 ∈ N (C 1 ), . . ., C n ∈ N (C n-1 ) and C b ∈ N (C n ).
Tabu list management Tabu list is a structure used to record forbidden moves that have been performed in the recent past. For our problem, a move is characterized by a couple < i, i ′ > meaning that the color c(i) of a conflicting vertex i is changed to a new color i ′ . Each time a move < i, i ′ > is realized, i is forbidden to receive again the color c(i) for the next T ℓ (Tabu tenure) iterations.

In our case, the Tabu tenure T ℓ is dynamically adjusted by a function depending on the conflict number (f ) (like in [START_REF] Dorne | A new genetic local search algorithm for graph coloring[END_REF][START_REF] Dorne | Tabu search for graph coloring, T-colorings and set T-colorings[END_REF][START_REF] Galinier | Hybrid Evolutionary Algorithms for Graph Coloring[END_REF]), but also on the number m of the last consecutive moves that have not changed f . More precisely, T ℓ = random(A) + α * f (C) + m mmax where α and A are two parameters whose values are taken from [START_REF] Galinier | Hybrid Evolutionary Algorithms for Graph Coloring[END_REF] (i.e. α = 0.6 and A = 10). The last term is introduced only to change T ℓ when the algorithm is completely blocked looping on a plateau, or more exactly when f does not change for m max moves. Each series of consecutive m max (m max = 1000) moves with no conflict number variation triggers the increment of all subsequent values of T ℓ (until f changes again). This additional term prevents the search process from getting blocked looping on a plateau while not affecting its behavior outside plateaus.

The benchmark graphs

In this article, experimental studies are carried out on a variety of difficult problems from the well-established DIMACS Challenge Benchmark [START_REF] Johnson | Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge[END_REF]: (i) dsjcX.Y -a series of classical random graphs [START_REF] Johnson | Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning[END_REF] with unknown chromatic numbers (X denotes |V | and Y denotes the density); (ii) le450.25c and le450.25d-the most difficult "Leighton graphs" [START_REF] Leighton | A graph coloring algorithm for large scheduling problems[END_REF] with χ = 25 (they have at least one clique of size χ); (iii) f lat300.28 and f lat1000.76-the most difficult "flat" graphs [START_REF] Culberson | Exploring the k-colorable landscape with iterated greedy[END_REF] with χ denoted by the last number (generated by partitioning the vertex set in χ classes, and by distributing the edges only between vertices of different classes); (iv) R1000.1-a geometric graph generated by picking random points (nodes) in the plane and by linking the points situated within a certain geometrical distance.

Cartography of the Graph Coloring Search Space

In this section, we explore the spatial distribution of the best configurations visited by TS in a given period of a single run. We consider these configurations as a set of points in the search space Ω (a |V |-dimensional space), and we measure the distance between each two points with the set-theoretic partition distance (see Section 4.2) that is a meaningful metric for graph coloring [START_REF] Galinier | Hybrid Evolutionary Algorithms for Graph Coloring[END_REF][START_REF] Glass | A polynomially searchable exponential neighbourhood for graph colouring[END_REF]. First, we provide 3D visualizations: the points from the |V |-dimensional space Ω are mapped into the 3D Euclidean space such that a distance distortion is minimized. This is achieved with a classical Multidimensional Scaling (MDS) procedure. Then, we analyze the values of distances between all points and we provide evidence that they are grouped in clusters in the search space Ω. We make an estimate of the cluster diameter. Surprisingly, we observed that it does not closely depend on the graph type, but mainly on |V |. Our assumption is that many of these clusters can be confined in spheres of radius 1 10 |V |.

Multidimensional Scaling

Multidimensional Scaling (MDS) is a common procedure in data visualization for representing similarities or dissimilarities in data. It takes as input a matrix of distances (or dissimilarities between pairs of items) and maps them to a set of locations in the Euclidean space (IR 2 or IR 3 ) such that a loss function (i.e. Kruskall stress in our case) is minimized. In our implementation, the MDS procedure has three steps: data collection, data mapping, and model verification.

Step 1: The matrix of distances in the real search space Given a sample of k-colorings {C 1 , C 2 , . . . C p } ⊂ Ω, the procedure first constructs the matrix D p×p where each element D ij = d(C i , C j ) is the distance between C i and C j . We define the distance as the minimum number of color changes required to transform C i in C j . This distance was used by most other graph coloring studies (e.g. [START_REF] Galinier | Hybrid Evolutionary Algorithms for Graph Coloring[END_REF][START_REF] Glass | A polynomially searchable exponential neighbourhood for graph colouring[END_REF]); it is very suitable for the T S algorithm because it also represents the minimal number of moves T S needs to perform to arrive from C i to C j . It can be expressed as a generic set-theoretic partition distance taking values between 0 and |V |; its computation can be done in O(|V |) time-we refer to Section 4.2 for more details.

Step 2: Generating IR 3 coordinates To obtain the corresponding locations in IR 3 , we use the classical cmdscale algorithm for metric (classical) multidimensional scaling as implemented in the well-known R programming language for statistical data analysis. The provided IR 3 locations are used to plot the 3D scatter graph and also to calculate the Euclidean distance matrix d p×p between the points. The distances in the 3D representation assess the spatial distribution of the real configurations in the Ω space.

Step 3: Quality assessment Since the isometry between the Euclidean distance matrix (d p×p ) and the initial distance matrix D p×p can not be exactly satisfied, the quality of the embedding is measured with a goodness-of-fit indicator; we chose to use the classical stress [START_REF] Kruskal | Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis[END_REF]:

s = 1≤i,j≤p (D ij -d ij ) 2 1≤i,j≤p D 2 ij
The guideline provided by Kruskal in his seminal MDS paper [START_REF] Kruskal | Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis[END_REF] states that the representation is:

a) poor if s > 0.2, b) fair if s ≤ 0.1, c) good if s ≤ 0.05, d) excellent if s ≤ 0.
025 and e) perfect if s = 0. In this paper, even if the total number of points is very high, we present no 'poor' (i.e. s > 0.2) representations.

Spatial distribution of configurations visited in limited-time runs

In this section we examine the sequence of colorings visited by (quite) short TS processes, more exactly we investigate the arrangement of high-quality configurations:

Definition 5 (High-quality configuration) We say that configuration C ∈ Ω is a highquality configuration (i.e. it is deep, or hard-to-find) if and only if f (C) ≤ B f , where B f is a fitness boundary. Otherwise, we say that C is a low-quality configuration.

Given a problem instance (G, k) and an initial high-quality coloring C 0 , we apply the TS algorithm starting from C 0 . TS visits a series of neighboring colorings and let C 0 ,C 1 , C 2 , . . . denote the high-quality configurations, those satisfying f (C i ) ≤ f (C 0 )-i.e. we consider the fitness boundary B f = f (C 0 ). In all our tests, the number of high-quality configurations represents only a very small fraction of the total number of colorings visited along the search; we ignore the colorings worse than C 0 because they can be easily found.

We show in Figure 1 the MDS representations of the colorings resulting from this experiment. Two instances are considered: (a) random graph dsjc1000.1 starting from a 4-conflict coloring and (b) Leighton graph le450.25c starting from a 1-conflict coloring. In order to limit the number of points (and the reliability of the MDS representation), we divide the TS exploration path in series of 100 and plot only the first coloring of each series. More exactly, if the search visits the following high-quality configurations in this order: C 0 , C 1 , C 2 , . . ., we graphically depict only C 0 , C 100 , C 200 , . . .. These 3D representations provide a good intuitive image of the exploration path. In the left graph, the exploration process starts from the front-bottom-left corner and passes from cluster to cluster until it reaches the right side; most colorings visited inbetween do not appear in the graph because they have worse fitness values (low quality configurations). In the right graph, the exploration path is even more clear (it starts from the front-bottom-left corner and ends toward the front-bottom-right corner) but the clusters are closer-for le450.25c, the distances between clusters are between 15%|V | = 67 and 22%|V | = 99 (see also Figure 2, bottom right graph) because the Leighton graphs have a peculiar structure as we discuss in Section 6.3.3.

Spatial distribution of colorings visited in long runs

Now, we present a more formal analysis of longer series of high-quality colorings visited by TS on all graph classes (Figure 2). We used a similar scenario as for Figure 1, but we examined much more configurations: indeed, all the high-quality colorings C 0 , C 1 , . . . , C n (i.e. satisfying f

(C i ) < f (C 0 ) ∀i ∈ [1.
.n], where n = 40.000) visited by TS are now considered for analysis (instead of the several hundreds of samples C 100 , C 200 , C 200 , . . . considered in the previous representations). We compute all distances1 d(C i , C j ) and, with a distance histogram, we show how many pairs (C i , C j ) correspond to each distance value.

Figure 2 shows bimodal distance distributions, with either very small or very long distances between the C i 's: this confirms the existence of some well separated regions with high densities of C i 's (clusters). If we denote a "cluster diameter" by c d , we observe that c d varies from 7%|V | to 10%|V | depending on the graph, such that: (i) there are numerous pairs (i, j) such that d(C i , C j ) < c d , (ii) there are very few (less than 1%) pairs (i, j) such that c d < d(C i , C j ) < 2c d and, (iii) there are numerous occurrences of some larger distance values. This distribution of the C i 's mainly reflects the path of the search process through the search space-and not the arrangement of all existing high quality configurations. However, regarding the colorings visited by TS, it is important to note that any two C i 's distanced by more than 1 10 |V | (the largest possible value of c d ) belong to different clusters of high-quality configurations. We keep this estimation in the rest of the paper and we use it to propose new search space exploration methods.

TS-Div-Tabu Search algorithm with diversification guarantee

While there are many well-studied methods to help a local search to escape a single basin of attraction, it seems more difficult to prevent it from looping between a limited number of basins of attraction. This is one of the main reasons for which, after a certain threshold, an increase of the execution time might not always improve the performance. We present in this section a TS algorithm (call it TS-Div) that integrates a learning process for avoiding looping between already-visited areas. TS-Div employs an extended Tabu list length if it detects that it comes upon configurations that are too close, according to the distance function, to other previously-visited configurations, i.e. while it passes through an already-explored cluster. This strategy prevents the algorithm from revisiting such regions by the reinforced diversification phase associated with the extended Tabu list.

Formal TS-Div description

The TS-Div algorithm (see Algorithm 2) is based on two central processes: (i) a basic TS exploring process (Tabucol), (ii) a reactive learning process that guides the first process by investigating the positions of the visited colorings. The orientation in space is achieved using the partition distance defined in Section 4.2 (basically, the distance between two colorings can be interpreted as the shortest path of TS steps between them). 2 , we say that C a and C b are completely different. The first task of the learning component is to investigate the TS exploration path by recording the centers of all visited spheres. While configuration C, at the current iteration, stays in the sphere of the last recorded center C p , we consider that the search process is "pivoting" around C p . And while it remains in the same sphere of C p , TS-Div explores the search space in the same way as the basic TS would do.

As soon as the search leaves the current sphere, the learning component concentrates on the guiding task. It first compares C to the archive of all previously recorded configurations (procedure Already-Visited in Algorithm 2) to check whether it is entering in a previously-explored sphere or not. If C is not in the sphere of any recorded configuration, it goes on only by changing the pivot-i.e. it replaces C p with C and records it in the archive. Otherwise, if the search process is re-entering the sphere of a previously recorded configuration, the learning process intervene in the search process: a diversification phase is needed. For this purpose, we extend the Tabu tenure T ℓ with a T c factor as explained in the next section.

Diversification using the Tabu tenure Indeed, the Tabu list length (or Tabu tenure) provides a very simple mechanism to control diversification. Using longer Tabu lists makes configuration changes more diverse because TS never repeats the moves performed during the last T ℓ + T c iterations. Therefore, the greater the T c value, the more diversification there is. A suitable control of T c guarantees that TS-Div keeps discovering new regions; in fact, it can even guarantee that the process can never get stuck looping through already-visited spheres. The longer the time TS-Div spends only running into previouslyvisited spheres, the more it increments T c -and T c is only decremented (to 0) when the search process finds a new sphere. As such, the Tabu list increases continuously until a sufficiently high value of T l is guaranteed to break any looping between already-visited

(C) (b) If d(C, Cp) > R • Cp = C • If ALREADY-VISITED(Cp) -Then Increment Tc • Else -Tc = 0 -Record Cp (c) Mark C as Tabu for T ℓ + Tc iterations (d) If (f (C) < f (C best )) • C best = C (e) If (f (C) < f (Cp))
• Replace Cp with C in the archive • Cp = C (i.e. ''recentering'' the current sphere)

5. return C best spheres (sooner or later). As such, TS-Div can discover new regions at all stages of the exploration, even in the very long run.

Distance definition and a fast computation method

The distance computation time is a crucial factor for TS-Div because, if this computation is too slow, it risks compromising the running speed of the algorithm. Fortunately, the set-theoretic partition distance fits well our purpose. Using the partition representation (see Definition 2), the distance between coloring C a and C b is the minimal number of vertices that need to be transferred from one class to another in C a so that the resulting partition is equal to C b (equivalent to the minimal number of moves needed by TS to arrive from C a to C b ). There exists a well-studied distance computation method using an O(|V | + k 3 ) Hungarian algorithm-see [START_REF] Gusfield | Partition-distance: A problem and class of perfect graphs arising in clustering[END_REF] for a general set-theoretic approach or [START_REF] Glass | A polynomially searchable exponential neighbourhood for graph colouring[END_REF] for the graph coloring application. However, in some conditions [START_REF] Porumbel | An improved algorithm for computing the partition distance[END_REF], the distance can be determined in O(|V |) time with a special method. Basically, the distance is calculated with the formula

d(C a , C b ) = |V | -s(C a , C b )
, where s is a measure of similarity defined as follows. Using the definitions from Section 2, s(C a , C b ) is max σ∈Π 1≤i≤k M i,σ(i) , where Π is the set of all bijections from {1, 2, . . . k} to {1, 2, . . . k} and M is a matrix with elements [START_REF] Glass | A polynomially searchable exponential neighbourhood for graph colouring[END_REF][START_REF] Gusfield | Partition-distance: A problem and class of perfect graphs arising in clustering[END_REF]. This similarity can be calculated by solving an assignment problem with the Hungarian algorithm. However, we applied the complete Hungarian algorithm only very rarely (less than 5% of all cases) because the calculation can be simplified by taking into account some problem particularities. Matrix M has at most |V | non-zero elements and, as also stated in [23, §2], they can be filled in O(|V |) with the appropriate data structure. Indeed, the non-zero elements of M are situated at positions M Ca(x),C b (x) (with x ∈ V ) and our algorithm works only with these elements. Furthermore, we do not require here a precise distance value but we only have to decide if

M ij = |C i a ∩ C j b | [
d(C a , C b ) > R-i.e. s(C a , C b ) < |V | -R. Since s(C a , C b ) is always less than s ′ (C a , C b ) = 1≤i≤k max j M ij (because M i,σ(i) ≤ max j M ij , ∀σ ∈ Π), in many cases it was enough to check s ′ (C , C b ) < |V | -R to decide s(C a , C b ) < |V | -R.
All maximums max j M ij can be identified by going through the non-zero elements of M , and so, s ′ (C a , C b ) can be computed in O(|V |). More conditions in which the problem can be solved in O(|V |) are available in [START_REF] Porumbel | An improved algorithm for computing the partition distance[END_REF].

As such, a distance computation requires (in average) approximately the same computation time as a TS iteration. The next section describes a method to keep the number of iterations and the number of distance computations in the same order of magnitude during long TS-Div executions. Thus, our distance computation procedure guarantees that the slowdown introduced by the learning component stays in acceptable limits.

Running time of TS-Div

The most critical issue of TS-Div concerns its running speed, more exactly the slowdown introduced by the distance computations of the learning component. Our objective is to keep the time spent on distance computations in the same order of magnitude as the time spent on the exploring component. The most numerous distances are computed when TS-Div needs to check the distance from the current coloring to all colorings from the archive-see Algorithm 2, the Already-Visited procedure (Forall Loop in Step 1). However, the archive processing time can be controlled if we focus the learning component only on the deep layers of search space, i.e. on the high quality configurations (with maximum B f conflicts, see Definition 5). The fitness boundary B f is automatically set by TS-Div in order to control the learning process overhead. More exactly, B f directly controls the number of distance computations because, the whole learning component

(Step 4.(b)) is now executed only if f (C) < B f .
In all our experiments, TS-Div always sets B f to a value so as to keep the number of distance computations in the same order of magnitude as the number of iterations. This proved to be a good "thumb rule" for obtaining an acceptable slowdown. In practice, we observed that B f varies from 5 conflicts to 20 conflicts. The number of distance computations can be further reduced in many ways. For example, the distance computation in

TS-Int-A tree traversal of the search space

A typical issue of classical local search algorithms can be described as follows: the search process arrives in a local minimum situated in the sphere of a solution, and it needs to choose the next moves. In the fortunate case, the search process chooses moves on the When this condition is verified, we say that a new high quality configuration is discovered and, if there is no close configuration already in Q (i.e. if there is no

C i ∈ Q such that d(C, C i ) ≤ 10%|V |), C is inserted into Q.
We note that a TS process can also be stopped when it arrives too far from the center (i.e. if d(C, C s ) > 20%|V |) without finding any high quality solution. After performing enough runs from one starting point, TS-Int takes the next configuration in Q and repeats (see Algorithm 3).

We can say that TS-Int organizes the search space in spheres that are processed in a methodical tree-traversal manner. C s is the root of the tree and its edges link it to all new sphere centers discovered by TS processes started from C s -recall that all sphere centers in Q are pairwise R-distanced. Similarly, each new discovered sphere center C c constitutes a new tree vertex linked to the configuration from which C c was reached. The degree of C s corresponds to the number of pairwise R-distanced new sphere centers reached from C s . Basically, TS-Int launches TS processes from C s as long as there are chances to discover new configurations, R-distanced from all other configurations in Q.

Figure 3 illustrates a simplified TS-execution. Here, the solution, situated at distance 23%|V | from the root vertex 1, is reached after an exploration of depth 3 (i.e. the tree on Figure 3 expanded on three levels). From experiments, the average degree of this exploration tree for this instance is actually 20. Consequently, the solution can be obtained by TS-Int after visiting at most 20 3 = 8000 vertices. Indeed, we experimentally remarked that TS-Int always finds the solution in 10 runs out of 10 if it starts from a point within a distance of 1 4 |V | from the solution (see more discussions in Section 6.3.2).

Results and Discussions

In this section, we present empirical results and discussions regarding both the search space structure and the two new algorithms. While TS-Div is a classical "stand-alone" algorithm, TS-Int is a second stage algorithm that can be used only to improve some existing configurations (typically provided by TS-Div).

Experimental procedures

First, we need to point out that TS-Div is equivalent to TS in the beginning of the exploration, while the archive is almost empty. The learning component intervenes in the exploration process only after a number of iterations, as soon as the exploration process stagnates. As such, if the basic TS can quickly find a solution, TS-Div does not find it more rapidly. The objective of TS-Div is visible in the long run, i.e. it only helps TS on the difficult instances where the basic TS fails.

To effectively test TS-Div, we perform 10 independent executions, each with a time limit of 50 hours. Within this time limit, TS-Div re-initializes its search with a random k-coloring each time it reaches 40 million iterations. Those restarts of TS-Div share the same archive of spheres. The statistics of the results are based on these 10 independent executions. Similarly, TS-Int is tested in the same experimental conditions, i.e. using 10 independent executions, each with a time limit of 50 hours. In Section 6.3.1, we will give some comments on the issue of running time with respect to the common practice of the literature. Regarding TS-Int, recall that it requires an input configuration C s from which TS-Int starts searching for a solution (only a proximity of C s is explored). As such, the successfulness of TS-Int depends entirely on the distance from C s to the solution. Typically, if TS-Div fails on an instance, our procedure collects the best colorings ever visited and tries to improve them with TS-Int. We usually filter these colorings so as to keep only completely different colorings as starting points for TS-Int; we present the results on the best input colorings.

Instance

Numerical results

Table 1 reports the detailed results of TS-Div for several difficult instances (G, k)especially those not easily solved by the basic TS. Columns 1-3 describe the instance, i.e. Column 1 is the graph, Column 2 shows χ (the chromatic number, or "?" if unknown) and k * (the best known k); Column 3 denotes the k for which we apply our algorithm. Columns 4-6 present the results of the algorithm, i.e. the success rate (the number of executions that solve the problem in 50 hours or less) in Column 4, the average number of iterations and the average time required to find a solution in Column 5 and 6, respectively.

Table 2 presents the results of TS-Int on several starting configurations whose proximity is explored. Columns 1-3 have the same meaning as for Table 1, Column 4 shows the amplitude of the improvement (the number of conflicts of the start and the end -or best visited-configuration), Column 5 presents the success rate of achieving this improvement and Columns 6 and 7 denote the average computing effort (in iterations and in CPU hours, respectively).

TS-Int can find the solution with 100% success rate (see Column 5 of Table 2) when it starts from an appropriate coloring (i.e. not too far from a solution, see also Section Section 6.3.2). Remarkably, it finds a new legal coloring with 223 colors for the large graph dsjc1000.9. While TS-Div assures diversification, TS-Int is an intensification algorithm that can be systematically executed after TS-Div in order to (try to) improve its best colorings.

Discussion

Running time of TS-Div and TS-Int

In our experimentations, TS-Div and TS-Int were allowed to run 50 hours per execution for a given coloring instance. We see that within this maximum time, TS-Div and TS-Int are able to reach very competitive results for the set of difficult graphs. Moreover, not all solutions required the maximum 50 hours computation time.

Let us mention that in the literature on graph coloring, it is a common practice to run a coloring algorithm several hours to several days to (try to) solve a hard coloring instance. For example, some of the most recent coloring algorithms [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Hertz | Variable space search for graph coloring[END_REF] use running times of 10 hours for the largest instances. Now if we compare the number of iterations, the values required by TS-Div are even more comparable with respect to other local search algorithms. Indeed, the maximum iterations of TS-Div are in the order of billions (between 10 9 and 8 × 10 9 ) while the best local searches in the literature report the same order of magnitude (e.g. 2 × 10 9 iterations [3, Table 6] or 3 × 10 9 [27, Table 5]). Now let us insist on a more important point of TS-Div concerning the running time. One understands that, by its very nature, TS-Div will continually explore new regions if it is given more computation time. Consequently, TS-Div will be able to find new or better solutions with the additional computation resources.

Notice that this is a desirable characteristic which is not verified by many existing algorithms. Very often, running them beyond some time (or iteration) threshold will not lead to better results simply because either the algorithms are trapped in deep local optima or because they re-explore again and again the same regions. TS-Div provides a simple, yet effective solution to this delicate issue because it is forced to discover new spheres at all stages of its execution. The same comment applies to TS-Int for which more computation time means more intensified exploitation of more spheres. Consequently, better results can naturally be expected.

TS-Int-finding the global optimum from an approximate location

TS-Int can be quite useful even in combination with other algorithms, especially when one could provide (by any means) an approximate location of the solution. In our main experimentation procedure, we consider that the configurations with lower conflict numbers have more chances to be close to a solution; thus, TS-Int always processes the spheres in the order of their conflict number. However, another possible "guess" of the solution location is obtained by considering that a legal k-coloring might be close to a legal (k + 1)-coloring or even to a (k + 2)-coloring.

This assumption worked perfectly well for the f lat300.28 graph for which TS-Int finds a legal coloring with χ = 28 colors starting from a legal coloring with χ + 2 colors (the colors greater than χ are replaced with color 1). The graphs in this family are generated by adding edges only between the χ independent sets of an initial χ-partition of V [START_REF] Culberson | Exploring the k-colorable landscape with iterated greedy[END_REF]. A large proportion of the 30 classes of the legal 30-coloring are very close to some of the initial 28 independent sets and, thus, TS-Int can easily reconstruct the rest of the coloring; the distance between the legal 30-coloring and the legal 28-coloring is only 7%|V |.

We experimentally observed that, if we provide a starting point within 1 4 |V | distance from a solution, TS-Int finds the solution with a 100% success rate. These facts were observed on several graphs and for different initial colorings within 1 4 |V | distance from a known solution. Searching a solution within 1 4 |V | = 25%|V | distance (around the start configuration) typically requires a complete exploration of a tree on 3 levels because each edge corresponds to a distance of 10%|V | in the search space. The number of levels that can be processed in a certain time limit depends on the exploration speed and on the average tree degree. Since TS-Int is also highly amenable to parallelization, one could speed up the algorithm by an order of magnitude by launching all processes from C s in parallel. The required 1 4 |V | precision of the solution location could thus be extended to 40%|V | and even |V | 2 if sufficient computation time is allowed.

Search space structure specificities for each graph family

We observed that, even if the number of legal k-colorings is always small (for a difficult problem), the number of 1-conflict colorings can greatly vary. In the random graph case, before discovering a legal coloring, T S usually visits between 3 and 20 1-conflict colorings.

For the f lat300.28 flat graph, TS-Div always directly descends to the legal 30-coloring from a coloring with 4 or 5 conflicts; as such, it can discover a solution even without visiting any 1-conflict coloring at all. At the other extreme, for the Leighton graphs we found more than 1 million 1-conflict colorings for several 0-conflict colorings (this is why it seems easier to solve this problem by first finding a 1-conflict coloring with TS-Div and by applying TS-Int on it). The explanation of these landscape differences lays in the structure of the graph to be colored. The Leighton graphs have a built-in 25-vertex clique [START_REF] Leighton | A graph coloring algorithm for large scheduling problems[END_REF], and numerous 1conflict colorings might share a common conflict on this clique while being very different outside it. They form very large plateaus in which it is difficult to find the coloring that correctly colors the 25 vertices of the clique. This is also confirmed by the search space analysis: the distances between the clusters of 1-conflict colorings (sequentially visited by TS, see Figure 2, Section 3) are significantly smaller than for the other cases.

The flat graphs are constructed from a χ-partition of V such that a legal coloring has to assign a different color to each set of vertices from the initial partition. Any 1-conflict coloring has already identified much of this partition and the transition to the solution is trivial; the descent to the solution is always very steep. For the random graphs, the numbers of 1-conflict and 0-conflict configurations visited by TS-Div differs by an order of magnitude. search space as a tree of connected spheres and applies a classical tree traversal algorithm to methodically explore all spheres one by one.

To summarize, we devised a pair of algorithms that assures both the diversification and the intensification tasks by guiding underlying search processes. Table 3 presents a comparison between the best results obtained in this study and the best results from the literature. Four papers in this table are very recent (year 2008) as we took into account only the best algorithms; moreover, some of these cited papers present in fact more than one algorithm version-but Table 3 shows the best k reported by any version. The population-based heuristics (last four columns) are traditionally the most effective and, on some instances, they all find better results than all searches. However, our method is also very effective comparing with all state-of-the-art algorithms and it even finds a new legal coloring for a very hard DIMACS instance (dsjc1000.9).

The principles behind TS-Int and TS-Div can be applied to any combinatorial optimization problem because they are both extensions of the Tabu Search algorithm. The necessary condition to achieve this is to find a search space distance measure that: (i) has low computation complexity (comparing to a TS iteration) and (ii) is in accordance with the proximity from the perspective of the TS process (i.e. the distance should be equivalent to the number of TS steps between configurations).

Definition 1 (

 1 Array coloring representation) Given G and k, a coloring function c : V → {1, 2, • • • , k} is encoded as an array C = [c(1) ,c(2), . . . , c(|V |)].

Definition 3 (

 3 Objective function) Given a configuration C, we call conflict (or conflicting edge) any edge having both ends of the same color in C. The number of conflicts (or the conflict number of C) represent the objective (or fitness) function f for the k-coloring problem (G, k).

Figure 1 :

 1 Figure 1: The high-quality colorings (with f (C) ≤ 4) visited during 60000 iterations by TS for G = dsjc1000.1, k = 20 (left) and the high-quality colorings (with f (C) ≤ 1) visited during 25000 iterations by TS for G = le450.25.c, k = 25 (right). The stress value is s = 0.19 and s = 0.15, respectively.

Figure 2 :

 2 Figure 2: Histograms of the distances between each two of the C 0 , C 1 , C 2 , . . . , C 40000 (high-quality) configurations visited by TS; f (C i ) is limited by: a) f (C 0 ) = 4 for (G = f lat300.28, k = 30), b) f (C 0 ) = 3 for (G = dsjc250.5, k = 28), c) f (C 0 ) = 4 for (G = dsjc1000.1, k = 20) and d) f (C 0 ) = 1 for (G = le450.25c, k = 25).

Definition 6 (

 6 Sphere) Given a (center) configuration C ∈ Ω and a radius R ∈ IN , the R-sphere S(C) is the set of configurations C ′ ∈ Ω such that d(C, C ′ ) ≤ R. Since we assume the clustering hypothesis (Section 3), we deal only with R-spheres of radius R = 1 10 |V | in the rest of the paper. Two colorings C a and C b satisfying d(C a , C b ) ≤ R = 1 10 |V | are called close or related ; otherwise they are R-distinct or R-distanced. If d(C a , C b ) > |V |

Algorithm 2 1 .• 2 . 4 .

 2124 Pseudocode TS-Div PROCEDURE ALREADY-VISITED Input: current configuration C Return value: TRUE or FALSE Forall recorded configurations Crec: If d(C, Crec) ≤ R -Return TRUE 2. Return FALSE ALGORITHM POSITION-GUIDED TABU SEARCH Input: the search space Ω Return value: the best configuration C best ever visited C: the current configuration 1. Choose randomly an initial configuration C ∈ Ω Cp = C (the pivot, i.e. the last recorded configuration) 3. Tc = 0 (the value by which it extends the Tabu tenure T ℓ ) While a stopping condition is not met (a) Set (next) C = the best non-Tabu neighbor in N

  Step 4.(b) is not always needed: if d(C p , C) < R, then TS needs at least Rd(C p , C) moves to get out of the sphere of C p . As such, after each distance calculation in this step, TS-Div can safely skip it for the next Rd(C p , C) iterations.

Table 1 :

 1 The results of TS-Div for a time limit of 50 hours. Columns 1, 2 and 3 denote the instance, the success rate (Column 4) is the number of successful executions out of 10; Column 5 and 6 show the average number of iterations and the average time needed to find a solution.

	TS-Div Algorithm

Table 2 :

 2 Instances for which colorings are improved by TS-Int using a time limit of 50 hours. The input colorings are typically provided by TS-Div; however, the cells marked * indicate that TS-Int finds a legal k-coloring only starting from a legal (k + 1) or (k + 2)-coloring.

	G	Instance χ, k * k f start -→ f end Improvement Success rate Iterations [×10 6 ] Time [hours] successes runs
	dsjc1000.1 ?, 20 20	1 → 0	10/10	3774	12
	dsjc1000.5 ?, 83 86	2 → 0	10/10	623	19
			85 80 * (k+1) → 0	2/10	1453	39
	dsjc1000.9 ?, 223 223	1 → 0	10/10	23	4
	le450.25c	25, 25 25	1 → 0	10/10	3410	10
	le450.25d 25, 25 25	1 → 0	10/10	6466	25
	f lat300.28 28, 28 28 150 * (k+2) → 0	10/10	< 1	< 1
	f lat1000.76 76, 83 85 74 * (k+1) → 0	10/10	1655	36

Considering n = 40000 colorings, the number of distances to compute is not extremely large, we computed all n × n = 1.600.000.000 distances in several hours.

Acknowledgments: This work is partially supported by the CPER project "Pôle Informatique Régional" (2000)(2001)(2002)(2003)(2004)(2005)(2006) and the Régional Project MILES (2007)(2008)(2009). We thank the referees for their useful suggestions and comments.

Conclusions

We have performed an empirical space search analysis that shows that the local minima of the coloring problem are grouped in clusters covered by spheres of 1 10 |V | diameter. We have devised a fast method to record the spheres of local minima visited by a local search process. The TS-Div algorithm records its exploration path (only by recording the spheres) and uses an additional learning process to discourage it from returning to already-explored spheres. Moreover, the TS-Div algorithm does not introduce any auxiliary user-provided parameters. The main objective of TS-Div is the global diversification of the search process: unlike the basic TS, TS-Div does not risk redundant explorations in the long run. As such, TS-Div is much more effective than the basic TS and it competes well even with the best algorithms from the literature. The search capacity of TS-Div is reinforced by TS-Int, which is an intensification-oriented algorithm used to better explore the proximity of the most promising configurations. It is able to systematically find a solution if the solution is situated within a certain distance from the starting configuration. TS-Int organizes the

Graph