Yangming Zhou

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

Béatrice Duval

Opposition-based Memetic Search for the Maximum Diversity Problem

Keywords: Maximum diversity, learning-based optimization, opposition-based learning, memetic search, tabu search

As a usual model for a variety of practical applications, the maximum diversity problem (MDP) is computational challenging. In this paper, we present an opposition-based memetic algorithm (OBMA) for solving MDP, which integrates the concept of opposition-based learning (OBL) into the wellknown memetic search framework. OBMA explores both candidate solutions and their opposite solutions during its initialization and evolution processes. Combined with a powerful local optimization procedure and a rank-based quality-and-distance pool updating strategy, OBMA establishes a suitable balance between exploration and exploitation of its search process. Computational results on 80 popular MDP benchmark instances show that the proposed algorithm matches the best-known solutions for most of instances, and finds improved best solutions (new lower bounds) for 22 instances. We provide experimental evidences to highlight the beneficial effect of opposition-based learning for solving MDP.

I. INTRODUCTION

G IVEN a set N of n elements where any pair of elements are separated by a distance, the maximum diversity problem (MDP) aims to select a subset S of m (m is given and m < n) elements from N in such a way that the sum of pairwise distances between any two elements in S is maximized. Let N = {e 1 , e 2 , . . . , e n } be the given set of elements and d ij ∈ R be the distance between e i and e j (d ij = d ji ). Formally, MDP can be formulated as the following quadratic binary problem [START_REF] Kuo | Analyzing and modeling the maximum diversity problem by zero-one programming[END_REF].

max f (x) = 1 2 n i=1 n j=1 d ij x i x j (1)
s.t.

n i=1 x i = m (2)
x ∈ {0, 1} n

where the binary variable x k = 1 (k = 1, . . . , n) if element e k ∈ N is selected; and x k = 0 otherwise. Equation [START_REF] Aringhieri | Tabu search versus GRASP for the maximum diversity problem[END_REF] ensures that a feasible solution x exactly contains m elements. MDP belongs to a large family of diversity or dispersion problems whose purpose is to identify a subset S from a set N of elements while optimizing an objective function defined over the distances between the elements in S [START_REF] Prokopyev | The equitable dispersion problem[END_REF]. Over the past three decades, MDP has been widely studied under different names, such as max-avg dispersion [START_REF] Ravi | Heuristic and special case algorithms for dispersion problems[END_REF], edge-weighted clique [START_REF] Macambira | The edge-weighted clique problem: valid inequalities, facets and polyhedral computations[END_REF], dense k-subgraph [START_REF] Feige | The dense k-subgraph problem[END_REF], maximum edge-weighted subgraph [START_REF] Macambira | An application of tabu search heuristic for the maximum edge-weighted subgraph problem[END_REF] and equitable dispersion [START_REF] Prokopyev | The equitable dispersion problem[END_REF]. In addition, MDP also proves to be a useful model to formulate a variety of practical applications including facility location, molecular structure design, agricultural breeding stocks, composing jury panels and product design [START_REF] Glover | Heuristic algorithms for the maximum diversity problem[END_REF], [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF]. In terms of computational complexity, MDP is known to be NP-hard [START_REF] Ghosh | Computational aspects of the maximum diversity problem[END_REF].

Given the interest of MDP, a large number of solution methods for MDP have been investigated. These methods can be divided into two main categories: exact algorithms and heuristic algorithms. In particular, exact algorithms like [START_REF] Aringhieri | Optimal results and tight bounds for the maximum diversity problem[END_REF], [START_REF] Martí | A branch and bound algorithm for the maximum diversity problem[END_REF] are usually effective on small instances with n < 150. To handle larger instances, heuristic algorithms are often preferred to find sub-optimal solutions in an acceptable time frame. Existing heuristic algorithms for MDP include construction methods [START_REF] Ghosh | Computational aspects of the maximum diversity problem[END_REF], [START_REF] Glover | Heuristic algorithms for the maximum diversity problem[END_REF], greedy randomized adaptive search procedure (GRASP) [START_REF] Aringhieri | Tabu search versus GRASP for the maximum diversity problem[END_REF], [START_REF] Duarte | Tabu search and GRASP for the maximum diversity problem[END_REF], [START_REF] Santos | A hybrid GRASP with data mining for the maximum diversity problem[END_REF], iterative tabu search (ITS) [START_REF] Palubeckis | Iterated tabu search for the maximum diversity problem[END_REF], variable neighborhood search (VNS) [START_REF] Aringhieri | Comparing local search metaheuristics for the maximum diversity problem[END_REF], [START_REF] Brimberg | Variable neighborhood search for the heaviest k-subgraph[END_REF], fine-tuning iterated greedy algorithm (TIG) [START_REF] Lozano | Iterated greedy for the maximum diversity problem[END_REF], memetic and hybrid evolutionary algorithms (MSES [START_REF] De Freitas | Memetic self-adaptive evolution strategies applied to the maximum diversity problem[END_REF], G SS [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF], MAMDP [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] and TS/MA [START_REF] Wang | A tabu search based memetic algorithm for the maximum diversity problem[END_REF]). Comprehensive surveys and comparisons of some important heuristic algorithms prior to 2012 for MDP can be found in [START_REF] Aringhieri | Comparing local search metaheuristics for the maximum diversity problem[END_REF], [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF].

Recently, research into enhancing search algorithms via machine learning techniques has gained increasing interest in artificial intelligence and operations research. Machine learning is one of the most promising and salient research areas in artificial intelligence, which has experienced a rapid development and has become a powerful tool for a wide range of applications. Researchers have made much effort on using machine learning techniques to design, analyze, and select heuristics to solve large-scale combinatorial search problems [START_REF] Bellio | Design and statistical analysis of a hybrid local search algorithm for course timetabling[END_REF], [START_REF] Kotthoff | An evaluation of machine learning in algorithm selection for search problems[END_REF], [START_REF] Leyton-Brown | Understanding the empirical hardness of NP-complete problems[END_REF], [START_REF] Raschip | Using association rules to guide evolutionary search in solving constraint satisfaction[END_REF], [START_REF] Zhou | Reinforcement learning based local search for grouping problems: A case study on graph coloring[END_REF]. Among the existing heuristics for MDP, two methods involve hybridization of heuristics and machine learning techniques. In [START_REF] Santos | A hybrid GRASP with data mining for the maximum diversity problem[END_REF], the proposed GRASP DM algorithm combines GRASP with data mining technique (i.e., frequent itemset mining). After each GRASP phase, the data mining process extracts useful patterns from recorded elite solutions to guide the following GRASP iterations. These patterns correspond to items that are shared by a significant number of elite solutions. Another learning-based heuristic is LTS EDA [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF], which uses data mining techniques (kmeans clustering and estimation of distribution algorithms) to extract useful information from the search history of tabu search in order to guide the search procedure to promising search regions. These learning-based methods have reported competitive results when they were published.

In this paper, we propose a new learning-based optimization method for solving MDP. The proposed "oppositionbased memetic algorithm (OBMA)" integrates the concept of opposition-based learning into the popular memetic algorithm (MA) framework. OBMA brings several improvements into the original MA framework. First, we employ oppositionbased learning (OBL) to reinforce population initialization as well as the evolutionary search process, by simultaneously considering a candidate solution and its corresponding opposite solution. Second, we apply a tabu search procedure for local optimization which relies on an improved parametric constrained neighborhood. Third, we propose a rank-based quality-and-distance pool updating strategy to maintain a healthy population diversity. We identify the main contributions of this work as follows.

• From an algorithmic perspective, we explore for the first time the usefulness of opposition-based learning to enhance a popular method (i.e., MA) for combinatorial optimization. We investigate how OBL can be beneficially integrated into the MA framework and show the effectiveness of the approach within the context of solving the maximum diversity problem. • From a computational perspective, we compare the proposed OBMA algorithm with state-of-the-art results on several sets of 80 large size MDP benchmark instances with 2, 000 to 5, 000 elements. Our results indicate that OBMA matches most of the best-known results and in particular finds improved best solutions (new lower bounds) for 22 instances. These new bounds are valuable for the assessment of new MDP algorithms. These computational results demonstrate the competitiveness of OBMA and the benefit of using OBL to enhance a memetic algorithm. The reminder of the paper is organized as follows. After a brief introduction of opposition-based learning and memetic search in Section II, we present in Section III the proposed opposition-based memetic algorithm. Sections IV and V show computational results and comparisons as well as an experimental study of key issues of the proposed algorithm. Conclusions and perspective are provided in Section VI.

II. BACKGROUND

This section introduces the concept of opposition-based learning and the general memetic search framework, which are then combined in the proposed approach.

A. Opposition-based Learning

Opposition-based learning (OBL) was originally proposed as a machine intelligence scheme for reinforcement learning [START_REF] Tizhoosh | Opposition-based learning: A new scheme for machine intelligence[END_REF]. The main idea behind OBL is the simultaneous consideration of a candidate solution and its corresponding opposite solution. To explain the concept of opposition, we consider a real number x ∈ [a, b], then the opposite number x is defined as x = a + b -x. For the case of MDP, we define the concept of opposite solution in Section III. OBL is a fast growing research field in which a variety of new theoretical models and technical methods have been studied to deal with complex and significant problems [START_REF] Al-Qunaieer | Opposition based computing -A survey[END_REF], [START_REF] Rahnamayan | Opposition-based differential evolution[END_REF], [START_REF] Ventresca | A diversity maintaining population-based incremental learning algorithm[END_REF], [START_REF] Xu | A review of oppositionbased learning from 2005 to 2012[END_REF]. Recently, the idea of OBL has also been used to reinforce several global optimization methods such as differential evolution, particle swarm optimization, biogeography-based optimization, artificial neural network, bee and ant colony optimization [START_REF] Xu | A review of oppositionbased learning from 2005 to 2012[END_REF], [START_REF] Aziz | Opposition-based magnetic optimization algorithm with parameter adaptation strategy[END_REF].

To apply OBL to solve an optimization problem, one needs to answer a fundamental question: given a solution from the search space, why is it more advantageous to consider an opposite solution of the current solution than a second pure random solution? For one dimensional search space, a proof and an empirical evidence confirmed how much an opposite solution is better than a uniformly generated random solution [START_REF] Rahnamayan | Opposition versus randomness in soft computing techniques[END_REF]. This result was further generalized to the N-dimensional search spaces for black-box (continuous) problems in [START_REF] Rahnamayan | An intuitive distance-based explanation of opposition-based sampling[END_REF].

We observe that existing studies on OBL-based optimization concerns only global optimization with two exceptions. In 2008, Ventresca and Tizhoosh [START_REF] Ventresca | A diversity maintaining population-based incremental learning algorithm[END_REF] proposed a diversity maintaining population-based incremental learning algorithm for solving the traveling salesman problem (TSP), where the concept of opposition was used to control the amount of diversity within a given sample population. In 2011, Ergezer and Simon [START_REF] Ergezer | Oppositional biogeography-based optimization for combinatorial problems[END_REF] hybridized open-path opposition and circular opposition with biogeography-based optimization for solving the graph coloring problem and TSP. The main difficulty of these applications is how to define and evaluate opposite solutions in a discrete space. OBL being a generally applicable technique, its efficiency depends on the matching degree between the definition of OBL and the solution space of the considered problem, as well as the rationality justifying a combination of OBL with a search algorithm [START_REF] Xu | A review of oppositionbased learning from 2005 to 2012[END_REF].

B. Memetic Algorithm

The memetic algorithm framework (MA) [START_REF] Moscato | Memetic algorithms: A short introduction[END_REF], [START_REF] Krasnogor | A tutorial for competent memetic algorithms: model, taxonomy, and design issues[END_REF] is a well-known hybrid search approach combining populationbased search and local optimization. MA has been successfully applied to tackle numerous classical NP-hard problems [START_REF] Chen | A multi-facet survey on memetic computation[END_REF], [START_REF] Hao | Memetic algorithms in discrete optimization[END_REF], such as graph coloring [START_REF] Lü | A memetic algorithm for graph coloring[END_REF], graph partitioning [START_REF] Benlic | A multilevel memetic approach for improving graph k-partitions[END_REF], [START_REF] Galinier | An efficient memetic algorithm for the graph partitioning problem[END_REF] and generalized quadratic multiple knapsack [START_REF] Chen | Memetic search for the generalized quadratic multiple knapsack problem[END_REF] as well as the maximum diversity problem [START_REF] De Freitas | Memetic self-adaptive evolution strategies applied to the maximum diversity problem[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF].

