Sébastien Verel

Arnaud Liefooghe

Laetitia Jourdan

Clarisse Dhaenens

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

Keywords: multiple objective programming, combinatorial optimization, local search, fitness landscape analysis, Pareto optimal set, Pareto local optima

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.

Introduction

In this paper, we study the structure of multiobjective combinatorial search spaces. The aim is to adapt and to enhance the comprehensive design of multiobjective local search approaches, motivated by an a priori analysis of problem properties. The attempt of this work is to reduce the gap between the fields of multiobjective combinatorial optimization and of fitness landscape analysis. On the one hand, multiobjective combinatorial optimization (MoCO) is one of the most challenging area from multicriteria decision making. Contrary to the single-objective case, there does not exist a single optimal solution, but a set of solutions forming the Pareto optimal set. A partial order is defined among feasible solutions, based on the so-called Pareto dominance relation. A fundamental issue is related to the identification of this set, or an approximation of it for large-size and difficult MoCO problems. The decision maker then has to select his/her most preferred solution among this set. On the other hand, fitness landscape analysis aims to understand the geometry of a combinatorial optimization problem in order to design more efficient search algorithms. However, there is a very little knowledge on the landscape of MoCO problems, where an additional difficulty relies on the structure of the Pareto optimal set. The impact of the main problemrelated properties on the behavior and the performance of multiobjective approaches is still far from being well understood.

Email addresses: verel@i3s.unice.fr (Sébastien Verel), arnaud.liefooghe@univ-lille1.fr (Arnaud Liefooghe), laetitia.jourdan@inria.fr (Laetitia Jourdan), clarisse.dhaenens@lifl.fr (Clarisse Dhaenens) We here try to give a first step towards understanding the structural properties of MoCO problems.

Motivations

There exists two main classes of approximate multiobjective search algorithms [START_REF] Ehrgott | Approximative solution methods for multiobjective combinatorial optimization[END_REF]Paquete and Stützle, 2007). Their individual dynamics is directly related to the structure of the problem under consideration, itself affected by the problem properties. First, scalar approaches are based on multiple scalarized aggregations of the objective functions, but they are only able to find a subset of Pareto optimal solutions, known as supported solutions. Second, Pareto-based approaches are based on the Pareto dominance relation. However, when the size of the Pareto optimal set gets too large, an algorithm should manipulate a limited-size solution set only.

In single-objective optimization, one of the main feature of fitness landscape analysis is related to the number of local optima, to their distribution over the search space and to the shape of their basins of attraction. It has become clear that local optima have a strong impact on the performance of search algorithms. For instance, it has been shown that local optima tend to be clustered in a 'central massif' for numerous combinatorial optimization problems, including the family of NKlandscapes [START_REF] Kauffman | The Origins of Order[END_REF]. Like in single-objective optimization, local optima clearly have a strong impact on the landscape of a MoCO problem, and then on the behavior and the efficiency of multiobjective approaches. Pareto-based local search algorithms are designed in order to take them into account (Paquete et al., 2007). In general, the aim of such approaches is to find a set of mutually non-dominated local optima. Surprisingly, up to now, there is a lack of study on the number and on the distribution of local optima in MoCO. In this work, one of our attempt is to analyze the structure of the search space, based on a notion of local optimum. However, local optima do not explain all the properties related to MoCO problems. The Pareto optimal set structure by itself also affects the behavior of multiobjective approaches. For the design of multiobjective local search algorithms, the following questions, related to the Pareto optimal set structure and to the number of local optima, are of our interest in this paper:

(i) What is the cardinality of the Pareto optimal set? Can we intend to identify or approximate the whole set of Pareto optimal solutions, or should we consider a mechanism to bound the size of the approximation set?

(ii) How many Pareto optimal solutions are supported? Is a scalar approach able to identify or approximate "enough" Pareto optimal solutions? (iii) How many local optima, in terms of Pareto dominance, are there in the search space? Can this number be estimated? Is a Pareto-based approach efficient according to such a number of local optima?

A particular attention is paid to the correlation between the objective functions. Indeed, this problem-related property is known to largely affect the solutions of a MoCO problem [START_REF] Mote | A parametric approach to solving bicriterion shortest path problems[END_REF], and the behavior of search algorithms (Paquete andStützle, 2006, 2010). To this end, a set of properlydefined problem instances, where all problem-properties can be tuned precisely, is strongly required. Unfortunately, there is a clear lack of benchmark MoCO problems. Most existing benchmark instances generally neglect objective correlation, or consist of two-objective problems. To the best of our knowledge, there does not exist any reliable way to set the objective correlation where more than two objective functions are involved.

The single exception should be the multiobjective quadratic assignment problem [START_REF] Knowles | Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem[END_REF], where a correlation parameter allows to tune the correlation between different pairs of objective functions, but not for all the objectives at the same time. The remaining properties of problem size, non-linearity and objective space dimension have been recently considered in the family of multiobjective NK-landscapes, proposed by [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF], but the objective correlation is null.

Contributions

In this paper, we conduct a fitness landscape analysis for MoCO, based on the multiobjective NK-landscapes with objective correlation. We study the structure of a MoCO search space according to the following problem properties: its size, its degree of non-linearity, its objective space dimension (up to five objective functions), and its objective correlation. We measure different features of the search space, related to the cardinality of the Pareto optimal set, the proportion of supported solutions, and the number of local optima. Our results show the importance of taking the objective correlation degree into account on the design of local search approaches. This paper extends recent works on the multiobjective NK-landscapes with objective correlation (Verel et al., 2011a,b). The main contributions of this work can be stated as follows.

• First, we propose a new approach allowing to precisely tune the correlation between multiple objective functions. Benchmark instances are proposed for correlated multiobjective NK-landscapes, and we make them available at the following URL: http://mocobench.sf.net. Note that our proposal can be generalized to other MoCO problems. We conduct a theoretical analysis and an experimental study to show the sharpness of the objective correlation, between every pair of objective functions.

• Second, we study the co-influence of objective correlation, objective space dimension and non-linearity on the properties of the Pareto optimal set by complete enumeration: its cardinality, the proportion of supported Pareto optimal solutions.

• Third, we show the co-influence of objective correlation, objective space dimension and non-linearity on the number of local optima. We propose a method based on the length of an adaptive walk to estimate this number, and we study the number of local optima for large-size problem instances. Hence, we can give better insights on the structure of the search space for large-size instances.

• At last, the consequences of these properties are discussed for the design of local search algorithms. Guidelines are provided in order to make proper choices for several methodological classes.

The remainder of the paper is organized as follows. Section 2 deals with MoCO, fitness landscapes and multiobjective local search. Section 3 presents a new approach for the design of multiobjective NK-landscapes with objective correlation. Section 4 deeply analyzes the Pareto optimal set structure according to objective space dimension, degree of non-linearity, and objective correlation. In Section 5, we study the number of local optima for enumerable instances, we propose a method to estimate this measure, and we put this method in application for large-size instances. At last, the consequences of the co-influence of problem size, objective space dimension, objective correlation and non-linearity on the main properties of the search space are summarized in the last section. This discussion is completed with multiple insights and guidelines on the design of multiobjective local search algorithms, together with open research directions.

Local search and fitness landscapes for multiobjective combinatorial optimization

This section introduces definitions for multiobjective combinatorial optimization (MoCO), and discusses fitness landscapes as well as the design of local search algorithms in such a context. Table 1 summarizes the main notations used in the paper.

Multiobjective combinatorial optimization

