Nicolas Szczepanski
email: nicolas.szczepanski@univ-lille.fr

Gilles

Laetitia Jourdan
email: laetitia.jourdan@univ-lille.fr

Christophe Lecoutre
email: lecoutre@cril.fr

Lucien Mousin
email: lucien.mousin@univ-catholille.fr

A Hybrid CP/MOLS Approach for Multi-Objective Imbalanced Classification

Keywords: Computing methodologies → Search methodologies, Machine learning approaches, Partial Classification, Imbalanced Data, Multi-objective Optimization, Local Search, Constraint Programming ACM

In the domain of partial classification, recent studies about multiobjective local search (MOLS) have led to new algorithms offering high performance, particularly when the data are imbalanced. In the presence of such data, the class distribution is highly skewed and the user is often interested in the least frequent class. Making further improvements certainly requires exploiting complementary solving techniques (notably, for the rule mining problem). As Constraint Programming (CP) has been shown to be effective on various combinatorial problems, it is one such promising complementary approach. In this paper, we propose a new hybrid combination, based on MOLS and CP that are quite orthogonal. Indeed, CP is a complete approach based on powerful filtering techniques whereas MOLS is an incomplete approach based on Pareto dominance. Experimental results on real imbalanced datasets show that our hybrid approach is statistically more efficient than a simple MOLS algorithm on both training and tests instances, in particular, on partial classification problems containing many attributes.

INTRODUCTION

In the domain of partial binary classification, predicting the class of new data has been studied extensively during the last decade [START_REF] Geng | Interestingness measures for data mining: A survey[END_REF]. As an illustration of such classification tasks, one can wish to predict whether a new patient is ill or not (i.e., to determine the class of this patient), according to known observations from previous patients, which are made up of several attributes (fever, age, . . . ). The classification is said to be partial because one just wants to know if an observation belongs to a specific class, even if many of them exist. In this paper, we deal with the classification rule mining problem, which is a problem over (discrete and) imbalanced data whose distribution greatly varies over the classes. For instance, a partial classification task can be executed in a medical diagnosis context, where less than 10% of patients are actually ill. This form of classification can be considered as a multi-objective optimization problem where each objective represents a different quality measure.

Learning classifier systems (LCS) are popular approaches to solve such problems. They often combine a genetic algorithm with a learning component (supervised learning, reinforcement learning, or unsupervised learning). Moreover, LCS deals with multi-objective optimization using an aggregating function that is often a simple sum [START_REF] Bacardit | Pittsburgh genetic-based machine learning in the data mining era: representations, generalization, and run-time[END_REF]. This kind of reduction to mono-objective optimization has unfortunately some drawbacks. To overcome them, an efficient approach was proposed in [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF] where a supervised partial classification task is solved by MOCA-I (Multi-Objective Classification Algorithm for Imbalanced data), based on a multi-objective local search algorithm (MOLS) and a dominance-based multi-objective local search (DMLS). Statistically better results are obtained this way than with single objective approaches like, for example, the famous C4.5 algorithm [START_REF] Jacques | The benefits of using multi-objectivization for mining pittsburgh partial classification rules in imbalanced and discrete data[END_REF]. More recently, some works have exploited the robustness of automatic algorithm configuration (AAC) approaches in order to tune the parameters of MOCA-I, and thus to improve performances [START_REF] Tari | Automatic Configuration of a Multi-objective Local Search for Imbalanced Classification[END_REF].

On the other hand, Constraint Programming (CP) is a framework that has been shown quite effective for modeling and solving various forms of optimization problems, by means of highly efficient inference and search algorithms [START_REF] Dechter | Constraint processing[END_REF][START_REF] Lecoutre | Constraint Networks: Techniques and Algorithms[END_REF][START_REF]Handbook of Constraint Programming[END_REF]. It is not coincidence that some data mining problems have been studied in CP. For example, in [START_REF] De Raedt | Constraint Programming for Data Mining and Machine Learning[END_REF], it is shown that constraint programming techniques can be applied to various pattern mining and rule learning problems as the frequent or discriminative itemset mining problems. More recently, a constraint-based declarative model [START_REF] Belaid | Constraint Programming for Association Rules[END_REF] has been proposed to solve the association rules problem, showing good results compared to the data mining state-of-the-art.

The main goal of this paper is to exploit CP for the partial classification rule mining problem. To the best of our knowledge, this is the first time that such an approach is used to solve this specific problem. Several reasons motivated us to adopt a CP approach. Firstly, modeling the rule mining problem with CP is rather easy and natural, and besides MOLS and CP share the concept of discrete variables (actually, finite domains containing integer values). Secondly, contrary to MOLS, the search conducted by CP (solvers) is strongly guided by the objective, which can be seen as a special dynamic constraint. Lastly, the MOLS and CP paradigms are rather complementary: while CP solving is based on depth-first exploration combined with strong deductions (inferences made by constraint propagation), MOLS handles a Pareto set (of non-dominated solutions) that continually evolves by exploring neighbourhoods. More generally, CP and MOLS search algorithms carry out different kinds of exploration of the search space: one is (typically) complete while the other is incomplete. Thus, using the orthogonality of these two approaches is an appealing option.

In a first step of this work, we noticed that the number of variables and constraints in a pure CP model, for the partial classification rule mining problem, could be huge and memory expensive, resulting in memory overflow on instances containing numerous observations. This is why we have designed and implemented a hybrid CP/MOLS algorithm to counteract this problem. This hybridization is composed of two phases, respectively handled by CP and MOLS. Basically, CP is applied on rather small sub-problems, in order to avoid memory issues, before exploiting solutions delivered by CP during the MOLS phase. Experimental results on real imbalanced datasets show that our approach is statistically more efficient than MOLS or CP, when applied stand-alone, on both training and tests instances.

The paper is organized as follows. In the next section, the supervised imbalanced classification problem is introduced. Then, Section 3 introduces the MOLS and CP approaches for this problem. Next, Section 4 introduces the hybridisation of both approaches. Experimental results are described in Section 5, before concluding.

THE SUPERVISED IMBALANCED CLASSIFICATION PROBLEM

In this section, we introduce the supervised partial classification problem and the manner the rule mining problem can be encoded. We also define some solution quality metrics for multi-objective optimization of both MOLS and CP.

Presentation

The goal of classification is to predict the class of an observation that is unlabeled (unknown). For this purpose, the classification process is based on observations that have already been encountered before, called labeled observations. Each observation is composed of several attributes that represent a variety of information concerning the problem under consideration. An attribute is defined by a continuous or discrete variable value. As an illustration, a classification task could aim at predicting the illness of new patients among (the classes) {flu, diabetic, healthy} by using their symptoms and personal information (fever, cough, age, weight) as attributes. Note that when an attribute is continuous, a discretization technique can be applied.

