Cyril Grelier
email: cyril.grelier@univ-angers.fr

Olivier Goudet
email: olivier.goudet@univ-angers.fr

Jin-Kao Hao
email: jin-kao.hao@univ-angers.fr

A memetic algorithm with adaptive operator selection for graph coloring

Keywords: Graph Coloring, Memetic Algorithm, Hyperheuristics

We present a memetic algorithm with adaptive operator selection for k-coloring and weighted vertex coloring. Our method uses online selection to adaptively determine the couple of crossover and local search operators to apply during the search to improve the efficiency of the algorithm. This leads to better results than without the operator selection and allows us to find a new coloring with 404 colors for C2000.9, one of the largest and densest instances of the classical DIMACS coloring benchmarks. The proposed method also finds three new best solutions for the weighted vertex coloring problem. We investigate the impacts of the different algorithmic variants on both problems.

Introduction

Graph coloring problems find applications across various domains, such as matrix decomposition [START_REF] Prais | Reactive grasp: An application to a matrix decomposition problem in tdma traffic assignment[END_REF], metropolitan area network design [START_REF] Halldórsson | Batch coloring flat graphs and thin[END_REF], and task scheduling in distributed computing [START_REF] Liu | Dynamic co-scheduling of distributed computation and replication[END_REF]. Given a graph G = (V, E), defined by its vertex set V and edge set E, a legal coloring S of the graph G partitions the vertex set V into k non-empty and disjoint color groups {V 1 , . . . , V k } such that the coloring constraint is satisfied, i.e., for each V i , if x ∈ V i and y ∈ V i , then {x, y} / ∈ E. In other words, the coloring constraint states that two adjacent vertices cannot go to the same color group (they cannot receive the same color). A coloring failing to meet the coloring constraint is an illegal coloring. Typically, graph coloring problems entail finding a legal coloring of the graph G while taking into account additional decision criteria and constraints. Specifically, the k-coloring problem (k-col) is a decision problem, where given a number of colors k, the goal is to find a legal coloring of the graph using these k colors. The graph coloring problem (GCP) is to determine the smallest number of colors (chromatic number of the graph) needed to color a graph. In the weighted vertex coloring problem (WVCP), an additional weight function w : V → R + is defined to assign a strictly positive weight w(v) to each vertex v ∈ V . The objective of the WVCP is then to find a legal coloring S = {V 1 , . . . , V k } with a minimal score f (S) = k i=1 max v∈Vi w(v), where the number of used colors k is not specified. This paper aims to develop a learning-based framework for solving both the k-col decision problem and the WVCP minimization problem, which have been addressed by various methods in the literature. Both problems are known to be NP-hard in the general case [START_REF] Garey | Computers and intractability: A guide to the theory of npcompleteness[END_REF], posing computational challenges in practice. For example, some random graphs with 250 vertices cannot be solved optimally by current exact algorithms (see [START_REF] Malaguti | An exact approach for the vertex coloring problem[END_REF] for k-col and [START_REF] Goudet | New bounds and constraint programming models for the weighted vertex coloring problem[END_REF] for WVCP). For this reason, a number of heuristics have been developed over the last thirty years to obtain approximate solutions to large graph coloring problems [START_REF] Galinier | Recent advances in graph vertex coloring[END_REF][START_REF] Malaguti | A survey on vertex coloring problems[END_REF].

For the k-col, two particularly interesting local search heuristics are TabuCol [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF] and PartialCol [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF], which were proposed many years ago. For the WVCP, dedicated and effective local search procedures are much more recent, including AFISA [START_REF] Sun | Adaptive feasible and infeasible tabu search for weighted vertex coloring[END_REF], RedLS [START_REF] Wang | Reduction and local search for weighted graph coloring problem[END_REF], ILS-TS [START_REF] Nogueira | Iterated local search with tabu search for the weighted vertex coloring problem[END_REF] and TabuWeight [START_REF] Grelier | On monte carlo tree search for weighted vertex coloring[END_REF]. None of these methods really dominates the others for all reference instances of the k-col and the WVCP [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF][START_REF] Grelier | On monte carlo tree search for weighted vertex coloring[END_REF][START_REF] Nogueira | Iterated local search with tabu search for the weighted vertex coloring problem[END_REF]. It would be interesting to choose an appropriate local search to solve each type of instance for each problem.

