A Liefooghe
email: arnaud.liefooghe@lifl.fr

L Jourdan

E.-G Talbi
email: talbi@lifl.fr

Metaheuristics and cooperative approaches for the bi-objective ring star problem

Keywords: Ring star problem, Multi-objective optimization, Metaheuristic, Cooperative approach

This paper presents and investigates different approaches to solve a new biobjective routing problem called the ring star problem. It consists of locating a simple cycle through a subset of nodes of a graph while optimizing two kinds of cost. The first objective is the minimization of a ring cost that is related to the length of the cycle. The second one is the minimization of an assignment cost from non-visited nodes to visited ones. In spite of its obvious bi-objective formulation, this problem has always been investigated in a single-objective way. To tackle the bi-objective ring star problem, we first investigate different stand-alone search methods. Then, we propose two cooperative strategies that combine two multi-objective metaheuristics: an elitist evolutionary algorithm and a population-based local search. We apply these new hybrid approaches to well-known benchmark test instances and demonstrate their effectiveness in comparison to non-hybrid algorithms and to state-of-the-art methods.

Introduction

The Bi-objective Ring Star Problem (B-RSP) aims at locating a simple cycle through a subset of nodes of a graph. The first objective consists in minimizing a ring cost related to the cycle length. The second objective is to minimize an assignment cost from non-visited nodes to visited ones. Two conflicting costs are then considered here, which naturally leads to a bi-objective formulation. But this problem has always been addressed in a single-objective way; either where both costs are combined [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF], or where the assignment cost is treated as a constraint [START_REF] Labbé | Locating median cycles in networks[END_REF]. However, from a practitioner point of view, it is often necessary to take multiple objectives into account simultaneously, and the problem investigated in this paper is a good illustration of what can typically be found in the industry. Indeed, as pointed out in [START_REF] Jozefowiez | Multi-objective vehicle routing problems[END_REF], a large number of routing problems can be formulated as multiobjective optimization problems, and according to the same paper, the problem at hand is a generalization of the single-objective problems introduced in [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF][START_REF] Labbé | Locating median cycles in networks[END_REF]. Besides, the B-RSP is highly combinatorial as, once is decided which nodes are to be visited, a standard traveling salesman problem is still to be solved. Therefore, in practice, large-scale problem instances generally cannot be solved exactly. This is the reason why heuristic search methods are considered in this paper. Note that the current work extends preliminary results presented during the EvoCOP 2008 conference [START_REF] Liefooghe | Metaheuristics for the bi-objective ring star problem[END_REF]. Nevertheless, a deeper analysis, extra stand-alone methods and novel hybrid approaches are additionally provided in the actual paper.

The main contribution of this work is twofold and can be summarized as follows. First, a set of multi-objective search methods are proposed for a new bi-objective problem, the B-RSP. Second, this paper introduces new generalpurpose cooperative schemes for multi-objective combinatorial optimization, and their features and efficiency are investigated and rather discussed on solving the problem at hand. Thus, as an initial step, we investigate four metaheuristics to approximate the set of efficient solutions for the problem under consideration. Hence, IBMOLS, a population-based local search recently proposed in [START_REF] Basseur | Indicator-based multi-objective local search[END_REF], is fitted for the B-RSP resolution. Next, we present slight variations of two well-known multi-objective search methods, namely IBEA [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] and NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. At last, we propose a general-purpose multiobjective metaheuristic called SEEA and presented in this paper for the first time. We compare all these methods to each other on state-of-the-art benchmark test instances and discuss their respective behaviors. As a second step, we propose two cooperative approaches combining the local search method and SEEA. These methods are based either on a periodic or on an adaptive strategy, each one trying to benefit of the advantages of each algorithm it is compound of. Experiments validate the contribution of these hybrid schemes over non-hybrid approaches by achieving a strict improvement of the generated set of non-dominated solutions.

The remainder of the paper is organized as follows. Section 2 is devoted to the B-RSP. Then, four metaheuristics for multi-objective optimization are introduced in Section 3. A general presentation of these methods and their application to the B-RSP is followed by a comparative study. In Section 4, we propose new cooperation schemes to solve multi-objective combinatorial optimization problems. We experiment the resulting search methods on the B-RSP and we compare the obtained computational results to the previous ones. At last, conclusions and perspectives are drawn in the last section.

The Bi-objective Ring Star Problem

In this section, we first present some basic concepts, notation and definitions related to multi-objective optimization. Next, we provide a formulation of the ring star problem as a bi-objective problem. Finally, we briefly survey the literature related to the problem at hand and discuss its industrial concerns.

Multi-objective Optimization

A Multi-objective Optimization Problem (MOP) aims of optimizing a set of n ≥ 2 objective functions f 1 , f 2 , . . . , f n simultaneously. Each objective function can be either minimized or maximized. Let X denote the set of feasible solutions in the decision space, and Z the set of feasible points in the objective space. Without loss of generality, we here assume that Z ⊆ ℜ n and that all n objective functions are to be minimized. To each decision vector x ∈ X is assigned exactly one objective vector z ∈ Z on the basis of a vector function f : X → Z with z = f (x) = (f 1 (x), f 2 (x), . . . , f n (x)). We will assume, throughout the paper, that objective values are normalized 1 . Therefore, a MOP can be formulated as follows:

(M OP ) = 'min' f (x) = (f 1 (x), f 2 (x), . . . , f n (x)) subject to x ∈ X (1)
Definition 1. An objective vector z ∈ Z weakly dominates another objective vector z ′ ∈ Z if and only if ∀i ∈ {1, 2, . . . , n}, z i ≤ z ′ i .

Definition 2. An objective vector z ∈ Z dominates2 another objective vector z ′ ∈ Z if and only if ∀i ∈ {1, 2, . . . , n}, z i ≤ z ′ i and ∃j ∈ {1, 2, . . . , n} such as z j < z ′ j .

Definition 3. An objective vector z ∈ Z is non-dominated if and only if there does not exist another objective vector z ′ ∈ Z such that z ′ dominates z.

A solution x ∈ X is said to be efficient (or Pareto optimal, non-dominated ) if its mapping in the objective space results in a non-dominated point. The set of all efficient solutions is the efficient (or Pareto optimal ) set, denoted by X E . The set of all non-dominated vectors is the non-dominated front (or the trade-off surface), denoted by Z N . A possible approach in MOP solving is to find the minimal set of efficient solutions, i.e. one solution x ∈ X E for each non-dominated vector z ∈ Z N such as f (x) = z (in case multiple solutions map to the same non-dominated point). But, generating the entire set of Pareto optimal solutions is usually infeasible due to the complexity of the underlying problem or to the large number of optima. Therefore, the overall goal is often to identify a good approximation of it. Populationbased metaheuristics are commonly used to this end as they naturally find multiple and well-spread non-dominated solutions in a single simulation run. The reader could refer to [START_REF] Coello Coello | Evolutionary Algorithms for Solving Multi-Objective Problems[END_REF][START_REF] Deb | Multi-Objective Optimization using Evolutionary Algorithms[END_REF] for more details about evolutionary multiobjective optimization and to [START_REF] Ehrgott | Approximative solution methods for multiobjective combinatorial optimization[END_REF] for more details about multi-objective combinatorial optimization.

Problem Definition

The Ring Star Problem (RSP) can be described as follows. Let G = (V, E, A) be a complete mixed graph where

V = {v 1 , v 2 , . . . , v n } is a set of ver- tices, E = {[v i , v j ]|v i , v j ∈ V, i < j} is a set of edges, and A = {(v i , v j )|v i , v j ∈ V } is a set of arcs. Vertex v 1 is the depot. To each edge [v i , v j
] ∈ E we assign a non-negative ring cost c ij , and to each arc (v i , v j ) ∈ A we assign a non-negative assignment cost d ij . The B-RSP consists of locating a simple cycle through a subset of nodes V ′ ⊂ V (with v 1 ∈ V ′ ) while (i) minimizing the sum of the ring costs related to all edges that belong to the cycle, and (ii) minimizing the sum of the assignment costs of arcs directed from every non-visited node to a visited one so that the associated cost is minimum. An example of solution is given in Figure 1, where solid lines represent edges that belong to the ring and dashed lines represent arcs of the assignments. The first objective is called the ring cost and is defined as:

[v i ,v j ]∈E c ij b ij (2)
where b ij is a binary variable equal to 1 if and only if the edge [v i , v j ] belongs to the cycle. The second objective, the assignment cost, can be computed as follows:

v i ∈V \V ′ min v j ∈V ′ d ij (3)
Let us remark that these objective functions are comparable only if we assume that the ring cost and the assignment cost are proportional one to another. But this is rarely the case in practice. Moreover, the fact of privileging a cost compared to the other is closely related to the decision-maker preferences, whereas we deal here with a posteriori optimization. However, the B-RSP is a N P -hard combinatorial problem because the particular case of visiting the whole set of nodes is equivalent to a traditional traveling salesman problem.

Related Works