In this paper, we deal with the partial classification problem. On the one hand, complete classification aims at discriminating between the target classes and consists in forming a partition of the set of observations (necessarily classifying a patient in one of the classes flu, diabetic or healthy. On the other hand, partial classification is restricted to a subset of the target classes and consists in dividing the observations into two complementary parts (for example, determining whether a patient has the flu or not).

From labeled observations, the outcome of a classification task is a classifier of the form 𝐴𝑇 ⇒ 𝑃. Each such rule indicates that 𝑃, a target class, is the logical consequence of the conjunction of some conditions denoted by 𝐴𝑇 , each of them representing a test on an attribute. For example, if the classifier is « {fever > 39 and cough = true} ⇒ 𝑖𝑙𝑙 », then the classifier answers « positive » to the prediction « patient is ill? » when the attribute values for a given patient logically validate the attribute tests. Otherwise, it returns « negative ».

Numerous metrics have been proposed in the literature to evaluate the efficiency of classifiers, and most of them are based on the confusion matrix presented in Table 1. For each observation, the confusion matrix reports a value among {TP, TN, FN, FP} according to the prediction made by the classifier and the actual class of the observation. The actual class is the known correct class of the observation, and this information is required to check the efficiency of a classifier. Consequently, True Positives (TPs) and True Negatives (TNs) count well-classified observations, whereas False Positives (FPs) and False Negatives (FNs) count misclassified observations. As an illustration, the classifier rule {fever > 39 and cough = true} ⇒ ill is not activated if the patient attribute values are {fever = 40 and cough = false}. However, if the patient is really ill (i.e. the actual class is « ill »), this is a False Negative. Usually, in order to fairly evaluate the ability of a classifier, data are divided into two parts: the training instances representing labeled observations and the test instances corresponding to unlabeled observations. In this way, a solving method exploits the training data set to produce a classifier, and then, confusion matrixbased measures are employed to evaluate this classifier on both training and test instances. Thus, this makes it possible to take into account the efficiency of the solving method to produce a good classifier (using training instances) and the classifier effectiveness on unknown data (using test instances).

This evaluation protocol is significant because a classifier can be effective on training instances but not on testing instances. In practice, this phenomenon is called overfitting and means that the classifier is too closely tied to the training data set. This can also mean that the training and test data sets are not similar enough.

Another issue to be addressed by solving methods is the handling of imbalanced data. They are characterised by a number of observations that varies greatly between classes. On top of that, on most datasets, the class to predict is often less frequent than the opposite class. For instance, in a medical context, the diagnosis can be positive on less than 10% of patients. To address this issue, several multi-objective techniques using confusion matrix-based measures and based on a solution encoding have been introduced in the literature [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF].

A solution encoding represents the form of the propositional formula encoding the attribute tests 𝐴𝑇 of a classifier (the prediction 𝑃 is omitted). In the literature concerning the rule mining problem, several encodings of solutions exist: the tree encoding [START_REF] Paul | Rule Induction for Classification Using Multi-objective Genetic Programming[END_REF], the Michigan encoding [START_REF] Wilson | Classifier Fitness Based on Accuracy[END_REF], and the Pittsburgh encoding [START_REF] Bacardit | Evolving Multiple Discretizations with Adaptive Intervals for a Pittsburgh Rule-Based Learning Classifier System[END_REF]. Later, in this paper, we use the variable-length Pittsburgh encoding [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF] which allows a large number of attributes to be handled.

In this encoding, a solution is called a ruleset: this is a disjunction of rules, where each rule is a conjunction of terms. Each term corresponds to an attribute test (𝐴𝑇 ) which is defined by an attribute, an operator and a value, i.e., a triplet of the form (attribute, operator, value). Classically, the operator is relational (<, >, or =), because data (values) are assumed to be discretized and subject to a total order. For example, (fever, >, 39) is a term representing the test fever > 39. This solution encoding is used to predict the class by using the terms and the logical operators or and and constituting the ruleset. The predicted class of the classifier is determined by the interpretation of a ruleset with the attribute values of an observation.

A Multi-Objective Model

The goal of Multi-Objective Optimisation (MOO) is to jointly optimize several criteria (objective functions) that directly affect the solution quality of a given problem. More precisely, a solution to a MOO problem is ideally one such that all objective functions 𝑓 𝑖 (𝑥) reach their optimal values. From now on, without any loss of generality, we consider minimization:

argmin 𝑥 ∈𝐷 (𝑓 1 (𝑋 1 ), 𝑓 2 (𝑋 2 ), . . . , 𝑓 𝑛 (𝑋 𝑛 )) (1)
In Equation 1, 𝑛 denotes the number of objectives (𝑛 ≥ 2), 𝐷 is the set of feasible solutions 𝑥 represented by the vector of 𝑘 decision variables 𝑥 = (𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑘 ). Moreover, the sets 𝑋 𝑖 ⊆ 𝑥 represent several vectors of decision variables which can be different depending on the associated objective function. Note that mixed MOO problems, consisting of both some objective functions to maximize and minimize, can easily be transformed into minimization MOO problems by changing their sign, 𝑓 ′ 𝑖 (𝑥) = -𝑓 𝑖 (𝑥). The concept of Pareto dominance is used to distinguish between solutions according to the involved criteria. A solution 𝑠 1 dominates another solution 𝑠 2 if, and only if, (i) 𝑠 1 is better than or equal to 𝑠 2 for all criteria, and (ii) 𝑠 1 is strictly better than 𝑠 2 for at least one criterion. A set of non-dominated solutions {𝑠 1 , 𝑠 2 , . . . , 𝑠 𝑚 }, where there is no pair of distinct solutions (𝑠 𝑖 , 𝑠 𝑗 ) such that 𝑠 𝑖 dominates 𝑠 𝑗 , is called a Pareto set, a Pareto front, or an archive in the context of multi-objective local search algorithms. Solving a MOO problem consists in finding a Pareto optimal set 𝑆 * ⊂ 𝐷, i.e., a Pareto set such that no other feasible solution 𝑥 ′ ∈ 𝐷 dominates any 𝑥 ∈ 𝑆 * .

For multi-objective local search (MOLS), introduced later, objectives are defined as (following the model described in [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF]):

• maximizing the sensitivity 𝑇 𝑃 𝑇 𝑃 +𝐹 𝑁 ∈ [0, 1]; • maximizing the confidence 𝑇 𝑃 𝑇 𝑃 +𝐹 𝑃 ∈ [0, 1]; • minimizing the number of terms in the ruleset.

The sensitivity corresponds to the proportion of samples detected by the ruleset that are positive with respect to the class under investigation. In contrast, the confidence corresponds to the probability that an observation detected as positive by the ruleset is a true positive. Minimizing the number of terms helps to reduce complexity and avoid the bloat effect caused by rulesets containing over-specific rules without any improvement of their quality. Moreover, note that these two metrics are highly susceptible to variation in the distribution of observations.

As almost none of the CP solvers deal with multi-objective optimization, in the CP approach, we use an aggregation based on the F-Measure (𝐹 1 ), a machine learning metric computed as follows:

𝐹 1 = 2 × Confidence × Sensitivity Confidence + Sensitivity
𝐹 1 corresponds to the harmonic mean, and thus a trade-off, between confidence and sensitivity. Thus, the closer the F-measure is to 1, the better the quality of the classifier (i.e. the ruleset). Moreover, as the F-Measure is recommended in partial classification [START_REF] He | Learning from Imbalanced Data[END_REF], the experimental evaluation of this work uses this measure.

MODELING AND SOLVING METHODS

In this section, we introduce MOLS and CP.

Multi-objective Local Search

Multi-objective local search (MOLS) algorithms are most often based on Pareto local search (PLS) [START_REF] Paquete | Pareto Local Optimum Sets in the Biobjective Traveling Salesman Problem[END_REF] that gradually improves a Pareto set. In the literature, numerous extensions to PLS have emerged, such as the iterated PLS [START_REF] Drugan | Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies[END_REF], the stochastic PLS [START_REF] Madalina | Path-Guided Mutation for Stochastic Pareto Local Search Algorithms[END_REF], the anytime PLS [START_REF] Dubois-Lacoste | Anytime Pareto local search[END_REF] and the dominance-based multi-objective local search (DMLS) [START_REF] Blot | Automatic Configuration of Multi-Objective Local Search Algorithms for Permutation Problems[END_REF]. As opposed to single-objective local search, focusing on only one solution, DMLS maintains multiple candidates and non-dominated solutions. First, this algorithm starts by creating an archive of several initial solutions. Note that this initialization phase is exploited later in our hybridisation. Thereafter, these solutions are improved by iteratively executing four distinct phases: selection, exploration, archiving and perturbation. Specifically, at each iteration, the first step of DMLS selects the solutions from the archive that will be explored (selection phase). Thereafter, the exploration phase seeks new candidate solutions to add to the archive by successively exploring the neighborhoods of the selected solutions. Such additions are realized according to the improving and/or non-dominated criteria. Once new solutions have been added to the archive, a filtering (i.e. the archiving phase) is performed to keep only non-dominated solutions. However, in some cases, no new improved solution can be added to the archive, meaning that solutions of the current archive are local optima. To remedy this problem, one aims at escaping from these local optima by moving to another area of the search space. The last phase, called perturbation, is dedicated to this task by generating new random solutions, or by carrying out some kick moves. This paper takes up the MOLS algorithm of [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF], specially designed for imbalanced data. It should be noted that, in this previous work, the MOLS method used (MOCA-I) has already been compared against 13 other classification methods using the KEEL software. MOCA-I has shown its superiority on all the compared algorithms. As with any local search algorithm, it is based on a neighborhood relation, which implicitly associates a set of neighbors with each solution [START_REF] Blot | Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation[END_REF]. For the classification rule mining problem, the neighborhood of a ruleset 𝑟 is the set of rulesets having one test attribute that differs from 𝑟 . More precisely, this difference can be one fewer or more term, or a term with a different value or operator.

Moreover, each phase of MOLS accepts various parameters (perturbation methods, selection and exploration strategies, the maximal archive size, . . . ). Thus, some works have exploited this parameter variety, as e.g., in [START_REF] Tari | Automatic Configuration of a Multi-objective Local Search for Imbalanced Classification[END_REF][START_REF] Tari | Multi-objective Automatic Algorithm Configuration for the Classification Problem of Imbalanced Data[END_REF], where optimized versions of MOLS have been proposed for the imbalanced classification problem by means of the automatic algorithm configuration (AAC) paradigm. Note that we have chosen the best identified parameters for MOLS from this literature, i.e., a initial population of solution of size 100, an archive of max size 500, a restart strategy, a random selection of solution and an exploration of all neighbors. The sequential MOLS algorithms have been rewritten from [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF] into a new library called MH-builder.

Constraint Programming

In this section, we present a CP model for the partial classification rule mining problem, under the form of a constraint optimization problem (COP) [START_REF] Lecoutre | Constraint Networks: Techniques and Algorithms[END_REF], before giving a few details about the solving process. Concerning related work, note that other data mining problems have already been studied in CP. The authors of [START_REF] De Raedt | Constraint Programming for Data Mining and Machine Learning[END_REF] show that constraint programming techniques can be applied to various pattern mining and rule learning problems (itemset mining, maximal frequent itemset mining, discriminative itemset mining, and so on). More recently, in [START_REF] Belaid | Constraint Programming for Association Rules[END_REF], a constraint-based declarative model has been introduced to solve the association rules (AR) problem and show good results compared to the data mining state-of-the-art. For interested readers, others pattern mining problems are processed with CP in [START_REF] Guns | Declarative Pattern Mining using Constraint Programming[END_REF].

Modeling Phase. Algorithm 1 depicts a simplified version

of the CP model we propose for the partial classification rule mining problem. To develop this model, we have used PyCSP 3 [START_REF] Lecoutre | PYCSP3: Modeling Combinatorial Constrained Problems in Python[END_REF], a recent Python modeling library. Roughly speaking, this model allows us to extract a ruleset while maximizing the F-measure. For simplicity, the number of rules and the number of terms, nRules and nTerms, constituting the target ruleset are considered as pre-defined. Each problem instance is then characterized by the following data:

• some information concerning the labeled observations: nObservations, their actual classes (actual) and their attribute values; • the number of attributes nAttributes;

• the number of values nValues w.r.t. the attributes.

First, the variables of the model are introduced. Six multidimensional arrays of variables are declared by using the function VarArray while specifying, as parameters, the size of each dimension (the size parameter) and the domain of each variable (the dom parameter). The three first arrays will represent the terms attributes, operators, values forming each rule of the ruleset. The three next arrays will permit to determine, for each observation, whether each attribute test, each rule and the ruleset is positive (satisfied) or not. Note that each such variable can be assigned to either 0 (negative) or 1 (positive). Two stand-alone variables are also introduced, tp and fp, by calling the Var function: they represent the number of true positives and false negatives, respectively.

Second, the constraints of the model are introduced. This is made possible by calling the satisfy function, passing constraints as parameters. A first global constraint allDifferent is posted (line 21) to ensure that all attributes in any rule are distinct. Next, at lines 23 and 24, a list (group) of table constraints is introduced. Due to lack of space, the auxiliary function aux_table is not described here, but its role is to return the list of 4-tuples that can be accepted for a given sequence of four variables. In other words, this allows us to establish a link between a specific observation and a specific term. Then, the two next lists of constraints (lines 25 to 28) encode, for each observation, the value of the ith rule (resp. the value of the ruleset) as a conjunction of terms (resp. as a disjunction of rules). For example, in any solution of the model, ruleset[0] is equal to 1 (resp. 0) when the first observation (with index 0) is identified as being positive (resp. negative). The two last constraints count, respectively, the number of tp and fp, according to the actual classes of observations (actual) and the values of the ruleset.

Third, the objective of the model is introduced. This objective consists in maximizing an expression denoting the F-measure (at lines 33 to 36).

Solving

Phase. Solving a CP model involves the use of a constraint solver (or a SAT solver, after translating the model in propositional form). Typically, such solvers are complete, performing a depth-first exploration with backtracking, taking a decision (usually, a variable assignment) at each step and running a filtering process called constraint propagation. To address the issue of heavytailed runtime distributions [START_REF] Gomes | Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems[END_REF], the search is restarted regularly, following a geometric progression (or the Luby sequence). The order in which variables are chosen during the depth-first traversal of the search space is decided by a variable ordering heuristic; a classical generic heuristic is dom/wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF], combined with a mechanism simulating a certain form of intelligent backjumps [START_REF] Lecoutre | Reasonning from Last Conflict(s) in Constraint Programming[END_REF]. The order in which values are chosen when assigning variables is decided by a value ordering heuristic; for COPs, it is highly recommended to use first the value present in the last found solution, which is a technique known as solution(-based phase) saving [START_REF] Demirovic | Solution-Based Phase Saving for CP: A Value-Selection Heuristic to Simulate Local Search Behavior in Complete Solvers[END_REF][START_REF] Vion | Une simple heuristique pour rapprocher DFS et LNS pour les COP[END_REF].