However, local search methods may fail to produce high-quality solutions due to their limited ability to diversify their search. To overcome this difficulty, hybrid algorithms using the framework of memetic algorithms have been proposed, which benefit from local search for intensification and offer diversification possibilities with a population of high-quality solutions recombined with crossover operators. Hybrid algorithms have mainly been used to date to solve the k-coloring problem. The HEA (Hybrid Evolutionary Algorithm) algorithm [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF] introduced the powerful GPX crossover (Greedy Partition Crossover ) operator and used a local tabu search inspired by TabuCol. Evo-Div [START_REF] Porumbel | An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring[END_REF] and MACOL [START_REF] Lü | A memetic algorithm for graph coloring[END_REF] both used crossover strategies with multiple parents and distance management between solutions. More recently, the HEAD algorithm (HEA in Duet) [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] proposes the use of only two individuals in the population and a reintegration system for high-quality individuals (elites) found earlier in the search. HEAD also uses the GPX crossover and an improved TabuCol algorithm. This algorithm HEAD is currently one of the most efficient solvers for the k-col. For the WVCP, to our knowledge, there is only one memetic algorithm in the literature, DLMCOL [START_REF] Goudet | A deep learning guided memetic framework for graph coloring problems[END_REF], which uses a large population (more than 20,000) and parallel GPU-based local searches, combined with a neural network-guided crossover selection.

It was observed by the authors of HEAD [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF], that the quality (number of conflicts) of an offspring solution for the k-col, generated with the GPX crossover from two parents, is highly correlated with the partition distance [START_REF] Porumbel | An efficient algorithm for computing the distance between close partitions[END_REF] between these two parents, which is the minimum number of vertices that must change color to transform one solution to another. Based on this insight, the authors suggested employing modified versions of the GPX crossover, such as conservative asymmetric crossovers, which can lead to better results for certain types of instances. In the context of a memetic algorithm, it is therefore important to choose not only the right local search, but also the right crossover operator to perform an efficient search.

To this end, in this work, we investigate the use of online hyperheuristics, suggested in the literature to dynamically select adapted low-level heuristic com-ponents during the search process for solving a specific problem instance. We refer the reader to [START_REF] Burke | Hyper-heuristics: A survey of the state of the art[END_REF][START_REF] Drake | Recent advances in selection hyperheuristics[END_REF] for an overview of existing hyperheuristics used to solve various combinatorial optimization problems. More specifically, hyperheuristics have been used to solve partitioning problems, with applications to planning and graph coloring [START_REF] Elhag | A grouping hyper-heuristic framework: Application on graph colouring[END_REF][START_REF] Grelier | Monte carlo tree search with adaptive simulation: A case study on weighted vertex coloring[END_REF][START_REF] Sabar | A graph coloring constructive hyperheuristic for examination timetabling problems[END_REF][START_REF] Sghir | A distributed hybrid algorithm for the graph coloring problem[END_REF]. However, to our knowledge, no hyperheuristic-based memetic algorithm for graph coloring has yet been proposed in the literature. This work fills this gap by :

investigating new memetic algorithms for the k-col and the WVCP using the HEAD framework [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] with diverse local search procedures and GPX variants.

examining the ability of adaptive operator selectors to jointly choose crossovers and local search procedures during the search for specific instances.

In the rest of the paper, we first present our new general framework, AHEAD (for Adaptive HEAD), with different strategies for selecting local search procedures and crossovers (Section 2). Next, we show the results of the different variants of AHEAD in comparison with state-of-the-art algorithms (Section 3).

Adaptive Memetic Algorithm

In this section, we present the general framework of the adaptive memetic algorithm developed for the k-col and the WVCP, as well as the selection operators.