The RSP belongs to the class of location-allocation problems aiming at locating structures in a graph (see [START_REF] Labbé | Path, tree and cycle location[END_REF] for a review). It has initially been formulated by Labbé et al. [START_REF] Labbé | The median cycle problem, working paper[END_REF] in two different ways. In the first formulation (denoted MCP1 in [START_REF] Labbé | The median cycle problem, working paper[END_REF] and more often called 'ring star problem'), a weighted sum of both objective functions is to be optimized. In the second formulation (MCP2 [START_REF] Labbé | The median cycle problem, working paper[END_REF], usually called 'median cycle problem'), the ring cost is to be minimized while the assignment cost is bounded by a prefixed value. Even if it was not explicitly noticed by the original authors, these two formulations are commonly employed to convert a MOP into a single-objective problem by using scalar approaches. They are respectively denoted by aggregation and epsilon-constraint methods in the multi-objective optimization literature [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF]. The first formulation of the problem has been more widely studied in [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF]. The authors used a branch-and-bound method and successfully solved TSPLIB and randomly generated instances involving up to 200 nodes in less than two hours. In [START_REF] Labbé | Locating median cycles in networks[END_REF], the same authors solved the second formulation of the problem by a similar method. Finally, one or both versions of the problem have been heuristically tackled by a variable neighborhood tabu search [START_REF] Moreno Pérez | Variable neighborhood tabu search and its application to the median cycle problem[END_REF], an evolutionary algorithm [START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF], a multi-start greedy add heuristic [START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF], and a variable neighborhood tabu search hybridized with a greedy randomized adaptive search procedure [START_REF] Dias | An efficient heuristic for the ring star problem[END_REF].

As shown in the survey of Jozefowiez et al. [START_REF] Jozefowiez | Multi-objective vehicle routing problems[END_REF], an increasing number of multi-objective routing problems appeared in the literature in recent years. However, in spite of its numerous industrial applications (see Subsection 2.4), the RSP has never been explicitly investigated in a multi-objective fashion. Nevertheless, Current and Schilling [START_REF] Current | The median tour and maximal covering tour problems: Formulations and heuristics[END_REF] defined two multi-objective variants of a very similar problem: the median tour problem and the maximal covering tour problem. In both versions, one objective is the minimization of the total length of the tour, while another one is the maximization of the access to the tour for non-visited nodes. To tackle these problems, the authors used a kind of lexicographic method, where a hierarchy is defined between objective functions. Additionally, Dorner et al. [START_REF] Doerner | Multicriteria tour planning for mobile healthcare facilities in a developing country[END_REF] recently formulated a three-objective optimization problem of tour planning for mobile health care facilities, closely related to the Single Vehicle Routing-Allocation Problem introduced in [START_REF] Beasley | The vehicle routing-allocation problem: A unifying framework[END_REF]. A mobile facility has to visit a subset of nodes. Nonvisited nodes are then assigned to their closest tour stop or are regarded as unable to reach a tour stop (within a predefined maximum distance). The considered objectives are (i) the minimization of the ratio between medical working time and total working time, (ii) the minimization of the average distance to the nearest tour stops and (iii) the maximization of a coverage criterion. To do so, a Pareto ant colony optimization algorithm as well as two genetic algorithms (namely VEGA [START_REF] Schaffer | Multiple objective optimization with vector evaluated genetic algorithms[END_REF] and MOGA [START_REF] Fonseca | Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization[END_REF]) were designed to solve real-world instances.

Real-world Applications and Industrial Concerns

The RSP has a wide range of industrial interests, especially in telecommunications and vehicle routing. Of course, practical real-world applications may contain additional constraints. For instance, as noticed by Labbé et al. [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF][START_REF] Labbé | Locating median cycles in networks[END_REF], a ring-based network is designed to interconnect a set of hubs in the case of digital data services [START_REF] Xu | Optimizing a ring-based private line telecommunication network using tabu search[END_REF]. Some concentrators are installed on a subset of locations and are interconnected on a ring network (the Internet) while the remaining locations are assigned to this concentrators (the Intranet). Closely related problems arise in rapid transit systems planning [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF] or while designing optical networks [START_REF] Baldacci | The capacitated m-ring star problem[END_REF]. In addition, other kinds of applications appear in the postal collection or delivery routes design, where the distance between a customer and a collection point has to be reasonable. For instance, post-box location while taking both the collection cost and the user inconvenience into account has been studied in [START_REF] Labbé | Maximizing user convenience and postal service effiency in post box location[END_REF]. Besides, other applications closely related to the RSP are the location of circular shaped transportation infrastructure (such as metro lines or motorways), the location of recyclable garbage collection bins, and school bus routing. Finally, the routing of essential health care services, already investigated in [START_REF] Doerner | Multicriteria tour planning for mobile healthcare facilities in a developing country[END_REF][START_REF] Akinc | Optimal routing and process scheduling for a mobile service facility[END_REF] among other authors, consists of a mobile clinic servicing an area without being able to visit every population nodes. Then, unvisited ones have to reach the nearest tour stop by their own to be medically treated.

Metaheuristics for the Bi-objective Ring Star Problem

In this section, four population-based metaheuristics are proposed to solve the bi-objective RSP. First is an iterative local search method called IB-MOLS [START_REF] Basseur | Indicator-based multi-objective local search[END_REF]. Next, three evolutionary algorithms are designed. They consist of slight variations of IBEA [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] and NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] and of a general-purpose search method called SEEA and introduced in this paper for the first time. IBMOLS and IBEA are both recent indicator-based metaheuristics, whereas NSGA-II can be considered as a state-of-the-art multi-objective resolution approach. A presentation of these metaheuristics is given below, and is followed by a detailed description of problem-specific components.

A Multi-objective Local Search

Since they are easily adaptable to the multi-objective context, many search methods proposed to tackle MOPs are evolutionary algorithms. However, local search algorithms are known to be effective metaheuristics for solving real-world applications [START_REF]Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques[END_REF][START_REF]Handbook of Metaheuristics[END_REF]. Several multi-objective neighborhood search methods have been proposed in the literature, see [START_REF] Ehrgott | Approximative solution methods for multiobjective combinatorial optimization[END_REF][START_REF] Paquete | Stochastic local search algorithms for multiobjective combinatorial optimization: A review[END_REF] for a survey. Most of them are based on a set of aggregations of the objective functions. Dominance-based local search algorithms are more rare. However, an Indicator-Based Multi-Objective Local Search (IBMOLS for short) has recently been proposed in [START_REF] Basseur | Indicator-based multi-objective local search[END_REF]. IBMOLS can be seen as a local search variant of IBEA [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], as the same strategy is used for fitness assignment. IBMOLS is a generic population-based multi-objective local search dealing with a fixed population size. This allows to obtain a set of efficient solutions in a single simulation run without specifying any mechanism to control the number of solutions during the search process. Moreover, IBMOLS presents an alternative to aggregation-and dominance-based multi-objective local search algorithms. Indeed, as proposed in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], it is assumed that the optimization goal is given in terms of a binary quality indicator I [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF] that can be regarded as an extension of the Pareto dominance relation. A value I(A, B) quantifies the difference in quality between two approximated efficient sets A and B. So, if R denotes a reference set (that can be the Pareto-optimal set X E or any other set), the overall optimization goal can be formulated as:

arg min A∈Ω I(A, R) , (4)
where Ω denotes the space of all efficient set approximations. As noted in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], R does not have to be known in advance, it is just required in the formalization of the optimization goal. Since R is fixed, I actually represents a unary function that assigns a real number reflecting the quality of any approximation set according to the optimization goal. If I is dominance preserving [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], I(A, R) is minimum for A = R. One of the main advantages of indicatorbased optimization is that no additional diversity preservation mechanism is generally required, according to the indicator being used. Indeed, diversity information is usually included into the indicator, since it may quantify the quality of a set both in terms of convergence and diversity.

Principle. The IBMOLS algorithm maintains a population P of size N . Then, it generates the neighborhood of a solution contained in P until an improving solution is found (i.e. one that is better than at least one solution of P in terms of the indicator being used), or until all its neighbors have been explored. If an improving solution is found, it replaces the worst solution of P . This corresponds to a 'first improving' strategy. By iterating this simple principle to every solution of P , we obtain a local search step. The whole local search procedure stops when the archive of potentially efficient solutions has not received any new item during a complete local search step. Hence, the IBMOLS method provides a natural stopping criterion.

Quality Indicator. Several quality indicators can be used in the frame of IB-MOLS. Some examples can be found in [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF]. One of them is the binary additive ǫ-indicator (I ǫ+ ) [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF][START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF], inspired by the concept of ǫ-dominance [START_REF] Helbig | On several concepts for ǫ-efficiency[END_REF]. This indicator appears to be particularly well-suited to indicator-based search.

And its efficiency has been experimentally proven to approximate the efficient set of different kinds of problems, see for instance [START_REF] Basseur | Indicator-based multi-objective local search[END_REF][START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF]. I ǫ+ computes the minimum value by which a solution x ∈ X has to or can be translated in the objective space to weakly dominate another solution x ′ ∈ X. For a minimization problem, it is defined as follows:

I ǫ+ (x, x ′ ) = max i∈{1,...,n} (f i (x) -f i (x ′ )) , (5)
where n stands for the number of objective functions. Furthermore, to evaluate the quality of a solution x ∈ X according to a whole population P , and then to compute the fitness value of x, different approaches exist. As proposed in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], we will here consider an additive technique that amplifies the influence of dominating solutions over dominated ones. It can be outlined as follows:

f itness(x) = x ⋆ ∈P \{x} -e -I(x ⋆ ,x)/κ , (6)
where κ > 0 is a fitness scaling factor, see [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] for more details. However, the initial experiments were not satisfactory because the algorithm was not able to find the extreme points of the trade-off surface. As pointed out in [START_REF] Hernández-Díaz | Pareto-adaptive epsilon-dominance[END_REF], this is known to be one of the drawbacks of the ǫ-dominance relation, apparently due to the high convexity of the front. Indeed, the authors illustrate that a limitation of ǫ-dominance is that extreme points of the Pareto front are usually lost. To tackle this problem, we add a simple condition preventing the deletion of solutions corresponding to the extreme non-dominated vectors during the replacement step of IBMOLS.