A MoCO problem can be defined by a set of M ≥ 2 objective functions f = ( f 1 , f 2 , . . . , f M ), and a (discrete) set X of feasible solutions in the decision space. Let Z = f (X) ⊆ IR M be the set of feasible outcome vectors in the objective space. In a maximization context, a solution x ′ ∈ X is dominated by a solution x ∈ X, denoted by x ′ ≺ x, iff ∀i ∈ {1, 2, . . . , M}, f i (x ′ ) ≤ f i (x) and ∃ j ∈ {1, 2, . . . , M} such that f j (x ′ ) < f j (x). A solution x ⋆ ∈ X is said to be Pareto optimal (or efficient, nondominated), if there does not exist any other solution x ∈ X such that x ⋆ ≺ x. The set of all Pareto optimal solutions is called the Pareto optimal set (or the efficient set). Its mapping in the objective space is called the Pareto front. A possible approach in MoCO is to identify a minimal complete Pareto optimal set, here denoted by X PO , i.e. for each point from the Pareto front, a single Pareto optimal solution in the decision space is considered, even if there could be more than one.

Generating the entire Pareto optimal set is often infeasible for two main reasons. First, for most MoCO problems, the number of Pareto optimal solutions is typically exponential in the size of the problem instance [START_REF] Ehrgott | Multicriteria optimization[END_REF]. In that sense, most MoCO problems are said to be intractable. Second, deciding if a feasible solution belongs to the Pareto optimal set is NPcomplete for numerous MoCO problems [START_REF] Serafini | Some considerations about computational complexity for multiobjective combinatorial problems[END_REF], even if none of its single-objective counterpart is NP-hard. Therefore, the overall goal is often to identify a good Pareto set approximation. To this end, heuristics in general, and evolutionary algorithms in particular, have received a growing interest since the late eighties. Multiobjective heuristics still constitute an active research area [START_REF] Deb | Multi-Objective Optimization using Evolutionary Algorithms[END_REF][START_REF] Ehrgott | Approximative solution methods for multiobjective combinatorial optimization[END_REF].

Multiobjective fitness landscapes

A neighborhood operator is a function N : X → 2 X that assigns a set of solutions N(x) ⊂ X to any solution x ∈ X. The set N(x) is called the neighborhood of x, and a solution x ′ ∈ N(x) is called a neighbor of x. In single-objective combinatorial optimization, a fitness landscape can be defined by the triplet (X, N, h), where h : X -→ IR represents the fitness function, that can be pictured as the height of the corresponding solutions. Each peak of the landscape corresponds to a local optimum. In a single-objective maximization context, a local optimum is a solution x ⋆ ∈ X such that ∀x ∈ N(x ⋆ ), h(x) ≤ h(x ⋆ ). The efficiency of local search algorithms has been shown to be related to the number of local optima for the problem under study, and to their distribution over the landscape [START_REF] Merz | Advanced fitness landscape analysis and the performance of memetic algorithms[END_REF].

In MoCO, given that Pareto optimal solutions are to be found, the notion of local optimum has to be defined in terms of Pareto optimality. Let us define the concepts of Pareto local optimum and of Pareto local optimum set. For more details, refer to Paquete et al. (2007). A solution x ∈ X is a Pareto local optimum (PLO) with respect to a neighborhood structure N if there does not exist any neighboring solution x ′ ∈ N(x) such that x ≺ x ′ . The Pareto local optimum set X PLO ∈ X is the set of whole PLO. A Locally non-dominated set A ∈ X with respect to a neighborhood structure N is a set of mutually nondominated solutions such that ∀x ∈ A, ∀x ′ ∈ (N(x) \ A), there exists x ′′ ∈ A such that x ′ ≺ x ′′ . In other words, a locally non-dominated set cannot be improved, in terms of Pareto optimality, by adding neighboring solutions. As a consequence, a locally non-dominated set is a subset of X PLO . Let us note that a Pareto optimal solution is a PLO, and that X PO is a locally non-dominated set.

A multi-objective fitness landscape can be defined by the triplet (X, N, f ), where f : X -→ IR M represents the multidimensional objective function. There exists a small amount of literature related to fitness landscape for MoCO. [START_REF] Borges | A basis for future successes in multiobjective combinatorial optimization[END_REF] study the distribution of local optima, in terms of scalarized functions, for the multiobjective traveling salesman problem (TSP). Another analysis of neighborhood-related properties for biobjective TSP instances of different structures is given by [START_REF] Paquete | Clusters of non-dominated solutions in multiobjective combinatorial optimization: An experimental analysis[END_REF]. [START_REF] Knowles | Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem[END_REF] lead a landscape analysis on the multiobjective quadratic assignment problem with a rough objective correlation. Garrett and Dasgupta (2007) discuss standard tools from fitness landscape analysis to MoCO, and an experimental study is conducted with fitness distance correlation. But this measure requires the true Pareto optimal set to be known. Afterwards, [START_REF] Garrett | Plateau connection structure and multiobjective metaheuristic performance[END_REF] consider the fitness landscape of a MoCO problem as a neutral landscape, where many solutions are incomparable. At last, in previous works on multiobjective NK landscapes [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF], enumerable fitness landscapes are divided into different fronts, i.e. layers of mutually non-dominated solutions, following the dominance principles of NSGA-II [START_REF] Deb | Multi-Objective Optimization using Evolutionary Algorithms[END_REF]. These landscapes are studied according to the number of fronts, the number of solutions on each front, the probability to move from one front to another, and the hypervolume of the Pareto front. However, this study allows to analyze only small search spaces from the single point of view of dominance rank.

Multiobjective local search

Initial approaches dealing with MoCO were based on successive transformations of the original multiobjective problem into single-objective ones by means of a scalarization strategy. Scalar approaches are generally based on a weighted-sum aggregation of the objective functions, that can be defined as follows. ∀x ∈ X:

f λ (x) = M i=1 λ i f i (x) (1)
where λ i > 0 for all i ∈ {1, . . . , M}. The problem is now to identify a (single) solution that maximizes f λ . For any given weighting coefficient vector λ, if x ⋆ = arg max x∈X f λ (x), then x ⋆ is a supported Pareto optimal solution [START_REF] Ehrgott | Multicriteria optimization[END_REF]. Multiple weighting coefficient vectors can be iteratively defined so that several non-dominated solutions are identified (or approximated). For each scalarization, the corresponding solution is incorporated into an approximation set, whose dominated solutions are then discarded. However, in the combinatorial case, a number of Pareto optimal solutions, known as non-supported solutions, are not optimal for any definition of

f λ . A solution x ∈ X is a non-supported Pareto optimal solution if (i) x ∈ X PO (i.e. x is a Pareto optimal solution), (ii) ∀λ ∈ IR M such that λ i > 0, i ∈ {1, . . . , M}, x arg max x ′ ∈X f λ (x ′
). On the contrary, there exist supported (Pareto optimal) solutions, that are solutions whose corresponding objective vectors are located on the convex hull of the Pareto front. The set of all supported Pareto optimal solutions will be denoted by X S PO . As a consequence, the proportion of non-supported solutions over the Pareto optimal set has a direct impact on the ability of scalar approaches to find a proper Pareto set approximation. Over the years, other types of approaches were proposed. Their internal search mechanisms are based on the explicit or implicit use of the Pareto dominance relation, that allows to define a partial order between feasible solutions. The basic idea is to maintain a set of solutions (typically an archive of mutually non-dominated solutions). The content of this set is then iteratively updated with new solutions built by means of neighborhood operators. The update of this set is based on a decision that specifies which solutions to accept or to choose for the next iteration. This process is iterated until no further improvement is possible or another stopping condition is fulfilled. In the end, this set corresponds to the approximation outputted by the algorithm. A whole family of such local search algorithms follows this general scheme [START_REF] Liefooghe | On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems[END_REF]. One of them is the Pareto Local Search (PLS), proposed by Paquete et al. (2007). PLS combines the use of a neighborhood structure with the management of an archive of mutually non-dominated solutions found so far. The basic idea is to iteratively improve this archive by exploring the neighborhood of its own content until no further improvement is possible, i.e. the archive falls in a Pareto local optimum set. Hence, the behavior of a PLS-like algorithm clearly depends on the number and the distribution of PLO found along the search process. Indeed, when an approximation set contains no PLO, improving solutions can be identified by exploring the neighborhood of solutions from the set. On the contrary, when an approximation set contains a large proportion of PLO, it becomes harder to find additional nondominated solutions. In general, the implicit goal of Paretobased approaches is to identify an approximation whose image in the objective space is (i) close to and (ii) well-spread along the Pareto front. However, as the number of Pareto optimal solutions is generally intractable, we often have to design specific strategies to limit the size of the approximation set for largesize problem instances [START_REF] Knowles | Bounded Pareto archiving: Theory and practice[END_REF]. As a consequence, the cardinality of the Pareto optimal set also plays a major role on the design of multiobjective local search algo-rithms.