For the k-col, with a graph G = (V, E) and k colors, the search explores the space Ω k of legal and illegal colorings where all vertices are colored, but allowing color conflicts between adjacent vertices:

Ω k = {{V 1 , . . . , V k } : (∪ k i=1 V i = V ) ∧ (V i ∩ V j = ∅, i = j, 1 ≤ i, j ≤ k)}. (1)
In this case, the fitness f (to be minimized) corresponds to the number of conflicts in the solution. A solution with the fitness of 0 is a legal coloring. For the WVCP, the algorithm works in the space of legal solutions Ω l , where all vertices are colored with no limit on the number of colors, but no adjacent vertices are allowed to share the same color:

Ω l = {{V 1 , . . . , V k } : (∪ k i=1 V i = V ) ∧ (V i ∩ V j = ∅, i = j, 1 ≤ i, j ≤ k) ∧ (∀v 1 , v 2 ∈ V i , (v 1 , v 2 ) / ∈ E, 1 ≤ i ≤ k)} (2)
and we search in this search space a solution S = {V 1 , . . . , V k } whose score

f (S) = k i=1 max v∈Vi w(v) is minimum.

Main Scheme

The architecture of the AHEAD framework, illustrated in Figure 1, extends the state-of-the-art HEAD framework [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] by introducing an operator selector. In particular, its simplicity with only two individuals in the population facilitates the parent matching and population updating phases compared to other memetic algorithms in the literature [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF][START_REF] Lü | A memetic algorithm for graph coloring[END_REF][START_REF] Porumbel | An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring[END_REF][START_REF] Goudet | A deep learning guided memetic framework for graph coloring problems[END_REF]. AHEAD takes as input a graph G = (V, E), and an integer value k for the kcol or a weight function w for the WVCP, a set of local search operators O l , a set of crossover operators O x , and a high-level selection strategy π θ characterized by a parameter vector θ. The π θ strategy chooses two pairs of operators < o l , o x > with o l ∈ O l and o x ∈ O x to apply in the current generation to create two new individuals, replacing their parents in the population for the next generation.

The population is initialized with two random colorings, S 1 and S 2 . Two elite solutions, E 1 and E 2 , are also created, which are updated by the best solution found during the search and are used to reintroduce diversity into the population under specific conditions. Then, each generation of the algorithm performs the next six steps until the stopping condition is met.

Automatic Operator Selection

To select the crossover and local search operators, a high-level π θ strategy automatically selects a pair of operators In the general case, the π θ function takes a pair of parents as input. For example, for (S 1 , S 2 ), π θ chooses a pair of operators < o x , o l >, with a crossover operator o x to be applied with S 1 as the first parent and S 2 as the second parent. It will produce a child C 1 , which will be improved by the local search procedure o l to obtain a new individual C 1 .

< o x , o l > ∈ O x × O l . Therefore, there are |O x | × |O l | different < crossover,
In this work, we examine the effects of six operator selection policies π θ with varying levels of complexity, including four fitness-based criteria, a neural network, and a random selector. Note that, except for the Deleter criteria, they are also used in combination with a Monte Carlo tree search in [START_REF] Grelier | Monte carlo tree search with adaptive simulation: A case study on weighted vertex coloring[END_REF].

-Random performs a uniform selection among all operators.

-Deleter deletes the operator with the worst average result every 5 generations, until only one remains. -Roulette (or Adaptive roulette wheel) [START_REF] Goëffon | Simulating non-stationary operators in search algorithms[END_REF] selects randomly the operator with a bias induced by the reward r (see Section 2.5) obtained by each operator.