Backtrack search for COP relies on Branch and Bound (B&B) whose principle is equivalent, assuming a minimization problem, to adding a special objective constraint obj < ∞ to the constraint network (although it is initially trivially satisfied), and to update the limit of this constraint whenever a new solution is found. It means that any time a solution S is found with cost 𝐵 = obj(𝑆), the objective constraint becomes obj < 𝐵. Hence, B&B provides a sequence of better and better solutions until no more exist, guaranteeing that the last found solution is optimal.

For our experiments, we have used the ACE constraint solver, which is the new avatar of AbsCon1 .

HYBRIDIZATION

In this section, the hybrid CP/MOLS approach we propose, HYB in short, is presented. Of course, some forms of hybridization between CP and LS (Local Search) have already been proposed in the literature. For example, LS has been used to guide local exploration by minimizing, at each step, the total number of conflicts when solving constraint satisfaction problems [START_REF] Minton | Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems[END_REF]. The original constraint-based local search proposed in [START_REF] Galinier | A General Approach for Constraint Solving by Local Search[END_REF][START_REF] Nareyek | Using Global Constraints for Local Search[END_REF] also combines CP and LS: constraints are used to describe and control LS [START_REF] Galinier | A General Approach for Constraint Solving by Local Search[END_REF][START_REF] Nareyek | Using Global Constraints for Local Search[END_REF].