Multiobjective NK-landscapes with objective correlation

In single-objective optimization, the family of NKlandscapes forms an interesting model to study the influence of non-linearity (epistasis) on the number of local optima [START_REF] Kauffman | The Origins of Order[END_REF]. In this section, we define the class of ρMNKlandscapes, which extend the multiobjective NK-landscapes recently proposed by [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF]. In our multiobjective model, the correlation between objective functions can be precisely tuned by a correlation coefficient value. It allows to study the simultaneous influence of problem size, nonlinearity, objective space dimension and objective correlation on the main properties of multiobjective fitness landscapes. We first introduce existing single-objective and multiobjective NKlandscapes. Then, the construction of ρMNK-landscapes is defined and the analytic proof of the correlation between objectives, completed with an experimental study, are given.

NK-and MNK-landscapes

The family of NK-landscapes is a problem-independent model used for constructing multimodal landscapes [START_REF] Kauffman | The Origins of Order[END_REF]. N refers to the number of bits in the decision space (i.e. the bit string length) and K to the number of bits that influence a particular bit from the string (the epistatic interactions or degree). By increasing the value of K from 0 to (N -1), NKlandscapes can be gradually tuned from smooth to rugged. The set of feasible solutions is made of binary strings X = {0, 1} N . The fitness function (to be maximized) f NK : X → [0, 1) associates to each solution a real number between 0 and 1. It can be computed as follows: An 'atom' with a fixed epistasis level is represented by a fitness component f i : {0, 1} K+1 → [0, 1) associated to each bit i ∈ {1, . . . , N}. Its value depends on the value of bit i and also on the values of K other bit positions (K must fall between 0 and N -1). In other words, there are K bits interacting with bit i. The fitness f NK (x) of a solution x ∈ X corresponds to the mean value of its N fitness components f i :

f NK (x) = 1 N N i=1 f i (x i , x i 1 , . . . , x i K ) (2)
where {i 1 , . . . , i K } ⊂ {1, . . . , i -1, i + 1, . . . , N}, and x i is the value of bit i in solution x. According to Eq. ( 2), the parameter K tunes the degree of non-linearity (epistasis). Several ways have been proposed to set the K bits from the bit strings. Two possibilities are mainly used: adjacent and random positions.

With an adjacent position, the nearest K bits to bit i ∈ N are chosen (the bit string is chosen to have periodic boundaries). In this work, we set the K bits randomly on the bit string of size N in order to avoid the exploitation of adjacent positions in order to improve the performance of algorithms [START_REF] Weinberger | NP completeness of kauffman's N-k model, a tuneable rugged fitness landscape[END_REF]. Indeed, such particular interactions can introduce some bias in the structure of the problem, which is beyond the scope of our study.

Each fitness component f i is specified by extension, i.e. a number y i x i ,x i 1 ,...,x i K from [0, 1) is associated with each element (x i , x i 1 , . . . , x i K ) from {0, 1} K+1 . Those numbers are uniformly distributed in the range [0, 1). As a consequence, it is very unlikely that the same fitness value is assigned to two different solutions.

More recently, a multiobjective variant of NK-landscapes (namely MNK-landscapes) has been defined with a set of M fitness functions [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF]. ∀m ∈ {1, . . . , M} ∀x ∈ X:

f m NK m (x) = 1 N N i=1 f m i (x i , x i m 1 , . . . , x i m Km ) (3)
The number of interactions between bits K m (also known as epistasis degree) can theoretically be different for each fitness function f m NK m with m ∈ {1, . . . , M}. But, in their analysis, [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF] only looked at landscapes with the same epistasis degree K m = K for all the objective functions. Similarly, we here analyze landscapes with the same epistasis degree K m = K for all the objective functions. Each fitness component f m i is specified by extension with the numbers y m,i

x i ,x i m 1 ,...,x i m K .
In the original MNK-landscapes, these numbers are randomly and independently drawn from [0, 1). We here propose an approach to design MNK-landscapes with correlated objective functions.

ρMNK-landscapes

First, let us define CMNK-landscapes, where the epistasis structure is identical for all the objectives: ∀m ∈ {1, . . . , M}, K m = K and ∀m ∈ {1, . . . , M}, ∀ j ∈ {1, . . . , K}, i m j = i j . The fitness components are not defined independently. Indeed, the M numbers (y 1,i

x i ,x i 1 ,...,x i K , . . . , y M,i x i ,x i 1 ,...,x i K ), associated with each element (x i , x i 1 , . . . , x i K ), follow a multivariate uniform distribution of dimension M, defined by a correlation matrix C. Thus, the y's follow a multidimensional distribution with uniform marginals and the correlations between y m,i ... s are defined by the matrix C.

The matrix C is a correlation matrix. As a consequence, it is a symmetric positive-definite matrix where M(M-1) 2 numbers can be defined. In order to limit the number of parameters, that tune the problem instance, we define the matrix C ρ = (c np ) with the same correlation between all the objective functions: c nn = 1 for all n, and c np = ρ for all n p. In this case, we denote CMNK-landscapes by ρMNK-landscapes. Let us note that, when ρ = 0, our model is not exactly equivalent to the classical MNK-landscapes proposed by [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF]. Indeed fitness values are drawn independently, but the two models are different in the epistasis structure.

For obvious reasons, it is not possible, for any MoCO problem, to have a high negative correlation between all pairs of objective functions. Then, for the ρMNK-landscapes, we cannot construct the matrix C ρ for all ρ values between [-1, 1]. Indeed, C ρ must be positive-definite: ∀u ∈ IR M , u t C ρ u ≥ 0. So, ρ must be greater than -1 M-1 . For two-objective problems, all the correlation coefficients in [-1, 1] are possible. However, for three-objective problems, the correlation ρ must fall in [-0.5, 1]. Of course, if one wants to study very negative correlations between some pairs of objectives, it is possible to design a matrix C that holds the condition that C is positive-definite. To generate random variables with uniform marginals and a specified correlation matrix C, we follow the work of [START_REF] Hotelling | Rank correlation and tests of significance involving no assumptions of normality[END_REF]. We first generate a (Z 1 , . . . , Z M ) vector following a multi-normal distribution of means 0 and correlation matrix R = 2 sin( π 6 C). Then, the values z i = Φ(Z i ) are uniformly distributed with a correlation matrix C, where Φ is the univariate normal cumulative density function. Note that this is not the only way to generate a multivariate uniform distribution.

Objective correlation

The objective correlation is the correlation between solutions in the objective space. The construction of CMNK-landscapes defines correlations between the y's but not directly between the objectives. In this section, we prove by algebra that the correlation between objectives is exactly tuned by the matrix C. This proof is completed by a short experimental study.

Theoretical analysis

This section gives the relation between the matrix C which defines the CMNK-landscapes and the objective correlation.

Proposition 1. Let C = (c np ) ∈ IR M × IR M be a correlation matrix. On the class of CMNK-landscapes, the expected value of the correlation between the objective functions n and p is given by the coefficient c np of the matrix C.