The better the reward is, the higher its associated probability of being picked is, using the same parameters as in [START_REF] Grelier | Monte carlo tree search with adaptive simulation: A case study on weighted vertex coloring[END_REF]. -UCB (Upper Confidence Bound, One-armed bandit strategy) [START_REF] Auer | Using confidence bounds for exploitation-exploration trade-offs[END_REF] selects the operator depending on the rewards obtained in previous generations and the number of times it has been picked using the UCB formula managing the exploitation-exploration trade-off. -Pursuit [START_REF] Goëffon | Simulating non-stationary operators in search algorithms[END_REF] randomly selects the operator with a proportional bias in favor of the best performing operator. This strategy is among the most elitist, as it gives more chances to the best strategy applied in previous iterations. -NN (Neural Network) uses the recommendations of a deep set neural network architecture [START_REF] Goudet | A deep learning guided memetic framework for graph coloring problems[END_REF][START_REF] Grelier | Monte carlo tree search with adaptive simulation: A case study on weighted vertex coloring[END_REF][START_REF] Zaheer | Deep sets[END_REF]. This neural network g θ takes as input a coloring S as a set of k binary vectors v j of size n, S = {v 1 , . . . , v k }, where each v j indicates the vertices belonging to the color group j. From such an entry the neural network outputs a vector with |O l | values in R corresponding to the expected reward of each local search. In order to select a pair of operators

< o x , o l >∈ |O x | × |O l |
, from a pair of parents (S 1 , S 2 ), the neural network selector π θ works as follows:

1. Each crossover operator o x ∈ O x creates an individual C x = o x (S 1 , S 2 ).

Each raw solution C

x is passed as input to the neural network g θ to obtain a vector of |O l | values in R corresponding to the estimated score that can be obtained after applying each local search o l ∈ O to C x . 3. The pair < o x , o l > corresponding to the highest output value of the neural network (for the |O x | evaluations given by g θ ) is selected. 10% of the time, the selection is random to encourage diversity.

Application of Crossover Operators

In this step, the parent solutions S 1 and S 2 are combined to create two offspring solutions

C 1 = o x 1 (S 1 , S 2 ) and C 2 = o x 2 (S 2 , S 1
) from the crossover operators o x 1 and o x 2 chosen during the selection phase detailed in the previous section. For both problems, we use the popular GPX crossover [START_REF] Galinier | Hybrid evolutionary algorithms for graph coloring[END_REF] used in the original HEAD algorithm [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF]. It consists of alternately taking the largest color group from each parent and transmitting it to the offspring solution. Note that GPX is asymmetrical, applying it with the pair (S 1 , S 2 ) or the pair (S 2 , S 1 ) does not produce the same offspring solution. Three variants of this crossover can be selected in AHEAD: GPX, GPX-3, and GPX-9 taking respectively 1, 3, and 9 groups of color in the first parent for 1 color in the second parent. Therefore the last two are more conservative than the original GPX as more groups of the first parent are transmitted to the offspring. This generally results in offspring with lower (better) fitness, but less different from its parents. The two new solutions C 1 and C 2 generated during the crossover phase will be improved in the local search phase detailed in the next subsection.

Local Searches

In this step, the new individuals C 1 and C 2 are improved by the selected local search operators o l 1 and o l 2 . These two independent local searches are run in parallel on two CPUs with a time limit of T LS seconds. The best solutions C 1 and C 2 found by o l 1 and o l 2 with this time budget are returned. For the k-col, two state-of-the-art local search operators can be chosen: the efficient implementation of TabuCol [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF] proposed in [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] and PartialCol [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF]. For the WVCP, the two best performing algorithms RedLS [START_REF] Wang | Reduction and local search for weighted graph coloring problem[END_REF] and ILS-TS [START_REF] Nogueira | Iterated local search with tabu search for the weighted vertex coloring problem[END_REF] can be chosen.

Operator Selection Strategy Update

Insertion and Elite Solutions

Like HEAD [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF], offspring solutions systematically replace the parents and elite solutions are used. Elites, which are high-quality solutions from previous generations, are added to the population after 10 generations. Thus, every 10 generations, the best individual encountered from the previous 11 to 20 generations is reintegrated into the population.