The hybridization we propose consists in considering the (partial) solutions computed by CP, during a limited time period, as an initial population for MOLS. Note that this kind of hybridization technique has already been applied between mixed integer linear programming (MILP) and CP for the airline planning problem [START_REF] Grönkvist | A Constraint Programming Model for Tail Assignment[END_REF]. Our hybrid approach is composed of two main phases. First, CP is applied on some relevant sub-problems in order to collect a set of partial solutions. These solutions are then used to establish an initial population, on which MOLS can be started.

CP Phase

This phase exploits the ability to deal with the classification rule mining problem by considering different ruleset sizes. Hereafter, the specific instance derived from our CP model where a ruleset of 𝑖 rules, each one composed of 𝑗 terms, is encoded, will be denoted by 𝑚(𝑖, 𝑗). Our approach consists in solving incrementally several related instances over time by starting from 𝑚(1, 1) until an instance of maximal size 𝑚(𝑖 𝑚𝑎𝑥 , 𝑗 𝑚𝑎𝑥 ) is reached, where 𝑖 𝑚𝑎𝑥 and 𝑗 𝑚𝑎𝑥 denote the maximal values used to stop the process (e.g., 6 rules of 5 terms). The incremental nature of this approach permits to solve a current instance while using the solution(s) found just earlier (e.g., using the solution obtained for 𝑚(1, 1) as a partial solution for 𝑚(1, 2)).

The entire process is composed of three steps. First, as mentioned above, we solve a sequence of related instances. Note that any instance of the sequence (except the first one) is built from the previous one by increasing, either the number of rules 𝑖 or the number of terms 𝑗. More precisely, this sequence is defined by the equation:

𝑚(𝑖, 𝑗)

= 𝑚(𝑖, 𝑗 + 1), if 𝑖 + 𝑗 is even 𝑚(𝑖 + 1, 𝑗), if 𝑖 + 𝑗 is odd (2)
Hence, the first elements of the sequence are: 𝑚(1, 1), 𝑚(1, 2), 𝑚(2, 2), 𝑚(2, 3), . . . It is important to note that, by construction, the quality (i.e., the F-measure) of solutions can only increase. Since we solve instances under assumptions (i.e., from assignments corresponding to previous solutions), the solution obtained for the last instance of the sequence is not necessarily optimal. This is why, in a second step, we solve this instance without any assumption (but we use the last solution that has been found for this instance, as a soft guide for the value ordering heuristic [START_REF] Vion | Une simple heuristique pour rapprocher DFS et LNS pour les COP[END_REF]).

Finally, from the best found solution, whose F-measure is 𝑓 , we build a final instance while constraining the objective to be around 𝑓 . By solving it, we hopefully obtain a certain number of diverse solutions.

MOLS Phase

The initialization step of MOLS involves generating an initial population of solutions. This step is simply replaced by considering the output (set of solutions) of the CP phase. Note that for our experiments, we use the same parameter values as in [START_REF] Jacques | Conception of a dominance-based multi-objective local search in the context of classification rule mining in large and imbalanced data sets[END_REF], that is to say, a production of 100 rulesets with a maximal size of 2 rules of 2 terms each.

EXPERIMENTAL RESULTS

In this section, the performance of the CP, MOLS and hybrid approaches are compared using a proper statistical test, executed on several data sets.

Protocol

This work follows the recommendations made by Demsar to compare several learning algorithms over multiple data sets [START_REF] Demšar | Statistical Comparisons of Classifiers over Multiple Data Sets[END_REF]. The principle is to get a solid measure of the overall performance of any algorithm over several independent data sets. For this purpose, we can use the Friedman statistical test [START_REF] Friedman | The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance[END_REF] in order to detect the differences existing between various algorithms over several problems. More precisely, this test is based on the ranking positions of algorithms over all problems. A post-hoc all pairwise comparison of algorithms is performed using the Wilcoxon statistical test on all computed F-Measures. Specifically, the Wilcoxon test allows us to determine whether two series of numbers are equivalent or not, from a pairwise comparison. Therefore, a solving method is considered as better than another one if its rank is better and if the two series of numbers are not equivalent in the Wilcoxon's sense. In contrast, two solving methods are equivalent if the series of numbers are equivalent, regardless of their rank.