Proof. Let F m = ( f m NK (x)) be the fitness vector values of the 2 N solutions with respect to objective m. The correlation between the objectives n and p is: cor(F n , F p ) = cov(F n ,F p ) σ n σ p where σ n and σ p are the standard deviations of fitness values over the landscape of the n th and p th objective functions. F n (resp. F p ) corresponds to the average value of the N vectors F n i (resp. F p j ) of fitness component values:

cov(F n , F p ) = 1 N 2 N i, j=1 cov(F n i , F p j ) (4)
By definition, when i j, cov(F n i , F p j ) = 0 and cov(F n i ,

F p i ) = c np • σ ni • σ pi ,
where c np is the correlation defined in the matrix C, and σ ni (resp. σ pi ) is the standard deviation of fitness component i. The correlation between objectives n and p becomes:

cor(F n , F p ) = c np N i=1 σ ni σ pi N 2 σ n σ p (5)
By construction of the fitness functions, the following relation between standard deviations stands σ 2 n = 1 N N i=1 σ 2 ni (resp. for σ 2 p ). On average, the σ ni are equal to the standard deviation of the uniform distribution on [0, 1).

E(cor(F n , F p )) = c np (6)
Then, the expected value of the correlations between objective functions are given by the matrix C. In the ρMNKlandscapes, the parameter ρ allows to tune very precisely the correlation between all pairs of objectives.

Experimental study

In order to validate the behavior of the correlation coefficient given by Eq. ( 6) experimentally, we conduct an empirical study for N = 18 in order to enumerate the search space exhaustively. To minimize the influence of the random creation of landscapes, we considered 30 different and independent landscapes for each parameter combinations: ρ, M, and K. Measures reported are the average over these 30 landscapes. The remaining set of parameters are given in Table 2. Figure 1 gives the average value1 of the Spearman correlation coefficient according to parameters ρ, M and K. This confirms the result of Eq. ( 6). Within 30 instances, the correlation coefficient is very close to the expected value ρ between all pairs of objective functions.

Discussion

To summarize, the four parameters of the family of ρMNKlandscapes are: (i) the length of bit strings N, (ii) the number of epistatic links K, (iii) the number of objective functions M, and (iv) the correlation coefficient ρ. The parameter ρ allows to tune the objective correlation very precisely. Note that the approach proposed to tune the objective correlation can also be applied to other MoCO problems where the objective functions are summing objectives, share the same definition, but are computed with different cost or profit matrices. This is the case, for instance, of most MoCO problems presented by [START_REF] Ehrgott | Multicriteria optimization[END_REF], including the multiobjective versions of the shortest path problem, minimum spanning tree problem, knapsack problem and traveling salesman problem, among others. Our approach can also be generalized to the previous attempt made in that direction for the multiobjective quadratic assignment problem [START_REF] Knowles | Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem[END_REF]. However, here the objective correlation can be tuned between every pair of objective functions, and note only between one arbitrary objective function with each remaining one, which is not reliable for problems with more than two objective functions. The source code of the instance generator and the set of benchmark instances used in the paper can be retrieved at the following URL: http://mocobench.sf.net.

In the following, we study the influence of the problem dimension, the non-linearity (epistasis), the number of objective functions and the objective correlation on the properties of the Pareto optimal set and of Pareto local optima for the ρMNKlandscapes.

Analysis of the Pareto optimal set

In this section, we conduct an experimental analysis on the ρMNK-landscapes in order to study different properties of the Pareto optimal set (X PO ): its cardinality and the proportion of extreme supported solutions. We conduct an empirical study for N = 18 so that we can identify the (exact) Pareto optimal set by a complete enumeration of the decision space. Measures reported are the average values over 30 different and independent landscapes. The parameters under investigation in this study are given in Table 2.

Cardinality of the Pareto optimal set

Figure 2 shows the proportion of Pareto optimal solutions in the search space according to parameters K, ρ and M of ρMNKlandscapes. First of all, the epistatic parameter K has a low influence on the results. This is in accordance with the results reported by [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF], where it was shown that the number of epistatic interactions is a weaker factor compared to the number of objectives. At the opposite, the objective correlation coefficient ρ modifies the number of Pareto optimal solutions to several orders of magnitude. Indeed, the proportion decreases from 10 -4 for ρ = -0.9 to 10 -5 for ρ = 0.9 for two-objective problems, and from 10 -1 for ρ = -0.2 to 10 -5 for ρ = 0.9 for five-objective problems. With respect to the number of objective functions (M = 2, 3, and 5), the size increases of several orders of magnitude with M. For a negative objective correlation (ρ = -0.2), the proportion of Pareto optimal solutions goes from 10 -4 up to 10 -1 , whereas it goes from 10 -5 up to 10 -4 for a positive correlation (ρ = 0.9).

The influence of objective correlation on the size of X PO is at least as important as the objective space dimension. A lot of solutions are Pareto optimal when the correlation is highly negative. Now, let us suppose that we want to set, or to bound, the size of an approximation set by 100 solutions, i.e. a proportion of 4 • 10 -4 solutions with respect to the search space size for N = 18. Such a parameter setting is often used while handling an archive of non-dominated solutions in any search approach. For any correlation value ρ, a 100-solution approximation set always allows to store the whole Pareto optimal set for two-objective problems. However, this is not the case for a higher objective space dimension. For instance, for M = 5, 100 solutions suffice to store the whole Pareto optimal set for a high objective correlation only (ρ > 0.5). In other words, for ρ < 0.5, we cannot intend to identify all the Pareto optimal solutions exhaustively by handling a 100-solution approximation set.

To summarize, when the number of objectives increases, and even more when the objective correlation becomes negative, the size of the Pareto optimal set is very large, and then quickly becomes intractable. In such a case, it is not reasonable to identify the whole Pareto optimal set, and a limited-size approximation should be considered. This first result shows the importance to design a benchmark where the objective correlation can be tuned precisely, even when M > 2. Such a property should be taken into consideration for the development of local search methods, when the number of objectives becomes too large, and when there is a very negative correlation between the objective functions. A special attention should be paid to the boundingsize mechanism of the approximation set maintained by the algorithm.

Proportion of supported Pareto optimal solutions

The number of extreme supported solutions in the search space roughly follows the number of Pareto optimal solutions. ρ { -0.9, -0.7, -0.4, -0.2, 0.0, 0.2, 0.4, 0.7, 0.9} such that ρ ≥ -1 The epistatic parameter K has low influence on the size. When the objective space dimension increases, or the objective correlation decreases, the number of supported solution gets higher.

M-1 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 Avg objective correlation ρ K=2 K=4 K=6 K=8 K=10 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 Avg objective correlation ρ K=2 K=4 K=6 K=8 K=10 (M = 2) (M = 5)
.1 1 -1 -0.5 0 0.5 1 | X SPO | / | X PO | ρ K=2 K=4 K=6 K=8 K=10 0.01 0.1 1 -0.2 0 0.2 0.4 0.6 0.8 1 | X SPO | / | X PO | ρ K=2 K=4 K=6 K=8 K=10 (M = 2) (M = 5) 0.01 0.1 1 2 4 6 8 10 | X SPO | / | X PO | K M=2 M=3 M=5 0.1 1 2 4 6 8 10 | X SPO | / | X PO | K M=2 M=3 M=5 (ρ = -0.2) (ρ = 0.9)
The proportion of supported solutions in the Pareto optimal set is given in Figure 3. This proportion is nearly independent of the epistasis degree (K). But note that it may change with a landscape using a different epistasis structure on every objective function. However, when the objective correlation increases, this proportion increases. For high objective correlation (ρ = 0.9), nearly all solutions become supported (this is even the case for some instances). The same observation can be made with respect to the number of objectives: the proportion of supported solutions increases with the cardinality of the Pareto optimal set, but the former increases faster than the latter. While putting this property in relation with the design of local search algorithms, we can conclude that scalar approaches should become more appropriate when the number of objectives is low, and when the objective correlation is high. Indeed, in such a case, most Pareto optimal solutions are supported, so that they correspond to optimal solutions for a weighted-sum aggregation problem and a given setting of the weighting coefficient vector.