Furthermore, at each generation, the set-theoretic partition distance [START_REF] Porumbel | An efficient algorithm for computing the distance between close partitions[END_REF] between the solutions S 1 and S 2 is evaluated. This distance is defined as the least number of one-move operator changes for transforming S 1 to S 2 . If the distance is 0, meaning that the two individuals are the same solution, the individuals of the population are randomly reinitialized. Note that when this happens, we do not reset the θ weights of the learning strategy in order to benefit from what the operator selector has learned since the start of the search.

Computational Experiments

This section is dedicated to a computational assessment of the proposed AHEAD algorithm for solving the k-coloring and the weighted vertex coloring problems, by making comparisons with state-of-the-art methods. We also discuss the impact of the different operator selection strategies on the results.

Experimental Settings

In these experiments, we consider 31 instances for the k-col and 48 instances for the WVCP, among the most challenging DIMACS benchmark instances and widely used in the experiments of many recent papers [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF][START_REF] Nogueira | Iterated local search with tabu search for the weighted vertex coloring problem[END_REF][START_REF] Sun | Adaptive feasible and infeasible tabu search for weighted vertex coloring[END_REF]. 20 independent runs per method and per instance are carried out for one hour with two CPU for the HEAD and AHEAD methods (four hours for the WVCP) and two hours with one CPU for the local search algorithms for the k-col (eight hours for the WVCP). For each k-col instance, and for each independent run, the smallest value of k for which the method is able to find a legal solution is reported.

The time spent, in seconds, in the local search during each generation in HEAD and AHEAD is 0.001 * |V | for the k-col and 0.04 * |V | for the WVCP, with |V | being the number of vertices in the graph. These values were chosen following tests on a range of values for each problem, which will not be presented here. To erase the impact of the training time of the neural network, for the versions with AHEAD, the methods perform as many generations in the memetic algorithm as the HEAD versions.

The experiments are run on a computer equipped with an Intel Xeon ES 2630, 2.66 GHz processor. All algorithms are coded in C++, compiled and optimized with the g++ 12.1 compiler. For the neural network implementation, the Pytorch 1.13 C++ library was used. The source code and complete tables of detailed results are available at https://github.com/Cyril-Grelier/gcp_ahead and https://github.com/Cyril-Grelier/wvcp_ahead.

Experimental Results for the k-coloring Problem

In this section, we first analyze the general results obtained for the k-coloring problem. The different methods tested can be regrouped into three categories:

-The standalone local searches PartialCol (PC) [START_REF] Blöchliger | A graph coloring heuristic using partial solutions and a reactive tabu scheme[END_REF] and TabuCol (TC) [START_REF] Hertz | Using tabu search techniques for graph coloring[END_REF] (with optimizations from [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF]). -The memetic algorithm HEAD [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] We first present a general comparison between all these methods, followed by detailed results on the different benchmark instances. 1 displays general performance comparisons between each pair of methods on the benchmark instances considered in this work for the k-col. Whenever the mean score of a method in the row for an instance is better than the mean score of a method in the column, and this difference is significant (non-parametric Wilcoxon signed rank test with p-value ≤ 0.001) the method in the row obtains one point. If the method in the row is better on more instances than the method in the column than the opposite, then the number of instances is in bold. As an example, we observe in Table 1 that Tabu-Col is significantly better on 14 instances when compared with PartialCol, while PartialCol is only better on 2 instances when compared with TabuCol. The last three columns of Table 1 gives the number of times a Best Known Score (BKS) from the literature is found by the method and the number of times the method reaches the best score and the best mean among the presented methods.

General Comparisons Table

We observe in Table 1 that using the memetic framework HEAD with Partial-Col or TabuCol (version HEAD + TC, and HEAD + PC) improves the results over the methods using the corresponding local search alone.

Overall, TabuCol is more effective than PartialCol, that is why HEAD+TC keeps good results against some versions of AHEAD with less elitist operator selection such as Random, Roulette or UCB. However, the other versions of 1. Comparison of each method for the k-col, the value is the number of instances where the method in the row is significantly better than the method in the column. The last three columns are a summary of the number of best scores.