As we deal with the supervised classification problem, the product classifier must be evaluated on unknown data, which are different from the training data. Recall that it permits to recognize an overfitting issue. Since it is almost impossible to find multiple and distinct datasets from the same classification problem, datasets are split into training and test sets as for classical machine learning algorithms [START_REF] He | Learning from Imbalanced Data[END_REF], by following the 𝑘-fold cross-validation protocol.

The 𝑘-fold cross validation produces 𝑘 training sets and 𝑘 test sets by splitting the dataset (i.e. the observations) into 𝑘 same-size folds. Each training set is simply a combination of 𝑘 -1 folds while the remaining fold becomes the test set. Classifiers are built from training data sets, but importantly, their evaluations are realized on both training and test instances. This way, the effectiveness of apparently good classifiers can be demonstrated on unknown data.

In our case, experiments have been carried on the basis of 5-fold cross validation. Moreover, in order to analyze the behavior of algorithms as fairly as possible, MOLS and HYB have been run from 30 distinct seeds, on each of the 5 folds, leading to 150 measures for each algorithm and each dataset. Note that the pure CP algorithm only needs one run, on each fold, to be launched because it is deterministic (i.e., the same result is always computed, with the same performance, as no random process is involved). Finally, to make sure that each algorithm has a chance to reach local optima, the timeout has been set to 20 minutes. Experiments have been conducted on two Intel XEON E5-2687W computers of 24 cores of 3.0GHz with 64GB of RAM each.

Datasets

The datasets come from various sources [START_REF] Frank | UCI machine learning repository[END_REF][START_REF] Guyon | Design and analysis of the causation and prediction challenge[END_REF][START_REF] Schölkopf | Advances in kernel methods: support vector learning[END_REF] and represent several supervised classification problems with various degrees of imbalance (27.85% to 2.90%). Table 2 exposes the main features of each dataset and confirms their imbalanced aspect in the column 𝑑 𝑎𝑠𝑦 , which denotes the proportion of observations to be expected in the target class. These datasets come from the UCI repository 2 , except for the lucap0 dataset coming from a Machine Learning Challenge [START_REF] Guyon | Design and analysis of the causation and prediction challenge[END_REF]. The last three datasets a1a, lucap0 and w1a are binary (i.e., the number of possibles values for any attribute is always 2), and, are more challenging because they contain a higher number of observations and attributes. Because we are interested in the partial classification problem, these datasets have been converted into partial classification datasets using the methodology presented in [START_REF] Fernández | Genetics-based machine learning for rule induction: state of the art, taxonomy, and comparative study[END_REF], and discretized using the 10-bin discretization method of the KEEL software [START_REF] Alcalá-Fdez | KEEL: a software tool to assess evolutionary algorithms for data mining problems[END_REF]. On the one hand, it is clear that CP alone is far less effective than both MOLS and HYB. Indeed, green lines are often quite low, and always underneath the medians of the box-and-whisker plots. On the other hand, one can observe that hybridization can pay off: CP combined with MOLS, i.e., HYB, globally outperforms MOLS. More precisely, whereas MOLS and HYB seem to be somewhat equivalent on the first 6 datasets, there are some significant differences on the last 3 datasets in favor of the hybridization method. It is worthwhile to recall that these last datasets (a1a, lucap0 and w1a) are challenging (due to their large number of attributes and observations; see Table 2).

Results

As explained in Section 5.1, we use the Friedman statistical test [START_REF] Friedman | The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance[END_REF] to emphasize significant differences between several algorithms over various datasets. Here, this statistical test has two main objectives: firstly, to confirm the previous results, given by Figure 1, about MOLS and HYB (on the training dataset) and, secondly, to check whether the best method on training instances is always the best one on unknown data (i.e., on test instances). On the training instances, the statistical tests clearly confirm the results presented in Figure 1. Interestingly, on the test instances, they prove that the hybrid method is the most robust approach, because either HYB is equivalent to MOLS or HYB outperforms MOLS. The latter case is true for the datasets a1a, lucap0 and w1a that have the particularity of involving binary attributes, which, technically, reduces the size of the table constraints in the CP model (and consequently, improve the performance of the CP phase of the hybridization). 4 displays the F-measures obtained by HYB on both the training and test datasets. This allows us to assess the effectiveness of HYB on unknown data. The F-measures remain rather similar (when passing from training to test instances), except for haberman, yeast2vs8d and w1a which are subject to overfitting. For such datasets, one may then try to refine the k-fold cross-validation protocol.

CONCLUSION

In this paper, we have presented an original form of hybridization mixing Constraint Programming (CP) and Multi-Objective Local Search (MOLS), for solving the partial classification rule mining problem. More precisely, we have shown that it was interesting to apply CP on particular sub-problems in order to build a relevant initial population for MOLS. Experimental results on real imbalanced datasets show that our hybrid approach is statistically better than MOLS or CP, when applied stand-alone, on both training and tests instances.

In the near future, we plan to build upon this work, exploring a few perspectives. Firstly, we intend to improve the CP model by, e.g., compressing the table constraints (using various techniques from the literature). Secondly, as hybridization seems to provide a substantial advantage on large instances, we project to analyse the reasons (e.g., features of the datasets) behind this observable efficiency.

A

  Hybrid CP/MOLS Approach for Multi-Objective Imbalanced Classification GECCO '21, July 10-14, 2021, Lille, France

GECCO ' 21 ,

 21 July 10-14, 2021, Lille, France Szczepanski et al.

Figure 1

 1 Figure1reports the quality of the classifiers produced by the three approaches (CP, MOLS and HYB) on the nine training datasets. The quality directly depends on the performance of the underlying optimization methods, and is given in term of F-measure. For each dataset, we have two box-and-whisker plots: the methods HYB and MOLS are respectively represented by the left (red) and right (blue) box-and-whisker plots, each one based on 150 F-measure values. The bottom and top of each box represent the first and third quartiles, while the band inside the box corresponds to the second quartile (the median). The ends of the whiskers represent minimum and maximum values. Note that, per dataset, there is also a green line segment indicating the median of the 5 F-measure values (for the 5 folds per dataset) obtained with CP.On the one hand, it is clear that CP alone is far less effective than both MOLS and HYB. Indeed, green lines are often quite low, and always underneath the medians of the box-and-whisker plots. On the other hand, one can observe that hybridization can pay off: CP combined with MOLS, i.e., HYB, globally outperforms MOLS. More precisely, whereas MOLS and HYB seem to be somewhat equivalent on the first 6 datasets, there are some significant differences on the last 3 datasets in favor of the hybridization method. It is worthwhile to recall that these last datasets (a1a, lucap0 and w1a) are challenging (due to their large number of attributes and observations; see Table2).As explained in Section 5.1, we use the Friedman statistical test[START_REF] Friedman | The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance[END_REF] to emphasize significant differences between several algorithms over various datasets. Here, this statistical test has two main objectives: firstly, to confirm the previous results, given by Figure1, about MOLS and HYB (on the training dataset) and, secondly, to check whether the best method on training instances is always the best one on unknown data (i.e., on test instances).Table3depicts the result of this statistical test per dataset (first column) on both training and test instances, respectively in the