A typical MA algorithm (Algorithm 1) begins with a set of random or constructed solutions (initial population). At each generation, MA selects two or more parent solutions from the population, and performs a recombination or crossover operation to generate one or more offspring solutions. Then a local optimization procedure is invoked to improve the offspring solution(s). Finally, a population management strategy is applied to decide if each improved offspring solution is accepted to join the population. The process repeats until a stopping condition is satisfied. We show below how OBL and MA can be combined to obtain a powerful search algorithm for the highly combinatorial maximum diversity problem.

III. OPPOSITION-BASED MEMETIC ALGORITHM FOR MDP

We describe in this section the proposed opposition-based memetic algorithm for MDP. We start with the issues of so-Algorithm 1 The general memetic algorithm framework 1: Input: a problem instance and population size p 2: Output: the best solution S * found // Build an initial population 3: P = {S 1 , S 2 , . . . , S p } ← PoolInitialization () // We suppose it is a maximization problem, record the best solution found so far 4: S * = arg max{f (S i )|i = 1, 2, . . . , p} 5: while a stopping condition is not reached do 6:

(S i , . . . , S j ) ← ParentsSelection (P ) // Generate an offspring solution 7:

S o ← CrossoverOperator(S i , . . . , S j ) // Improve the offspring solution

if f (S o ) > f (S * ) then 11: S * ← S o 12:
end if 13: end while lution representation and search space, followed by a detailed presentation of the ingredients of the proposed approach.

A. Solution Representation and Search Space

Given a MDP instance with set N = {e 1 , e 2 , . . . , e n } and integer m, any subset S ⊂ N of size m is a feasible solution. A candidate solution S can then be represented by S = {e S(1) , e S(2) , . . . , e S(m) } such that S(i) is the index of element i in N or equivalently by a binary vector of size of n such that exactly m variables receive the value of 1 and the other n -m variables receive the value of 0. The quality of a candidate solution S is assessed by the objective function f of Equation [START_REF] Al-Qunaieer | Opposition based computing -A survey[END_REF].

Given a MDP instance, the search space Ω is composed of all the m-element subsets of N , i.e., Ω = {S ⊂ N : |S| = m}. The size of Ω is given by n m = n! m!(n-m)! and increases extremely fast with n and m.

B. Main Scheme

The proposed OBMA algorithm for MDP is based on opposition learning, which relies on the key concept of opposite solution in the context of MDP, which is defined as follows.

Definition 1 (Opposite solution): Given a MDP instance with set N and integer m, let S be a feasible solution of Ω represented by its binary n-vector x, an opposite solution S corresponds to a feasible binary vector x whose components match the complement 1 of x as closely as possible.

According to this definition, if m < n 2 , S corresponds to any subset of elements of size of m from N \S. If m = n 2 , the unique opposite solution is given by S = N \ S. If m > n 2 , S is any subset of n -m elements from N \ S, completed by other 2m -n elements from S.

We observe that a diversification framework introduced in [21] also yields the type of opposite solution provided by our definition and applies to constraints more general than 1

Let x ∈ {0, 1} n , its complement x is an n-vector such that x[i] = 1 if x[i] = 0; x[i] = 0 if x[i] = 1.
the constraint defined by Equation [START_REF] Aringhieri | Tabu search versus GRASP for the maximum diversity problem[END_REF]. We make two related comments. First, as we observe in Section IV, the MDP benchmark instances in the literature correspond to the case m n 2 . Second, in practice, when an opposite solution is required while there are multiple opposite solutions, we can just select one solution at random among the candidate opposite solutions. The proposed OBMA algorithm consists of four key components: an opposition-based population initialization procedure, a backbone-based crossover operator, an opposition-based double trajectory search procedure and a rank-based qualityand-distance pool updating strategy. OBMA starts from a collection of diverse elite solutions which are obtained by the opposition-based initialization procedure (Section III-C). At each generation, two parent solutions are selected at random from the population, and then the backbone-based crossover operator (Section III-E) is applied to the selected parents to generate an offspring solution and a corresponding opposite solution. Subsequently, the opposition-based double trajectory search procedure (Section III-D) is invoked to search simultaneously from the offspring solution and its opposite solution. Finally, the rank-based pool updating strategy (Section III-F) decides whether these two improved offspring solutions should be inserted into the population. This process repeats until a stopping condition (e.g., a time limit) is satisfied. The general framework of the OBMA algorithm is shown in Algorithm 2 while its components are described in the following sections.

C. Opposition-based Population Initialization

The initial population P is composed of p diverse and high quality solutions. Unlike traditional population initialization, our population initialization procedure integrates the concept of OBL. As shown in Algorithm 3, the OBL-based initialization procedure considers not only a random candidate solution but also a corresponding opposite solution. Specifically, we first generate a pair of solutions, i.e., a random solution S r ∈ Ω and a corresponding opposite solution S r according to Definition (1) of Section III-B (if multiple opposite solutions exist, one of them is taken at random). These two solutions are then improved by the tabu search procedure described in Section III-D. Finally, the better one of the two improved solutions S ′ is inserted into the population if S ′ is not the same as any existing individual of the population. Otherwise, we modify S ′ with the swap operation (see Section III-D1) until S ′ becomes different from all individuals in P before inserting it into the population. This procedure is repeated until the population is filled up with p solutions. With the help of this initialization procedure, the initial solutions of P are not only of good quality, but also of high diversity.

D. Opposition-based Double Trajectory Search Procedure

In the proposed OBMA algorithm, we use an oppositionbased double trajectory search procedure (ODTS) for local optimization. ODTS simultaneously searches around an offspring solution S o and one opposite solution S o . The local optimization procedure used here is an improved constrained neighborhood tabu search. Tabu search is a well-known metaheuristic that guides a local search heuristic to explore the solution space beyond local optimality [START_REF] Glover | Tabu search[END_REF]. The original constrained neighborhood tabu search algorithm was proposed in [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF], which is specifically designed for MDP by using a constrained neighborhood and a dynamic tabu tenure management mechanism. Compared with this tabu search algorithm, our improved tabu search procedure (see Algorithm 4) distinguishes itself by its parametric constrained neighborhood which allows the search process to explore more promising candidate solutions. In the following, we present the key ingredients of this local optimization procedure including the parametric constrained neighborhood, the fast neighborhood evaluation technique and the dynamic tabu tenure management scheme. Determine subset U c S according to Eq. ( 6)

10:

maxGain ← max{gain(ei) : ei ∈ N \ S} 11:
Determine subset U c N \S according to Eq. ( 7)

12:

Choose a best eligible swap(eu, ev) (see Sect. III-D3)

13:

S ← S \ {eu} ∪ {ev} 14:

Update the tabu list and gain(ei) for each element ei ∈ N according to Eq. ( 8)

15: if f (S) > f (S * ) then 16:
S * ← S iter ← iter + 1 19: end while according to some specific transition rule (e.g., accepting the first or the best improving transition). Clearly, the size of this neighborhood is bound by O(m(n -m)) and an exhaustive exploration of all the possible swap moves is too time-consuming for the large values of n. To reduce the size of the swap neighborhood, we employ an extension of a candidate list strategy sometimes called a neighborhood decomposition strategy [START_REF] Glover | A Users Guide to Tabu Search[END_REF] or a successive filtration strategy [START_REF] Rangaswamy | Tabu search candidate list strategies in scheduling[END_REF], and which we refer to as a constrained swap strategy [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. As it is shown in the experimental analysis of Section V-A, although this constrained swap strategy accelerates the search process, it imposes a too strong restriction and may exclude some promising swap moves for the tabu search procedure. In this work, we introduce the parametric constrained neighborhood which adopts the idea of the constrained neighborhood, but weakens the imposed constraint by introducing a parameter ρ (ρ 1) to control the size of the explored neighborhood. Both constrained neighborhoods rely on the notion of move gain of each element e i with respect to the objective value of the current solution S defined as follows.

gain

(e i ) = ej ∈S d ij , i = 1, 2, . . . , m (4)
Let swap(e u , e v ) denote the swap operation which exchanges an element e u ∈ S against an element e v ∈ N \ S.

Once a swap S swap(eu,ev)

--------→ S ′ is made, it provides a new solution S ′ = S \ {e u } ∪ {e v } and the move gain ∆ uv of this swap can be calculated according to the following formula.

∆ uv = f (S ′ ) -f (S) = gain(e v ) -gain(e u ) -d uv (5)
Equation [START_REF] Aziz | Opposition-based magnetic optimization algorithm with parameter adaptation strategy[END_REF] suggests that in order to maximize the move gain, it is a good strategy to consider swap moves that replaces in the current solution S an element e u with a small gain by an element e v out of S with a large gain. In other words, the search process can only consider swap moves that involve an element e u * from S with the minimal gain value and an element e v * in N \ S with a maximal gain value. However the move gain also depends on the distance d u * v * between e u * and e v * . These remarks lead to the following definition for the parametric constrained neighborhood.

For a current solution S, let minGain = min{gain(e i ) : e i ∈ S} and maxGain = max{gain(e i ) : e i ∈ N \ S} and d max = max{d ij : 1 i < j n}. The parametric constrained neighborhood relies on the two following sets.

U c S = {e i ∈ S : gain(e i ) minGain + ρ 2 d max } (6)
and

U c N \S = {e i ∈ N \ S : gain(e i ) maxGain - ρ 2 d max } (7)
Therefore, a constrained neighbor solution S ′ can be obtained from S by swapping one element e u ∈ U c S and another element e v ∈ U c N \S . Clearly, the evaluation of all constrained neighboring solutions can be achieved in

O(|U c S | × |U c N \S |).
Conveniently, we can adjust the value of parameter ρ (ρ 1) to control the size of the constrained neighborhood.

One notices that the neighborhood of [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] is a special case of the above neighborhood when ρ = 2. In general, a larger ρ value leads to a less constrained neighborhood compared to the neighborhood of [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF], allowing thus additional promising candidate solutions to be considered by the tabu search procedure. The experimental analysis of Section V-A confirms the effectiveness of this parametric constrained neighborhood.

2) Fast neighborhood evaluation technique: Once a swap(e u , e v ) move is performed, we need to update the gains gain(e i ) affected by the move. To rapidly determine the gain of each element e i , we resort to the fast neighborhood evaluation technique used in [START_REF] Aringhieri | Tabu search versus GRASP for the maximum diversity problem[END_REF], [START_REF] Aringhieri | Comparing local search metaheuristics for the maximum diversity problem[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF].

gain(e i ) =      gain(e i ) + d iv if e i = e u gain(e i ) -d iu if e i = e v gain(e i ) + d iv -d iu if e i = e u and e i = e v .
(8) Updating the gains of n elements requires O(n) time. Therefore, the time to update the parametric constrained neighborhood at each iteration is bounded by

O(n)+O(|U c S |×|U c N \S |).
3) Dynamic tabu tenure management scheme: Starting with a solution S, tabu search iteratively visits a series of neighboring solutions generated by the swap operator. At each iteration, a best swap (i.e., with the maximum move gain ∆ uv ) is chosen among the eligible swap moves to transform the current solution even if the resulting solution is worse than the current solution. To prevent the search from cycling among visited solutions, tabu search typically incorporates a short-term history memory H, known as the tabu list [START_REF] Glover | Tabu search[END_REF].

Initially, all elements are eligible for a swap operation. Once a swap(e u , e v ) is performed, we record it in the tabu list H to mark element e u as tabu, meaning that element e u is forbidden to join again solution S during the next T u iterations (T u is called the tabu tenure). Similarly, element e v is also marked as tabu for the next T v iterations and thus cannot be removed from S during this period. The tabu status of an element is disabled if the swap operation with this element leads to a solution better than any already visited solution (this rule is called the aspiration criterion in tabu search). An eligible swap move involves only elements that are not forbidden by the tabu list or satisfy the aspiration criterion.