AHEAD, using Deleter, Pursuit and the neural network (NN), obtained overall better results than the memetic algorithm HEAD+TC without operator selection. It highlights the interest of dynamically choosing the best operator to apply for each given instance.

The Random selection policy is less effective in comparison with the other operator selection strategies, especially against Deleter, Pursuit and NN, which have a stronger bias on selecting the best operators. Surprisingly, the simplest but most elitist selection strategy, Deleter, achieves the best results, indicating that for this problem, once the best operator has been identified for each specific instance, there is generally no need to change it for the rest of the search.

Detailed Results

Table 2 shows, for each instance, the Best Known Score (BKS) in the literature1 with a star if it is optimal, then, for each method, the best score, the mean score and the average time to reach the best scores over the 20 executions. Bold values indicate the best scores among the studied methods. The average score is not shown if equal to the best score. Due to space limitations, only a selection of methods is shown in the various tables, and not all instances studied are shown. Complete tables are available on the github repository.

First, those results confirm that the TabuCol local search is more often better than PartialCol, but that the latter can give better results for some in- stances such as queen11 11 and can be faster for solving other instances such as flat300 28 0 or wap03a. It shows to some extent that these two local searches can be complementary.

Second, we obviously confirm that when TabuCol is integrated within the HEAD memetic framework and combined with the GPX crossover (version HEAD +TC), it can generally improve the results significantly, but it does not improve the results for all instances. For example, for the instances flat300 28 0, r1000.5, and some wap, it is actually better to use the local search alone for better intensification. Using crossovers for these instances can actually disrupt the search too early, preventing the local search from significantly improving its results. Note that the results of HEAD in [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] can differ from our results with HEAD+TabuCol using exactly the same operators, because we did not perform a fine-tuning of the number of iterations spent in local search for each given instance, unlike it was done in the original article.

Third, the algorithm AHEAD + Random can find the best results for more instances than the HEAD+TabuCol version whose choice of operators does not change during the search. For example, AHEAD + Random finds the optimal coloring with 28 colors for the instance flat300 28 0. This is due to the fact that TabuCol is not able to reach the chromatic number of the graph in a short amount time compared to PartialCol which can reach it systematically more than three times faster. Therefore, AHEAD + Random benefits from having a chance at each generation to select the right local search for each given instance.

Fourth, from Table 2, we observe that using an elitist strategy in local search and crossover selection can significantly improve the results compared to the random selection strategy. In particular, as shown in this table, the version AHEAD + Deleter can find a new best coloring with k = 404 for the instance C2000.9 that has never been reported in the literature. This new best score is also found by the versions AHEAD + Pursuit and AHEAD + NN. In general, these versions of AHEAD with elitist operator selection strategies obtain the best results for a wide variety of instances of different types.

Figure 2 shows the average cumulative selections for each pair of operators, performed by the different selection criteria for the DSJC500.1 and queen12 12 instances. In the plots, TabuCol and PartialCol selections are indicated by red and blue lines, respectively, and a higher contrast indicates a more conservative crossover. When we look at the frequencies of the local search operators selected by AHEAD, we see that TabuCol is selected most often in comparison with PartialCol, which is no surprise, as TabuCol is already better on its own for a greater number of instances. However, when it comes to crossovers, we observe a balanced choice between the three GPX variants, with a bias toward the more conservative crossover GPX-9 for geometric graphs (e.g., DSJR500.5) and sparse graphs (e.g., wap instances), for which local optima are very distant in the search space, while the GPX crossover is more often preferred for random and dense graphs (e.g., DSJC1000.9), for which there is often larger backbones of solutions shared by the high-quality solutions (as shown in [START_REF] Goudet | A deep learning guided memetic framework for graph coloring problems[END_REF]).

Experimental Results for WVCP

Now, we analyze the general results obtained for the WVCP. We first present a general comparison between the methods, followed by detailed results on the different benchmark instances. The studied methods are the following:

-The local searches, RedLS [START_REF] Wang | Reduction and local search for weighted graph coloring problem[END_REF] and ILS-TS [START_REF] Nogueira | Iterated local search with tabu search for the weighted vertex coloring problem[END_REF] (8h runs on 1 CPU).