GECCO ' 21 ,

 21 July 10-14, 2021, Lille, France Szczepanski et al.

A

  Hybrid CP/MOLS Approach for Multi-Objective Imbalanced Classification GECCO '21, July 10-14, 2021, Lille, France

Table 1 :

 1 Confusion Matrix

		Predicted Class
		positive negative
	Actual positive	TP	FN
	Class negative	FP	TN

  ] is the attribute involved in the j 𝑡ℎ term of the i 𝑡ℎ rule 4 attributes = VarArray ( size =[ nRules , nTerms ] , dom = range ( nAttributes ))5 # operators [ i ][ j ] is the operator involved in the j 𝑡ℎ term of the i 𝑡ℎ rule

	1	from pycsp3 import *
	2	... # first , data are loaded ( code not inserted here , for simplicity )
	3 # attributes [ i ][ j 6 operators = VarArray ( size =[ nRules , nTerms ] , dom ={ EQ , LT , GT })
	7 # values [ i ][ j ] is the value involved in the j 𝑡ℎ term of the i 𝑡ℎ rule
	8	values = VarArray ( size =[ nRules , nTerms ] , dom = range ( nValues ))
	9 # terms [k ,i , j ] is 1 iff the k 𝑡ℎ observation satisfies the j 𝑡ℎ term of the i 𝑡ℎ rule
	10	terms = VarArray ( size =[ nObservations , nRules , nTerms ] , dom ={0 , 1})
	11 # rules [k , i ] is 1 if the k 𝑡ℎ observation satisfies the i 𝑡ℎ rule
	12	rules = VarArray ( size =[ nObservations , nRules ] , dom ={0 ,1})
	13 # ruleset [ k ] is 1 if the k 𝑡ℎ observation satisfies the ruleset ( i . e . , at least one of the rules )
	14	ruleset = VarArray ( size = nObservations , dom ={0 ,1})
	15 # tp is the number of true positives
	16 tp = Var ( dom = range ( nObservations ))
	17 # fp is the number of false positives
	18 fp = Var ( dom = range ( nObservations ))
	19	satisfy (
	20	# in each rule , involved attributes must be different
	21	[ AllDifferent ( attributes [ i ]) for i in range ( nRules )] ,
	22	# determining if observations satisfy terms
	23
	32 )
	33	maximize (
	34	# maximizing the F -measure
	35	(2×( tp/( tp+fp )) ×( tp/( tp+fn )))/(( tp/( tp+fp ))+( tp/( tp+fn )))
	36 )

[( terms [ k ]

[ i ][ j ] , attributes [ i ][ j ] , operators [ i ][ j ] , values [ i ][ j ]) in aux_table (k ,i , j )

24 for k in range ( nObservations ) for i in range ( nRules ) for j in range ( nTerms )] , 25 # determining if observations satisfy rules 26 [ rules [ k ][ i ] == conjunction ( terms [ k ][ i ]) for k in range ( nObservations ) for i in range ( nRules )] , 27 # determining if observations satisfy the ruleset 28 [ ruleset [ k ] == disjunction ( rules [ k ]) for k in range ( nObservations )] , 29 # computing the values of variables tp and fp 30 Count ([ ruleset [ k ] for k in range ( nbObservations ) if actual [ k ] == POSITIVE ] , value =1) == tp , 31 Count ([ ruleset [ k ] for k in range ( nbObservations ) if actual [ k ] == NEGATIVE ] , value =1) == fp , Algorithm 1: A PyCSP 3 Model for the Partial Classification Rule Mining Problem

Table 2 :

 2 Description of the datasets (number of observations, attributes, numerical attributes and degree of asymmetry). Figure 1: F-measure of the training instances by dataset. The hybrid and MOLS methods are respectively represented by the left (red) and right (blue) box-and-whisker plots (150 runs each) while the CP method is represented by the green lines (median of 5 runs).

	Name	#obs #att #num 𝑑 𝑎𝑠𝑦	ref
	haberman	306	3	3	27.42% [14]
	ecoli2d	336	7	7	15.48% [14]
	ecoli1d	336	7	7	22.92% [14]
	yeast3d	1484 8	8	10.35% [14]
	abalone9-18d 731	8	7	5.65%	[14]
	yeast2vs8d	482	8	8	4.85%	[14]
	a1a	1605 123 0	24.61% [35]
	lucap0	2000 144 0	27.85% [21]
	w1a	2477 300 0	2.90%	[35]

Table 3

 3 depicts the result of this statistical test per dataset (first column) on both training and test instances, respectively in the 2 http://archive.ics.uci.edu/ml/index.php

Table 3 :

 3 Friedman statistical test with 𝛼 = 0.01 The Friedman statistical test can output EQUIVALENT, MOLS or HYBRID according to the two specific series of numbers and ranks that are associated with the two methods. Of course, these series represent the 150 F-measure values for MOLS and HYB. The Wilcoxon signed rank test is used with a significance level of 𝛼 = 0.01. We obtain EQUIVALENT when the Wilcoxon test ensures that the probability of having MOLS F-measures greater than HYB F-measures is equal to the probability of having HYB Fmeasures greater than MOLS F-measures. But we obtain either MOLS or HYB when the two series are not equivalent in the Wilcoxon's sense; in that case, the best method is the one with the best ranking according to the Friedman statistical test.

	Name	Training	Test
	haberman	EQUIVALENT EQUIVALENT
	ecoli2d	EQUIVALENT EQUIVALENT
	ecoli1d	EQUIVALENT EQUIVALENT
	yeast3d	EQUIVALENT EQUIVALENT
	abalone9-18d EQUIVALENT EQUIVALENT
	yeast2vs8d	EQUIVALENT EQUIVALENT
	a1a	HYBRID	HYBRID
	lucap0	HYBRID	HYBRID
	w1a	HYBRID	HYBRID
	second and third columns.

Table 4 :

 4 Average values and standard deviations (given between parentheses) of F-measures obtained with the hybrid approach.

	Name	Training	Test
	haberman	0.661 (0.026) 0.389 (0.122)
	ecoli2d	0.959 (0.007) 0.794 (0.094)
	ecoli1d	0.928 (0.008) 0.755 (0.075)
	yeast3d	0.817 (0.009) 0.725 (0.043)
	abalone9-18d 0.226 (0.029) 0.344 (0.236)
	yeast2vs8d	0.924 (0.019) 0.528 (0.194)
	a1a	0.683 (0.006) 0.647 (0.022)
	lucap0	0.953 (0.001) 0.945 (0.009)
	w1a	0.610 (0.032) 0.407 (0.138)
	Table

http://www.cril.univ-artois.fr/software/abscon.html


Sylvain Clay
email: sylvain.clay.etu@univ-lille.fr