It is important to determine a suitable tabu tenure for the elements of a swap. Yet, there does not exist a universally applicable tabu tenure management scheme. In this paper, we adopt a dynamic tabu list management technique which was proposed in [START_REF] Galinier | An efficient memetic algorithm for the graph partitioning problem[END_REF] and proved to work well for MDP [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. The tabu tenure T x of an element e x taking part in a swap operation is determined according to a periodic step function T (iter), where iter is the number of iterations. Specifically, T (iter) takes the value of α (a parameter set to 15 in this work), 2×α, 4×α and 8×α according to the value of iter, and each T (iter) value is kept for 100 consecutive iterations (see [START_REF] Galinier | An efficient memetic algorithm for the graph partitioning problem[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] for more details). Following [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF], we set T u = T (iter) for the element e u dropped from the solution and T v = 0.7 * T (iter) for the element e v added to the solution.

To implement the tabu list, we use an integer vector H of size n whose components are initially set to 0 (i.e.,

H[i] = 0, ∀i ∈ [1, . . . , n]). After each swap(e u , e v ) operation, we set H[u] (resp. H[v]) to iter + T u (resp. iter + T v )
, where iter is the current number of iterations and T u (resp. T v ) is the tabu tenure explained above. With this implementation, it is very easy to know whether an element e i is forbidden by the tabu list as follows. If iter ≤ H[i], then e i is forbidden by the tabu list; otherwise, e i is not forbidden by the tabu list.

E. Backbone-based Crossover Operator

The crossover operator plays a critical role in memetic search and defines the way information is transmitted from parents to offspring [START_REF] Hao | Memetic algorithms in discrete optimization[END_REF]. A meaningful crossover operator should preserve good properties of parent solutions through the recombination process. In our case, we adopt a backbonebased crossover operator which generates an offspring solution in the same way as in [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] while introducing additionally an opposite solution. For MDP, the backbone is a good property that is to be transmitted from parents to offspring, as shown in Definition 2. Specially, the backbone-based crossover operator not only produces an offspring solution, but also creates a corresponding opposite solution.

Definition 2 (backbone [START_REF] Hao | Memetic algorithms in discrete optimization[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]): Let S u and S v be two solutions of MDP, the backbone of S u and S v is defined as the set of common elements shared by these two solutions, i.e., S u ∩ S v .

Given a population P = {S 1 , S 2 , . . . , S p } of p individuals, an offspring solution is constructed in two phases. The first phase randomly selects two parents S u and S v in P and identifies the backbone which is used to form the partial offspring S o , i.

F. Rank-based Pool Updating Strategy

To maintain a healthy diversity of the population, we use a rank-based pool updating strategy to decide whether the improved solutions (S o and S o ) should be inserted into the population or discarded. This pool updating strategy simultaneously considers the solution quality and the distance between individuals in the population to guarantee the population diversity. Similar quality-and-distance pool updating strategies have been used in memetic algorithms in [START_REF] Chen | Memetic search for the generalized quadratic multiple knapsack problem[END_REF], [START_REF] Lü | A memetic algorithm for graph coloring[END_REF], [START_REF] Sörensen | MA|PM: memetic algorithms with population management[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF].

For two solutions S u and S v , we use the well-known settheoretic partition distance [START_REF] Gusfield | Partition-distance: A problem and class of perfect graphs arising in clustering[END_REF] to measure their distance.

D(S u , S v ) = m -Sim(S u , S v ) (9)
where Sim(S u , S v ) = |S u ∩ S v | denotes the number of common elements shared by S u and S v . Given a population P = {S 1 , S 2 , . . . , S p } and one solution S i in P , the average distance between S i and the remaining individuals in P is computed by [START_REF] Chen | Memetic search for the generalized quadratic multiple knapsack problem[END_REF].

AD(S i , P ) = 1 p S j ∈P,j =i D(S i , S j ) (10)
To update the population with an improved offspring solution (S o or S o ), let us consider the case of S o (the same procedure is applied to S o ). We first tentatively insert S o into the population P , i.e., P ′ ← P ∪ {S o }. Then all individuals in P ′ are assessed based on the following function.

Score(S i , P ′ ) = β * RF (f (S i )) + (1 -β) * RF (AD(S i , P ′ )) (11)
where RF (f (S i )) and RF (AD(S i , P ′ )) represent respectively the rank of solution S i with respect to its objective value and the average distance to the population. Specifically, RF (•) ranks the solutions of P in decreasing order according to their objective values or their average distances to the population. In case of ties, the solution with the smallest index is preferred. β is the weighting coefficient between the objective value of the solution and its average distance to the population, which is empirically set to β = 0.6.

Based on this scoring function, we identify the worst solution S w with the largest score value from the population P ′ . If the worst solution S w is not the improved offspring S o , then the population is updated by replacing S w by S o ; otherwise, S o is simply discarded.

G. Computational Complexity of OBMA

To analyze the computational complexity of the proposed OBMA algorithm, we consider the main steps in one generation in the main loop of Algorithm 2.

As shown in Algorithm 2, each generation of the OBMA algorithm is composed of four components: parents selection, backbone-based crossover, tabu search and rank-based pool updating strategy. The step of parents selection is bounded by O(1). The backbone-based crossover operation can be achieved in O(nm 2 ). The computational complexity of the parametric constrained neighborhood search procedure is O((n+|U c S |×|U c N \S |)M axIter), where |U c S | is the number of elements that can be swapped out from S, |U c N \S | is the number of elements in N \ S that can be swapped into S, and M axIter is the allowable maximum number of iterations in tabu search. The computational complexity for the pool updating strategy is O(p(m 2 + p)), where p is the population size. To summarize, the total computational complexity of the proposed OBMA within one generation is

O(nm 2 + (n + |U c S | × |U c N \S |)M axIter).

IV. COMPUTATIONAL RESULTS

This section presents computational experiments to test the efficiency of our OBMA algorithm. We aim to 1) demonstrate the added value of OBMA (with OBL) compared to the memetic search framework (without OBL), and 2) evaluate the performance of OBMA with respect to the best-known results ever reported by state-of-the-art algorithms in the literature.

A. Benchmark Instances

Our computational assessment were based on 80 large instances with 2000 to 5000 elements which are classified into the following sets.

Set I contains three data sets: MDG-a (also known as Type1 22), MDG-b and MDG-c. They are available at http: //www.optsicom.es/mdp/.

• MDG-a: This data set consists of 20 instances with n = 2000, m = 200. The distance d ij between any two elements i and j is an integer number which is randomly selected between 0 and 10 from a uniform distribution. • MDG-b: This data set includes 20 instances with n = 2000, m = 200. The distance d ij between any two elements i and j is a real number which is randomly selected between 0 and 1000 from a uniform distribution. • MDG-c: This data set is composed of 20 instances with n = 2000, m = 300, 400, 500, 600. The distance d ij between any two elements i and j is an integer number which is randomly selected between 0 and 1000 from a uniform distribution.

Set II (b2500) contains 10 instances with n = 2500, m = 1000, where the distance d ij between any two elements e i and e j is an integer randomly generated from [-100, 100]. This data set was originally derived from the unconstrained binary quadratic programming problem by ignoring the diagonal elements and is part of ORLIB: http://people.brunel.ac. uk/ ∼ mastjjb/jeb/orlib/files/.

Set III (p3000 and p5000) contains 5 very large instances with n = 3000 and m = 1500, and 5 instances with n = 5000 and m = 2500, where d ij are integers generated from a [0, 100] uniform distribution. The sources of the generator and input files to replicate this data set can be found at: http: //www.proin.ktu.lt/ ∼ gintaras/mdgp.html.

B. Experimental Settings

Our algorithm 2 was implemented in C++, and complied using GNU gcc 4.1.2 with '-O3' option on an Intel E5-2670 with 2.5GHz and 2GB RAM under Linux. Without using any compiler flag, running the DIMACS machine benchmark program dfmax 3 on our machine requires 0.19, 1.17 and 4.54 seconds to solve graphs r300.5, r400.5 and r500.5 respectively. To obtain our experimental results, each instance was solved according to the settings (including time limit and number of runs) provided in Tables I and II. Notice that, like most reference algorithms of Section IV-D, we used a cutoff time limit (instead of fitness evaluations) as the stopping condition. This choice is suitable in the context of MDP given that its fitness evaluation is computationally cheap enough, contrary to expensive-to-evaluate problems like many engineering optimization problems where using fitness evaluations is a standard practice [START_REF] Jin | Surrogate-assisted evolutionary computation: Recent advances and future challenges[END_REF].

C. Benefit of OBL for Memetic Search

To verify the benefit of OBL for memetic search, we compare OBMA with its alternative algorithm OBMA 0 without OBL. To obtain OBMA 0 , two modifications have been made on OBMA: 1) for the population initialization phase, we randomly generate two initial solutions at a time (instead of a random solution and an opposite solution); 2) for the crossover phase, we perform twice the crossover operation to generate two offspring solutions (instead of one offspring solution and an opposite solution). To make a fair comparison between OBMA and OBMA 0 , we ran both algorithms under the same conditions, as shown in Tables I and II. The comparative results for the five data sets are summarized in Tables III-VII. 2 The best solution certificates and our program will be made available at http://www.info.univ-angers.fr/pub/hao/OBMA.html.

3 dfmax: ftp://dimacs.rutgers.edu/pub/dsj/clique