-The memetic algorithm HEAD [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF] with RedLS or ILS-TS (HEAD + RedLS /ILS-TS) and the crossover GPX (4h runs on 2 CPUs). -The different proposed AHEAD versions with the 6 different operator selection strategies presented in Section 2.2 with the two local searches (RedLS and ILS-TS) and the three variants of GPX crossovers (4h runs on 2 CPUs).

General Comparisons As seen in Table 3, using HEAD with RedLS (HEAD + RedLS) improves the results for 26 instances but the standalone local search RedLS stays better in 9 instances. On the other hand, for ILS-TS, using the HEAD framework is better only for 6 instances, while ILS-TS remains better for 19 instances. We observe that the use of crossovers in combination with the ILS-TS local search procedure does not improve the results of ILS-TS. This can be explained by the fact that ILS-TS is already a method incorporating a strong perturbation strategy for search diversification, making the use of crossovers somewhat superfluous. Regarding the results of AHEAD, we confirm what we have observed for the k-col, even if it's less pronounced. The AHEAD versions are more often better than the other methods, and the most elitist operator selection strategies (Deleter and Pursuit) obtain the best results. 3. Comparison of each method for the WVCP, the value is the number of instances where the method in the row is significantly better than the method in the column.

Detailed Results First, we see in Table 4 that with the help of the eight hours of computation, RedLS is capable of finding five new scores (underlined score). ILS-TS is also able to find two new upper bounds with this longer execution time. The RedLS local search alone remains better on large instances (e.g., C2000, latin square and flat) than the different memetic versions using this local search procedure (HEAD + RedLS, and all AHEAD variants). Contrary to what was observed for the k-col, this shows that for very large WVCP instances, using the GPX crossover is not very beneficial. This can be by the fact that for the WVCP, only the maximum weight of each color group affects the score. Thus, for large instances, many different groupings of vertices are possible without impacting the score, which generally results in a very high distance between the two solutions S 1 and S 2 of the population. However, as observed in [START_REF] Moalic | Variations on memetic algorithms for graph coloring problems[END_REF], the solution quality of an offspring built with the GPX crossover is poorer (higher fitness) if the individuals are too distant in the search space.

However, for medium-sized instances, such as le450 15a/b and queen14 14, the AHEAD memetic framework with an elitist operator selection (AHEAD + Deleter) significantly improves results and yields three new best upper bounds.

Regarding the operators selected by AHEAD, the two local search operators RedLS and ILS-TS are almost equally preferred, with a choice depending on the type of instance. On the other hand, unlike the k-col, the choice of crossover is almost exclusively oriented towards the most conservative crossover, GPX-9, particularly in combination with the local search ILS-TS. As mentioned above, this is due to the large distance between individuals in the population in the case of the WVCP.

Conclusion

The proposed AHEAD (Adaptive HEAD) framework is based on a population of two individuals and uses learning-driven operator selectors to determine a pair of local search and crossover to apply during the search process for solving a given instance of the k-coloring and weight vertex coloring problems. For both problems, the proposed approach shows advantages over versions without automatic selection of low-level operators. In the course of these experiments, we obtained three new best scores for the WVCP with the proposed AHEAD method, as well as a new best coloring with 404 colors for the very large and dense graph C2000.9.