Lucien Mousin
email: lucien.mousin@univ-catholille.fr

Nadarajen Veerapen
email: nadarajen.veerapen@univ-lille.fr

Laetitia Jourdan
email: laetitia.jourdan@univ-lille.fr

CLAHC -custom late acceptance hill climbing first results on TSP

Keywords: Computing methodologies → Search methodologies Local Search, Hill Climbing, Late Acceptance Hill Climbing

come

INTRODUCTION

Combinatorial optimization aims to find good solutions to NP-hard problems within an affordable execution time. Local searches are among the simplest methods to achieve that. They involve trying to reach a solution with the best possible objective function value, starting from an initial solution and moving from solution to solution using a neighborhood operator. Numerous local search methods have been investigated in the literature, including Simulated Annealing (SA) [START_REF] Kirkpatrick | Optimization by Simulated Annealing[END_REF], Threshold Accepting (TA) [START_REF] Dueck | Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing[END_REF] or the Great Deluge Algorithm (GDA) [START_REF] Dueck | New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel[END_REF]. Late Acceptance Hill Climbing (LAHC) [START_REF] Burke | The late acceptance Hill-Climbing heuristic[END_REF] is another related method, and it has been shown to be very competitive in previous work [START_REF] Franzin | Comparison of Acceptance Criteria in Randomized Local Searches[END_REF]. It is inspired by the simplest local search method, Hill Climbing (HC) [START_REF] Holger | Stochastic Local Search: Foundations & Applications[END_REF].

In this paper, we present Custom Late Acceptance Hill Climbing (CLAHC), a new version of LAHC which produced an improvement in the majority of cases we examined.

The paper is structured as follows. We first give more details about the difference between these two heuristics in Section 2. Then we present the experimental protocol and results in Section 3. Finally we present the conclusion and further possible investigations into CLAHC in Section 4.

CLAHC -AN IMPROVED LAHC

LAHC uses the same principle as a simple HC, and improves it by using a record of the history of objective function values of the accepted solutions. We will refer to this as the history for short. In practice, this is a sliding window of objective function values that were encountered earlier during the execution of the heuristic. The history is used as part of an acceptance criterion for any new solution that we encounter. If a candidate solution has a better value than the oldest value in the history, then this solution is accepted and we carry on from there. This idea allows LAHC to avoid, to some extent, the local optimum problem of HC, which quickly reaches a final solution that can be far from the global optimum. This problem occurs because HC is not allowed to accept solutions that have a worse value than the current solution.

Beside its effectiveness, one of the most interesting properties of LAHC is that it requires only one parameter, the history size, so it is fairly simple to use. It has been shown in previous works [START_REF] Burke | The late acceptance Hill-Climbing heuristic[END_REF] that increasing the size of the history has an impact on both the final solution and the execution time. More complex metaheuristics have been experimented with using LAHC as a base, like PLAHC [START_REF] Bazargani | Parameter-less late acceptance hillclimbing[END_REF] which consists in an Iterative Local Search [START_REF]Handbook of Metaheuristics[END_REF] that uses LAHC with an increasing size of history, starting at 1 and doubling at each iteration of LAHC. The intention of this version is to free oneself from the parameter of LAHC, the size of the history, and still be able to find a good solution in the end.

In contrast, CLAHC works almost exactly like LAHC, with a single difference which is the replacement criterion for a value in the history at each iteration of the algorithm (Algorithm 1). With LAHC, first we decide if a solution is accepted as our new current solution to continue the algorithm by comparing it with our current solution and with the value in the history at the current index. If the new value is better than any of these two, then we replace the current solution by this new solution. Then we do the same thing whether we have accepted a new solution or not : we compare the value of the current solution with the one in the history at the current index. If the value in the history is worse than the value of our solution, then we replace the value in the history with the value of our solution.