In these tables, columns 1 and 2 respectively show for each instance its name (Instance) and the current best objective value (f prev ) jointly reported in recent studies [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF], [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF], [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF]. Columns 3-7 report the results of the OBMA 0 algorithm: the difference between f prev and the best objective value f best (i.e., ∆f best = f prev -f best ), the difference between f prev and average objective value f avg (i.e., ∆f avg = f prev -f avg ), the standard deviation of objective values (σ), the average CPU time to attain the best objective values (t best ) and the success rate (#succ) over 30 or 15 independent runs. 8-12 present the same information of the OBMA algorithm. The best values among the results of the two compared algorithms are indicated in bold. At the last row, we also provide the average number of instances for which one algorithm outperforms the other algorithm. 0.5 is assigned to each compared algorithm in case of ties.

To analyze these results, we resort to a widely-used statistical methodology known as two-tailed sign test [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF]. This test is a popular way to compare the overall performance of algorithms by counting the number of winning instances of each compared algorithm and thus to identify the overall winner algorithm. The test makes the null hypothesis that the compared algorithms are equivalent. The null hypothesis is accepted if each algorithm wins on approximately X/2 out of X instances. Otherwise, the test rejects the null hypothesis, suggesting a difference between the compared algorithms. The Critical Values (CV ) for the two-tailed sign test at a significance level of 0.05 are respectively CV 20 0.05 = 15 for X = 20 instances and CV 10 0.05 = 9 for X = 10 instances. In other words, algorithm A is significantly better than algorithm B if A performs better than B for at least CV X 0.05 instances for a data set of X instances.

From Table III which shows the results of OBMA 0 and OBMA for the 20 MDG-a instances, we first observe that both algorithms attain the best-known results reported in the literature. However, OBMA performs better than OBMA 0 in terms of the average objective value and success rate, and wins 14.5 instances and 13.5 instances respectively. We also observe that the standard deviation of the best objective values is significantly smaller for OBMA, and OBMA wins 14.5 instances, which is very close to the critical value (CV 20 0.05 = 15). Finally, compared to OBMA 0 , OBMA needs less average CPU time to find the best-known solutions for all instances except MDGa 26 and wins 13.5 instances in terms of the success rate.

Table IV shows the results of OBMA 0 and OBMA for the 20 MDG-b instances. The best-known objective values (f prev ) of this data set were obtained by a scatter search algorithm (G SS) [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF] with a time limit of 2h on an Intel Core 2 Quad CPU 8300 with 6GB of RAM running Ubuntu 9.04 [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF]. This table indicates that both OBMA and OBMA 0 find improved best-known solutions for 14 out of 20 instances and attain the best objective values for the remaining 6 instances. On the other hand, compared to the OBMA 0 algorithm, OBMA obtains a better average objective value and higher success rate for 13.5 and 13 instances. It is worth noting that OBMA has a steady performance, and achieves these results with a 100% success rate on almost all instances except for MDG-b 24, MDG-b 32 and MDG-b 33. To summarize, OBMA performs The fprev values were obtained by several algorithms including LTS-EDA [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF] and MAMDP [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. The best-known values fprev were obtained by a scatter search algorithm (G SS) [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF] with a time limit of 2 hours, which are available at http://www.optsicom.es/mdp/.

better than OBMA 0 for this data set, but the differences are not very significant at a significance level of 0.05. Table V presents the results of OBMA 0 and OBMA for the 20 instances of the MDG-c instances. All best-known results (f prev ) were achieved by iterative tabu search (ITS) [START_REF] Palubeckis | Iterated tabu search for the maximum diversity problem[END_REF] or variable neighborhood search (VNS) [START_REF] Brimberg | Variable neighborhood search for the heaviest k-subgraph[END_REF] under a time limit of 2 hours on an Intel Core 2 Quad CPU 8300 with 6GB of RAM running Ubuntu 9.04 [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF]. We observe that both OBMA and OBMA 0 obtain improved best-known solutions for 8 instances and match the best-known solutions for 4 instances. In fact, OBMA improves all best-known solutions obtained by VNS, but it fails to attain 8 best-known solutions found by ITS. Compared to OBMA 0 , OBMA obtains 2 improved best solutions for MDG-c 17 and MDG-c 19. 20 0.05 = 15) at a significance level of 0.05. Table VI reports the results of OBMA 0 and OBMA for the 10 instances of the b2500 data set. From this table, we observe that both algorithms reach the best-known values for all the instances. Meanwhile, the average value of best objective values of OBMA is better than that of OBMA 0 , and the difference of this measure between these two algorithms is weakly significant (8.5 < CV 10 0.05 = 9). Even though there is no significant difference on the success rate, OBMA obtains a higher success rate for 8.5 instances, while the reverse is true only for 1.5 instances. In addition, OBMA achieves these results more steadily than OBMA 0 , wining 8.5 out of 10 instances in terms of the standard deviation.

Table VII displays the results of OBMA 0 and OBMA for the 10 largest instances (p3000 and p5000 instances). For these very large instances, OBMA matches all the best-known objective values without exception while OBMA 0 fails to do so for 4 instances. In addition, OBMA performs significantly better than OBMA 0 , and wins 10, 9.5 instances in terms of the average best objective value and success rate, respectively. The performance of OBMA is also more stable than OBMA 0 by wining 8 out of 10 instances in term of the standard deviation.

Finally, Table VIII provides a summary of the comparative results for the five data sets between OBMA (OBL enhanced memetic algorithm) and OBMA 0 (memetic algorithm without OBL). As we observe from the table, OBMA achieves a better performance than OBMA 0 , i.e., achieving improved solutions for 6 instances and matching the best solutions on the remain-ing 75 instances. In addition, OBMA also achieves a better performance in terms of the average best value, the success rate and the standard deviation, wining OBMA 0 on most benchmark instances. Therefore, we conclude that oppositionbased learning can beneficially enhance the popular memetic search framework to achieve an improved performance. The fprev values were compiled from the results reported by ITS [START_REF] Palubeckis | Iterated tabu search for the maximum diversity problem[END_REF], LTS-EDA [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF] and MAMDP [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. The best-known values fprev were extracted from [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF].

of the memetic algorithm (MAMDP) [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] is available. For our comparative study, we report the results of the MAMDP algorithm by running its code on our platform with its default parameter values reported in [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. For the other reference algorithms, we use their results presented in the corresponding references. The detailed comparative results in terms of ∆f best and ∆f avg are reported in Tables IX andX. Table IX presents the comparative results on the 40 instances of the data sets MDG-a, b2500, p3000-p5000 for which the detailed results of reference algorithms are available. At the last row of the table, we also indicate the number of wining instances relative to our OBMA algorithm both in terms of the best objective value and average objective value (recall that a tied result counts 0.5 for each algorithm). From this table, we observe that OBMA dominates all the reference algorithms. Importantly, OBMA is the only algorithm which obtains the best-known values and the largest average objective values for all 40 instances.

Table X displays the comparative results on the data sets MDG-b and MDG-c. The best-known objective values f prev for the MDG-b instances are obtained by G SS [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF] while the f prev values of the MDG-c instances are obtained by ITS and VNS [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF], both with a time limit of 2 hours. No result is available for the TIG and LTS-EDA algorithms for these data sets. The results of our OBMA algorithm (and MAMDP) are obtained with a time limit of 10 minutes. Table X indicates that both OBMA and MAMDP improve the best-known results for the majority of the 40 instances. Moreover, compared to MAMDP, our OBMA algorithm obtains an improved best objective value for 1 MDG-b instance and 3 MDG-c instances, while matching the best objective values for the remaining instances. Finally, OBMA dominates MAMDP in terms of the average objective value, wining 18 out of the 20 MDG-b instances and all 20 MDG-c instances.

To summarize, compared to the state-of-the-art results, our OBMA algorithm finds improved best-known solutions (new lower bounds) for 22 out of the 80 benchmark instances, matches the best-known solutions for 50 instances, but fails to attain the best-known results for 8 instances. Such a performance indicates that the proposed algorithm competes favorably with state-of-the-art MDP algorithms and enriches the existing solution arsenal for solving MDP.

V. EXPERIMENTAL ANALYSIS

In this section, we perform additional experiments to gain some understanding of the proposed algorithm including the ITS [START_REF] Palubeckis | Iterated tabu search for the maximum diversity problem[END_REF] VNS [START_REF] Brimberg | Variable neighborhood search for the heaviest k-subgraph[END_REF] TIG [START_REF] Lozano | Iterated greedy for the maximum diversity problem[END_REF] LTS-EDA [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF] MAMDP [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] The fprev values were compiled from the results reported by the reference methods [START_REF] Palubeckis | Iterated tabu search for the maximum diversity problem[END_REF], [START_REF] Brimberg | Variable neighborhood search for the heaviest k-subgraph[END_REF], [START_REF] Lozano | Iterated greedy for the maximum diversity problem[END_REF], [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. The results of MAMDP are those we obtained by running its program on our computer, which are slightly different from the results reported in [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] due to the stochastic nature of the algorithm.

parametric constrained neighborhood, the rank-based qualityand-distance pool management and the benefit of OBL for population diversity.

A. Study of the Parametric Constrained Neighborhood

Our tabu search procedure relies on the parametric constrained neighborhood whose size is controlled by the parameter ρ. To highlight the effect of this parameter and determine a proper value, we ran the tabu search procedure to solve the first 10 instances of MDG-a (i.e., MDG-a 21 ∼ MDG-a 30) with ρ ∈ [START_REF] Al-Qunaieer | Opposition based computing -A survey[END_REF][START_REF] Chen | Memetic search for the generalized quadratic multiple knapsack problem[END_REF]. Each instance was independently solved until the number of iterations reached M axIter. Figure 1 shows the average objective values achieved (left) and the average CPU times consumed (right) by tabu search on these 10 instances.

As we see from Figure 1 (left), the average objective value has a drastic rise when we increase ρ from 1 to 3. Then, it slowly increases if we continue to increase ρ to 10. On Figure 1 (right), the average CPU time of tabu search needed to finish M axIter iterations continuously increases when ρ increases from 1 to 10. As ρ increases, the size of the constrained neighborhood also increases, thus the algorithm needs more time to examine the candidate solutions. To make a compromise between neighborhood size and solution quality, we set the scale coefficient ρ to 4 in our experiments.

B. Effectiveness of the Pool Updating Strategy

To validate the effectiveness of the rank-based quality-anddistance (RBQD) pool updating strategy, we compare it with the general quality-and-distance (GQD) pool updating strategy The fprev values for the MDG-b instances are reported by G SS [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF], while the fprev values for the MDG-c instances are from [START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF] with a time limit of 2 hours, all available at http://www.optsicom.es/mdp/. The results of MAMDP were obtained by running the program on our computer (results of MAMDP for these instances are not reported in [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]). used in [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. GQD evaluates each individual by a weighted sum of the quality and the distance to the population. In this experiment, we compared the performance of the OBMA algorithm under these two pool updating strategies (the two OBMA variants are called OBMA RBQD and OBMA GQD ). The experiment was performed on the largest data set, i.e., p3000 and p5000. We performed 20 runs of each algorithm to solve each instance, and recorded the best objective value (f best ), the difference between the average objective value and the best objective value (∆f avg ), the standard deviation of objective value over each run (σ), the average time of one run (t avg ), the average time over the runs which attained f best (t best ), and the success rate (#succ).

Table XI shows the comparison of the results obtained by OBMA under the rank-based quality-and-distance strategy (OBMA RBQD ) and the general quality-and-distance strategy (OBMA GQD ). From the table, we observe that OBMA RBQD achieves the same best objective values for all tested instances compared with OBMA GQD . However, for the five metrics, OBMA RBQD performs better than OBMA GQD for much more instances, and respectively winning 8, 8, 6, 6 and 8 out of 10 tested instances. These results confirm the effectiveness of our proposed rank-based quality-and-distance pool updating strategy.

C. Opposition-based Learning over Population Diversity

In this section, we further verify the benefit brought by OBL in maintaining the population diversity of the OBMA algorithm. To assess the diversity of a population, a suitable metric is necessary. In this experiment, we resort to minimum distance and average distance of individuals in the population to measure the population diversity. The minimum distance is defined as the minimum distance between any two individuals in the population, i.e., M D = min i =j∈{1,2,...,p} D(S i , S j ). Correspondingly, the AD is the average distance between all individuals in the population, as defined by Equation [START_REF] Chen | Memetic search for the generalized quadratic multiple knapsack problem[END_REF].

Using the data sets MDG-a and b2500, we compared the diversity of the population with or without OBL. The population initialization (P I 0 ) procedure without OBL first generates two random solutions, which are then respectively improved by the tabu search procedure. The best of two improved solutions is inserted into the population if it does not duplicate any existing individual in the population. We repeat this process until p different solutions are generated. In contrast, the population initialization with OBL (P I OBL ) is the procedure described in Section III-C, which considers both a random solution and its corresponding opposite solution. We solved each instance 20 times and recorded the minimum distance and average distance of each population initialization procedure on each instance. The comparative results of the population constructed with or without OBL are shown in Figure 2, where the X-axis shows instances in each benchmark and Y-axis indicates the average distance and minimum distance. From Figure 2, we observe that the population built by P I OBL has a relatively larger average distance and minimum distance. This is particularly true for all instances of the MDG-a data set except for MDG-a 31. Also, the population produced by P I OBL has a larger minimum distance than that of P I 0 for 18 out of 20 instances of the MDG-a data set. Equal or better results are found for the b2500 data set, since the population generated by P I OBL dominates the population produced by P I 0 in terms of the average and minimum distances. This experiment shows that OBL helps the OBMA algorithm to start its search with a population of high diversity, which is maintained by the rank-based quality-and-distance strategy during the search.

VI. CONCLUSIONS AND FUTURE WORK

We have proposed an opposition-based memetic algorithm (OBMA) which uses opposition-based learning to improve a memetic algorithm for solving MDP. The OBMA algorithm employs OBL to reinforce population diversity and improve evolutionary search. OBMA distinguishes itself from existing memetic algorithms by three aspects: a double trajectory search procedure which simultaneously both a candidate solution and a corresponding opposite solution, a parametric constrained neighborhood for effective local optimization, and a rank-based quality-and-distance pool updating strategy.

Extensive comparative experiments on 80 large benchmark instances (with 2000 to 5000 items) from the literature have demonstrated the competitiveness of the OBMA algorithm. OBMA matches the best-known results for most of instances and in particular finds improved best results (new lower bounds) for 22 instances which are useful for the assessment of other MDP algorithms. Our experimental analysis has also confirmed that integrating OBL into the memetic search framework does improve the search efficiency of the classical memetic search.

As future work, several potential research lines can be followed. First, to further improve OBMA, it is worth studying alternative strategies for tuning tabu tenure, generating initial solutions, and managing population diversity. Second, it would be interesting to study the behavior of the OBMA algorithm on much larger instances (e.g., with tens of thousands items) and investigate whether techniques developed for large scale continuous optimization ( [START_REF] Omidvar | Cooperative co-evolution with differential grouping for large scale optimization[END_REF], [START_REF] Ran | A competitive swarm optimizer for large scale optimization[END_REF]) could be helpful in this setting. Third, OBL being a general technique, it is worth studying its usefulness within other heuristic algorithms. Finally, it would be interesting to investigate the oppositionbased optimization approach for solving additional combinatorial problems including those with other diversity and dispersion criteria.

Algorithm 3 7 :else 14 :

 3714 Opposition-based population initialization 1: Input: population size p 2: Output: an initial population P = {S 1 , S 2 , . . . , S p } 3: count = 0 4: while count < p do 5: / * Generate a random solution S r and its opposite solution S r * / 6: S r ← TabuSearch (S r ) S r ← TabuSearch (S r ) 8: / * Identify the better solution between S r and S r * / 9: S ′ ← arg max{f (S r ), f (S r )} 10: / * Insert S ′ into the population P or modify it * / 11: if S ′ is different from any solutions in the P then 12: Add S ′ into the population P directly 13:Modify S ′ and add it into the population P

1 )Algorithm 4 2 :

 142 Parametric constrained neighborhood: In general, local search for MDP starts from an initial solution S and subsequently swaps an element of S and an element of N \ S Parametric constrained neighborhood tabu search 1: Input: a starting solution S, the maximum allowed iterations M axIter Output: the best solution S * found 3: S * ← S 4: iter ← 0 5: Initialize the tabu list 6: Calculate the gain(ei) for each element ei ∈ N according to Eq. (4) 7: while iter < M axIter do 8: minGain ← min{gain(ei) : ei ∈ S} 9:

  e., S o = S u ∩ S v . If |S o | < m, then the second phase successively extends S o with m -|S o | other elements in a greedy way. Specifically, we alternatively consider each parent and select an unassigned element with maximum gain with respect to S o until S o reaches the size of m. Once the offspring solution S o is obtained, we generate its corresponding opposite solution S o according to Definition 1. Consequently, we obtain two different and distant offspring solutions S o and S o which are further improved by the tabu search procedure of Section III-D.

Fig. 1 .

 1 Fig. 1. Average objective values and average CPU times spent on 10 MDGa instances obtained by executing TS with different values of the scale coefficient ρ.

Fig. 2 .

 2 Fig. 2. Comparative results of the populations built by population initialization with OBL (P I OBL ) or without OBL (P I 0 ).

TABLE I 80

 I LARGE BENCHMARK INSTANCES USED IN THE EXPERIMENTS.

	Data set	n	m	#instance	time limit (s) #run
	MDG-a	2000	200	20	20	30
	MDG-b	2000	200	20	600	15
	MDG-c	2000 300-600	20	600	15
	b2500	2500	1000	10	300	30
	p3000	3000	1500	5	600	15
	p5000	5000	2500	5	1800	15

TABLE II THE

 II PARAMETER SETTING OF THE OBMA ALGORITHM.

	Parameters	Description	Value	Section
	p	population size	10	III-C
	M axIter	allowable number of iterations of TS	50,000	III-D
	α	tabu tenure management factor	15	III-D
	ρ	scale coefficient	4	III-D
	β	weighting coefficient	0.6	III-F

TABLE III COMPARISON

 III OF THE RESULTS OBTAINED BY OBMA 0 AND OBMA ON THE DATA SET MDG-A.

				OBMA 0				OBMA
	Instance	fprev	∆f best	∆favg	σ	t best	#succ	∆f best	∆favg	σ	t best	#succ
	MDG-a 21 114271	0	4.5	10.6	9.3 22/30	0	5.2 10.8	7.4 20/30
	MDG-a 22 114327	0	4.2	22.6	9.2 29/30	0	0.1	0.5	7.2 29/30
	MDG-a 23 114195	0	10.9 15.2	11.5 15/30	0	15.2 15.1	7.0 11/30
	MDG-a 24 114093	0	25.3 21.0	11.3	4/30	0	11.2 12.1	8.2	7/30
	MDG-a 25 114196	0	55.9 32.7	13.3	1/30	0	41.5 30.7	8.8	5/30
	MDG-a 26 114265	0	7.3	10.2	9.9 17/30	0	10.2 11.5	11.6 14/30
	MDG-a 27 114361	0	0.0	0.0	4.8 30/30	0	0.2	0.9	4.1 29/30
	MDG-a 28 114327	0	57.1 53.8	15.2 12/30	0	18.9 39.2	7.9 23/30
	MDG-a 29 114199	0	11.2 16.0	14.6	8/30	0	4.4	8.4	9.0 14/30
	MDG-a 30 114229	0	12.8 16.3	10.5 14/30	0	8.1 10.5	7.2 14/30
	MDG-a 31 114214	0	30.4 22.7	16.2	5/30	0	16.7 13.6	11.9	9/30
	MDG-a 32 114214	0	28.5 19.9	10.4	4/30	0	23.7 17.1	6.0	3/30
	MDG-a 33 114233	0	6.1	10.5	12.8 15/30	0	2.0	5.6	8.8 23/30
	MDG-a 34 114216	0	25.4 43.8	11.6 15/30	0	2.4	7.0	6.6 26/30
	MDG-a 35 114240	0	1.6	2.2	12.2	9/30	0	1.6	2.4	10.7 11/30
	MDG-a 36 114335	0	7.5	11.7	12.4 19/30	0	5.7	9.5	10.5 21/30
	MDG-a 37 114255	0	4.2	8.2	12.2 18/30	0	5.2	8.6	7.8 18/30
	MDG-a 38 114408	0	1.2	3.1	10.6 19/30	0	0.5	1.1	7.6 25/30
	MDG-a 39 114201	0	2.2	6.0	9.7 26/30	0	2.0	6.0	4.9 27/30
	MDG-a 40 114349	0	28.1 37.7	9.9 18/30	0	23.0 31.5	9.1 19/30
		wins	10	5.5	5.5	1	6.5	10	14.5 14.5	19	13.5

TABLE IV COMPARISON

 IV OF THE RESULTS OBTAINED BY OBMA 0 AND OBMA ON THE DATA SET MDG-B.

				OBMA 0				OBMA
	Instance	fprev	∆f best	∆favg	σ	t best	#succ	∆f best	∆favg	σ	t best	#succ
	MDG-b 21 11299895	0	0.2	0.0 378.6 15/15	0	0.2	0.0 325.1 15/15
	MDG-b 22 11286776	-5622	-5622.2	0.0 336.5 15/15	-5622	-5622.2	0.0 380.8 15/15
	MDG-b 23 11299941	0	0.5	0.0 300.5 15/15	0	0.5	0.0 283.4 15/15
	MDG-b 24 11290874	-245	-229.1	61.2 345.5 14/15	-245	-220.5	67.2 323.4 13/15
	MDG-b 25 11296067	-1960	-1959.9	0.0 271.2 15/15	-1960	-1959.9	0.0 313.9 15/15
	MDG-b 26 11292296	-6134	-5216.0 1836.9 276.8 12/15	-6134	-6134.4	0.0 336.0 15/15
	MDG-b 27 11305677	0	0.2	0.0 330.0 15/15	0	0.2	0.0 256.0 15/15
	MDG-b 28 11279916	-2995	-2994.6	0.5 329.5 10/15	-2995	-2994.7	0.4 351.1 12/15
	MDG-b 29 11297188	-151	-151.5	0.0 323.0 15/15	-151	-151.5	0.0 288.3 15/15
	MDG-b 30 11296415	-1650	-1649.6	0.0 311.2 15/15	-1650	-1649.6	0.0 274.9 15/15
	MDG-b 31 11288901	0	-0.2	0.0 313.9 15/15	0	-0.2	0.0 308.0 15/15
	MDG-b 32 11279820	-3719	-3669.3	25.0 177.5	3/15	-3719	-3694.3	30.6 283.0	9/15
	MDG-b 33 11296298	-1740	-1381.7	216.1 112.2	4/15	-1740	-1675.0 166.1 277.5 13/15
	MDG-b 34 11281245	-9238	-8881.8	435.8 325.7	9/15	-9238	-9237.6	0.0 355.4 15/15
	MDG-b 35 11307424	0	-0.1	0.0 343.6 15/15	0	-0.1	0.0 331.0 15/15
	MDG-b 36 11289469	-13423 -13174.5	929.8 251.7 14/15	-13423 -13423.0	0.0 329.4 15/15
	MDG-b 37 11290545	-5229	-5099.5	329.7 217.5 13/15	-5229	-5228.8	0.0 291.2 15/15
	MDG-b 38 11288571	-7965	-7964.5	0.0 242.5 15/15	-7965	-7964.5	0.0 297.6 15/15
	MDG-b 39 11295054	0	-0.2	0.0 374.5 15/15	0	-0.2	0.0 289.7 15/15
	MDG-b 40 11307105	-2058	-2057.6	0.0 301.1 15/15	-2058	-2057.6	0.0 266.5 15/15
		wins	10	6.5	8	10	7	10	13.5	12	10	13

TABLE V COMPARISON

 V OF THE RESULTS OBTAINED BY OBMA 0 AND OBMA ON THE DATA SET MDG-C. Results are obtained by VNS with 2 hours CPU time[START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF].

				OBMA 0					OBMA
	Instance	fprev	∆f best	∆favg	σ	t best	#succ	∆f best	∆favg	σ	t best	#succ
	MDG-c 1	24924685 ⋆	-1659	-493.5	852.7 165.5	5/15	-1659	-1262.4	749.0 251.3 11/15
	MDG-c 2 MDG-c 3	24909199 ⋆ 24900820 *	-3347 -4398	140.3 2514.6 -299.2 4040.7	94.6 22.5	4/15 7/15	-3347 -4398	-3346.3 -2805.2 2717.9 239.4 11/15 2.5 286.6 14/15
	MDG-c 4 MDG-c 5 MDG-c 6	24904964 ⋆ 24899703 * 43465087 *	-4746 3999 20139	-1890.5 1999.4 106.5 4767.8 1025.0 8.7 22534.4 2512.3 77.4	4/15 9/15 6/15	-4746 3999 20139	-3917.2 1657.6 276.2 12/15 4047.3 180.6 212.5 14/15 21054.5 1190.4 290.8 6/15
	MDG-c 7	43477267 ⋆	0	277.5 1038.2	6.1 14/15	0	126.9	314.7 111.7 12/15
	MDG-c 8	43458007 ⋆	-7565	-4644.3 1833.2	58.9	3/15	-7565	-7546.7	68.6 163.6 14/15
	MDG-c 9 MDG-c 10 43476251 * 43448137 ⋆	0 10690	142.2 10690.0	116.1 0.0	82.1 27.1 15/15 6/15	0 10690	0.0 10690.0	0.0 0.0	72.5 15/15 115.1 15/15
	MDG-c 11 67009114 ⋆ -12018 MDG-c 12 67021888 * 7718	-11345.3 2110.0 12209.1 5502.4	90.8 13/15 9.3 7/15	-12018 -11776.3 7718 10179.7 3250.5 302.8 522.3 335.0 10/15 9/15
	MDG-c 13 67024373 ⋆	0	2082.0 2944.8 106.4 10/15	0	839.4 2140.1 380.1 13/15
	MDG-c 14 67024804 ⋆	-5386	-4667.9 1830.9		13/15	-5386	-5118.7 1000.3 276.3 14/15
	MDG-c 15 67056334 ⋆	0	1846.5 1353.5	31.0	5/15	0	1021.2 1122.0 269.0	5/15
	MDG-c 16 95637733 ⋆ MDG-c 17 95645826 * MDG-c 18 95629207 * MDG-c 19 95633549 * MDG-c 20 95643586 *	-1196 75241 97066 100609.9 3526.8 5861.5 8193.7 318.8 86848.9 8727.7 291.8 90.5 35131 39027.5 5420.3 236.5 59104 59133.2 109.3 111.0 14/15 2/15 2/15 7/15 7/15	-1196 74713 97066 34385 59104	-1116.3 74981.7 99767.0 2972.8 292.1 298.3 270.8 14/15 373.3 312.8 8/15 8/15 35121.3 816.2 343.7 4/15 59133.2 109.3 299.9 14/15
		wins	9	1	1	18	5	11	19	19	2	15
	Moreover, OBMA performs significantly better than OBMA 0 in terms of the average best solution (19 > CV 20 0.05 = 15), success rate (15 >= CV 20 0.05 = 15) and standard deviation
	(19 > CV

*

Results are obtained by ITS with 2 hours CPU time

[START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF]

. ⋆

TABLE VI COMPARISON

 VI OF THE RESULTS OBTAINED BY OBMA 0 AND OBMA ON THE DATA SET B2500.

				OBMA 0					OBMA
	Instance	fprev	∆f best	∆favg	σ	t best	#succ	∆f best	∆favg	σ	t best	#succ
	b2500-1	1153068	0	193.1 429.2 154.1 23/30	0	0.0	0.0	100.3 30/30
	b2500-2	1129310	0	106.0 163.1 149.2 21/30	0	37.9	73.2 147.4 22/30
	b2500-3	1115538	0	303.2 347.2 105.5 17/30	0	0.4	2.2	95.3	29/30
	b2500-4	1147840	0	549.7 461.9 191.2	8/30	0	65.8 118.5	98.9	20/30
	b2500-5	1144756	0	50.9 129.3 117.6 24/30	0	5.3	28.4	86.3	29/30
	b2500-6	1133572	0	88.9 210.9	89.4 22/30	0	0.0	0.0	66.8	30/30
	b2500-7	1149064	0	106.2 111.9 114.8 13/30	0	14.1	31.0 128.3 23/30
	b2500-8	1142762	0	113.7 349.0	98.4 22/30	0	1.5	5.5	105.4 28/30
	b2500-9	1138866	0	0.2	1.1	135.7 29/30	0	1.3	2.9	139.8 25/30
	b2500-10 1153936	0	0.0	0.0	81.4 30/30	0	0.0	0.0	107.5 30/30
		wins	5	1.5	1.5	4	1.5	5	8.5	8.5	6	8.5

TABLE VII COMPARISON

 VII OF THE RESULTS OBTAINED BY OBMA 0 AND OBMA ON THE DATA SETS P3000 AND P5000.

					OBMA 0					OBMA
	Instance	fprev	∆f best	∆favg	σ	t best	#succ	∆f best	∆favg	σ	t best	#succ
	p3000 1	6502330	0	84.1	28.0	172.6	1/15	0	24.4	35.8	275.6	9/15
	p3000 2	18272568	0	152.8	151.1	151.5	7/15	0	0.0	0.0	89.3 15/15
	p3000 3	29867138	0	544.5	344.2	244.0	4/15	0	0.0	0.0	26.2 15/15
	p3000 4	46915044	0	715.0	531.0	250.1	2/15	0	1.2	19.3	336.9 14/15
	p3000 5	58095467	0	209.9	198.2	180.0	6/15	0	0.0	0.0	65.4 15/15
	p5000 1	17509369	0	168.9	176.5	518.7	7/15	0	128.2 181.8 1053.9 13/15
	p5000 2	50103092	70	819.1	494.3	242.5	1/15	0	22.8	8.0	370.8	1/15
	p5000 3	82040316	176	3450.3 1671.3	333.1	1/15	0	209.3 141.3	217.1	2/15
	p5000 4 129413710	598	1460.1	661.6 1019.1	1/15	0	97.8 122.1	625.7	7/15
	p5000 5 160598156	344	669.6	323.6 1348.7	1/15	0	102.9	52.3	843.2	5/15
		wins	3	0	2	4	0.5	7	10	8	6	9.5

TABLE IX COMPARISON

 IX OF OBMA WITH OTHER ALGORITHMS ON THE DATA SETS MDG-A, B2500, P3000 AND P5000.

TABLE X COMPARISON

 X OF OBMA WITH MAMDP[START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] ON THE DATA SETS MDG-B AND MDG-C, THE BEST-KNOWN RESULTS ARE OBTAINED BY G SS[START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF], ITS AND VNS[START_REF] Martí | Heuristics and metaheuristics for the maximum diversity problem[END_REF].

			MAMDP [53]	OBMA			MAMDP [53]	OBMA
	Instance	fprev	∆f best	∆favg	∆f best	∆favg	Instance	fprev	∆f best	∆favg	∆f best	∆favg
	MDG-b 21 11299895	0	225.8	0	0.2	MDG-c 1	24924685	-1659	3481.7	-1659	-1262.4
	MDG-b 22 11286776	-5622	-3472.1	-5622	-5622.2	MDG-c 2	24909199	0	4938.7	-3347	-3346.3
	MDG-b 23 11299941	0	0.5	0	0.5	MDG-c 3	24900820	-4398	5206.1	-4398	-2805.2
	MDG-b 24 11290874	-245	226.0	-245	-220.5	MDG-c 4	24904964	-4746	-411.2	-4746	-3917.2
	MDG-b 25 11296067	-1960	-1888.9	-1960	-1959.9	MDG-c 5	24899703	3999	7500.3	3999	4047.3
	MDG-b 26 11292296	-6134	-2530.6	-6134	-6134.4	MDG-c 6	43465087	20139	25023.7	20139	21054.5
	MDG-b 27 11305677	0	0.2	0	0.2	MDG-c 7	43477267	0	1020.8	0	126.9
	MDG-b 28 11279916	-2994	-2634.6	-2995	-2994.7	MDG-c 8	43458007	-4568	-1329.9	-7565	-7546.7
	MDG-b 29 11297188	-151	451.8	-151	-151.5	MDG-c 9	43448137	237	1207.3	0	0.0
	MDG-b 30 11296415	-1650	-1649.6	-1650	-1649.6	MDG-c 10 43476251	10690	11060.9	10690	10690.0
	MDG-b 31 11288901	0	375.7	0	-0.2	MDG-c 11 67009114	-12018	-6942.7	-12018 -11776.3
	MDG-b 32 11279820	-3719	-3632.3	-3719	-3694.3	MDG-c 12 67021888	7718	17470.0	7718	10179.7
	MDG-b 33 11296298	-1740	-878.7	-1740	-1675.0	MDG-c 13 67024373	0	6673.1	0	839.4
	MDG-b 34 11281245	-9238	-8191.3	-9238	-9237.6	MDG-c 14 67024804	-5386	-1050.9	-5386	-5118.7
	MDG-b 35 11307424	0	-0.1	0	-0.1	MDG-c 15 67056334	0	3716.2	0	1021.2
	MDG-b 36 11289469	-13423 -10792.5	-13423 -13423.0	MDG-c 16 95637733	-1196	1495.2	-1196	-1116.3
	MDG-b 37 11290545	-5229	-4372.1	-5229	-5228.8	MDG-c 17 95645826	74713	79061.1	74713	74981.7
	MDG-b 38 11288571	-7965	-5896.0	-7965	-7964.5	MDG-c 18 95629207	97066 106806.6	97066	99767.0
	MDG-b 39 11295054	0	472.4	0	-0.2	MDG-c 19 95633549	34385	36189.1	34385	35121.3
	MDG-b 40 11307105	-2058	-517.5	-2058	-2057.6	MDG-c 20 95643586	59104	61961.2	59104	59133.2
	wins		9.5	2	10.5	18	wins		8.5	0	11.5	20

TABLE XI COMPARISON

 XI OF THE RESULTS OBTAINED BY OBMA UNDER THE RANK-BASED QUALITY-AND-DISTANCE POOL UPDATING STRATEGY (OBMA RBQD ) AND THE GENERAL QUALITY-AND-DISTANCE (GQD) POOL UPDATING STRATEGY (OBMA GQD ).

				OBMA RBQD					OBMA GQD
	Instance	f best	∆favg	σ	tavg	t best	#succ	f best	∆favg	σ	tavg	t best	#succ
	p3000 1	6502330	-23.0	35.3 176.9 118.8 14/20	6502330	-27.3	37.4 158.3	81.4 13/20
	p3000 2	18272568	0.0	0.0	75.8	75.8 20/20	18272568	-10.5	45.8	54.7	57.1 19/20
	p3000 3	29867138	0.0	0.0	37.7	37.7 20/20	29867138	0.0	0.0	55.4	55.4 20/20
	p3000 4	46915044	0.0	0.0 113.7 113.7 20/20	46915044	-0.9	3.9	147.5	146.4 19/20
	p3000 5	58095467	0.0	0.0	22.9	22.9 20/20	58095467	0.0	0.0	92.8	92.8 20/20
	p5000 1	17509369	-13.8	60.4 621.9 624.3 19/20	17509369	-27.8	83.1 674.3	646.1 17/20
	p5000 2	50103071	-23.4	4.8 561.1 594.3 16/20	50103071	-26.4	6.0	584.3	464.0 11/20
	p5000 3	82040316	-305.8 304.2 791.1 527.5 01/20	82040316	-241.0 176.8 642.2	718.4 01/20
	p5000 4 129413710	-116.4 143.9 756.5 802.8 12/20	129413710	-174.3 176.2 662.5	705.2 09/20
	p5000 5 160598156	-161.8	99.4 511.7 471.6 02/20	160598156	-182.6 112.7 745.5 1081.3 02/20
	wins	5	8	8	6	6	8	5	2	2	4	4	2

ACKNOWLEDGMENT

We are grateful to the anonymous referees for their insightful comments and suggestions which helped us to significantly improve the paper. We would like to thank Dr. Qinghua Wu for kindly sharing the source code of the MAMDP algorithm described in [53]. Support for Yangming Zhou from the China Scholarship Council (2014-2018) is also acknowledged.

D. Comparison with State-of-the-Art Algorithms

We turn now our attention to a comparison of our OBMA algorithm with state-of-the-art algorithms, including iterated tabu search (ITS) [START_REF] Palubeckis | Iterated tabu search for the maximum diversity problem[END_REF], scatter search (G [START_REF] Gallego | Hybrid heuristics for the maximum diversity problem[END_REF], variable neighborhood search (VNS) [START_REF] Brimberg | Variable neighborhood search for the heaviest k-subgraph[END_REF], fine-tuning iterated greedy algorithm (TIG) [START_REF] Lozano | Iterated greedy for the maximum diversity problem[END_REF], tabu search with estimation of distribution algorithm (LTS-EDA) [START_REF] Wang | Learnable tabu search guided by estimation of distribution for maximum diversity problems[END_REF] and memetic algorithm (MAMDP) [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF]. We omit the tabu search/memetic algorithm (TS/MA) [START_REF] Wang | A tabu search based memetic algorithm for the maximum diversity problem[END_REF] and the memetic self-adaptive evolution strategies (MSES) [START_REF] De Freitas | Memetic self-adaptive evolution strategies applied to the maximum diversity problem[END_REF] since TS/MA performs quite similar to MAMDP of [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF] while MSES does not report detailed results. Among these reference algorithm, only the program


Long Li

Étienne Mémin

Bruno Deremble

Oceanic fluid dynamics under location uncertainty Part.I : Towards a stochastic modeling for the Quasi-Geostrophic system

Lagrangian displacement : dX(x, t) = w(X(x, t), t)dt + σ(X(x, t), t)dBt, ∀(x, t)

∈ D × R + , D ⊂ R 3 X(x, 0) = x, ∀x ∈ D Eulerian velocity : U (x, t) = w(x, t) large-scale + σ(x, t) Ḃt small-scale , ∀ (x, t) ∈ D × R + Multiplicative noise (Bt) t∈R + is a cylindrical Wiener process in L 2 (D, R 3 ) Spatial correlation : σ(x, t)dBt = D σ(x, y, t)dBt(y)dy, ∀ (x, t) ∈ D × R + L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018 3 / 20

Lagrangian displacement :

dX(x, t) = w(X(x, t), t)dt + σ(X(x, t), t)dBt, ∀(x, t) Volumetric rate of change of a scalar for 0 = ∇ ⋅ σdBt = ∇ ⋅ σ :

∈ D × R + , D ⊂ R 3 X(x, 0) = x,
d V(t) q(x, t)dx = V(t) dtq + ∇ ⋅ (qw) - 1 2 d i,j=1 ∂ 2 ∂xi∂xj (qaij) dt + ∇q ⋅ σdBt dx
Volumetric rate of change of a scalar for 0 = ∇ ⋅ σdBt = ∇ ⋅ σ : Momentum equation :

d V(t) q(x, t)dx = V(t) dtq + ∇ ⋅ (qw) - 1 2 d i,j=1
dtw + w * dt + σdBt ⋅ ∇w - 1 ρ ∇ ⋅ 1 2 ρa∇w dt + f × wdt + σdBt = - 1 ρ ∇ pdt + dp ′ t -ρkdt + ν∇ 2 wdt + σdBt ,
where ν = µ ρ is the kinematic viscosity and dp ′ t is a centered random process.

L.Li (FLUMINANCE) Towards a stochastic QG modeling 12/06/2018 5 / 20

Momentum equation :

dtw + w * dt + σdBt ⋅ ∇w - 1 ρ ∇ ⋅ 1 2 ρa∇w dt + f × wdt + σdBt = - 1 ρ ∇ pdt + dp ′ t -ρkdt + ν∇ 2 wdt + σdBt ,
where ν = µ ρ is the kinematic viscosity and dp ′ t is a centered random process. Mass equation :

dtρ + w * dt + σdBt ⋅ ∇ρ -∇ ⋅ 1 2 a∇ρ dt = -ρ∇ ⋅ w * dt ∇ ⋅ σdBt = 0 L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018 5 / 20

Momentum equation :

dtw + w * dt + σdBt ⋅ ∇w - 1 ρ ∇ ⋅ 1 2 ρa∇w dt + f × wdt + σdBt = - 1 ρ ∇ pdt + dp ′ t -ρkdt + ν∇ 2 wdt + σdBt ,
where ν = µ ρ is the kinematic viscosity and dp ′ t is a centered random process. Mass equation :

dtρ + w * dt + σdBt ⋅ ∇ρ -∇ ⋅ 1 2 a∇ρ dt = -ρ∇ ⋅ w * dt ∇ ⋅ σdBt = 0
Continuity equation (a sufficient constraint) : A small Rossby number :

0 = ∇ ⋅ w = ∇ ⋅ (∇ ⋅ a) = ∇ ⋅ σ L.Li (FLUMINANCE)
dtw + w * dt + σdBt ⋅ ∇w -∇ ⋅ 1 2 a∇w dt + f k × udt + (σdBt)H = -∇ pdt + dp ′ t + bkdt + ν∇ 2 wdt + σdBt , b = -g δρ ρb Boussinesq thermodynamic equation : ▷ Applies SRRT with ∇ ⋅ σdBt = 0 for b(x, t) = b0(z) + b ′ (x, t) : dtb ′ + w * dt + σdBt ⋅ ∇b ′ + N 2 w * dt + (σdBt)z = ∇ ⋅ 1 2 a∇b ′ dt + ∇ ⋅ 1 2 a⋅zN 2 dt L.Li (
Ro ≪ 1 A small variation of f : βL ≪ f0
The scale of motion is not significantly larger than the deformation scale : 2. Uncertainties scalings :

Ro Bu = O(Ro) ⇒ ∂b ′ ∂z ≪ N 2 L.Li (
The vertical uncertainty is small compared with the horizontal uncertainties :

(σdBt)z (σdBt)H ∼ Ro Bu D, D = h L ≪ 1 L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018 8 / 20

2. Uncertainties scalings :

The vertical uncertainty is small compared with the horizontal uncertainties :

(σdBt)z (σdBt)H ∼ Ro Bu D, D = h L ≪ 1
A moderate uncertainty such that the energy dissipated by the horizontal small-scale flow is the same order than the large-scale kinetic energy :

aH ∼ U L ⇐ M KE ∼ U 2 , T KE ∼ AH Tσ L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018 8 / 20

2. Uncertainties scalings :

The vertical uncertainty is small compared with the horizontal uncertainties :

(σdBt)z (σdBt)H ∼ Ro Bu D, D = h L ≪ 1
A moderate uncertainty such that the energy dissipated by the horizontal small-scale flow is the same order than the large-scale kinetic energy :

aH ∼ U L ⇐ M KE ∼ U 2 , T KE ∼ AH Tσ Results : (σdBt)z ∂ ∂z = O Ro Bu aHz aH ∼ Ro Bu D, azz aH ∼ Ro Bu 2 D 2 ∀ i ∈ H, aHz ∂ 2 ∂x i ∂z dt = O Ro Bu , azz ∂ 2 ∂z 2 dt = O Ro Bu 2 L.Li (
Ro d t u + u * dt + (σdB t ) H ⋅ ∇ H u -∇ H ⋅ 1 2 a H ∇ H u dt + O Ro Bu + f 0 + Roβ(y -y 0 ) k × udt + (σdB t ) H = -∇ H pdt + d p′ t L.Li (
Ro d t u + u * dt + (σdB t ) H ⋅ ∇ H u -∇ H ⋅ 1 2 a H ∇ H u dt + O Ro Bu + f 0 + Roβ(y -y 0 ) k × udt + (σdB t ) H = -∇ H pdt + d p′ t Hydrostasy : b ′ dt + O RoD 2 = ∂ ∂z pdt + d p′ t L.Li (
Ro d t u + u * dt + (σdB t ) H ⋅ ∇ H u -∇ H ⋅ 1 2 a H ∇ H u dt + O Ro Bu + f 0 + Roβ(y -y 0 ) k × udt + (σdB t ) H = -∇ H pdt + d p′ t Hydrostasy : b ′ dt + O RoD 2 = ∂ ∂z pdt + d p′ t Continuity : ∇ H ⋅ u + ∂w ∂z = 0 ∇ H ⋅ (∇ H ⋅ a H ) + Ro Bu ∂ ∂z (∇ H ⋅ a Hz ) = ∇ H ⋅ (σdB t ) H + Ro Bu ∂(σdB t )z ∂z = 0 (1)
Ro d t u + u * dt + (σdB t ) H ⋅ ∇ H u -∇ H ⋅ 1 2 a H ∇ H u dt + O Ro Bu + f 0 + Roβ(y -y 0 ) k × udt + (σdB t ) H = -∇ H pdt + d p′ t Hydrostasy : b ′ dt + O RoD 2 = ∂ ∂z pdt + d p′ t Continuity : ∇ H ⋅ u + ∂w ∂z = 0 ∇ H ⋅ (∇ H ⋅ a H ) + Ro Bu ∂ ∂z (∇ H ⋅ a Hz ) = ∇ H ⋅ (σdB t ) H + Ro Bu ∂(σdB t )z ∂z = 0 (1)
Thermodynamic :

Ro d t b ′ + u * dt + (σdB t ) H ⋅ ∇ H b ′ -∇ H ⋅ 1 2 a H ∇ H b ′ dt + ∂b ′ ∂z wdt +Bu wdt + Ro (σdB t )z - 1 2 ∇ H ⋅ a Hz dt + O Ro Bu = 0 L.Li (
f 0 k × (u 0 dt + (σdB t ) H ) = -∇ H (p 0 dt + d p′ t ) ⇔ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ f 0 v 0 = ∂p 0 ∂x , f 0 u 0 = - ∂p 0 ∂y f 0 (σdB t )y = ∂d p′ t ∂x , f 0 (σdB t )x = -
f 0 k × (u 0 dt + (σdB t ) H ) = -∇ H (p 0 dt + d p′ t ) ⇔ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ f 0 v 0 = ∂p 0 ∂x , f 0 u 0 = - ∂p 0 ∂y f 0 (σdB t )y = ∂d p′ t ∂x , f 0 (σdB t )x = - ∂d p′ t ∂y
Horizontal incompressibilities :

0 = ∇ H ⋅ u 0 = ∇ H ⋅ (σdB t ) H (1) → ∂(σdB t )z ∂z ≈ 0, ∂ ∂z (∇ H ⋅ a Hz ) ≈ 0 (2)
f 0 k × (u 0 dt + (σdB t ) H ) = -∇ H (p 0 dt + d p′ t ) ⇔ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ f 0 v 0 = ∂p 0 ∂x , f 0 u 0 = - ∂p 0 ∂y f 0 (σdB t )y = ∂d p′ t ∂x , f 0 (σdB t )x = - ∂d p′ t ∂y
Horizontal incompressibilities :

0 = ∇ H ⋅ u 0 = ∇ H ⋅ (σdB t ) H (1) → ∂(σdB t )z ∂z ≈ 0, ∂ ∂z (∇ H ⋅ a Hz ) ≈ 0 (2)
Relative vorticity :

∂v 0 ∂x - ∂u 0 ∂y = ∇ 2 H p 0 f 0 L.Li (
f 0 k × (u 0 dt + (σdB t ) H ) = -∇ H (p 0 dt + d p′ t ) ⇔ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ f 0 v 0 = ∂p 0 ∂x , f 0 u 0 = - ∂p 0 ∂y f 0 (σdB t )y = ∂d p′ t ∂x , f 0 (σdB t )x = - ∂d p′ t ∂y
Horizontal incompressibilities :

0 = ∇ H ⋅ u 0 = ∇ H ⋅ (σdB t ) H (1) → ∂(σdB t )z ∂z ≈ 0, ∂ ∂z (∇ H ⋅ a Hz ) ≈ 0 (2)
Relative vorticity :

∂v 0 ∂x - ∂u 0 ∂y = ∇ 2 H p 0 f 0 Hydrostrasy : ∂p 0 ∂z = b 0 , ∂ p′ t ∂z = O(RoD 2 ) L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018

Pressure balances rotation :

f 0 k × (u 0 dt + (σdB t ) H ) = -∇ H (p 0 dt + d p′ t ) ⇔ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ f 0 v 0 = ∂p 0 ∂x , f 0 u 0 = - ∂p 0 ∂y f 0 (σdB t )y = ∂d p′ t ∂x , f 0 (σdB t )x = - ∂d p′ t ∂y
Horizontal incompressibilities :

0 = ∇ H ⋅ u 0 = ∇ H ⋅ (σdB t ) H (1) → ∂(σdB t )z ∂z ≈ 0, ∂ ∂z (∇ H ⋅ a Hz ) ≈ 0 (2)
Relative vorticity :

∂v 0 ∂x - ∂u 0 ∂y = ∇ 2 H p 0 f 0 Hydrostrasy : ∂p 0 ∂z = b 0 , ∂ p′ t ∂z = O(RoD 2 )
Thermal wind balance : Momentum equations :

∂u 0 ∂z ⋅ ∇ H b 0 = 0, ∂(σdB t ) H ∂z = O(RoD 2 ), ∂a H ∂z = O(Ro 2 D 4 ) (3)
dtu0 + u * 0 dt + (σdBt)H ⋅ ∇ H u0 -∇ H ⋅ aH 2 ∇ H u0 dt-f0v1dt -β(y -y0) v0dt + (σdBt)y = - ∂p1 ∂x dt-A4∇ 4 H u0dt (4) dtv0 + u * 0 dt + (σdBt)H ⋅ ∇ H v0 -∇ H ⋅ aH 2 ∇ H v0 dt+f0u1dt +β(y -y0) u0dt + (σdBt)x = - ∂p1 ∂y dt -A4∇ 4 H v0dt (5)
dtu0 + u * 0 dt + (σdBt)H ⋅ ∇ H u0 -∇ H ⋅ aH 2 ∇ H u0 dt-f0v1dt -β(y -y0) v0dt + (σdBt)y = - ∂p1 ∂x dt-A4∇ 4 H u0dt (4) dtv0 + u * 0 dt + (σdBt)H ⋅ ∇ H v0 -∇ H ⋅ aH 2 ∇ H v0 dt+f0u1dt +β(y -y0) u0dt + (σdBt)x = - ∂p1 ∂y dt -A4∇ 4 H v0dt (5)
dtu0 + u * 0 dt + (σdBt)H ⋅ ∇ H u0 -∇ H ⋅ aH 2 ∇ H u0 dt-f0v1dt -β(y -y0) v0dt + (σdBt)y = - ∂p1 ∂x dt-A4∇ 4 H u0dt (4) dtv0 + u * 0 dt + (σdBt)H ⋅ ∇ H v0 -∇ H ⋅ aH 2 ∇ H v0 dt+f0u1dt +β(y -y0) u0dt + (σdBt)x = - ∂p1 ∂y dt -A4∇ 4 H v0dt (5)
Continuity equation :

∂u1 ∂x + ∂v1 ∂y + ∂w1 ∂z = 0 (6)
Cross-differentiating ( 4)-( 5) combining with (6) :

dt ∇ 2 H p0 f0 + β(y -y0) + u * 0 dt + (σdBt)H ⋅ ∇ H ∇ 2 H p0 f0 + β(y -y0) -∇ H ⋅ aH 2 ∇ H ∇ 2 H p0 f0 + β(y -y0) dt = f0 ∂w1 ∂z - A4 f0 ∇ 6 H p0 dt + R L.Li (
= -tr D[u]JD[-∇ H ⋅ aH 2 ] dt R 2 = - ∂(σdBt)x ∂x ∂v0 ∂x + ∂(σdBt)x ∂y ∂u0 ∂x - ∂(σdBt)y ∂x ∂v0 ∂y + ∂(σdBt)y ∂y ∂u0 ∂y = -tr D[u]JD[(σdBt)H ] R 3 = ∇ H ⋅ 1 2 ∂aH ∂x ∇ H v0 dt -∇ H ⋅ 1 2 ∂aH ∂y ∇ H u0 dt R 4 = -β∇ H ⋅ a⋅ydt L.Li (
= -tr D[u]JD[-∇ H ⋅ aH 2 ] dt R 2 = - ∂(σdBt)x ∂x ∂v0 ∂x + ∂(σdBt)x ∂y ∂u0 ∂x - ∂(σdBt)y ∂x ∂v0 ∂y + ∂(σdBt)y ∂y ∂u0 ∂y = -tr D[u]JD[(σdBt)H ] R 3 = ∇ H ⋅ 1 2 ∂aH ∂x ∇ H v0 dt -∇ H ⋅ 1 2 ∂aH ∂y ∇ H u0 dt R 4 = -β∇ H ⋅ a⋅ydt ▷ a homogeneous ⇒ R = R 2 , E[R] = 0 N.B. D[u] = 1 2 ∇ H u + ∇ T H u : deformation tensor, J = 0 -1 1 0 : 90°rotation matrix L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018

Thermodynamic equation :

dtb0+ u * 0 dt+(σdBt)H ⋅∇ H b0-∇ H ⋅ aH 2 ∇ H b0 dt+Bu w1-∇ H ⋅ aHz 2 dt+(σdBt)z = 0 (7)
L.Li (FLUMINANCE) Towards a stochastic QG modeling 12/06/2018 13 / 20

Continuously stratified QG system First order equations Thermodynamic equation :

dtb0+ u * 0 dt+(σdBt)H ⋅∇ H b0-∇ H ⋅ aH 2 ∇ H b0 dt+Bu w1-∇ H ⋅ aHz 2 dt+(σdBt)z = 0 (7) Derivating (7) along z : dt ∂b0 ∂z + u * 0 dt + (σdBt)H ⋅ ∇ H ∂b0 ∂z -∇ H ⋅ aH 2 ∇ H ∂b0 ∂z dt +Bu ∂w1 ∂z - ∂ ∂z ∇ H ⋅ aHz 2 0 ⇐ (2) dt + ∂(σdBt)z ∂z 0 ⇐ (2) + S = 0 L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018 13 / 20

Thermodynamic equation :

dtb0+ u * 0 dt+(σdBt)H ⋅∇ H b0-∇ H ⋅ aH 2 ∇ H b0 dt+Bu w1-∇ H ⋅ aHz 2 dt+(σdBt)z = 0 (7) Derivating (7) along z : dt ∂b0 ∂z + u * 0 dt + (σdBt)H ⋅ ∇ H ∂b0 ∂z -∇ H ⋅ aH 2 ∇ H ∂b0 ∂z dt +Bu ∂w1 ∂z - ∂ ∂z ∇ H ⋅ aHz 2 0 ⇐ (2) dt + ∂(σdBt)z ∂z 0 ⇐ (2) + S = 0 S = ∂u0 ∂z - 1 2 ∇ H ⋅ ∂aH ∂z dt + ∂(σdBt)H ∂z ⋅ ∇ H b0 -∇ H ⋅ 1 2 ∂aH ∂z ∇ H b0 dt = 0 ⇐ (3) L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018 13 / 20

Thermodynamic equation :

dtb0+ u * 0 dt+(σdBt)H ⋅∇ H b0-∇ H ⋅ aH 2 ∇ H b0 dt+Bu w1-∇ H ⋅ aHz 2 dt+(σdBt)z = 0 (7) Derivating (7) along z : dt ∂b0 ∂z + u * 0 dt + (σdBt)H ⋅ ∇ H ∂b0 ∂z -∇ H ⋅ aH 2 ∇ H ∂b0 ∂z dt +Bu ∂w1 ∂z - ∂ ∂z ∇ H ⋅ aHz 2 0 ⇐ (2) dt + ∂(σdBt)z ∂z 0 ⇐ (2) + S = 0 S = ∂u0 ∂z - 1 2 ∇ H ⋅ ∂aH ∂z dt + ∂(σdBt)H ∂z ⋅ ∇ H b0 -∇ H ⋅ 1 2 ∂aH ∂z ∇ H b0 dt = 0 ⇐ (3)
Results :

- ∂w1 ∂z = 1 Bu dt ∂b0 ∂z + u * 0 dt + (σdBt)H ⋅ ∇ H ∂b0 ∂z -∇ H ⋅ aH 2 ∇ H ∂b0 ∂z dt
Potential vorticity (PV) :

q0 = ∇ 2 H p0 f0 + β(y -y0) + ∂ ∂z f0 Bu b0 , b0 = ∂p0 ∂z L.Li (
q0 = ∇ 2 H p0 f0 + β(y -y0) + ∂ ∂z f0 Bu b0 , b0 = ∂p0 ∂z
Evolution of PV :

dtq0 + u * 0 dt + (σdBt)H ⋅ ∇ H q0 -∇ H ⋅ aH 2 ∇ H q0 dt = - A4 f0 ∇ 6 H p0dt + R Dimensional version : q = ∇ 2 H p f0 + f + ∂ ∂z f0 N 2 ∂ p ∂z dtq + u * dt + (σdBt)H ⋅ ∇ H q -∇ H ⋅ aH 2 ∇ H q dt = - A4 f0 ∇ 6 H pdt + R L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018

Homogeneous and isotropic turbulence model :

a is diagonal and constant ▷ Through a pass-band spectral cutoff :

In 2D, (σ(x)dBt)H = ∇ ⊥ H ψσ ⋆ dBt, ψσ(κ) = A1 κ 1 ≤ κ ≤κ 2 κ -α
Homogeneous and isotropic turbulence model :

a is diagonal and constant ▷ Through a pass-band spectral cutoff :

In 2D, (σ(x)dBt)H = ∇ ⊥ H ψσ ⋆ dBt, ψσ(κ) = A1 κ 1 ≤ κ ≤κ 2 κ -α
Reduced order model :

▷ POD approach using observations from velocity field a is stationnary L.Li (FLUMINANCE) Towards a stochastic QG modeling 12/06/2018

A type of uncertainty living on the iso-surface of buoyancy, i.e. σdBt ⋅ ∇b = 0 :

▷ Iso-surface projector :

P b = ⎛ ⎜ ⎝ 1 0 αx 0 1 αy αx αy α 2 ⎞ ⎟ ⎠ α = (αx, αy) T = - ∇ H b ∂b ∂z = - ∇ H b ′ N 2 1 + O(Ro) = -∇ H ∂p ∂z N 2 L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018

A type of uncertainty living on the iso-surface of buoyancy, i.e. σdBt ⋅ ∇b = 0 :

▷ Iso-surface projector :

P b = ⎛ ⎜ ⎝ 1 0 αx 0 1 αy αx αy α 2 ⎞ ⎟ ⎠ α = (αx, αy) T = - ∇ H b ∂b ∂z = - ∇ H b ′ N 2 1 + O(Ro) = -∇ H ∂p ∂z N 2
▷ Divergence-free projector :

(σdBt)H = I2 -∆ -1 H ∇ H ∇ T H δ ij - κ i κ j κ 2 in Fourier αξ z t ,
where ξ z t is the 3rd component of an original noise ξt, which may be may be the homogeneous and isotropic one, or Kraichnan turbulent model.

L.Li (FLUMINANCE)

Towards a stochastic QG modeling 12/06/2018

A type of uncertainty living on the iso-surface of buoyancy, i.e. σdBt ⋅ ∇b = 0 :

▷ Iso-surface projector :

P b = ⎛ ⎜ ⎝ 1 0 αx 0 1 αy αx αy α 2 ⎞ ⎟ ⎠ α = (αx, αy) T = - ∇ H b ∂b ∂z = - ∇ H b ′ N 2 1 + O(Ro) = -∇ H ∂p ∂z N 2
▷ Divergence-free projector :

(σdBt)H = I2 -∆ -1 H ∇ H ∇ T H δ ij - κ i κ j κ 2 in Fourier αξ z t ,
where ξ z t is the 3rd component of an original noise ξt, which may be may be the homogeneous and isotropic one, or Kraichnan turbulent model. A multi-layer model

An N-layers QG shallow water system Evolution of q (k) , k = 1, . . . , N :

dtq (k) + 1 f0 J p (k) , q (k) dt -∇ H ⋅ a (k) H 2 ⋅ ∇ H q (k) dt + (σdBt) (k) H ⋅ ∇ H q (k) -∇ H ⋅ a (k) H 2 ∇ H q (k) dt = - A4 f0 ∇ 6 H p (k) dt + R (k) + f0 H (k) wekδk1 surface pumping - hek 2f0 ∇ 2 H p (N ) δkN bottom drag L.Li (FLUMINANCE)
Towards a stochastic QG modeling 12/06/2018

dtq (k) + 1 f0 J p (k) , q (k) dt -∇ H ⋅ a (k) H 2 ⋅ ∇ H q (k) dt + (σdBt) (k) H ⋅ ∇ H q (k) -∇ H ⋅ a (k) H 2 ∇ H q (k) dt = - A4 f0 ∇ 6 H p (k) dt + R (k) + f0 H (k) wekδk1 surface pumping - hek 2f0 ∇ 2 H p (N ) δkN bottom drag
Evolution of p (k) , k = 1, . . . , N :

q (k) = ∇ 2 H p (k) f0
+ β(y -y0) + f0 H (k) (η (k) -η (k-1) )

L.Li (FLUMINANCE) Towards a stochastic QG modeling 12/06/2018

dtq (k) + 1 f0 J p (k) , q (k) dt -∇ H ⋅ a (k) H 2 ⋅ ∇ H q (k) dt + (σdBt) (k) H ⋅ ∇ H q (k) -∇ H ⋅ a (k) H 2 ∇ H q (k) dt = - A4 f0 ∇ 6 H p (k) dt + R (k) + f0 H (k) wekδk1 surface pumping - hek 2f0 ∇ 2 H p (N ) δkN bottom drag
Evolution of p (k) , k = 1, . . . , N :

q (k) = ∇ 2 H p (k) f0 + β(y -y0) + f0 H (k) (η (k) -η (k-1) )
Perturbation interface height : k) , k = 1, . . . , N -1; η (N ) = D(x, y) g (k) = g ρb (ρ (k+1) -ρ (k) ), k = 1, . . . , N -1

η (0) = 0; η (k) = p (k+1) -p (k) g (
dtq (k) + 1 f0 J p (k) , q (k) dt -∇ H ⋅ a (k) H 2 ⋅ ∇ H q (k) dt + (σdBt) (k) H ⋅ ∇ H q (k) -∇ H ⋅ a (k) H 2 ∇ H q (k) dt = - A4 f0 ∇ 6 H p (k) dt + R (k) + f0 H (k) wekδk1 surface pumping - hek 2f0 ∇ 2 H p (N ) δkN bottom drag
Evolution of p (k) , k = 1, . . . , N :

q (k) = ∇ 2 H p (k) f0 + β(y -y0) + f0 H (k) (η (k) -η (k-1) )
Perturbation interface height : k) , k = 1, . . . , N -1; η (N ) = D(x, y) g (k) = g ρb (ρ (k+1) -ρ (k) ), k = 1, . . . , N -1

η (0) = 0; η (k) = p (k+1) -p (k) g (
Horizonal uncertainties :

(σdBt) (k) H = I2 -∆ -1 H ∇ H ∇ T H ∇ H η (k-1) -∇ H η (k) ξ (k)

  ∀x ∈ D Eulerian velocity :U (x, t) = w(x, t) large-scale + σ(x, t) Ḃt small-scale , ∀ (x, t) ∈ D × R + Multiplicative noise (Bt) t∈R + is a cylindrical Wiener process in L 2 (D, R 3 ) Spatial correlation : σ(x, t)dBt = D σ(x, y, t)dBt(y)dy, ∀ (x, t) ∈ D × R + Subgrid tensor : a = σσ T = 1 dt E (σdBt)(σdBt) T

a

  Figure: A multi-layer Shallow Water QG system

t

  , k = 1, . . . , N L.Li (FLUMINANCE)Towards a stochastic QG modeling 12/06/2018

Thanks for your attentions ! L.Li (FLUMINANCE) Towards a stochastic QG modeling 12/06/2018