Discussion

In this section, we analyzed the consequence of the objective space dimension, the non-linearity, and the objective correla-tion on the structure of the Pareto optimal set. Figure 4 shows three examples of ρMNK-landscapes represented in the objective space. The number of objectives is M = 2, the epistasis parameter is K = 4 and the bit string length is N = 18. The figure gives a summary of the results in a more intuitive way. When the objective correlation is negative, the objective functions are in conflict with each other (feasible solutions are in green). The Pareto optimal set (in red) is large. In such a case, a local search has to find a limited-size Pareto set approximation only, and not the whole Pareto optimal set. When the objective correlation is null, the image of the search space in the objective space can be represented as a multidimensional "ball". The objective functions are independent, as previous studies based on the MNK-landscapes [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF]. When the objective correlation is positive, there exist few solutions in the Pareto optimal set. Nearly all Pareto optimal solutions become supported. Indeed, when the number of objectives is low, and when the objective correlation is high, Pareto optimal solutions are supported. We can conclude that scalar approaches should become more appropriate.

Bringing those properties with the design of local search algorithms helps to take proper decisions for several methodological issues. Moreover, while keeping the intensification vs. diversification trade-off in mind, it seems that neighboring or variation operators promoting exploitation should be more appropriate when the objective correlation is high. On the con-

(ρ = -0.9) (ρ = 0.0) (ρ = 0.9)
Figure 4: The objective space (maximization problem) for three landscapes. The number of objectives is M = 2, the length of bit strings is N = 18, the epistasis parameter is K = 4. From left to right, the correlation increases from negative correlation to positive correlation (ρ = -0.9, 0.0 and 0.9). Green points are random solutions from the search space (10% of the size), red points are Pareto optimal solutions, and blue points are supported Pareto optimal solutions.

trary, exploration has more importance for conflicting objectives, since many Pareto optimal solutions are to be found. However, the Pareto optimal set does not cover all the search space properties. In the next section, we focus on the properties related to Pareto local optima.

Analysis of Pareto local optima

In this section, we first study the number of Pareto local optima according to the objective correlation, the number of objectives and the epistasis of ρMNK-landscapes. Next, we analyze its relation with the size of the Pareto optimal set. Then, we propose an adaptive walk that is able to estimate the number of Pareto local optima. At last, we estimate the number of Pareto local optima for large-size problems. The instances under study are defined by the parameter setting given in Table 2.

Number of Pareto local optima

First, let us remind that a Pareto Local Optimum (PLO) is a solution with no neighbor that dominates it (see Section 2.2). Figure 5 shows the average number of PLO to the size of the search space for different ρMNK-landscapes parameter settings. PLO are enumerated exhaustively for N = 18. As the well-known result from single-objective NK-landscapes [START_REF] Kauffman | The Origins of Order[END_REF], the number of PLO increases with the epistasis degree. For instance, with an objective space dimension M = 2 and an objective correlation ρ = 0.9, the average number of PLO increases more than 30 times: from 192 for K = 2 to 6048 for K = 10. However, the range of PLO is larger with respect to objective correlation. For the same epistatic degree and number of objectives, the number of PLO decreases exponentially (Figure 5,top). Indeed, for an objective space dimension M = 2 and an epistasis degree K = 4, the average number of PLO decreases more than 120 times: from 82, 093 for a negative correlation (ρ = -0.9) to 672 for a positive correlation (ρ = 0.9). This result can be interpreted as follows. Let us consider an arbitrary solution x ∈ X, and two different objective functions f n , f p such that n p. When the objective correlation is highly positive, there is a high probability for f n (x) to be close to f p (x). In the same way, the fitness values f n (x ′ ) and f p (x ′ ) of a given neighbor x ′ ∈ N(x) are probably close. So, for a given solution x such that it exists a neighbor x ′ ∈ N(x) with a better f n -value, the probability is high that f p (x ′ ) is better than f p (x). More formally, the probability IP(

f p (x ′ ) > f p (x) | f n (x ′ ) > f n (x)), with
x ∈ X and x ′ ∈ N(x), increases with the objective correlation. Then, a solution has a higher probability of being dominated when the objective correlation is high. Moreover, the probability that a solution dominates all its neighbors decreases with the number of objectives. Figure 5 (bottom) corroborates this hypothesis. When the objective correlation is negative (ρ = -0.2), the number of PLO changes in an order of magnitude from M = 2 to M = 3, and from M = 3 to M = 5. This range is smaller when the correlation is positive. When the number of objectives is large and the objective correlation is negative, almost all solutions are PLO.

Assuming that the difficulty for Pareto-based search approaches gets higher when the number of PLO is large, the difficulty of ρMNK-landscapes increases when: (i) the epistasis increases, (ii) the number of objective functions increases, (iii) the objective correlation is negative, and its absolute value increases. Section 5.4 will precise the relative difficulty related to those parameters for large-size problem instances.

Estimating the cardinality of the Pareto optimal set?

When the number of Pareto optimal solutions is too large, it becomes impossible to enumerate them all. A search approach should then manipulate a limited-size solution set only during the search. The cardinality of the Pareto optimal set has been shown to play a major role in the design of multiobjective local search in Section 4.1. It would then be convenient to approximate the size of the Pareto optimal set from the number of PLO. Figure 6 shows the scatter plot of the average size of the Pareto optimal set vs. the average number of PLO in log-scales. Points are scattered over the regression line with the Spearson correlation coefficient of 0.82, and the regression line equation is log(y) = a log(x) + b with a = 1.059 and b = -6.536. For such a log-log scale, the correlation is low. It is only possible to estimate the cardinality of the Pareto optimal set from the number of PLO with an order of magnitude. Nevertheless, there is a high positive correlation between the number of Pareto optimal solutions and the number of PLO.

Adaptive walk

In single-objective optimization, the length of adaptive walks, computed by means of a hill-climber, allows to estimate the average diameter of the local optima basins of attraction. That is, the number of local optima can be estimated when the whole search space cannot be enumerated exhaustively. Here, we define a multiobjective hill-climber, and we show that the length of the corresponding adaptive walk is correlated with the number of PLO. However, a word of caution regarding the estimation by means of adaptive walks is the following: The height of the highest peak increases with the ruggedness (K), i.e. it decreases with the length of adaptive walks [START_REF] Aguirre | Insights on properties of multiobjective MNK-landscapes[END_REF][START_REF] Mathias | Niches in NK-landscapes[END_REF][START_REF] Skellett | Maximally rugged NK landscapes contain the highest peaks[END_REF][START_REF] Smith | New methods for tunable, random landscapes[END_REF].

We define a very basic single solution-based Pareto Hill-Climbing (PHC). At each iteration of the PHC algorithm, the current solution is replaced by one dominating random neighboring solution. As a consequence, PHC stops on a PLO. The number of iterations, or steps, of the PHC algorithm is the length of the Pareto adaptive walk. For the ρMNK-landscapes investigated here, we consider the 1-bit-flip neighborhood operator, which is directly related to a Hamming distance 1 over a bit string solution space.

We performed 10 3 independent PHC executions for each problem instance and N ∈ {8, 10, 12, 14, 16, 18}. The variation of the average length follows the opposite variation of the number of PLO. In order to show the link with the number of PLO, Figure 7 gives the scatter-plot of the average Pareto adaptive length vs. the logarithm of the average density of PLO for difference instance sizes, as given in Table 2. The correlation is strong (r = 0.997), and the regression curve equation is:

|X PLO |/|X| = C • 2 aL ,
where L is the average length of the adaptive walks, C = 0.97 and a = -1.60. For any ρMNKlandscapes parameter setting with a problem size N ≤ 18, the average length of the Pareto adaptive walks can then give a precise estimation of the average number of PLO. When the adaptive length is short, the diameter of the basin of attraction associated with a PLO is short. This means that the distance between PLO decreases. Moreover, assuming that the volume of this basin is proportional to a power of its diameter, the number of PLO increases exponentially when the adaptive length decreases. This corroborates known results from single-objective NK-landscapes [START_REF] Ochoa | A study of NK landscapes' basins and local optima networks[END_REF].

Properties vs. multi-modality for large-size problems

In this section, we study the number of PLO for large-size ρMNK-landscapes using the length of the adaptive walk as defined in the previous section. First, we analyze this number according to the problem dimension (N ∈ {18, 32, 64, 128}). Then, we give more insights on the problem difficulty, in terms of PLO, with respect to objective space dimension (M) and objective correlation (ρ).

We performed 10 3 independent PHC executions for each problem instance with N ≥ 18. Figure 8 shows the average length of the Pareto adaptive walks for different landscapes according to the parameters given in Table 2. Whatever the objective space dimension and the objective correlation, the length of the adaptive walks increases linearly with the search space dimension N: L = α • N, with a slope α < 0.33. The equation given in Section 5.3 allows to estimate the PLO density from the average length of the adaptive walk for small-size problems. Let us remind that |X| = 2 N . Following this estimation for largesize instances, the density of PLO decreases exponentially:

|X PLO |/|X| = C • 2 aαN ,
such that -0.6 < aα < 0. The coefficient aα is higher than -1, so that the number of PLO increases exponentially: |X PLO | = C.2 (1+aα)N , with 0.4 < 1 + aα < 1. We can then reasonably conclude that the size of the Pareto optimal set grows exponentially as well (Section 5.2). The slope of the Pareto adaptive length increase is related to the objective space dimension (M) and to the objective correlation (ρ). The higher the number of objective functions, the smaller the slope. As well, the higher the objective correlation, the smaller the slope.

Figure 8 (bottom) gives a qualitative comparison for given problem sizes (N = 64 and N = 128). Let us consider an arbitrary adaptive walk length of 10. For ρMNK-landscapes with N = 64 and K = 4, this length corresponds approximately to the following parameter tuples at the same time: (ρ = -0.4, M = 2), (ρ = 0.3, M = 3), and (ρ = 0.7, M = 5). As well, for N = 128 and K = 4, we have (ρ = -0.9, M = 2), (ρ = -0.1, M = 3), and (ρ = 0.3, M = 5). Still assuming that the efficiency of a Pareto-based local search algorithm is closely related to the density of PLO, a problem with a small objective space dimension but a negative objective correlation can be more difficult to solve than another problem with many positively correlated objectives.

Discussion

This section gives one of the first analysis related to the local optima of a MoCO problem, based on the Pareto dominance relation. We first focused on small-size problems with a study of the number of PLO by complete enumeration. Like in singleobjective optimization, the number of PLO increases with the degree of non-linearity of the problem (epistasis). However, the number of objective functions and the objective correlation have a stronger influence. Moreover, our results show that the cardinality of the Pareto optimal set clearly increases with the number of PLO. We proposed a Pareto adaptive walk, associated with a Pareto hill-climber, to estimate the number of PLO for small-size problems. Next, for large-size instances, the length of such Pareto adaptive walk can give a measure related to the difficulty of a MoCO problem. We show that this measure increases exponentially with the problem size. A problem with a small number of negatively correlated objectives gives the same degree of multi-modality, in terms of Pareto dominance, than another problem with a high objective space dimension and a positive objective correlation. This feature should be taken into account when dealing with large objective space dimension in many-objective optimization problems [START_REF] Wagner | Pareto-, aggregation-, and indicatorbased methods in many-objective optimization[END_REF].

Summary and future works

A qualitative summary of the results from the paper is given in Table 3. It provides a complementary view of the precise measures reported in the previous sections, and makes a stronger link with the following local search design issues.

(i) Archiving. The approximation set manipulated by the algorithm (i.e. the archive), is directly related to the cardinality of the Pareto optimal set. The number of Pareto optimal solutions grows exponentially with the problem size, the number of objectives and with the degree of conflict between the objectives. Moreover, it decreases with the non-linearity. As a consequence, the archive size should be limited as soon as the problem under consideration is large, and with many conflicting objectives. A review of existing bounded archiving techniques are provided by [START_REF] Knowles | Bounded Pareto archiving: Theory and practice[END_REF], and more recently by [START_REF] López-Ibáñez | On sequential online archiving of objective vectors[END_REF].

(ii) Scalar approach. Scalar approaches are only able to find a subset of Pareto optimal solutions, known as supported solutions. The proportion of supported solutions in the Pareto optimal set decreases with the number of objectives, and their degree of conflict. Scalar approaches should then be well-performing when there is few correlated objectives. Of course, this always relies on the efficiency of the single-objective algorithm used in the scalar approach, and on the number of Pareto optimal solutions that are likely to be found, or approximated.

(iii) Pareto-based approach. The number of local optima, measured in terms of Pareto optimality, grows exponentially with the number of objectives, their degree of conflict, and also with the problem size. As opposed to its impact on the cardinality of the Pareto optimal set, the degree of non-linearity makes the number of Pareto local optima grows. Therefore, if we assume that the algorithm effi-ciency is largely influenced by local optima, as in singleobjective optimization, the performance of Pareto-based search approaches is higher when the problem is large, and aims at optimizing many conflicting objective functions. However, the performance quality of such approaches is with no doubt associated with an increase of the computational cost, particularly when a time-consuming archiving technique is used to bound the approximation set. This result supports previous conclusions from [START_REF] Paquete | A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices[END_REF], where an experimental analysis focused on algorithmic components is conducted on the biobjective QAP.

Of course, other transversal views of Table 3, based e.g. on the problem properties, are also possible. The summary attempts to give a "big picture" of the multi-dimensional features that make local search algorithms efficient for the problem under study. All these results show that no expectation on the performance of multiobjective local search algorithms can be drawn without taking the problem properties into account very precisely. Indeed, it has now become clear that the number of objectives is one of the key issue to explain a problem complexity [START_REF] Wagner | Pareto-, aggregation-, and indicatorbased methods in many-objective optimization[END_REF], but we also pointed out that the objective correlation is at least as important. Multiobjective fitness landscape analysis plays a central role to explain the performance of local search algorithms, and to design more efficient methods, that suit better the problem features. A similar study, as the one leaded in the paper, would allow to better understand the structure of the landscape for other multiobjective combinatorial optimization problems. Moreover, additional work is required in order to compute, or rather estimate, the impact of the problem size on the proportion of supported solutions. Another perspective is to study the influence of the epistatic interactions, possibly defined with a different structure on every objective function, on the number of Pareto optimal solutions, and the proportion of supported solutions. Indeed, as studied originally by [START_REF] Aguirre | Working principles, behavior, and performance of MOEAs on MNK-landscapes[END_REF], a different epistasis structure per objective may change significantly the features of the landscape. At last, we know that the Pareto optimal set structure, as well as the number and the distribution of local optima have a strong impact on the performance of multiobjective search algorithms, but it is not yet clear how they exactly affect the search. The next step is to more precisely classify the relationship between problem structure and algorithm behavior. For sure, this open issue will constitute one of the main challenge in the emerging field of fitness landscape analysis for multiobjective combinatorial optimization.

Figure 1 :

 1 Figure 1: Average values of the objective correlation according to the parameter ρ. The number of objectives is M = 2 (left) and M = 5 (right).