c(s') = objective value of s' if c(s') ≥ c(s) then count++ else count = 0 end if v = i mod l //the index where we are in the history if c(s') < f[v] or c(s') ≤ c(s) then s = s' //we use this solution to continue end if if c(s') < f[v] then //use s' instead of s in LAHC f[v] = c[s'] //s' instead of s end if i++ end while return s
With CLAHC, things are different: we follow the same approach to decide whether to accept a new solution to continue the algorithm, however to decide whether we replace the value in the history, we do not compare it with the value of our current solution, but with the one of the solution that was candidate (highlighted in red in Algorithm 1). In other words, if the candidate solution was accepted to continue the algorithm, then CLAHC does exactly the same thing as LAHC. But if the solution was not accepted, then CLAHC compares the value in the history with the value of the solution that was not accepted, and replaces the value in the history with the value of this solution if this one is better. In other words, this means that CLAHC actually never replaces the value in the history if the candidate solution was not accepted.

This behavior allows CLAHC to keep worse values than LAHC would have allowed in its history. At first glance, it could seem like a problem, but previous works [START_REF] Bazargani | Parameter-less late acceptance hillclimbing[END_REF] have posited the idea that diversity in the history is necessary to allow the algorithm to continue its execution. With CLAHC, we propose the idea that diversity in the history also improves the performance of the algorithm, because it increases the diversification strength of the algorithm. Conversely, this behavior also has an impact on the execution time. For a history of the same size, CLAHC is slower than LAHC. But that is not a problem since CLAHC seems to perform better than LAHC even with a smaller history. 3 EXPERIMENTAL RESULTS

Protocol

We consider the Traveling Salesman Problem (TSP) for our experiments and, in particular, instances from TSPLIB [START_REF] Reinelt | TSPLIB -A Traveling Salesman Problem Library[END_REF]. Briefly, in the TSP, we have a set of cities and we try to find the shortest cycle that links all of them while passing through every city only once.

The neighborhood operator we used is the 2-opt operator, which breaks two edges in the solution and reconnects the resulting paths in the opposite order. The initial solution is random.

A configuration is an association of an algorithm (LAHC or CLAHC), a history size and an instance. For every configuration, we performed 30 runs using 30 different random seeds. We used 7 instances: rat783, u1060, fl1400, u1817, d2103, pcb3038 and fl3795. The number in the instance name indicates the respective number of cities, i.e. the size of the instance. We also chose a limited budget of function evaluations for every instance, as detailed in Table 1, in order to take the size and difficulty of the instance into consideration.

Both LAHC and CLAHC were implemented using the same MH-Builder platform. This is a C++ metaheuristics platform that is under development in our research team. As described previously, and as implemented, the only difference between LAHC and CLAHC is the history replacement criterion. Experiments were carried out on a Lenovo Z50-70 laptop, with a 4-core Intel Core i7-4510U 2.00GHz CPU and 8 GB of RAM.

Results

We first wanted to assess the impact of the history size on the performance and the execution time of CLAHC. In Table 2, we compare two versions: CLAHC 10 with a history size of 10, and CLAHC 100 with a history size of 100. We could have used a bigger history, but the algorithm would not have been able to converge with the limited budget we chose. This table shows that, just like LAHC, CLAHC gets better when we increase the size of its history.

In Figure 1 we compare execution traces on the rat783 instance. This single instance is presented here in order to remain within the paper's page limit constraint, but the general observed behavior is the same across the different instances tested. The three plots in the figure use a logarithmic scale for the y-axis (objective value) in order to better observe the inflection in the curves.

Figure 1a compares CLAHC execution traces for different sizes of history. It shows that even though our algorithm reaches a better final value, it gets slower when we increase the size of its history. This is reminiscent of LAHC's original behavior. Then we compared CLAHC and LAHC. We first compared those two algorithms with the same size of history in Figure 1b. It shows that LAHC is faster in the beginning for the same history size, but is really far from a good objective function value at the end of its execution, to the point where it is not really better than a simple HC. So we tried to find two different history sizes for LAHC and CLAHC that would allow the two algorithms to converge and be the most efficient with the same evaluation budget for every instance. We used CLAHC 100 and, depending on the instance, we compared it with LAHC with a history size between 10,000 and 25,000. Table 3 shows these results. In this table, LAHC * is the version of LAHC with the history size that performs the best on a given instance. For example, on instance rat783, CLAHC 100 is compared to LAHC 10000 , because the number of evaluations that they need to converge is the same. This table also contains the standard deviation of the concerned algorithm's solution. We also added the HC solution and the percentage deviation from the best known solution for every instance, so we have two reference points with which we can compare our results. Wilcoxon and Friedman statistical tests were performed on our results, and the best ones are in bold. We see that, for a same budget, CLAHC performs better than LAHC on every instance with the exception of fl1400.

We also wanted to see which one of LAHC or CLAHC was the fastest to reach a good solution in the beginning of the execution. Figure 1c shows that CLAHC 100 is faster than LAHC 10000 to reach a good solution, and at the end, the final value of CLAHC is still better. Even though it is not presented graphically here, even on instance fl1400 for which CLAHC is not as good as LAHC in the end, CLAHC reaches a good value faster at the beginning of the execution. We can try to interpret the worse results on fl1400 by saying that since CLAHC is faster to converge in the beginning, then it might have a bigger chance to be trapped in a local minimum than LAHC.

Figure 2 contains boxplots also showing that CLAHC 100 is faster than LAHC 10000 to reach a good solution over 30 runs, and that its performance is very steady. This figure here uses a linear scale for the y-axis (instead of the logarithmic scale in previous figures), so we can see more clearly the difference of speed between CLAHC 100 and LAHC 10000 . All these observations tend to indicate that CLAHC performs better than LAHC, because 6 out of the 7 instances that we used during our tests got better results, and even for the only instance where it is not as good as LAHC, CLAHC is faster in the beginning, meaning it might be more effective to use it in more complex methods like iterative local searches with different restart mechanisms.

We can also add the fact that the history size of CLAHC to reach a solution as good as LAHC is smaller, meaning that CLAHC uses less memory.

CONCLUSION AND FUTURE WORKS

In this paper, we proposed to alter the behavior of Late Acceptance Hill Climbing by changing how new values are accepted in the history it maintains.

Whereas with LAHC the last accepted solution value was added to the history, our method adds the value of the last candidate solution. This naturally allows for worse values to stay in the history.

We tested this simple change on 7 TSP instances. Our results show that, on the instances we used, our contribution CLAHC reaches, in all cases but one, a better final solution, is faster in the beginning of the execution, and uses less memory than LAHC, which already is considered as one of the most robust local search metaheuristics by some previous works [START_REF] Franzin | Comparison of Acceptance Criteria in Randomized Local Searches[END_REF].

This highlights the importance of the variety in the history of LAHC, and we can imagine that using other and more complex replacement criteria than the one we used for CLAHC could give even better results at the end of the day.

Another interesting point to study would be the use of a greedy heuristic for the initial solution, and study the differences between CLAHC and LAHC in that case.

Also, CLAHC being a metaheuristic, it could be adapted easily to other problems, since the only thing that would need to be changed is the neighborhood operator. This will be investigated in further works.

  Require: l, the history size Ensure: s, the final solution s = new solution c(s) = score of s for i in [0, ... , l-1] do f[i] = c(s) end for i = 0 //number of evaluations count = 0 //number of successively non-improving evaluations while i < 100000 or count < i * 0.02 do s' = new solution //neighbor of s

  CLAHC -Custom Late Acceptance Hill Climbing: first results on TSP GECCO '21 Companion, July 10-14,2021, Lille, France Traces of CLAHC 10 , CLAHC 40 and CLAHC 100 on rat783. (b) Traces of CLAHC 100 and LAHC 100 on rat783. (c) Traces of CLAHC 100 and LAHC 10000 on rat783.

Figure 1 :

 1 Figure 1: Execution traces on the rat783 instance, with a logarithmic scale on the y-axis.

Figure 2 :

 2 Figure 2: Boxplots for 30 runs of CLAHC 100 and LAHC 10000 over time on rat783.

Table 1 :

 1 Budget of the number of evaluations for each instance

	Instance	Budget
	rat783	54,000,000
	u1060	82,500,000
	fl1400	110,000,000
	u1817	315,000,000
	d2103	370,000,000
	pcb3038	830,000,000
	fl3795	1100,000,000

Table 2 :

 2 CLAHC average results over 30 runs with standard deviation in subscript, and percentage deviation from the best known solution.

	Instance	CLAHC 10		CLAHC 100
	rat783	9, 518 88	8%	9,141 54 3.8%
	u1060	239, 142 1937	6.7% 229,692 841 2.5%
	fl1400	21, 616 349	7.4%	20,803 242 3.4%
	u1817	62, 344 525	9%	59,378 279 3.8%
	d2103	89, 942 780 11.8%	85,498 529 6.3%
	pcb3038	149, 202 711	8.3% 142,672 506 3.6%
	fl3795	31, 371 660	9%	29,990 368 4.2%

Table 3 :

 3 CLAHC vs LAHC average final solutions over 30 runs, standard deviation and percentage deviation from the best known solution. LAHC * is the best LAHC configuration (with a history size chosen between 10,000 and 25,000) for an instance with the fixed budget.

	Instance	HC		LAHC *	CLAHC 100
	rat783	10, 051 84	14%	9, 296 52 5.5%	9,141 54 3.8%
	u1060	256, 117 3607	14% 232, 734 1345 3.8% 229,692 841 2.5%
	fl1400	22, 106 392	9.8%	20,582 141 2.2%	20, 803 242 3.4%
	u1817	69, 225 751	21%	60, 442 448 5.6%	59,378 279 3.8%
	d2103	99, 338 1025	23%	87, 380 729 8.6%	85,498 529 6.3%
	pcb3038 159, 325 1074 15.7% 145, 316 529 5.5% 142,672 506 3.6%
	fl3795	33, 634 716	17%	30, 406 335 5.6%	29,990 368 4.2%