Iterative Version. Firstly, let us remind that IBMOLS handles a natural stopping condition. However, it is commonly known that iteratively repeating a local search algorithm can lead to very high performances and can significantly improve the results. In the frame of single-objective optimization, two main iterative strategies are generally distinguished, that is random restart and perturbation techniques [START_REF] Lourenco | Iterated local search[END_REF]. Random restart is the simplest possibility, and a well-designed perturbation technique generally achieves better results. Furthermore, within IBMOLS, we now have to deal with a population of solutions that needs to be re-initialized between each local search phase. As proposed in [START_REF] Basseur | Indicator-based multi-objective local search[END_REF], we decide to perturb a set of solutions from the archive to obtain the restarting population. The choice of such a strategy has been motivated by preliminary experiments as well as conclusive results obtained in [START_REF] Basseur | Indicator-based multi-objective local search[END_REF] for another problem. Then, the population re-initialization scheme is based on random noise, such as in a basic simulated annealing [START_REF]Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques[END_REF]. This noise consists of multiple mutations applied to N different randomly chosen solutions contained in the elite set. If the size of the archive is less than N , the population is filled with random solutions, just like in random restart. More details about IBMOLS and I-IBMOLS as well as algorithm pseudocodes can be found in [START_REF] Basseur | Indicator-based multi-objective local search[END_REF].

Multi-objective Evolutionary Algorithms

The first two multi-objective evolutionary algorithms designed to tackle the bi-objective RSP are small variations of two state-of-the-art search methods, namely IBEA [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] and NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. Some minor modifications have been carried out in order to save the whole set of non-dominated solutions found during the search process. Finally, a general-purpose approach for MOP solving, called SEEA, is proposed in this paper for the first time and is presented in details.

IBEA

Introduced by Zitzler and Künzli [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], the Indicator-Based Evolutionary Algorithm (IBEA) is, like IBMOLS, an indicator-based metaheuristic. The fitness assignment scheme of this evolutionary algorithm is based on a pairwise comparison of solutions contained in a population by using a binary quality indicator. The selection scheme for reproduction is a binary tournament between randomly chosen individuals. The replacement is based on an iterative elitist strategy that consists in deleting, one-by-one, the worst individuals, and in updating the fitness values of the remaining solutions each time there is a deletion; this is continued until the required population size is reached. Moreover, an archive stores solutions mapping to potentially nondominated points in order to prevent their loss during the stochastic search process. However, in our case, and in contrast to the IBEA defined in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], this archive is updated at each generation since the beginning of the evolutionary algorithm, so that the output size is not necessarily less than or equal to the population size. Just like for the IBMOLS algorithm, the indicator used within IBEA is the additive ǫ-indicator; and the same mechanism has been used to prevent the loss of the extreme points on the trade-off surface. More information about this algorithm can be found in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF].

NSGA-II

At each generation of NSGA-II (the Non-dominated Sorting Genetic Algorithm II introduced by Deb et al. in [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]), the solutions contained in the population are ranked into several classes. Individuals mapping to vectors from the first front all belong to the best efficient set; individuals mapping to vectors from the second front all belong to the second best efficient set; and so on. Two values are computed for every solution of the population. The first one corresponds to the rank the corresponding solution belongs to, and represents the quality of the solution in terms of convergence. The second one, the crowding distance, consists in estimating the density of solutions surrounding a particular point of the objective space, and represents the quality of the solution in terms of diversity. A solution is said to be better than another solution if it has a best rank value, or in case of equality, if it has the best crowding distance. The selection strategy is a deterministic tournament between two random solutions. At the replacement step, only the best individuals survive, with respect to the population size. Similarly, an external population is added to NSGA-II in order to store every potentially efficient solution found during the search. The reader is referred to [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] for more details about NSGA-II.

SEEA

If evaluating a solution in the objective space is not too much time consuming (which is the case for our problem), computing fitness and diversity information is generally the most computationally expensive step of a multi-objective evolutionary algorithm. Based on this observation, we here propose a simple search method for which none of these phases is required. The resulting evolutionary algorithm, called Simple Elitist Evolutionary Algorithm (SEEA for short), is detailed in Algorithm 1. An archive of potentially efficient solutions is updated at each generation, and the individuals contained in the main population are generated by applying variation operators to randomly chosen archive members. The replacement step is a Algorithm 1 Simple Elitist Evolutionary Algorithm (SEEA)

Input: P Initial population Output: A Efficient set approximation
Step 1: Initialization. A ← non-dominated solutions of P ; N ← |P |; P ′ ← ∅.

Step 2: Selection. Repeat until |P ′ | = N : randomly select an individual from A and add it to the offspring population P ′ .

Step 3: Variation. Apply crossover and mutation operators to individuals of the offspring population P ′ .

Step 4: Replacement. P ← P ′ ; P ′ ← ∅.

Step 5: Elitism. A ← non-dominated solutions of A ∪ P .

Step 6: Termination. If a stopping criteria is satisfied return A, else go to Step 2.

generational one, i.e. the parent population is replaced by the offspring one. Note that the initial population can, for instance, be filled with random solutions. Thus, as proposed in [START_REF] Zitzler | Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach[END_REF] among other authors, the archive is not only used as an external storage, but it is integrated into the optimization process during the selection phase of the evolutionary algorithm; that is called elitism. Elitism is an important issue in the field of evolutionary multiobjective optimization [START_REF] Laumanns | On the effects of archiving, elitism, and density based selection in evolutionary multi-objective optimization[END_REF] and SEEA is in somehow related to other elitist evolutionary algorithms such as SPEA [START_REF] Zitzler | Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach[END_REF], PESA [START_REF] Corne | The pareto envelope-based selection algorithm for multiobjective optimization[END_REF] or SEAMO [START_REF] Valenzuela | A simple evolutionary algorithm for multi-objective optimization (SEAMO)[END_REF]. But, contrary to other approaches, no strategy to preserve diversity or to manage the size of the archive is involved here, as solutions are selected randomly and the archive is unbounded. Note that to be used for solving optimization problems where an exponential number of efficient solutions are involved, an additional mechanism should be designed to bound the archive size, see [START_REF] Knowles | Bounded Pareto archiving: Theory and practice[END_REF].

The biggest advantage of this evolutionary algorithm is that the population (or the population size if solutions are randomly initialized) is the only problem-independent parameter. If non-dominated solutions are relatively close to each other in the decision space and if the archive is not too small compared to the main population, we believe that SEEA may convergence to a good approximation of the efficient set in a very short runtime.

Application to the Bi-objective Ring Star Problem

This section presents the problem-specific components that are necessary to instantiate the metaheuristics introduced above for the resolution of our bi-objective RSP. Hence, the encoding mechanism, the population initialization as well as the neighborhood, the mutation and the recombination operators, are described in details below.

Solution Encoding