Figure 2 :

 2 Figure 2: Average ratio of the number of Pareto optimal solutions compared to the size of the search space (2 N ) according to parameter ρ for different K-values (top left M = 2, right M = 5), and according to parameter K for different M-values (bottom left ρ = -0.2, right ρ = 0.9). Notice the log y-scale and the different y-ranges.

  0

Figure 3 :

 3 Figure 3: Average ratio of the number of supported Pareto optimal solutions compared to the of the Pareto optimal set according to parameter ρ for different K-values (top left M = 2, right M = 5), and according to parameter K for different M-values (bottom left ρ = -0.2, right ρ = 0.9). Notice the log y-scale.

Figure 5 :

 5 Figure 5: Average number of PLO to the size of the search space according to parameter ρ for different K-values (top left M = 2, right M = 5), and to parameter K for different M-values (bottom left ρ = -0.2, right ρ = 0.9). The problem size is N = 18.

Figure 6 :

 6 Figure 6: Scatter plot of the average size of the Pareto optimal set (to the size of the search space) vs. the average number of PLO (to the size of the search space) for the 110 possible combinations of parameters. The problem size is N = 18. The correlation coefficient is 0.82. Notice the log-scales.

Figure 7 :

 7 Figure 7: Scatter plot of the average density of PLO (to the size of the search space) vs. the average length of the Pareto adaptive walk for multiple N-values.

Figure 8 :

 8 Figure 8: Average length of the Pareto adaptive walk according to problem size (N) for K = 4 and ρ = -0.2 (top-left) and for K = 4 and M = 2 (top-right). Average length of the Pareto adaptive walk according to objective correlation (ρ) for K = 4 and N = 64 (bottom-left) and for K = 4 and N = 128 (bottom-right).

Table 1 :

 1 Main notations used in the paper.

	Notation Meaning
	X	set of feasible solutions in the decision space
	Z	set of feasible outcome vectors in the objective space
	X PO	set of Pareto optimal solutions
	PLO	a Pareto local optimum solution
	X PLO	set of Pareto local optima
	X S PO	set of supported Pareto optimal solutions

Table 2 :

 2 Parameter setting used in the paper for the experimental analysis (30 random landscapes are created for each parameter combination: ρ, M, N and K).

	Description	Parameter	Set of values
	problem size	N	(see text for details)
	epistasis	K	{2, 4, 6, 8, 10}
	number of objectives	M	{2, 3, 5}
	objective correlation

Table 3 :

 3 Guidelines for the design of multiobjective local search algorithms.

	Landscape features	Problem properties		Suggestion for the
	N	K	M	ρ	design of local search
	Cardinality of the Pareto				+ limited-size archive
	optimal set				-unbounded archive
	Proportion of supported				+ high efficiency of scalar approach
	solutions				-low efficiency of scalar approach
	Number of Pareto local				+ low efficiency of Pareto approach
	optima				-high efficiency of Pareto approach

For M >

2, there are several correlation coefficients. We report here the average correlation coefficients over all the objectives.

Acknowledgments. The authors are grateful to the anonymous referees for their valuable and constructive comments that largely contributed to improve the quality of the paper.


Enlightened Vegetarians

By Sophie Audidière

In the eighteenth century, vegetarianism was viewed as a philosophical question in its own right, at the intersection of debates about animal suffering and good health. It was also a controversial issue that saw anti-Christianism and social criticism produce similar positions.

On: Renan Larue, Le Végétarisme des Lumières. L'abstinence de viande dans la France du XVIIIe siècle, Paris, Classiques Garnier, 2019, 257 p., 22 €.

In the twenty-first century, vegetarianism is experienced and conceptualised in terms of malnutrition and political inertia, of unhealthy eating and environmental urgency. Renan Larue's book, however, makes an important contribution to the history of vegetarianism by showing that, at the broader level of human history, it has been present within various frameworks of constraint or freedom and has been a locus for various stakes to be played out. The book's title, Le Végétarisme des Lumières [Enlightenment Vegetarianism] might appear simply to be restated, in more academic terms, in its subtitle L'abstinence de viande dans la France du XVIIIe siècle [abstaining from meat in eighteenth-century France). However, while the 'Enlightenment' label is never innocently applied to any historical object of study, Larue's book does not claim to present a version of vegetarianism that might be described as 'enlightened' but rather to present the version (or versions) in circulation in eighteenthcentury France. As the book's subtitle indicates, it focuses on eating habits that deliberately avoid 'meat' or animal flesh in general.

Vegetarianism and the Enlightenment