The work could be extended by considering a wider variety of complementary crossover procedures and searches to be by the high level operator selection strategy. Future work could also involve coupling the choice of operators with the setting of critical hyperparameters involved in these operators, such as the number of local search iterations to be performed at each generation, or the size of the tabu list.

  1. A selection phase to select two pairs of operators < crossover, local search > to be applied during this generation: < o x 1 , o l 1 > and < o x 2 , o l 2 >. This selection is made using the function π θ , which takes as input the two individuals in the population, with S 1 as the first input for the selection of < o x 1 , o l 1 >, then S 2 as the first input for the selection of < o x 2 , o l 2 > (Section 2.2). 2. A crossover phase to create two offspring individuals C 1 and C 2 with C 1 = o x 1 (S 1 , S 2 ) and C 2 = o x 2 (S 2 , S 1 ) (see Section 2.3). 3. An intensification phase to obtain improved offspring solutions with local search, C 1 = o l 1 (C 1 ) and C 2 = o l 2 (C 2 ) (Section 2.4). 4. An insertion phase to replace S 1 and S 2 by C 1 and C 2 , regardless of the fitness of the offspring solutions compared to the parents. 5. An update phase to adjust the π θ selection policy from the examples collected over the last few generations (Section 2.5). 6. As in the original HEAD algorithm [21], each generation ends with a step of storing the best individual (elite) from the cycle (10 generations). The elite individual is reintroduced two cycles later (Section 2.6).

Fig. 1 .

 1 Fig. 1. General architecture of the Adaptive HEAD (AHEAD) framework.

  local search > pairs possible considered as independent meta-operators. The set of crossover operators O x is presented in Section 2.3 and the set of local search operators O l in Section 2.4.

  At each generation, new learning examples are collected from the results of pairs of operators to update the selection strategy for future generations.Learning examples memory. Reward scores r 1 = -f (C 1 ) and r 2 = -f (C 2 ) are associated with the choice of operator pairs < o x 1 , o l 1 > and < o x 2 , o l 2 >, with f the fitness function of the k-col or the WVCP. These rewards are negative, as the fitness f is to be minimized in both problems. Then, two learning examples(o x 1 , o l 1 , C 1 , r 1 ) and (o x 2 , o l 2 , C 2 , r 2 )are stored in a database D, specific to the current execution. D is a queue of the N last examples obtained during previous generations (N is set to 50 empirically). This limited queue size enables us to better adapt to potential variations in operator results, in the event that certain operators are better at the beginning of the search than at the end.Online learning of the selection criteria. Every generation, the π θ policy is trained on the database D and all its θ parameters are updated. For the NN policy, the training phase occurs every nb = 20 generations. During this training phase, each training example (o x , o l , C, r) from the database D is converted into a supervised learning example (X, y), with X an input matrix of size k × |V | corresponding to the set of k vectors C = {v 1 , . . . , v k }, and y is a real vector of size |O l | (number of local search operators), so that y is initialized with g θ (C), the output vector of the neural network taking as input C, then its value y[o l ] for the chosen operator o l is replaced by the expected reward r: y[o l ] = r. Once this conversion of the training examples is done, g θ is trained to minimize the mean square error computed over the |O l | outputs (supervised learning) on this training dataset for 10 epochs with the Adam optimizer[START_REF] Kingma | Adam: A method for stochastic optimization[END_REF].

  combined with local search operators PartialCol (version HEAD + PC) and TabuCol (version HEAD + TC).-The different proposed AHEAD versions with the 6 different operator selection strategies presented in Section 2.2. These versions are called "AHEAD + the name of the selection strategy".

  AHEAD+UCB 19 11 20 1 1 0 0 -0 0 10 18 10 AHEAD+Pursuit 19 13 20 3 5 2 0 1 -0 11 20 14 AHEAD+NN 19 12 20 2 4 0 0 0 0 -12 23 16 Table

Fig. 2 .

 2 Fig. 2. Average cumulative selections, along with error bars, for each pair of operators based on different criteria on the DSJC500.1 and queen12 12 instances.

Table 2 .

 2 Results of the main methods for the GCP.

Achieving these BKS for k-col, especially for the largest instances, is a very difficult task. Some have only been found by few algorithms under particular conditions (hyperparameter tuning, extended execution times of several days to a month).

Acknowledgment

We would like to thank Dr. Yiyuan Wang, [31] and Pr. Bruno Nogueira [23] for sharing their codes. This work was granted access to the HPC resources of IDRIS (Grant No. AD010611887R1) from GENCI and the Centre Régional de Calcul Intensif des Pays de la Loire (CCIPL). We are grateful to the reviewers for their comments.