The representation of a RSP solution is based on the random keys mechanism proposed by Bean [START_REF] Bean | Genetic algorithms and random keys for sequencing and optimization[END_REF]. Such an encoding mechanism has already been successfully applied for solving a single-objective version of the RSP in [START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF]. A random key k i ∈ [0, 1[ is assigned to every node v i that belongs to the ring, with k 1 = 0. A special value is assigned to unvisited nodes. Thus, the ring route associated to a solution corresponds to the nodes read according to their random keys in the increasing order; i.e. if k i < k j , then v j comes after v i . A possible representation for the cycle (v 1 ,v 7 ,v 4 ,v 9 ,v 2 ,v 6 ) is given in Figure 2. Nodes v 3 ,v 5 ,v 8 and v 10 are assigned to a visited node in such a way that the associated assignment cost is minimum.

Vertex v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10
Random key 0 0.7 -0.3 -0.8 0.2 -0.5 -Figure 2: A RSP solution represented by random keys.

Population Initialization

For each search method, the initial population has been generated randomly. Each node has a probability p = 0.5 to be visited or not, and to each visited vertex v i we associate a random key k i uniformly generated in [0, 1[.

Neighborhood and Mutation Operators

As the RSP is both a routing and an assignment problem, different move and mutation operators have to be designed. For this kind of problems, usual operators consists in removing or adding a node to the cycle. Here we also consider an operator specifically dedicated to the ring improvement by means of a 2-opt move. The resulting three operators are the following:

• remove operator : selects a visited node v i ∈ V ′ at random and removes it from the ring

• insert operator : selects an unvisited node v i ∈ V \ V ′ at random and adds it to the cycle, the position to insert v i is chosen so that the increment on the ring cost is minimum

• 2-opt exchange operator : selects two visited nodes v i ∈ V ′ and v j ∈ V ′ at random and applies a 2-opt move between v i and v j , so that the sequence of visited nodes located between v i and v j is reversed.

Note that it is not necessary to re-evaluate a solution each time a neighborhood or a mutation operator is applied. Thus, after a remove operator, we just have to re-assign the unvisited nodes previously assigned to the one that has been removed. After an insert operator, we just have to re-assign unvisited nodes in order to minimize the assignment cost. Finally, after a 2-opt exchange operator, we just have to recompute the ring cost, the assignment cost being unchanged. For the local search method, the neighbors of a given solution are randomly explored, without considering any order between these three operators. And each neighbor is at most visited once during a search step.

Recombination Operator

The recombination operator is a one-point crossover closely related to the one proposed in [START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF]. Two randomly selected solutions x 1 and x 2 are first divided according to a random position. Then, the first part of x 1 is combined with the second part of x 2 to build a first offspring, and the first part of x 2 is combined with the second part of x 1 to build a second offspring. Every node retains its random key so that it enables an easy reconstruction of the new individuals. Due to the random keys encoding mechanism, solutions having different ring sizes can easily be recombined, even if the initial ring structures are generally broken in the offspring solutions. Figure 3 illustrates a recombination between two solutions (v 1 ,v 7 ,v 4 ,v 9 ,v 2 ,v 6 ) and (v 1 ,v 8 ,v 4 ,v 3 ,v 5 ) after vertex v 6 , which gives rise to a couple of new solutions (v

1 ,v 8 ,v 4 ,v 2 ,v 6 ) and (v 1 ,v 7 ,v 9 ,v 4 ,v 3 ,v 5 ).
Another recombination operator preserving a bigger part of the initial ring structures, has been experimented. But it was tending to reduce the number of nodes belonging to the cycle and then was causing a premature convergence with solutions having a small number of visited nodes.

Experiments

All the metaheuristics presented in this paper have been implemented using the ParadisEO-MOEO software framework3 [START_REF] Liefooghe | A unified model for evolutionary multiobjective optimization and its implementation in a general purpose software framework: ParadisEO-MOEO[END_REF]. ParadisEO-MOEO is a C++ white-box object-oriented framework dedicated to the reusable design of metaheuristics for multi-objective optimization. All the algorithms share the same base components for a fair comparison between them. Computational runs were performed on an Intel Core 2 Duo 6600 (2 × 2.40 GHz) machine, with 2 GB RAM.

Parent 1 Vertex v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 Random key 0 0.7 -0.3 -0.8 0.2 -0.5 - Parent 2 Vertex v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 Random key 0 -0.8 0.7 0.9 - -0.2 - - Offspring 1 Vertex v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 Random key 0 0.7 -0.3 -0.8 -0.2 - - Offspring 2 Vertex v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v

Experimental Protocol

Benchmark Test Instances. Experiments were conducted on a set of eight benchmark instances taken from the TSPLIB4 [START_REF] Reinelt | TSPLIB -A traveling salesman problem library[END_REF]. These instances contain between 51 and 299 nodes. The number at the end of an instance name represents the number of nodes involved for the instance under consideration. Let l ij denote the distance between two nodes v i and v j of a TSPLIB file.

The ring cost c ij and the assignment cost d ij have both been set to l ij for every pair of nodes v i and v j .

Stopping Conditions. From our point of view, there does not exist a standard approach to define an unquestionable condition for stopping a multi-objective metaheuristic. Common strategies are quite basic and generally consist of an arbitrary user-given number of iterations or evaluations. However, in the frame of this paper, an evolutionary algorithm iteration has nothing to do with a local search iteration. Moreover, computing the number of evaluations performed from the beginning of the search process does not make any sense here, as mutated or neighbor solutions are not fully, but incrementally evaluated. Therefore, in this study, the search process simply stops after a fixed amount of runtime. Indeed, all methods share the same base components and their respective implementations can then be compared in term of computational time. But, as small instances are supposedly easier to solve than large ones, this stopping criteria has been arbitrary set according to the size of the instance under consideration, as shown in Table 1. Note that the maximum runtime available stands for a single simulation run per instance and per algorithm. Performance Assessment. In the frame of multi-objective optimization, the performance assessment of a number of algorithms in solving the same problem is a key issue. In this study, a set of 20 runs per instance, with different initial populations, has been performed for each search method. In order to evaluate the quality of the non-dominated front approximations for every instance we experimented, we follow the protocol given by Knowles et al. in [START_REF] Knowles | A tutorial on the performance assessment of stochastic multiobjective optimizers[END_REF]. For a given instance, let Z all denote the union of the outputs we obtained during all our experiments. Note that this set probably contains both dominated and non-dominated points, as a given approximation may contain vectors dominating the ones of another approximation, and vice versa. We first compute a reference set Z ⋆ N containing all the non-dominated points of Z all . Second, we define z max = (z max 1 , z max 2 ), where z max 1 (respectively z max

2

) denotes the upper bound of the first (respectively second) objective for all the points contained in Z all . Now, to measure the quality of an output set A in comparison to Z ⋆ N , we compute the difference between these two sets by using the unary hypervolume metric [START_REF] Zitzler | Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach[END_REF], z max being the reference point. As illustrated in Figure 4, the hypervolume difference indicator (I - H ) computes the portion of the objective space that is weakly dominated by Z ⋆ N and not by A, cf. Definition 1; the closer this measure to 0, the better the approximation A. Furthermore, we also consider the additive ǫ-indicator proposed in [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF]. Contrary to the one proposed in Equation 5, this indicator is used to compare non-dominated set approximations, and not solutions. The unary additive ǫ-indicator (I 1 ǫ+ ) gives the minimum factor by which an approximation A has to be translated in the objective space to weakly dominate the reference set Z ⋆ N . I 1 ǫ+ can then be defined as follows:

I 1 ǫ+ (A) = min ǫ {∀z ∈ Z ⋆ N , ∃z ′ ∈ A : z ′ i -ǫ ≤ z i , ∀1 ≤ i ≤ n} . (7)
As a consequence, for each test instance, we obtain 20 I - H measures and 20 I ǫ+ measures, corresponding to the 20 runs, per algorithm. As suggested by Knowles et al. [START_REF] Knowles | A tutorial on the performance assessment of stochastic multiobjective optimizers[END_REF], once all these values are computed, we perform a statistical analysis for a pairwise comparison of methods. To this end, we use the Wilcoxon signed rank test. Such a non-parametric statistical test is motivated by the fact that the samples collected here can be considered as matched samples. Indeed, for a given run, both the initial population and the random seed are identical for all algorithms, so that the final indicator values can be taken as pairs. Details for this statistical testing procedure are given in [START_REF] Knowles | A tutorial on the performance assessment of stochastic multiobjective optimizers[END_REF]. Hence, for a given test instance, and according to the p-value and to the metric under consideration, this statistical test reveals if the sample of approximation sets obtained by a given search method is significantly better than the ones of another search method, or if there is no significant difference between both. Note that all the performance assessment procedures have been achieved using the performance assessment tool suite provided in PISA5 [START_REF] Bleuler | PISA -a platform and programming language independent interface for search algorithms[END_REF].

Parameter Setting

A preliminary experimental phase has been performed to determine the following parameters, see [START_REF] Liefooghe | Metaheuristics and their hybridization to solve the bi-objective ring star problem: a comparative study[END_REF] for more details. Hence, as no general trend has been identified for some algorithms, the population size were fixed according to the instance under consideration, as shown in Table 2. The noise rate for I-IBMOLS has been set to a fixed percentage of the number of nodes involved in the problem at hand. Next, following [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], the scaling factor κ of Equation 6 has been set to 0.05 for indicator-based metaheuristics, i.e. IBEA and I-IBMOLS. The remainder parameters are shared by all evolutionary algorithms and consist of a crossover probability of 0.25, and of a mutation probability of 1.00, with rates of 0.25, 0.25 and 0.50 for the remove, the insert and the 2-opt exchange operator, respectively.

Computational Results

Table 3 and Table 4 provide a comparison of SEEA, NSGA-II, IBEA and I-IBMOLS with respect to the I - H metric and to the I 1 ǫ+ metric, respectively. According to the experimental protocol used in the paper, I-IBMOLS is never statistically outperformed by any other algorithm with respect to both metrics. The only exceptions are for the st70 and the pr264 instances, where SEEA obtained better results with respect to the I 1 ǫ+ metric. About NSGA-II, it is outperformed by all the other algorithms on every test instances, except for pr264 where there is no significant difference between its results Table 3: Algorithms comparison with respect to the I - H metric. The number in brackets denotes the average metric value for the algorithm and the instance under consideration (multiplied by 10 -3 ). For each instance, either the algorithm located at a specific row significantly dominates the algorithm located at a specific column (≻ or for a p-value less or equal to 0.01 or to 0.05, respectively), either it is significantly dominated (≺ or for a p-value less or equal to 0.01 or to 0.05, respectively), or there is no significant difference between both (≡).

I

≡ - ≻ ≻ NSGA-II (8.515) ≺ ≺ - ≺ SEEA (3.822) ≺ ≺ ≻ - pr264 I-IBMOLS (1.535) - ≻ ≻ ≡ IBEA (1.912) ≺ - ≻ ≺ NSGA-II (3.663) ≺ ≺ - ≺ SEEA (1.520) ≡ ≻ ≻ - pr299 I-IBMOLS (1.303) - ≻ ≻ ≻ IBEA (1.964) ≺ - ≻ ≡ NSGA-II (4.185) ≺ ≺ - ≺ SEEA (2.179) ≺ ≡ ≻ -
Table 4: Algorithms comparison with respect to the I 1 ǫ+ metric. The number in brackets denotes the average metric value for the algorithm and the instance under consideration (multiplied by 10 -3 ). For each instance, either the algorithm located at a specific row significantly dominates the algorithm located at a specific column (≻ or for a p-value less or equal to 0.01 or to 0.05, respectively), either it is significantly dominated (≺ or for a p-value less or equal to 0.01 or to 0.05, respectively), or there is no significant difference between both (≡).

I and the ones of IBEA according to the I 1 ǫ+ metric. At last, with respect to the I - H metric, the results of IBEA and SEEA are quite heterogeneous, so that no general trend can be identified. However, according to the I 1 ǫ+ metric, it seems that SEEA is more efficient that IBEA on most test instances.

Discussion

We can conclude that the iterative version of IBMOLS is globally significantly better than all the evolutionary algorithms we investigated. Nevertheless, the behavior of such a simple search method as SEEA in comparison to state-of-art algorithms like IBEA and NSGA-II is very encouraging with regard to combinatorial problem solving. One of the main characteristics of the problem under consideration seems to be the high number of points located in the trade-off surface. Then, after a couple of iterations, a large part of the population involved in I-IBMOLS, IBEA and NSGA-II might map to non-dominated points. That could explain the low efficiency of NSGA-II. Indeed, since the same fitness value is assigned to the major part of the population, only the crowding distance is used to compare solutions. The indicator-based fitness assignment scheme of I-IBMOLS and IBEA is obviously much more suited to discriminate potentially efficient solutions than the single crowding distance. Note that this is not the case within SEEA because all non-dominated solutions contained in the archive can potentially take part in the evolution engine. However, the good performance of I-IBMOLS might also depend on how close are solutions mapping to non-dominated points in the decision space. If these solutions are close to each other according to the neighborhood operators, a local search method is known to be particularly well-suited to find additional interesting solutions. As a next step, it could then be interesting to design a cooperation scheme between two different search methods in order to benefit of their individual features.

Cooperative Approaches for the Bi-objective Ring Star Problem

This section presents a general-purpose cooperative approach combining SEEA and the non-iterative version of IBMOLS for multi-objective combinatorial optimization. Two variants are proposed: a periodic one that operates a systematic cooperation and an adaptive one that decides on-line when the cooperation must occur. These hybrid models are next experimented on the bi-objective RSP investigated in this paper.

Motivations

Designing metaheuristics for solving combinatorial optimization problems is generally a matter of intensification and diversification. This is even more pronounced for MOPs where the goal is to find a well-converged and welldiversified efficient set approximation. However, local search methods are known to be particularly efficient as intensifying methods whereas evolutionary algorithms are clearly powerful to explore the decision space thanks to their variation operators. Instead of trying to improve one method in term of diversification or the other in term of intensification, a common approach is to hybridize both in order to make them cooperate and then to benefit of their respective behaviors. Thus, hybrid metaheuristics have shown their efficiency to solve different optimization problems [START_REF] Talbi | A taxonomy of hybrid metaheuristics[END_REF], including MOPs [START_REF] Ehrgott | Hybrid metaheuristics for multi-objective combinatorial optimization[END_REF].

In the previous section, we saw that SEEA and I-IBMOLS were the overall more efficient method to approximate the efficient set for the problem under consideration. Moreover, these two methods are quite different to each other and do not explore the search space in the same way. Indeed, SEEA has been conceived in order to find a rough approximation of the Pareto set in a very short amount of time whereas the non-iterative version of IBMOLS is able to improve an approximated set in a very efficient way. It could then be interesting to design a cooperation scheme between these two algorithms. The resulting hybrid metaheuristic could be particularly efficient for solving large size problems. Furthermore, both methods maintain a secondary population (the archive) in parallel of the main population to store non-dominated solutions. This archive is not only used as an external storage, but also takes part in the evolution engine as it serves to build new solutions to explore. Thus, each method can manage its own population and therefore use the archive as a single shared memory.

Cooperative Schemes

The general idea of our hybridization scheme is to run SEEA and to launch IBMOLS regularly by using a subset of archive items as an initial population. Since the non-iterative version of IBMOLS naturally stops when its own archive does not receive any new efficient solution anymore, we can restart the SEEA process until the next step of the hybrid algorithm. A step can, for instance, be defined by a certain amount of time or by a certain number of generations. Besides, as SEEA uses the non-dominated solutions found by IBMOLS to create new ones and vice versa, the global archive is the only memory shared by the two search agents to exchange information.

Resulting from this, we can imagine two versions of the hybrid algorithm: (i) a periodic version, in which IBMOLS is launched at each step, and (ii) an adaptive version, in which IBMOLS is launched at a specific step only if a condition is verified. These two approaches will be denoted by PCS (for Periodic Cooperative Search) and ACS (for Adaptive Cooperative Search) in the remainder of the paper, and are respectively illustrated in Figure 5 and Figure 6. The ACS method decides by itself, and on-line, if it is interesting to launch IBMOLS at a given step of the search process. The condition outlined here is that the archive of potentially efficient solutions does not improve enough with regards to the optimization scenario. A possibility is to measure the quality of the current archive A t in comparison to the one of the previous step A t-1 . Different metrics exist to evaluate the convergence properties of an approximated efficient set in comparison to another. For instance, the hypervolume metric could have been envisaged, but its computation has the drawback of being time consuming. Thus, let us introduce the contribution metric C proposed by Meunier et al. [46]. This metric gives an idea of the quality of an approximated efficient set in comparison to another one in term of convergence, and can be computed in a reasonable runtime. In our case, at each step t of the ACS, we compute the contribution of the current archive A t on the archive of the previous step A t-1 . Thus, as non-dominated solutions are not lost between two steps, A t is at least as good as A t+1 , so that we know that C(A t , A t-1 ) ∈ [0.5, 1] due to the contribution metric properties; see [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF]. Assuming that the archive does not improve enough if the contribution of A t on A t-1 is less than a user-given threshold δ ∈ [0.5, 1], we choose to launch IBMOLS only if C(A t , A t-1 ) ≤ δ. Let us remark that an ACS with a δ = 0.5 is equivalent to SEEA, and that an ACS with a δ = 1.0 is equivalent to PCS, the time spent in calculating the different contribution values in less.

Thus, thanks to the definition of a step t and to the δ parameter, it is possible to intentionally bias the balance between evolutionary search and local search within both PCS and ACS. This issue was pointed out in [START_REF] Ishibuchi | Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling[END_REF] for hybrid multi-objective metaheuristics. For instance, the higher the δ value, the more often the local search will be launched in the frame of the ACS method. Hence, the proposed hybrid algorithm can directly handle different specifications of the evolutionary-local search balance, i.e. from almost pure SEEA (δ = 0.5) to almost pure IBMOLS (δ = 1.0).

Related Works

Different schemes exist on how two search methods can be combined. According to the taxonomy proposed in [START_REF] Talbi | A taxonomy of hybrid metaheuristics[END_REF], the hybrid metaheuristic investigated in this paper can be classified on the High-level Teamwork Hybrid (HTH) class, and can then be denoted by HTH(SEEA+IBMOLS). In their survey on hybrid metaheuristics to solve combinatorial MOPs [START_REF] Ehrgott | Hybrid metaheuristics for multi-objective combinatorial optimization[END_REF], Ehrgott and Gandibleux identify three categories of methods hybridizing an evolutionary algorithm with a neighborhood search algorithm: (i) an hybridization to make a method more aggressive, (ii) an hybridization to drive a method and (iii) an hybridization for exploiting complementary strengths. The last one consists of alternating between both search methods, which is the case within our hybridization. But, most existing approaches occur in a pipeline way: first the evolutionary algorithm, then the local search. The few teamwork hybridization techniques from the literature are most often compound of the same metaheuristic, like in the island model. Moreover, this class of hybrid methods often uses a neighborhood search method combining a set of scalarizing functions. The originality of the approach proposed in this paper is that search agents are based on different types of metaheuristics, are hybridized in a teamwork mode, and do not use any scalar approach to convert the multi-objective vector function into a single-objective one. Furthermore, one of the variants we propose, the adaptive one, automatically detects when to start the local search according to the optimization scenario.

Experiments

In order to experiment the efficiency of our two cooperative approaches, we compare them to SEEA and to the iterative version of IBMOLS by using the same experimental protocol as the one defined in Section 3.4.1. The parameter setting for each hybrid method is followed by some computational results and by a discussion on the contribution of the hybridization for the resolution of the RSP as a bi-objective problem. Finally, we give an idea of the behavior of our approaches in comparison to the state-of-art singleobjective approach proposed in [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF] for the problem under study.

Parameter Setting

For both cooperative search methods, the population size managed by SEEA is set to 100, and the population size managed by IBMOLS is set according to the instance under consideration. These sizes have been set on the same way that for the stand-alone iterative version of IBMOLS on the previous section, see Table 2. But, for large-size instances, initial experiments were not satisfying since the hybrid algorithms were generally not able to launch IBMOLS more than once during the search process, as it was too much time consuming. For this reason, we bounded the IBMOLS population size to 30. Then, a IBMOLS population of 20 individuals has been set for instances with less than 100 nodes, and a IBMOLS population of 30 individuals has been set for instances with 100 nodes and more. Moreover, note that in addition to the benchmark test instances we investigated previously, we experimented two larger TSPLIB problems, namely pr439 and pr1002. Following the general trend identified in the previous section, we set the instance-specific parameters for I-IBMOLS as follows: a population of 70 and 100 individuals respectively, and a noise rate of 10%. The other parameters were set in the same way than for other instances. The step t of the hybrid algorithms has been set to 0.5% of the maximum runtime available for the instance under consideration. In [START_REF] Liefooghe | Metaheuristics and their hybridization to solve the bi-objective ring star problem: a comparative study[END_REF], we investigated different δ-values for the ACS method: 0.6, 0.7, 0.8 and 0.9. As pointed out above, an ACS with a δ-value of 0.5 and 1.0 is similar to PCS and SEEA, respectively. This has lead to an effective δ-value of 0.8 for the stopping criterion we adopted.

Computational Results

Table 6 and Table 7 give a comparison between the results obtained by SEEA, I-IBMOLS, PCS and ACS according to the I - H and I 1 ǫ+ metric, respectively. Firstly, except for the eil51 instance, PCS and ACS both always statistically outperform SEEA with respect to, at least, one metric. In comparison to I-IBMOLS, PCS and ACS often obtain better results, in particular for instances with 150 nodes and more. However, in any case, both hybrid metaheuristics are never statistically outperformed by a stand-alone search method. Thus, the benefit of the cooperation scheme appears relevant in most large-size instances, but the addition of an adaptive mechanism does not seem to have a big influence on the results. Indeed, for almost every test instance, the outcome measures did not return a statistically significant difference between PCS and ACS. The few exceptions to notice are for the bier127 and the pr439 instances where PCS obtain better results with regard to one or both metrics, and for the pr1002 instance where ACS outperforms PCS with respect to I - H . However, during our experiments, we observed that the difference between the average number of times that IBMOLS is launched during the search process of PCS and ACS is relatively thin. This can be explained by the fact that (i) IBMOLS takes more time to find non-dominated solutions by starting with a population of poorer quality, that is the case in PCS comparing to ACS (at least for the first launch), and (ii) a part of the runtime allocated to the algorithm is used to compute a contribution value at every step of ACS, whereas PCS devotes all of its runtime to the search process. These two aspects lead to the fact that the number of times that IBMOLS is launched is in the end, more or less balanced between both cooperative methods.

Comparison with Exact Single-objective Results. As a last step, we provide a comparison between the results found for the bi-objective RSP investigated in this paper and the ones of the single-objective RSP investigated in [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF], where both costs are summed up 6 . In order to provide optimal solutions visiting approximately 25, 50, 75 and 100% of the total number of nodes, the authors set the ring cost c ij and the assignment cost d ij between two nodes v i and v j in the following way: c ij = ⌈αl ij ⌉ and d ij = ⌈(10α)l ij ⌉ with Table 6: Algorithms comparison with respect to the I - H metric. The number in brackets denotes the average metric value for the algorithm and the instance under consideration (multiplied by 10 -3 ). For each instance, either the algorithm located at a specific row significantly dominates the algorithm located at a specific column (≻ or for a p-value less or equal to 0.01 or to 0.05, respectively), either it is significantly dominated (≺ or for a p-value less or equal to 0.01 or to 0.05, respectively), or there is no significant difference between both (≡).

I-IBMOLS SEEA PCS ACS eil51 PCS (4.751)

≡ ≡ - ≡ ACS (4.482) ≡ ≡ ≡ - st70 PCS (2.691) ≻ - ≡ ACS (2.865) ≡ ≻ ≡ - kroA100 PCS (3.738) ≡ ≻ - ≡ ACS (3.326) ≻ ≡ - bier127 PCS (3.071) ≡ ≻ - ≻ ACS (3.693) ≡ ≻ ≺ - kroA150 PCS (2.792) ≻ ≻ - ≡ ACS (2.624) ≻ ≻ ≡ - kroA200 PCS (2.247) ≻ ≻ - ≡ ACS (2.260) ≻ ≻ ≡ - pr264 PCS (1.342) ≻ ≻ - ≡ ACS (1.404) ≻ ≡ - pr299 PCS (1.277) ≡ ≻ - ≡ ACS (1.293) ≡ ≻ ≡ - pr439 PCS (0.348) ≻ ≻ - ≻ ACS (0.733) ≻ ≡ ≺ - pr1002 PCS (2.449) ≻ ≻ - ≺ ACS (0.707) ≻ ≻ ≻ -
Table 7: Algorithms comparison with respect to the I 1 ǫ+ metric. The number in brackets denotes the average metric value for the algorithm and the instance under consideration (multiplied by 10 -3 ). For each instance, either the algorithm located at a specific row significantly dominates the algorithm located at a specific column (≻ or for a p-value less or equal to 0.01 or to 0.05, respectively), either it is significantly dominated (≺ or for a p-value less or equal to 0.01 or to 0.05, respectively), or there is no significant difference between both (≡).

I α ∈ {3, 5, 7, 9}, where l ij denotes the distance between v i and v j given in the TSPLIB files. In order to give a rough idea of the results we obtained, we compare the best found scalar value as detailed above to the optimum7 found in [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF]. Additionally, we compare the best solution visiting every node we have found with the optimal TSP solution available on the TSPLIB website 8 . Table 8 gives the error ratio between the best known value and the best one we have found for every identified (single) objective and every benchmark test instance. In comparison to [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF], this ratio is always under 1.5%, and is mostly below 1% for every instance. The optimum is even found for the kroA100 and the kroA150 instances with an α = 9, and a better solution is found for the kroA200 instances with an α = 3 and an α = 9. As regards to optimal TSP solutions, our results are quite close for instances with 200 nodes or less. For larger instances, they are not quite as good, especially for the pr1002 instance, where the error ratio is close to 15%. To summarize, in comparison to single-objective optimal or near optimal results, the search methods we proposed in this paper to solve the B-RSP are quite promising with regard to the relatively small computational time available and to the size of the problem instances to be solved. Nevertheless, let us remind that the comparison is here done with the best results we obtained during the whole set of experiments we performed, and may not be as good for a single simulation run.

Discussion

Two general-purpose cooperative schemes combining SEEA and the noniterative version of IBMOLS have been designed in this section for multiobjective combinatorial optimization: a periodic one (PCS), and an adaptive one (ACS). Indeed, ACS evolves adaptively according to the search scenario and decides by itself, and on-line, when the cooperation must occur. Another benefit of ACS is the possibility of deliberately orienting the balance between evolutionary search and local search. In comparison to stand-alone metaheuristics, these two hybrid search methods statistically improve the results on a large number of RSP instances, and particularly on large-size ones. However, the efficiency difference between PCS and ACS is almost negligible. This can be explained by the fact that ACS spends, at each step, a significant time to compute whether the cooperation should occur or not. This is not the case in the frame of PCS, so that the latter devotes all of its computational time to the search process. Moreover, in comparison to single-objective approaches from the literature, the algorithms proposed in this paper for the bi-objective RSP seem to provide good-quality solutions.

Further Comments

A new multi-objective routing problem, the bi-objective ring star problem, has been investigated in this paper for the first time. It aims at locating a cycle through a subset of nodes of a graph while minimizing a ring cost, related to the length of the cycle, and an assignment cost, from non-visited nodes to visited ones. In spite of its clear bi-objective nature, this problem has always been addressed in a single-objective way, either where both costs are combined [START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF], or where one cost is regarded as a constraint [START_REF] Labbé | Locating median cycles in networks[END_REF][START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF]. As a first step, we proposed a set of four population-based metaheuristics to approximate the efficient set for the problem under consideration, namely I-IBMOLS [START_REF] Basseur | Indicator-based multi-objective local search[END_REF], IBEA [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF], NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], and SEEA, proposed here for the first time. We concluded that I-IBMOLS was the overall most competitive method, and that SEEA was a solid competitor. As a second step, we designed two general-purpose cooperative schemes between SEEA and the non-iterative version of IBMOLS for multi-objective combinatorial optimiza-tion problems. And we illustrated the contribution of these hybridization mechanisms to improve the performance of stand-alone methods.

Although the approaches proposed in this paper are already promising, a few research directions are still open. First is the possibility to improve the population initialization strategy used within every search method. Second, we pointed out that the recombination operator designed for the problem under study has a tendency to break the parent ring structures in the offspring individuals. Then, as proposed in [START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF], we could employ a traveling salesman problem heuristic to improve the ring cost of newly generated solutions. Third, given the number of mutation operators designed within the evolutionary algorithms, it would be interesting to determine the appropriate rate for each one of them in an adaptive way, such as in [START_REF] Basseur | Design of multi-objective evolutionary algorithms: Application to the flow shop scheduling problem[END_REF]. Note that the last two points could largely improve the efficiency of evolutionary algorithms, and then would be beneficial for the hybrid methods as well. Finally, we found out that SEEA was a good alternative to state-of-the-art multiobjective evolutionary algorithms when a given, relatively small, amount of computational time is available. In the future, we plan to tackle other kinds of combinatorial problems within SEEA to verify if our observations are still valid, especially for problems where more than two objectives are involved. The same remark can also be done with regard to the cooperative approaches proposed in this paper.

Figure 1 :

 1 Figure 1: An example of solution for the ring star problem.

Figure 3 :

 3 Figure 3: Recombination operator.

Figure 4 :

 4 Figure 4: Illustration of the hypervolume difference (I - H ) between a reference set Z ⋆ N and a non-dominated front approximation S (shaded area).

Figure 5 :Figure 6 :

 56 Figure 5: Illustration of the Periodic Cooperative Search (PCS).

Table 1 :

 1 Stopping criteria: runtime per simulation run.

	Instance Runtime	Instance Runtime
	eil51	20"	kroA150	10'
	st70	1'	kroA200	20'
	kroA100	2'	pr264	30'
	bier127	5'	pr299	50'

Table 2 :

 2 Parameter setting.

		I-IBMOLS	IBEA	NSGA-II	SEEA
	Instance pop. size noise rate pop. size pop. size pop.size
	eil51	20	10%	100	100	100
	st70	20	10%	50	100	100
	kroA100	30	10%	100	200	100
	bier127	30	10%	100	200	100
	kroA150	30	10%	200	200	100
	kroA200	30	10%	200	200	100
	pr264	30	20%	50	200	100
	pr299	50	10%	50	200	100

Table 5 :

 5 Stopping criteria for additional test instances. For other instances, see Table1.

	Instance Runtime
	pr439	50'
	pr1002	50'

Table 8 :

 8 Error ratio between the cost value of the best known TSP solution and the best single-objective ring cost value found in[START_REF] Labbé | The ring star problem: Polyhedral analysis and exact algorithm[END_REF] in comparison to the best value found during our experiments.

	Instance Optimal TSP solution	Optimal RSP solution [1]
			α = 3	α = 5 α = 7	α = 9
	eil51	0.67%	0.67% 0.75% 0.37%	0.69%
	st70	0.31%	0.31% 0.49% 0.56%	0.42%
	kroA100	0.08%	0.08% 0.05% 0.12%	0.00%
	bier127	0.64%	0.64% 0.34% 0.52%	0.01%
	kroA150	1.38%	1.01% 1.04% 0.17%	0.00%
	kroA200	1.22% -4.82% 1.05% 0.69% -1.55%
	pr264	2.26%	-	-	-	-
	pr299	1.72%	-	-	-	-
	pr439	4.63%	-	-	-	-
	pr1002	14.51%	-	-	-	-

To achieve this, the minimum and the maximum value of each objective function are used in order to adaptively replace each objective function by its corresponding normalized function, so that its values lie in the interval [0, 1].

We will also say that a decision vector x ∈ X dominates a decision vector x ′ ∈ X if f (x) dominates f (x ′ ).

ParadisEO is available at http://paradiseo.gforge.inria.fr.

http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

The package is available at http://www.tik.ee.ethz.ch/pisa/assessment.html.

Note that it was not possible to compare our results to the ones of the other formulation of a single-objective RSP investigated in[START_REF] Labbé | Locating median cycles in networks[END_REF][START_REF] Moreno Pérez | Variable neighborhood tabu search and its application to the median cycle problem[END_REF][START_REF] Renaud | Efficient heuristics for median cycle problems[END_REF], where the assignment cost is subject to a constraint, due to the way the bound has been fixed.

In fact, the authors imposed a time limit for their experiments. They report the best solution found so far for the instances exceeding this time limit, which is the case for the kroA200 instance with an α = 3, 5 and 9 in Table

[START_REF] Coello Coello | Evolutionary Algorithms for Solving Multi-Objective Problems[END_REF] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

Acknowledgment

A subpart of this work has already been published in [4]. The authors would like to acknowledge Matthieu Basseur and Edmund K. Burke for their helpful contribution. Furthermore, the authors are grateful for valuable discussions held with Nicolas Jozefowiez and Clarisse Dhaenens.


Florent Berthaut
email: berthaut@labri.fr

Martin Hachet
email: hachet@labri.fr

Myriam Desainte-Catherine
email: myriam@labri.fr

Piivert: Percussion-based Interaction for Immersive Virtual EnviRonmenTs

3D graphical interaction offers a large amount of possibilities for musical applications. However it also carries several limitations that prevent it from being used as an efficient musical instrument. For example, input devices for 3D interaction or new gaming devices are usually based on 3 or 6 degrees-of-freedom tracking combined with push-buttons or joysticks. While buttons and joysticks do not provide good resolution for musical gestures, graphical interaction using tracking may bring enough expressivity but is weakened by accuracy and haptic feedback problems. Moreover, interaction based solely on tracking limit the possibilities brought by graphical interfaces in terms of musical gestures. We propose a new approach that separates the input modalities according to traditional musical gestures. This allows to combine the possibilities of graphical interaction as selection and modulation gestures with the accuracy and the expressivity of musical interaction as excitation gestures. We implement this approach with a new input device, Piivert, which combines 6DOF tracking and pressure detection. We describe associated interaction techniques and show how this new device can be valuable for immersive musical applications.

INTRODUCTION

Graphical musical interfaces have several advantages over hardware controllers. They may give more meaningful visual clues about musical processes as stated by Jordà [START_REF] Jordà | Interactive music systems for everyone: exploring visual feedback as a way for creating more intuitive, efficient and learnable instruments[END_REF], for example by displaying perceptual parameters, processes' status, or even musical structures. 3D environments add even more possibilities in terms of navigation [START_REF] Rodet | Study of haptic and visual interaction for sound and music control in the phase project[END_REF], visualization, manipulation [START_REF] Mäki-Patola | Experiments with virtual reality instruments[END_REF] [START_REF] Mulder | Design of virtual three-dimensional instruments for sound control[END_REF], and immersion. In the case of multi-processes instruments, i.e instruments that handle several sound synthesis processes, this allows musicians to easily visualize and select the processes, represented by graphical objects, they want to control. One can navigate a 3D musical piece, and manipulate these audiovisual objects with a ray-casting metaphore, i.e a virtual ray going from an input device that can be aimed at 3D objects in the virtual environment.

Handheld input devices used to interact in these environments, i.e to control virtual rays, mostly rely on 3 or 6 degrees-of-freedom tracking often combined with push-buttons and joysticks. This is also the case for new gaming devices such as the Nintendo Wii remote-controller. Push-buttons or joysticks of these devices have lower resolutions than video, magnetic, or accelerometer based tracking. Thus they do not fit most musical gestures and reduce musical possibilities. For example, a push-button only outputs 0 or 1, so it cannot reproduce the dynamics of a percussion gesture. On the other hand, tracking-based graphical interaction provides sufficiently high resolution but one can not rely exclusively on it for musical interaction because of tracking accuracy problems and/or lack of haptic feedback, and interaction limitations. These limitations may explain why existing immersive instruments have not been much developed and played until now.

To overcome these issues, we propose to take inspiration from traditional musical instruments and to split 3D interaction with immersive instruments into several musical gestures, as explained in section 2. This allows us to combine advanced musical interaction, such as the applications described in [START_REF] De Laubier | Meta-instrument 3: a look over 17 years of practice[END_REF] [START_REF] Waisvisz | The hands[END_REF], with 3D graphical interaction. To explore this idea, we designed a new input device, called Piivert and described in section 3, which is based on 6DOF tracking and fine pressure sensing. Basically, with such a device, the musician will graphically select and manipulate audiovisual objects through a virtual ray metaphor, while using the pressure capabilities of the device to interact with the selected objects within fine musical controls. These interation techniques are presented in section 4.

GENERAL APPROACH

We propose to split 3D musical interaction into several categories of musical gestures, i.e gestures that musicians do when playing an instrument, following Cadoz's [START_REF] Cadoz | Musique, geste, technologie[END_REF] research. Cadoz defines selection gestures, modification gestures and excitation gestures.

Selection gestures are gestures by which musicians select instruments components, like the choice of the string on a violin. Modification gestures can be separated into structural modification gestures, which modify the structure of the instrument, and parametric modification gestures, which are also called modulation gestures. Modulation gestures modify the properties of an instrument, such as the action of the left hand on a violin or guitar. They can be discrete as with a guitar, or continuous as with a trombone. Excitation gestures directly and physically generate the sound, such as picking the string of the violin. They can be instantaneous, continuous or maintained.

We believe that separating usual 3D interaction into three gestures categories, i.e selection, excitation and modulation gestures, may improve the interaction with immersive musical applications.

Selection gestures may be done graphically, using ray-casting technique [START_REF] Bowman | An evaluation of techniques for grabbing and manipulating remote objects in immersive virtual environments[END_REF]. Hardware music controllers, equipped with rotary knobs, also allow the selection of sound components, but they have a limited range, and they do not give much information on the selected components. On the contrary, graphical interfaces give access to an infinite number of graphical elements. Each of these elements can give meaningful visual clues on their associated sound processes and their parameters. Selection gestures also require less temporal accuracy than excitation gestures. They will not be disrupted by latency or tracking problems that may occur with graphical interaction.

Modulation gestures may also be done graphically, to benefit from the numerous tweakable visual parameters of graphical elements, such as shape, 3D position, texture and so on, to modify sound processes parameters. Moreover, one may easily change between continous and discrete scales graphically, to provide both discrete and continuous modulation gestures. When gaining expertise, these modulation gestures may be done more efficiently using hardware sensors with haptic feedback.

For excitation gestures, expert modulation gestures, and other controls that require accuracy and expressivity, graphical interaction may lead to inaccuracy problems and restrict musical interaction possibilities, for example by preventing combination with other musical gestures. High-efficiency tracking systems may partially solve the problem but they usually lack haptic feedback, which is difficult to setup in virtual reality centers in which movements of users should not be constrained. This feedback is however fundamental for music as explained in [START_REF] O'modhrain | Playing by feel: incorporating haptic feedback into computer-based musical instruments[END_REF]. For excitation gestures, hardware sensors used in hardware musical controllers are better suited since they provide better sample rate and quantization, combined with passive haptic feedback. Using these sensors, musicians may be able to perform expert gestures, i.e gestures that are expressive and accurate.

There are many musical instruments and thus many existing musical gestures that can be used as these expert gestures. In a first approach to validate our concept, we chose to focus on percussion gestures. The first reason is that there is a large amount of them available. For example, in hand percussions, one can hit the drum skin at different points, scratch it or press it to modulate the pitch of the sound. The second reason is that these gestures are easy to obtain from hardware sensors [START_REF] Tindale | A comparison of sensor strategies for capturing percussive gestures[END_REF], for example pressure sensors, with low latency and high quantization.

Based on these considerations, we developed Piivert, a new input device that combines graphical interaction and percussion gestures. This device is associated to a set of new interaction techniques, which may improve interaction with immersive instruments such as the example depicted in figure 1.

PIIVERT DEVICE

Our current prototype, as presented in figure 2 is strapped to the hand. It allows comfortable manipulation of the virtual ray using the wrist, while leaving the fingers free for percussive interaction.

The 6DOF tracking is achieved using A.R Tracking DTrack 1 system. Reflective targets are fixed on the devices and detected by two infrared cameras. The data is analysed in a dedicated computer and sent to the graphical application using the VRPN protocol [START_REF] Taylor | Vrpn: a device-independent, network-transparent vr peripheral system[END_REF]. The maximum frame rate of this system is 60 fps.

As explained in section 2, graphical interaction using tracking may lead to inaccuracy and thus restrict musical possibilities. In order to keep critical gestures independent of the display process, 1 http://www.ar-tracking.de we use hardware sensors that give higher temporal accuracy. Force sensitive resistors (fsr) are used to get the percussion excitation gestures so that both pressure and hits can be detected [START_REF] Tindale | A comparison of sensor strategies for capturing percussive gestures[END_REF]. Sensors are placed under the thumbs, index fingers, middle fingers and ring fingers of each hand. The little finger is not used because it appears to be less easily usable for percussion gestures. The acquisition is done with an Interface-Z2 sensor board which transmits the values to a soundcard using Musical Instrument Digital Interface (MIDI) messages. The current prototype, as it can be seen in figure 2, is linked to a box that embeds the batteries and the sensor board. This box is hooked on the user's belt so that only one MIDI cable goes from the musician to the soundcard. The Interface-Z sensor board can be configured to send up to 1500 samples per second for all sensors. If the eight sensors are used simultaneously, this gives approximatively 187 samples per second, thus a latency of 5ms. Each data sample is 12 bits wide, i.e 4096 values, and it is obtained by mixing two 7 bits MIDI Control Change messages. The sensor board is connected to an external usb sound card, and MIDI messages are transmitted to the audio application using the ALSA MIDI driver and sequencer.

The complete setup of an example immersive musical application using our device can be seen in figure 3.

PIIVERT INTERACTION TECHNIQUES

We developed a set of interaction techniques associated with Piivert. These techniques combine percussion gestures that we get from the fsr sensors and graphical interaction.

Percussion gestures for excitation and control gestures

Percussion gestures are extracted from fsr sensors values. We first identify low-level gestures and then their combinations in higherlevel gestures. In our current implementation, each gesture is sent to a callback function as a piivert event * containing the type of the event, the finger(s) used and the value of the event.

Low-level percussion gestures

From the acquired data for each fsr sensor, i.e each finger, we can extract three low-level percussion gestures. The first one is the hit gesture, defined as piivert event hit. It is detected as a jump in the fsr sensor's values from 0 to at least 100 in less than 50ms. These threshold values were defined empirically after some testing. The value of the hit, i.e the velocity, is the first maximum following the jump. The second kind of gestures are pressure gestures. These are detected as any slow variation of fsr sensors' values. For example, they appear when sensors' values raise from 0 but do not reach the hit threshold fast enough. They are also detected as the non-zero values of a sensor following a hit gesture, typically when the user keeps pressing the sensors after having hit it. During a pressure gesture every value of the sensor is sent with a piivert event pressure event. Finally, a piivert event release is detected when the sensor's value gets back to 0, after a hit or pressure gesture. The value of the release gesture is the last non-zero value. We use a simple notation to describe these simple gestures, to make them more understandable. This results in a score for interaction gestures, which is depicted in figure 4. These low-level gestures may each be used for different excitation gestures. For example, hit gestures may play sound files associated to 3D audiovisual objects, loudness of the sounds being set by gestures' values. Pressure gestures may be used to control granular synthesis, which consists in reading short "grains" of the sound file in random order, with grains' positions set by gestures' value. Moreover, each finger can be associated to different sound synthesis parameters.

High-level percussion gestures

High-level gestures can be detected as combinations of low-level gestures. These gestures allow us to trigger various actions such as changing the musical samples being used, or controlling musical sequences. The maximum time difference between two low-level gestures, so that they are not only understood as two low-level gestures, but also as part of a higher-level gesture, is 50 ms. In our current implementation, three high-level gestures are defined. The piivert event flam corresponds to a short sequence of two piivert event hit, which is known as a "flam". A short sequence of three piivert event hit, which is also known as a "three strikes roll", will be identified as a piivert event roll3.

Finally, a piivert event roll4 will be sent when a sequence of four piivert event hit, called a "four strikes roll", is detected. Examples of these high-level gestures are shown in figure 4.

Actions triggered by these high-level gestures integrate well with low-level gestures since they are also percussion gestures. They may thus be inserted in rythms, which may result in smoother and faster interaction after some practicing. One must also note that, in contrast to events triggered by simple buttons, high-level gestures have several usable parameters. First of all, the fingers used to make a gesture are identified so that one can make a distinction between a piivert event flam with the ring finger before the middle finger, and a piivert event flam in the other way. Each different fingers combination for each gesture may then be assigned to a different action. Bimanual gestures can thus be easily defined to get more meaningful actions, or to allow faster gestures sequences. These percussion gestures all have velocity, defined as the value of its last low-level gesture, and duration parameters, which may bring additional arguments for various actions, or add possibilities for musical interaction. An example of use for these parameters is that one may start an animation of some sound parameters with a flam, the velocity controlling the speed of the animation, and stop it using a flam in the other direction.

The velocity parameter of a high-level gesture is still 12 bits wide. The duration parameter of a gesture is between 10 and 50 ms for a piivert event flam, between 20 and 100 ms for a piivert event roll3, and between 30 and 150 ms for a piivert event roll4.

Beside the three high-level gestures defined above, one can also use combinations of low-level gestures. For example, simultaneous piivert event pressure and piivert event hit are similar to what can be done with many percussions, when musicians press the drum head to modify its tension and thus change the pitch of the sound while playing.

Graphical interaction for selection and modulation gestures

Selection gestures are performed graphically, using the ray-casting technique. Musicians manipulate two virtual rays, one in each hand, as bimanual gestures are common in musical instruments. The ray-casting technique is known to be very simple to use, and very efficient for fast selection of near objects in virtual environments [START_REF] Poupyrev | Egocentric object manipulation in virtual environments: Empirical evaluation of interaction techniques[END_REF]. By using this technique for selection gestures, one can directly point 3D graphical elements corresponding to sound processes, i.e audiovisual objects.

Because playing musical sequences may require to quickly select small objects distant from each other, one may need to perform very fast and large movements while keeping good temporal and spatial accuracy. Our implementation uses software aids to improve these selection gestures.

First we define larger bounding boxes for the audiovisual objects to be selected, as depicted on figure 5. Smaller movements are then needed to select the objects, because musicians do not have to point exactly on the objects. Another possible strategy is to divide the entire virtual environment according to the audiovisual objects. Hence the closest object to the virtual ray is automatically selected. A third method to minimize movements and improve efficiency of selection gestures is to snap the virtual ray to the closest object as proposed in [START_REF] De Haan | Intenselect: Using dynamic object rating for assisting 3d object selection[END_REF].

With our current prototype, hit gestures may induce virtual ray jittering. This results in possible loss of the selected object. To overcome this ergonomic limitation, ray's movements are low-pass filtered when an audiovisual object is being played. This approach is similar to the anisomorphic ray-casting technique proposed in [START_REF] Andujar | Virtual environments: Anisomorphic ray-casting manipulation for interacting with 2d guis[END_REF].

In addition to these techniques, we use another method to adapt ray-casting to musical interaction, the vibrating ray. When excitation gestures are performed to excite the audiovisual objects, vibrations are displayed as propagating on the virtual ray. This visual feedback improves the integration of musical gestures in the immersive environment. The vibrating ray can be seen in figure 5.

Playing very fast musical sequences using one virtual ray requires some training even when using the techniques described above. To facilitate musical interaction, we can take advantage of the fact that there is a fsr sensor for each finger on Piivert. We propose to split the virtual ray into two or three sub-rays, and to assign them to the fingers, so that they can be excited separately. Musicians can enter a selection mode, and select up to three objects with one ray. When re-entering any of the selected objects, the ray is then split accordingly, each sub-ray grabbing one object, as seen in figure 5. For example, if the ray is split in three, the index, middle and ring fingers may grab three selected audiovisual objects, that may respectively be associated to snare, kick and hi-hat sounds. Performing hit gestures with the sensors of those three fingers then allows to easily play drums rythms. This split ray technique allows us to select any group of two or three audiovisual objects of the environment, and to excite each of them easily, as one would do with a keyboard. After one has selected an audiovisual object, he may grab it using a low-level pressure gesture with the thumb. Modulation gestures can then be defined as manipulation of the 3D objects, with different mappings. For example, position on the z-axis can be associated to the amplitude of the sound process, so that moving the object away reduces its volume. Position on the x and y axes may be respectively associated to sound processes' panning and pitch. One may also graphically modify other parameters of the audiovisual object, such as color hue, transparency, 3D shape. All these graphical parameters can be mapped to different musical parameters.

With Piivert it is possible to "excite" audiovisual objects with low-level gestures while performing these modulation gestures. This is similar to what one would do on a guitar by picking a string and sliding a finger on this string at the same time. Combined with the split ray technique described above, this allows us to trigger and modulate simultaneously up to three 3D audiovisual objects with each hand, as depicted on figure 5. This is almost impossible to do, or at least far less versatile with hardware musical instruments, as the selection and modulation of multiple objects is made possible by the graphical interaction.

CONCLUSION

In this paper, we presented a new input device, Piivert, and associated interaction techniques for immersive instruments. They rely on the separation of 3D interaction into musical gestures categories, i.e selection gestures, modulation gestures, and excitation gestures. This allows us to combine the possibilities of graphical interaction with the accuracy and expressivity of musical controls, here percussion gestures.

The work presented in this paper validates the foundations of a new approach for efficient musical interaction in immersive virtual environments. In the future, we want to push this concept more in depth. For example, we plan to improve the interaction techniques by first taking into account additional parameters, such as all finger velocities and velocity range in high-level events, and by allowing other high-level events. The device has also shown some ergonomic limitations which could be overcome using different materials and mechanisms. Numerous other directions are still to be explored.

Piivert has been developed for musical needs. However, we are convinced that such an approach may be valuable in other contexts, where efficiency and accuracy are required. This is the case for applications where time plays an important role, such as interactive simulations, visual performances and video games. Beyond efficiency and accuracy, we think that our approach opens new directions for interaction with 3D content. Indeed, the classical hardware buttons or software widgets that are currently used to control the system could be replaced by high-level gestures. The high-level parameters described in section 4.1.2 can add semantic links between the performed gestures and the corresponding graphical actions. We believe that such a percussion-based interaction have an interesting potential for future interactive applications.

Figure 1 :

 1 Figure 1: Immersive musical application using Piivert.

Figure 2 :

 2 Figure 2: Current prototype.

Figure 3 :

 3 Figure 3: Immersive musical application setup.

Figure 5 :

 5 Figure 5: Split ray and vibrating ray techniques.

http://www.interface-z.com/