The question of the Enlightenment is nevertheless unquestionably present and lends the book its historiographical dimension, made clear from the introduction. A certain received idea about Enlightenment philosophywhich can be traced back to the eighteenth century itself when it was first expressed in the thought of certain anti-philosophes (such as Bergier, Yvon, and Fréron; see Didier Masseau, Les Ennemis des philosophes. L'antiphilosophie au temps des Lumières, Paris, Albin Michel, 2000)equates philosophes with proponents of a narrow, instrumental (or technocratic), and anthropocentric rationalism, inherently assuming that 'Voltaire's century was the least likely to be willing to receive vegetarian ideology' (p. 13).

However, the book's clear and erudite analysis establishes that vegetarianism was considered from various viewpoints, seriously debated, and even championed in eighteenthcentury France, across a vast spectrum of philosophes and scholars. One of the welcome effects of this demonstration is its deconstruction of this received idea, which has proved so productive that, when reading eighteenth-century works today, we still find ourselves hesitating between endorsing and rejecting the 'Enlightenment' as defined by its enemiesabove all the anti-philosophesand avoiding the word 'Enlightenment' as we focus, more academically, on the 'Eighteenth century' whose 'enlightened' or 'modern' dimensions we avoid examining. And yet, at the same time, we cannot entirely detach ourselves from what we continue to find interesting about the ideas of the eighteenth-century philosophes.

However, to pursue this line is perhaps to pull the book in directions other than the one it proposes. Larue's book does not claim to be historiographical, nor does it seek to determine whether the eighteenth century was a source of contemporary vegetarianism, any more than it attempts to trace the differences between them and us. In this sense, it does indeed argue for linking the terms 'vegetarianism' and 'Enlightenment,' if we take the latter to be synonymous with 'the ideas of the philosophes': the aim is to show that, today as in the eighteenth century, certain so-called carnivorist arguments 'cause philosophers to shrug their shoulders' (p. 13).

The book thus endeavours to reveal a history of vegetarianism as an issue that is necessarily distorted and downplayed if we write about it in the terms used by its opponents. In 1804, the Civil Code defined animals as 'movable and sometimes immovable property'. The fact that the state wrote itself into the debates of the eighteenth century, legally bringing them to an end, retrospectively reveals, as Larue demonstrates, the extent to which vegetarianism was a focal point of controversy in the philosophical writing and literature of the timea controversy to which the nineteenth century would then strive to put an end.

A doubly modern dynamic

The books begins with an effective typology of the practices that relate to abstaining from the consumption of animal flesh, whose four components, of course, intersect: dietary vegetarianism, where the central concern is health; ascetic vegetarianism, focused on mortification of the flesh and spiritual elevation; religious vegetarianism, organised around sacred precepts; and finally, ethical vegetarianism, linked to the issue of animal sensibility and suffering. This typology is further supplemented by a long historical overview that brings out the capacity of Ancient vegetarianism to 'undermine the religion of the Greeks and the Romans '(p. 18) renewed in its ability to unsettle Christianity, whose universal destiny presupposes an omnivorous destiny reaching beyond the dietary prescriptions of other faiths ('vegetarianism is a form of anti-Christianism 'states the author, p. 18). While it remains compatible with an ascetic vegetarianism based on abstaining from meat at certain times for religious reasons, and does not prevent a history of compassion for animals, this Christian dietary 'becoming 'gives vegetarianism a whiff of heresy, at least for so long as there were heretical sects, up to and including the Jansenists, who harboured vegetarian tendencies.

In the modern period, the author identifies a dual dynamic that was favourable to eighteenth-century vegetarianism: first, the de-Christianised Parisian elites' interest in a healthier diet; second the 'civilising process' that affected social mores in these same social classes. The opening chapter discusses 'old and new questions about diet' and establishes, first, that vegetarianism was a familiar concept in the eighteenth century and second, that it was increasingly discussed in medical terms rather than in terms of mortification. The question of what constitutes the 'most natural' diet (p. 34) became the topic of lively debate in the eighteenth century, as a medical issue, based on a framework of ideas borrowed from Plutarch. These debates called for the taking of physiological and naturalist positions, as we can see in the discussions between Gassendi, Wallis, and Tyson, or in the controversy between Buffon and Rousseau. The discussions did not, however, amount to an apologia, as evidenced by the controversy sparked by Hecquet, a Jansenist doctor, at the beginning of the century: his defence of vegetarianism, based on a somewhat disparate collection of medical, poetic, and theological evidence, was discredited on chiefly medical grounds due to its mechanistic explanation of digestion. During this century of gluttony, and in counterpoint to the medical viewpoint, a discourse developed concerning the virtues of frugality. Chefs and gastronomes discussed the vegetarian diet, even in L'Encyclopédie, as an occasional remedy to gastronomic excesses or as a diet for children or writers. Once this discourse on frugality had been accepted at a profound level, a second and clear apologia for vegetarianism, defended by the Italian doctor Cocchi, was better received.

The author then explores the 'civilising process' in more depth and focuses on hunting, vivisection, and professions linked to meat-eating (slaughterers, butchers). The book primarily examines these three areas by studying discourses about, and sometimes accounts of, practices, focusing much more rarely on the practices themselves. It clearly demonstrates that numerous publications discussed and opposed the latter, thus revealing a new form of, or shift in, sensibility. Further historical research would be necessary, however, to determine the extent to which the positions advanced by the authors, or the testimonies they report in their fiction and essays, are representative of a 'state of mentalities' (p. 105, my emphasis) that is difficult to establish based solely on the corpus of scholarly and literary works chosen here.

The discussions of which the book offers an account relate to the observation and understanding of animal behaviour, as well as to natural history, and played a role in debates about theories of knowledge and the birth of ideas-in areas ranging from philosophical history to Biblical narrative. Arguments in favour of vegetarianism could be found everywhere and did not present a united front whereas, according to the author, there was far more coherency among those who opposed anything resembling a philosophical equiparation of humans and other animals (mainly religious apologists and clergymen). For this reason, when Larue seeks to separate moral vegetarianism from the religious question ('strictly from the moral point of view, however, independently of any religious considerations, the problem raised by vegetarians remains unsolved: do we have the right to kill animals in order to feed on them? Is it ethically just to be carnivorous?' p. 91), we cannot help but find that the vegetarians in question are more our contemporaries than they are Condorcet's. Nevertheless, and this is one of the most convincing results of Larue's investigation, Condorcet was precisely one of those who, without being vegetarian himself, explicitly addressed the question as a separate moral question. On this point, as on that of the animal-machine and its treatment in terms of animal ethics or the infra-juridical conclusions it draws from its examination of our right to eat animals, the book manages to show that historical precedents offer some measure of response to our current questions, despite the differing intellectual contexts. In other words, those wishing to defend vegetarianism today could well find inspiration in its eighteenth-century forms.

Vegetarianism problematised

Vegetarianism emerged as a system less in treatises defending it than within social mores, as generally found in imaginary spaces. Larue moves between travel-writing and fiction, both underpinned here by utopian considerations, showing the extent to which vegetarianism can shed new light on objects, mores, ideas, and representations. Here the book's value no longer consists in showing that medical, ontological, moral, and religious arguments existed in favour of a diet without animal flesh, but rather in showing the power of that diet to pose questions, as evidenced in the chapters devoted to vegetarian spaces and then, respectively, to Voltaire and Rousseau.

In this book, travel-writing poses questions about the Brahman caste and the sacralisation of the cow, for example, which were taken up in utopian literature (Desfontaines, Morelly, and Sade) to the extent that, according to Larue, vegetarianism could even be qualified as a 'common trope in the utopian genre' (p. 137). Larue draws on a theory of utopia, and in fact of literature, as helping to resolve real contradictions as opposed to advancing a political or social programme, and suggests that these utopias 'resolve the sociological problem of the shift in the threshold of sensibilities' (p. 126) which, in real life, only results in contradictions.

As for Voltaire, he appears to have been particularly prolix in discussing different types of vegetarianism, drawing on economic, naturalist, ontological, exegetic, religious, and spiritual concerns to try to understand the prevalence of 'carnivorous anthropocentrism or teleology' (p. 161) and even of the 'appetite for "cadavers in disguise"' (p. 170), two expressions that reveal what lies at the heart of the Deist Voltaire's existential angst faced with a world seemingly reborn only for the purposes of murder. The guiding thread appears to be the fight against Christianity, which reinforces the previously cited hypothesis of vegetarianism's anti-Christian potential. This requires the secularisation of vegetarianism and the writing of its social and political history. Incidentally, we can see how advantageous it is, for Voltaire in particular, to rid himself of the distinction between philosophy and controversy.

At the other end of the philosophical spectrum, Larue posits vegetarianism as the foundation of Rousseau's entire anthropological and philosophical construct (p. 198), thereby making it fully necessary as the result of a sort of argumentative regression, itself not without ambivalence or tensions. The natural history and taxonomy invoked by Rousseau, framing mankind as opportunistic vultures devoid of any carnivorous instinct, argue for human emancipation from determinism, for good or bad, as far as we and other living creatures are concerned. The fundamental place occupied, within the genetic order, by frugivorism and pastoralism-which unsurprisingly leads to the vegetarian diet being presented in Julie ou la Nouvelle Héloïse as pertaining to women, children, and the poor, and is re-enacted in 'the scene of ancient table-companionship' (p. 224)-lends a regressive connotation to Rousseau's somewhat complacent and embellished self-portrait as a vegetarian (p. 220). In short, much like Voltaire, Rousseau as a vegetarian remains consistent with himself.

The book fulfils its stated objective to rewrite the history of the vegetarian question in a way that highlights its rich and consistent role in our history more broadly. In doing so, it faces the same inevitable issues and methodological difficulties as any study of such scope, especially with regard to this century. Three of these, in particular, warrant further development. First, although readers will be grateful to the author, given the book's focus on a century as resolutely literary as it was philosophical, for drawing on such a broad range of fiction and essays, this breadth perhaps requires a distinction to be made between essayistic evidence and what the author also refers to as 'evidence', even when this is drawn from fiction (for example with regard to Voltaire, p. 173). Second, with the Revolution came new issues that remain implicit here. For example, La Harpe's 'new carnivorous arguments' in 1834, which consisted above all in demolishing the philosophers as 'vegetarian poseurs' (p. 105), should probably be considered in the post-and counter-revolutionary context: a time of intensive rewriting of the history of what was then just beginning to be called the Enlightenment. Finally, given the author's argument, the question of labour might have warranted further discussion. For example, it seems that even in the eighteenth century the question of sensibility could be viewed differently depending on whether the animals in question were, on the one hand, pets or even hunting animals and subjects for vivisection, or, on the other hand, working animals that were the driving force for labour or even its product. Similarly, explicitly foregrounding labour and exploitation, both very present in utopiasfrom 'fantasies about climates where it is possible to live off delicious food without needing to work or have others work' (p. 125) to Morelly's philosophy of 'mutual dependency' between all living creatures-might provide further resources for the author's overall intention to produce an enlightened philosophy of the living, whether endowed with sensibility or providing labour.

Published in booksandideas.net 07 mars 2020