Boris Bontoux
email: boris.bontoux@univ-avignon.fr

Christian Artigues
email: artigues@laas.fr

Dominique Feillet
email: feillet@emse.fr

A Memetic Algorithm with a Large Neighborhood Crossover Operator for the Generalized Traveling Salesman Problem

Keywords: Genetic Algorithm, Traveling Salesman Problem, Large Neighborhood

The Generalized Traveling Salesman Problem (GTSP) is a generalization of the well-known Traveling Salesman Problem (TSP), in which the set of cities is divided into mutually exclusive clusters. The objective of the GTSP consists in visiting each cluster exactly once in a tour, while minimizing the sum of the routing costs. This paper addresses the solution of the GTSP using a Memetic Algorithm. The originality of our approach rests on the crossover procedure that uses a large neighborhood search. This algorithm is compared with other algorithms on a set of 54 standard test problems with up to 217 clusters and 1084 cities. Results demonstrate the efficiency of our algorithm in both solution quality and computation time.

Introduction

In this paper, we propose a solution method for the Generalized Traveling Salesman Problem (GTSP) based on a Memetic Algorithm (Genetic Algorithm plus Local Search, see [START_REF] Moscato | A Gentle Introduction to Memetic Algorithms[END_REF] or [START_REF] Hart | Recent Advances in Memetic Algorithms[END_REF] for further details). The GTSP is a generalization of the well-known Traveling Salesman Problem (TSP). The main contribution of the paper stands in the crossover operator based on the exploration of a large neighborhood around the father and mother individuals.

The GTSP can be described as follows. Let G = (V, E) be a complete undirected graph, V = {v 1 , . . . , v n } a set of cities and W = {W 1 , . . . , W m } a set of clusters, with 0 < m ≤ n. Each city v i ∈ V belongs to exactly one cluster (note that from this definition the clusters are mutually disjoint). Let c ij denote the routing costs for v i , v j ∈ V . The objective is to find a tour visiting exactly once each cluster while minimizing the sum of the routing costs. In this work, we only consider symmetric cost matrices (c ij = c ji ), but the algorithm could easily be generalized to the asymmetric case. In particular, the crossover operator can be indifferently applied on symmetric or asymmetric instances.

The GTSP is NP-hard in the strong sense since it generalizes the TSP. Indeed, the special case where m = n (a city per cluster) is a TSP: the problem resorts to find a tour visiting each city at a minimum cost.

In Section 2, we review the literature on the GTSP. Section 3 presents a new Memetic Algorithm developed for the GTSP. The main characteristic of this algorithm is its Large Neighborhood Search crossover procedure (see [START_REF] Ahuja | A survey of very large-scale neighborhood search techniques[END_REF] for a recent work on Large Neighborhood Search techniques). Section 4 provides a computational evaluation of our algorithm through benchmark instances from the GTSPLIB [START_REF] Reinelt | TSPLIB -A Traveling Salesman Problem Library[END_REF].

State of the art

The GTSP was first introduced by Srivastava et al. [START_REF] Srivastava | Generalized Traveling Salesman Problem through n sets of nodes[END_REF] and Henry-Labordere [START_REF] Henry-Labordere | The record balancing problem : A dynamic programming solution of a generalized traveling salesman problem[END_REF], each one proposing to solve it through dynamic programming. Laporte and Norbert [START_REF] Laporte | Generalized Travelling Salesman Problem through n Sets of Nodes : An integer programming approach[END_REF] and Laporte et al. [START_REF] Laporte | Generalized Travelling Salesman Problem through n Sets of Nodes : the Asymmetrical Case[END_REF] developed integer programming formulation, permitting to solve exactly the GTSP with Branch & Bound techniques. More recently, an efficient Branch & Cut solution scheme was proposed by Fischetti et al. [START_REF] Fischetti | A Branch-and-Cut algorithm for the Symmetric Generalized Traveling Salesman Problem[END_REF], who provide optimal solutions for instances with up to 89 clusters and 442 cities.

Many attempts have been done to transform efficiently the GTSP into the TSP [START_REF] Lien | Transformation of the Generalized Traveling-Salesman Problem into the Standard Traveling-Salesman Problem[END_REF][START_REF] Noon | An Efficient Transformation of the Generalized Traveling Salesman Problem[END_REF][START_REF] Dimitrijevic | An Efficient Transformation of the Generalized Traveling Salesman Problem into the Traveling Salesman Problem on Digraphs[END_REF][START_REF] Laporte | Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem[END_REF][START_REF] Ben-Arieh | Transformations of generalized ATSP into ATSP[END_REF]. Some of the resulting TSP instances have nearly the same number of nodes as the original GTSP instances. Moreover, some transformations of the GTSP into the TSP [START_REF] Noon | An Efficient Transformation of the Generalized Traveling Salesman Problem[END_REF] have an important property: an optimal solution to the related TSP can be converted to an optimal solution to the GTSP. Unfortunately, a feasible non-optimal solution for the TSP may be not feasible for the GTSP. Furthermore, well-known heuristics for the TSP may not perform well for the GTSP.

Two approximation algorithms have been published for the GTSP. Slavík [START_REF] Slavík | On the approximation of the generalized traveling salesman problem[END_REF] presented a 3ρ/2-approximation algorithm for the GTSP, where ρ is the number of cities in the largest cluster (ρ = max i=1,...,m (| W i |). Unfortunately, the worst-case bound may be relatively weak, as ρ may be quite large. Garg et al. [START_REF] Garg | A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem[END_REF] proposed an approximation algorithm for the group Steiner tree problem, which provided an O(log 2 (n) log(log(n)) log(m))-approximation algorithm for the GTSP. In both cases, the triangle inequality must be satisfied.

In [START_REF] Noon | A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem[END_REF], Noon proposed several heuristics, including an adaptation of the nearest-neighbor heuristic developed for the TSP. Similar adaptations have been implemented by Fischetti et al. [START_REF] Fischetti | A Branch-and-Cut algorithm for the Symmetric Generalized Traveling Salesman Problem[END_REF], such as farthest-insertion, nearest-insertion and cheapest-insertion. More recently, Renaud and Boctor [START_REF] Renaud | An Efficient Composite Heuristic for the Symmetric Generalized Traveling Salesman Problem[END_REF] proposed an heuristic called GI 3 (Generalized Initialization, Insertion and Improvement), which is a generalization of the I 3 heuristic presented in [START_REF] Renaud | A fast composite heuristic for the symmetric traveling salesman problem[END_REF] for the TSP. This heuristic consists of three phases: an initialization during which a partial tour is constructed, an insertion phase which completes the tour by inserting at the cheapest cost cities from unvisited clusters and an improvement phase based on 2-opt and 3-opt moves between clusters, called here G2-opt and G3-opt.

The authors also explain how the cheapest sequence of cities visiting the set of clusters in a given order can be determined in polynomial time. They present a procedure called ST algorithm (for Shortest Tour). [START_REF] Snyder | A Random-Key Genetic Algorithm for the Generalized Traveling Salesman Problem[END_REF] proposed to solve the GTSP with a Genetic Algorithm using a random-key encoding which assures that solutions constructed by crossover or mutations are feasible. The Genetic Algorithm was coupled with local search improvement, namely a swap procedure and a 2-opt neighborhood search, yielding a Memetic Algorithm. Computational results show the efficiency of their algorithm, in terms of solution quality and computation time. A Particle Swarm Optimization based algorithm was also recently developed by Shi et al. [START_REF] Shi | Particle swarm optimization-based algorithms for TSP and generalized TSP[END_REF].

Snyder and Daskin

Finally, Silberholz and Golden [START_REF] Silberholz | The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach[END_REF] very recently proposed a Genetic Algorithm with several new features, including isolated initial populations and a new reproduction mechanism, based upon the TSP ordered crossover operator. This new mechanism was called mrOX, for modified rotational ordered crossover.

Local improvement procedures combined with this mechanism, yielding again a Memetic Algorithm, permit to obtain very good results on large new instances. This algorithm can be considered as the most competitive algorithm published to date.

A new Memetic Algorithm

A Genetic Algorithm is a search technique widely used to find approximate solutions of optimization problems (see, e.g., [START_REF] Vose | The Simple Genetic Algorithm: Foundations and Theory[END_REF][START_REF] Man | Genetic Algorithms: Concepts and Designs[END_REF][START_REF] Winter | Genetic Algorithms in Engineering and Computer Science[END_REF]). Genetic Algorithms are categorized as metaheuristics and are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover. Genetic Algorithms maintain a large number of solutions during the solution process. The set of solutions is called the population. Each solution is called an individual. At each iteration of a Genetic Algorithm, a new population is generated using several operators: reproduction, crossover and mutation.

Genetic algorithms paired with local search techniques are categorized as

Memetic Algorithms [START_REF] Hart | Recent Advances in Memetic Algorithms[END_REF][START_REF] Moscato | A Memtic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems[END_REF][START_REF] Moscato | A Gentle Introduction to Memetic Algorithms[END_REF]. In this section, we present a new Memetic Algorithm. We particularly insist on the crossover operator, which is our main contribution. Moreover, to clearly evaluate the impact of this operator, we voluntarily adopt a very standard implementation for the rest of the algorithm. Each individual (a solution of the problem) is represented by an ordered list of clusters, where the first and last clusters are identical. From this representation, a city tour can be derived, defined as the optimal tour maintaining the visiting order of clusters. The cost of the individual is the cost of this city tour. It is obtained using the Shortest Tour algorithm developed by Renaud and Boctor [START_REF] Renaud | An Efficient Composite Heuristic for the Symmetric Generalized Traveling Salesman Problem[END_REF].

The principle of the Shortest Tour algorithm is the following. A succession of clusters defines a sequence of sets of cities, where cities from one cluster can only be attained from cities belonging to the preceding cluster. Representing cities by nodes, we obtain a directed acyclic graph. In this graph, the subset of paths having identical starting and ending nodes exactly corresponds to the set of GTSP solutions respecting the order defined by the cluster sequence. The best of these solutions coincides with the shortest path of this subset. Seeing that calculating the shortest path in an acyclic graph can be done in polynomial time with a simple recursion, the best city tour can easily be obtained. One just has to successively consider each city of the first (and last) cluster and compute the shortest path constrained to start and end with this city. The optimal city tour is the best path found during this process. The Shortest Tour procedure is computationally cheap and, consequently, can be called very often (more precisely, its complexity is O(n 3 /m 3 ) -see [START_REF] Renaud | An Efficient Composite Heuristic for the Symmetric Generalized Traveling Salesman Problem[END_REF]).

Initial population

Our initial population contains N individuals. Individuals are constructed through randomly generated cluster lists. The Shortest Tour algorithm is applied to determine the optimal city tour and the cost for each individual. In order to avoid symmetries, the first (and last) cluster is identical for all individuals; in order to limit the computation time of the Shortest Tour procedure, the cluster containing the fewest cities is chosen.

Population renewal

At each generation, two individuals are randomly chosen through Roulette Wheel Selection and paired for crossover. These two parents breed two children. This operation is repeated k times. The children are then added to the population and only the N best individuals are kept. A mutation procedure is applied to improve the population diversity and avoid premature convergence. Each individual has a probability µ of being selected for mutation (in our experiments µ = 0.05). The mutation consists in swapping two randomly chosen clusters and applying the Shortest Tour algorithm to compute the optimal city tour and the new individual cost. The heuristic stops when N 1 generations have been computed or when no improvement has been performed during N 2 generations.

Memetic Algorithm

The proposed Memetic Algorithm associates all the elements described above, plus the crossover operator and the local search procedures presented in the next sections. Figure 1 presents a synthetic view of the algorithm.

Crossover operator

The crossover operator is very important in a Genetic or a Memetic Algorithm. This operator allows constructing new solutions from existing solutions and plays a great part in the behavior of the algorithm.

A crossover, or reproduction, is the equivalent of two parents mating and producing two children. These children bear a resemblance to each parent.

Several crossover operators have been proposed for the TSP or for TSP-like problems: e.g., the maximal preservative crossover (MPX, [START_REF] Mühlenbein | Evolution algorithms in combinatorial optimization[END_REF]) or the modified rotational ordered crossover (mrOX) proposed by Silberholz and Golden [START_REF] Silberholz | The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach[END_REF].

A comparison of different crossovers used for the TSP is presented in [START_REF] Tsai | Some issues of designing genetic algorithms for traveling salesman problems[END_REF].

The crossover procedure we propose here is inspired from the dropstar procedure used in Bontoux and Feillet [START_REF] Bontoux | Ant Colony Optimization for the Traveling Purchaser Problem[END_REF]; shortly, in that paper, the context was the solution of the Traveling Purchaser Problem and dropstar was used as a local search operator determining the best subsequence from a sequence of cities.

It is noteworthy saying that this operator is also inspired from the algorithm used by Prins in [START_REF] Prins | A simple and effective evolutionary algorithm for the VRP[END_REF].

Let W i ′ 1 , . . . , W i ′ m and v i1 , .
. . , v im respectively be the cluster tour and the derived city tour of an individual, called the father. Let W j ′ 1 , . . . , W j ′ m and v j1 , . . . , v jm respectively be these tours for another individual, called the mother.

A new individual -a child -is built by the following procedure. Note that once a child has been constructed, the roles of the two parents are reversed and a second child is obtained using the same procedure.

Every city of the mother individual is progressively inserted into the father city tour. The order in which cities are inserted is the order of the mother city tour. We determine the insertion position of a city v j k as follows: we consider every insertion position of v j k between cities v i l and v i l+1 of the father such that

W i ′ l = W j ′ k and W i ′ l+1 = W j ′
k (thus avoiding that two identical clusters follow); among these possibilities, the one minimizing insertion cost

c i l j k +c j k i l+1 -c i l i l+1 is chosen.
Once every city of the mother individual is inserted, we derive a cluster sequence in which every cluster appears twice. This sequence is called the redundant-sequence. The next step is to determine an optimal feasible subsequence, i.e., where every cluster is visited exactly once.

The search is computed through a dynamic programming algorithm, applied to a graph obtained from the redundant-sequence. This graph is built by the following procedure. A vertex is inserted for every city of every cluster, once for every appearance of the cluster in the sequence. Basically, an arc is added for every pair of vertices issued from different cluster position in the sequence, in the direction of the sequence (see Figure 1 for an aggregated vision of the graph and Figure 2 for an extract of the real graph). Some graph reductions will however be defined subsequently (see Section 3.3). The objective is to find the shortest path in the graph between the two extreme clusters, with the constraints that every cluster must be visited exactly once and that the solution must be a cycle.

Before giving more details on the dynamic programming algorithm, let us illustrate the behavior of this crossover operator on a simple example. Consider a set of clusters W = {W 1 , . . . , W 5 }. The father and mother cluster tours are:

father: W 4 W 3 W 1 W 5 W 2 W 4 mother: W 4 W 1 W 3 W 5 W 2 W 4
The insertion procedure defines a redundant-sequence of clusters of the form:

child: W 4 W 1 W 3 W 1 W 5 W 2 W 3 W 2 W 5 W 4
where the clusters from the father node are underlined and the insertion positions are defined using the city tours of the individuals.

The graph represented by Figures 1 and2 is then implicitly defined. From this graph, the dynamic programming algorithm determines an optimal city tour, from which the cluster sequence defining the new individual is derived.

The implementation of this algorithm is detailed in Section 3.3.

The main advantage of this operator is to span a very large solution space.

Indeed, the number of feasible cluster subsequences of the redundant-sequence is O(2 m ). Furthermore, for a given subsequence, the number of city tours is O((n/m) m ) (it can be easily seen that the largest space is obtained when every cluster has the same size n/m). As a consequence, the solution defined by the crossover operator is the best among O(2 m (n/m) m ) solutions. In our sense, it both allows high diversification and populations of good quality. However, of course, the price to pay is a high computation cost compared to classic crossover operators. The objective of this work is to evaluate whether this price is worth being paid or not.

W 4 W 1 W 3 W 1 W 5 W 2 W 3 W 2 W 5 W 4

Detailed implementaion of the crossover operator

Dynamic programming algorithm

The dynamic programming algorithm used to find the shortest path in the graph defined in the previous section is inspired from the algorithm developed in Feillet et al. [START_REF] Feillet | An exact algorithm for the Elementary Shortest Path Problem with Resource Constraints: application to some vehicle routing problems[END_REF] for the Elementary Shortest Path Problem with Resource Constraints. This algorithm is an extension of the classical Bellman's labelling algorithm [START_REF] Bellman | Dynamic programming[END_REF]. Our algorithm starts with initial labels associated to every vertex of the first cluster. Labels are then extended iteratively with the constraint that every cluster has to be visited exactly once. This constraint is treated like the elementary path constraint in [START_REF] Feillet | An exact algorithm for the Elementary Shortest Path Problem with Resource Constraints: application to some vehicle routing problems[END_REF]. The graph being acyclic, extending the labels in the topological order of the vertices provides the optimal path.

In the following, we denote each label by L = (C, δ 1 , . . . , δ m ), where C is the cost of the partial path represented by L and δ i ∈ {0, 1} indicates whether cluster W i is present in the path or not. The extension of a label through an arc is feasible when δ i = 0 for the cluster W i of the destination city, except when this cluster is the last cluster of the sequence. In this case, the feasibility conditions are that the destination city is the first city of the partial path and

that δ i = 1 for 1 ≤ i ≤ m.
A label L 1 dominates a label L 2 , which is noted L 1 < L 2 , when the two partial paths represented by these labels lead to the same vertex and one can be sure that any extension of L 1 is going to be cheaper than the identical extension for L 2 . Here,

L 1 < L 2 when C 1 ≤ C 2 , δ 1 i ≥ δ 2 i for 1 ≤ i ≤ m
and the first and last cities of the two partial paths are identical. Under these conditions, L 2 can be deleted.

Lower bound

Every time a new label L = (C, δ 1 , . . . , δ m ) is extended, a lower bound on the cost of any path that could be obtained from this label, is computed. This lower bound is compared with an upper bound initially defined as the value of the father. This upper bound is valid seeing that the city tour of the father exists in the graph. The upper bound is updated each time a new best solution is found by the algorithm. When the lower bound is greater than the upper bound, L is deleted.

The lower bound LB(L) is given by the following formula:

LB(L) = C + {1≤j≤m,δj =0} C lj
where l is the position in the redundant-sequence of the cluster to which L has just been extended and C lj is the minimal cost incurred by the future visit of cluster W j .

C lj is computed as the minimum arc cost among arcs whose:

1. destination is one of the cities of the last occurence of W j in the redundantsequence, 2. origin is one of the cities located between the cluster in position l (included) and the last occurence of W j in the redundant-sequence.

Values C lj are computed in a pre-processing phase, as soon as the redundantsequence is set, for every position l of the sequence and for every cluster W j .

The time complexity of this computation is O(nm).

Note that, it might happens that the last occurence of W j precedes position l. In this case C lj is set to a large value and the label is automatically deleted if δ j = 0 since cluster W j is unreachable.

Graph reduction

Since every cluster has to be visited, edges skipping all occurrences of a cluster can be removed. Moreover, two occurrences of a cluster do not need to be connected. Finally, a cluster only needs to be connected to the first occurrence of any other cluster located after him in the redundant-sequence.

Heuristic speed-ups

In order to limit the time consumed by the crossover operator, we have implemented two simple heuristic speed-ups. Limitation of the size of the label lists. Throughout the dynamic programming algorithm, a list of labels is associated with every city. Despite the dominance rule, these lists may be significantly long. The purpose here is to limit their size. A unique limit is set (100 in our experiments). An evaluation rule is defined to determine which labels should be removed when the size of a list exceeds the limit. The labels removed are those with the greatest evaluations. The evaluation eval(L) of a label L = (C, δ 1 , . . . , δ m ) is:

W 4 W 1 W 3 W 1 W 5 W 2 W 3 W 2 W 5 W 4
eval(L) = C + U B 0 {1≤j≤m} C 1j {1≤j≤m,δj =0} C lj
where U B 0 is the cost of the father individual and l is the position of the label in the redundant-sequence. {1≤j≤m} C 1j is the lower bound cost of an empty label (whose cost is equal to 0), {1≤j≤m,δj =0} C lj is the lower bound of the extension of the label L towards the clusters which have not been visited yet. The formula aims to balance the actual cost of the label and an evaluation of the extension cost (as proposed in Section 3.3.2). The two terms are normalized so that the evaluations of an initial label (with a cost equal to 0) and of the label corresponding to the father city tour have an identical value U B 0 .

Reduction of the clusters. The purpose here is to limit the size of the graph, by removing some cities from the different clusters. A measure is defined to evaluate the attractiveness of a city. The less attractive cities are removed for each cluster of the redundant-sequence. The measure quantifying the interest of city v k of the cluster at position l of the sequence is:

eval(k, l) = vi∈Γ -(l) vj ∈Γ + (l) c ik + c kj -c ij
where Γ -(l) (respectively, Γ + (l)) is the set of cities belonging to the two clusters preceding (respectively, following) position l in the redundantsequence. This measure gives a tendency on the insertion cost of city v k in a solution. Based on this measure, the maximum size of a cluster W i is set to ⌈|W i | ρ ⌉, where ρ is a parameter (0.8 in our experiments). Note that with this formula the percentage of cities removed from a cluster increases with its size.

Complexity of the dynamic programming algorithm

It is interesting to note that the algorithm described in section 3.3.1 does not achieve a polynomial time complexity. The objective of this section is to give some more insights into this complexity. In this analysis, we do not consider the two heuristic speed-ups described above.

A state is defined for every vertex of the graph and for every value of re- One can deduce that the worst case complexity of the algorithm is O(n 2 m2 2m ).

Obviously, one can expect that the number of operations is significantly reduced in practice. Note also that with the limitation of the size of the label lists, the complexity becomes O(n 2 m).

Local search heuristics

The local search procedures presented here are applied in order to improve the quality of the individuals, both for the initial population and for every new child obtained from crossover. We first present the set of local search operators included in the Memetic Algorithm and then explain how they are managed.

2-opt

This procedure is well-known in the context of the TSP (see [START_REF] Lin | Computer solutions of the traveling salesman problem[END_REF] for more details). A 2-opt move consists in choosing two arcs in the city tour, permuting the circulation between the ending vertices of these arcs and reconnecting the tour. The complexity of a move is O(m 2 ) where m is the number of clusters.

2-opt moves are repeated as long as improvements are achieved.

3-opt

Similar to the 2-opt, the 3-opt (presented also in [START_REF] Lin | Computer solutions of the traveling salesman problem[END_REF]) chooses three arcs in the tour and de-interlace the path between the ending cities of these arcs. The complexity of the procedure is O(m 3 ). Again, moves are repeated as long as improvements are achieved.

Lin-Kernighan

The Lin-Kernighan algorithm [START_REF] Lin | An Effective Heuristic Algorithm for the Traveling-Salesman Problem[END_REF] is one of the best heuristics for Euclidean Traveling Salesman Problems. Briefly, it involves swapping pairs of subtours to make a new tour. It is a generalization of 2-opt and 3-opt We use the implementation of this heuristic available on the Concorde website1 .

Move

The Move operator considers the cluster sequence of the individual, selects a cluster and determine the best position for this cluster in the sequence. This move is applied once for every cluster. To determine the best position for a given cluster W i , a redundant-sequence is created where W i is first removed and then re-inserted between every pair of clusters. The dynamic programming presented in Sections 3.2 and 3.3 is then applied to recover the best feasible city tour.

The Move operator can be illustrated with the following example. Let W 4 W 3 W 1 W 5 W 2 W 4 be the cluster tour of an individual. When applying the

operator to cluster W 1 , redundant-sequence W 4 W 1 W 3 W 1 W 5 W 1 W 2 W 1 W 4
is obtained. A best city tour is then computed in the corresponding graph (see Figure 4). (computed as explained in Section 3.2 for the crossover operator). In the dynamic programming algorithm a label L is defined by a pair (C, δ i ). The number of states is thus O(n) and the complexity of the procedure is O(nm).

W 4 W 1 W 3 W 1 W 5 W 1 W 2 W 1 W 4

Control of the local search operators

The call to the previous operators is controled in the following fashion.

When a new individual is introduced into the population during the initialization phase, 2-opt, 3-opt and Lin-Kernighan procedures are successively applied, in this order.

When a new child is computed with the crossover operator, one of the two following local search schemes is applied with a probability 0.5:

• apply 2-opt, 3-opt and Move, in this order,

• apply Lin-Kernighan. Table 1 shows that, with 5 attempts, 41 instances out of 41 are optimally solved and that for 37 of these instances, the optimal solution is found at each run of the Memetic Algorithm. The difference between the best and the worst solution returned from the 5 trials always remains small (never exceeding 0.75%), which tends to indicate that our algorithm is robust.

For larger instances, the table shows that the mean results of our algorithm outperform the best known averaged solutions for 10 instances out of 13. For 3 instances, solutions are even improved by our worst result. In the worst case, the results produced by our algorithm never exceeds a gap equal to 0.66% with the best known averaged results, which confirms the robustness of the algorithm.

Table 2 presents our best results within five trials for twelve instances for which the best known averaged solution value is improved. In order to measure more precisely the efficiency of the crossover procedure proposed in this paper, we have also implemented a simpler and more classic crossover procedure, namely the one-point crossover (Goldberg [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]). The parameters are left unchanged for both crossover procedures. Table 3 compares these crossovers and the results of our algorithm without the mutation operator.

In this table, the crossover based on large neighborhood search is called LNS crossover and our algorithm without the mutation operator "LNS w/o Mutation". The results presented are the mean results obtained through 5 attempts for each instance. The column headings are as follows:

• instance: the name of the test problem;

• best: the optimal objective value when known or the best known averaged solution value;

• gap: the mean gap of the algorithm above the optimal solution or the best known averaged solution (percentage);

• CPU: the CPU time in seconds. The LNS crossover shows a significant advantage in solution quality over the one-point crossover. For the smaller instances (for which the optimal solution is known), the average gap of the one-point crossover is equal to 0.26%, whereas the average gap is reduced to 0.02% with the LNS crossover. The runtimes of the algorithms using the LNS crossover and the one-point crossover are however significantly different, the one-point crossover being six times faster.

For larger instances, the LNS crossover produces much better solutions than the one-point crossover, keeping the same differences between runtimes. The mutation operator permits to avoid premature convergence.

Table 4 finally compare our algorithm LNS (for one trial) with the mean results of our algorithm LNS (through 5 attempts), the Genetic Algorithm mrOX proposed by Silberholz and Golden [START_REF] Silberholz | The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach[END_REF], the Memetic Algorithm from Snyder

and Daskin [START_REF] Snyder | A Random-Key Genetic Algorithm for the Generalized Traveling Salesman Problem[END_REF], the GI 3 algorithm of Renaud et al. [START_REF] Renaud | An Efficient Composite Heuristic for the Symmetric Generalized Traveling Salesman Problem[END_REF] and the Branch & Cut algorithm from Fischetti et al. [START_REF] Fischetti | A Branch-and-Cut algorithm for the Symmetric Generalized Traveling Salesman Problem[END_REF]. These comparisons are only given for the instances where the optimal solution is known.

The results have been obtained on the following computers:

• mrOX and Snyder and Daskin: Pentium IV 3.0 GHz processor and 1 GB RAM.

• GI 3 : Sun Sparc Station LX.

• B& C.: HP 9000/720.

For each algorithm, two columns are presented in the table:

• gap: the mean gap of the algorithm above the optimal solution (percentage);

• CPU: the CPU time in seconds.

The average behavior of the different algorithms is given at the end of the table. Table 4 shows that our algorithm produces in average the better solution, compared to the other heuristics. The average gap with optimal solutions is only 0.02%.

Runtime comparisons with other heuristics are difficult because different computers with various computing powers were used. The table however shows that our algorithm is much slower than mrOX algorithm (which runs on a faster computer), for a limited improvement in terms of quality, or the Snyder and Daskin's algorithm, for a more significant improvement. Note however that the presence of many easy instances solved optimally by all algorithms tends to tighten the gaps.

Conclusions

In this paper, we proposed to solve the GTSP using a Memetic Algorithm where the crossover operator relies on large neighborhood search. Our main contribution is the originality of our crossover procedure. Experimental results

show that our algorithm is robust and presents a good balance between CPU time and quality of the solutions. 41 out of the 41 problems for which the optimal solution is known are solved optimally. 10 out of 13 best known averaged solution values are improved. Among all the executions of the algorithm the worst solution returned exhibits a gap of 0.66 % with the best known solution.

3. 1 .

 1 Basic components of the algorithm 3.1.1. Individuals

Algorithm 1

 1 Memetic Algorithm Compute an initial population of N random individuals Apply local search on these individuals while the number of iterations is lower than N 1 and an improvement has occurred since less than N 2 iterations do for i = 1 to k do Choose 2 individuals randomly Construct 2 children with crossover Apply local search on both children Add children to the population end for Keep the N best individuals in the population Apply mutation with a probability µ to every individual of the population. end while

Figure 1 : 1 Figure 2 :

 112 Figure 1: Graph obtained from the redundant-sequence: aggregated view of clusters

Figure 3

 3 Figure 3 presents the graph obtained applying these rules from the graph of Figure 1.

Figure 3 :

 3 Figure 3: Reduced graph obtained from the redundant-sequence: aggregated view of clusters

sources {δ 1

 1 , . . . , δ m }. The graph contains 2n cities. Resources δ i are binary. Hence the number of states is O(n2 m ). The label associated with a state is extended toward a maximum of n other states. Every new label is inserted in a label list of maximal size 2 m . The insertion consists in the comparison with every label of the list. Each comparison has a complexity O(m). The cost of inserting a new label in a list is then O(m2 m ) and the cost of extending a label O(nm2 m )

Figure 4 :

 4 Figure 4: Graph obtained from the redundant-sequence (Move operator): aggregated view of clusters

Table 1 :

 1 Experimental results: quality of the solutions

	instance	best	value	CPU	♯opt	mean gap	min gap	max gap	CPU
	29pr144.gtsp	45886	45886	5.38	5	0.00	0.00	0.00	5.42
	30kroA150.gtsp	11018	11018	5.27	5	0.00	0.00	0.00	5.95
	30kroB150.gtsp	12196	12196	4.61	5	0.00	0.00	0.00	5.02
	31pr152.gtsp	51576	51576	4.45	5	0.00	0.00	0.00	5.24
	32u159.gtsp	22664	22664	5.53	5	0.00	0.00	0.00	5.58
	39rat195.gtsp	854	854	10.42	5	0.00	0.00	0.00	11.01
	40d198.gtsp	10557	10557	8.72	5	0.00	0.00	0.00	10.15
	40kroA200.gtsp	13406	13406	6.74	5	0.00	0.00	0.00	10.41
	40kroB200.gtsp	13111	13111	8.78	5	0.00	0.00	0.00	10.81
	45ts225.gtsp	68340	68340	35.31	3	0.04	0.00	0.09	31.45
	46pr226.gtsp	64007	64007	6.92	5	0.00	0.00	0.00	8.25
	53gil262.gtsp	1013	1013	25.12	2	0.14	0.00	0.3	24.34
	53pr264.gtsp	29549	29549	16.64	5	0.00	0.00	0.00	18.27
	60pr299.gtsp	22615	22615	20.19	5	0.00	0.00	0.00	21.25
	64lin318.gtsp	20765	20765	24.89	5	0.00	0.00	0.00	26.33
	80rd400.gtsp	6361	6361	38.33	1	0.42	0.00	0.75	32.21
	84fl417.gtsp	9651	9651	21.9	5	0.00	0.00	0.00	31.63
	88pr439.gtsp	60099	60099	56.46	5	0.00	0.00	0.00	42.55
	89pcb442.gtsp	21657	21673	76.64	1	0.19	0.00	0.38	62.53
	99d493.gtsp	20117.2	20073	115.08		-0.03	-0.28	0.23	166.11
	107att532.gtsp	13510.8	13470	67.08		-0.30	-0.34	-0.17	137.54
	107si535.gtsp	13513.2	13502	69.49		-0.01	-0.08	0.06	90.98
	113pa561.gtsp	1051.2	1046	165.64		-0.84	-1.26	-0.21	149.43
	115rat575.gtsp	2414.8	2408	155.97		0.04	-0.45	0.09	157.01
	131p654.gtsp	27439	27428	74.81		-0.03	-0.04	0.00	144.95
	132d657.gtsp	22599	22533	234.68		-0.15	-0.43	0.28	259.11
	145u724.gtsp	17370.6	17448	214.98		0.45	0.24	0.66	218.66
	157rat783.gtsp	3300.2	3290	462.74		-0.07	-0.58	0.12	391.79
	201pr1002.gtsp	114582.2	114751	415.69		0.03	-0.18	0.16	513.48
	207si1032.gtsp	22388.8	22348	680.95		-0.26	-0.33	-0.17	616.28
	212u1060.gtsp	108390.4	107395	663.44		-0.92	-1.58	0.19	762.86
	217vm1084.gtsp	131884.6	131345	613.76		-0.26	-0.65	0.09	583.44

Table 2 :

 2 Experimental results: Best solutions found

	instance	best	this paper
	99d493.gtsp	20117.2	20061
	107att532.gtsp	13510.8	13464
	107si535.gtsp	13513.2	13502
	113pa561.gtsp	1051.2	1038
	115rat575.gtsp	2414.8	2404
	131p654.gtsp	27439	27428
	132d657.gtsp	22599	22502
	157rat783.gtsp	3300.2	3281
	201pr1002.gtsp	114582.2	114374
	207si1032.gtsp	22388.8	22315
	212u1060.gtsp	108390.4	106677
	217vm1084.gtsp	131884.6	131028

Table 3 :

 3 Experimental results : comparisons between our algorithms

			LNS		One-Point	LNS w/o Mutation
	instance	best	gap	CPU	gap	CPU	gap	CPU
	10att48.gtsp	5394	0.00	0.76	0.00	0.15	0.00	0.94
	10gr48.gtsp	1834	0.00	0.79	0.00	0.14	0.00	0.84
	10hk48.gtsp	6386	0.00	0.5	0.00	0.17	0.00	0.49
	11eil51.gtsp	174	0.00	0.81	0.00	0.15	0.00	0.73

Table 3 :

 3 Experimental results : comparisons between our algorithms

			LNS	One-Point	LNS w/o Mutation
	name	best	gap	CPU	gap	CPU	gap	CPU
	12brazil58.gtsp	15332	0.00	0.65	0.00	0.24	0.00	0.52
	14st70.gtsp	316	0.00	0.93	0.00	0.2	0.00	0.75
	16eil76.gtsp	209	0.00	1	0.00	0.17	0.00	0.96
	16pr76.gtsp	64925	0.00	1.17	0.00	0.25	0.00	0.82
	20kroA100.gtsp	9711	0.00	1.81	0.00	0.27	0.00	1.65
	20kroB100.gtsp	10328	0.00	2.17	0.00	0.27	0.00	2.17
	20kroC100.gtsp	9554	0.00	1.85	0.00	0.27	0.00	1.7
	20kroD100.gtsp	9450	0.00	2.77	0.00	0.27	0.00	2.63
	20kroE100.gtsp	9523	0.00	1.81	0.00	0.53	0.00	1.79
	20rat99.gtsp	497	0.00	3.89	0.00	0.44	0.00	4.21
	20rd100.gtsp	3650	0.00	2.91	0.36	0.4	0.00	2.61
	21eil101.gtsp	249	0.00	2.09	0.56	0.61	0.00	2.23
	21lin105.gtsp	8213	0.00	3.18	0.00	0.36	0.00	2.75
	22pr107.gtsp	27898	0.00	4.78	0.08	0.33	0.00	4.65
	24gr120.gtsp	2769	0.00	2.34	0.62	0.07	0.00	2.58
	25pr124.gtsp	36605	0.00	2.84	0.00	0.44	0.00	2.47
	26bier127.gtsp	72418	0.00	3.35	0.00	0.42	0.00	2.52
	28pr136.gtsp	42570	0.00	4.23	0.72	0.86	0.00	5.61
	29pr144.gtsp	45886	0.00	5.42	0.00	0.54	0.00	5.54
	30kroA150.gtsp	11018	0.00	5.95	0.01	1.14	0.00	6.2
	30kroB150.gtsp	12196	0.00	5.02	0.33	1.45	0.00	4.56
	31pr152.gtsp	51576	0.00	5.24	0.00	0.68	0.00	3.36
	32u159.gtsp	22664	0.00	5.58	0.43	0.83	0.00	6.1
	39rat195.gtsp	854	0.00	11.01	1.05	1.63	0.00	10.36
	40d198.gtsp	10557	0.00	10.15	0.07	1.41	0.17	8.4
	40kroA200.gtsp	13406	0.00	10.41	0.21	1.65	0.00	7.7
	40kroB200.gtsp	13111	0.00	10.81	0.15	2.09	0.00	9.75
	45ts225.gtsp	68340	0.04	31.45	0.29	1.91	0.00	33.42
	46pr226.gtsp	64007	0.00	8.25	0.00	1.03	0.00	7.15
	53gil262.gtsp	1013	0.14	26.34	1.8	2.35	0.89	16.44
	53pr264.gtsp	29549	0.00	18.27	0.46	2.43	0.00	18
	60pr299.gtsp	22615	0.00	21.25	0.2	5.79	0.00	27.84
	64lin318.gtsp	20765	0.00	26.33	0.59	4.67	3.33	31.67
	80rd400.gtsp	6361	0.42	32.21	1.45	10.12	1.56	36.45
	84fl417.gtsp	9651	0.00	31.63	0.00	3.41	0.00	29.75
	88pr439.gtsp	60099	0.00	42.65	0.09	10.56	0.2	33.87
	89pcb442.gtsp	21657	0.19	62.53	1.26	11.22	0.38	108.9
	99d493.gtsp	20117.2	-0.03	166.11	0.03	12.1	0.82	122.73
	107att532.gtsp	13510.8	-0.30	121.54	0.21	18.73	-0.01	91.29
	107si535.gtsp	13513.2	-0.01	90.98	0.01	10.58	0.07	103.33
	113pa561.gtsp	1051.2	-0.84	149.43	1.58	11.66	0.27	131.53
	115rat575.gtsp	2414.8	0.04	157.01	5.01	17.99	2.78	151.88
	131p654.gtsp	27439	-0.03	144.95	-0.01	10.95	-0.03	91.52
	132d657.gtsp	22599	-0.15	259.11	1.15	27.2	2.66	203.8
	145u724.gtsp	17370	0.45	218.66	2.76	45.31	1.08	241.83
	157rat783.gtsp	3300.2	-0.07	391.79	3.68	42.76	1.08	527.74
	201pr1002.gtsp	114582.2	0.03	513.48	1.49	76.54	1.67	345.26
	207si1032.gtsp	22388.8	-0.26	616.28	0.33	75	-0.04	619.99
	212u1060.gtsp	108390.4	-0.92	762.86	-0.28	88.6	0.78	697.36
	217vm1084.gtsp	131884.6	-0.26	583.44	0.3	89.87	1.16	462.46

Table 4 :

 4 Comparison with several algorithms

		LNS -1 trial	LNS -5 trials	mrOX	Snyder	GI		BC
	instance	value	CPU	gap	CPU	gap	CPU	gap	CPU	gap	CPU	CPU
	10att48	5394	0.57	0	0.76	0	0.36	0	0.18	*	*	2.1
	10gr48	1834	0.97	0	0.79	0	0.32	0	0.08	*	*	1.9
	10hk48	6386	0.58	0	0.5	0	0.31	0	0.08	*	*	3.8
	11eil51	174	0.84	0	0.81	0	0.26	0	0.08	0	0.3	2.9
	12brazil58	15332	0.85	0	0.65	0	0.78	0	0.1	*	*	3
	14st70	316	1.02	0	0.93	0	0.35	0	0.07	0	1.7	7.3
	16eil76	209	1.18	0	1	0	0.37	0	0.11	0	2.2	9.4
	16pr76	64925	1.27	0	1.17	0	0.45	0	0.16	0	2.5	12.9
	20kroA100	9711	1.98	0	1.81	0	0.5	0	0.24	0	5	51.5

Table 4 :

 4 Results for several algorithms

		LNS -1 trial	LNS -5 trials	mrOX	Snyder		GI	BC
	instance	value	CPU	gap	CPU	gap	CPU	gap	CPU	gap	CPU	CPU
	20kroB100	10328	2.01	0	2.17	0	0.63	0	0.25	0	6.8	18.4
	20kroC100	9554	1.84	0	1.85	0	0.6	0	0.22	0	6.4	22.2
	20kroD100	9450	2.93	0	2.77	0	0.62	0	0.23	0	6.5	14.4
	20kroE100	9523	1.87	0	1.81	0	0.67	0	0.43	0	8.6	14.3
	20rat99	497	3.52	0	3.89	0	0.58	0	0.15	0	6.7	13
	20rd100	3650	2.93	0	2.91	0	0.51	0	0.29	0.08	7.3	16.6
	21eil101	249	2.07	0	2.09	0	0.48	0	0.18	0.4	5.2	25.6
	21lin105	8213	3.25	0	3.18	0	0.6	0	0.33	0	14.4	16.4
	22pr107	27898	4.67	0	4.78	0	0.53	0	0.2	0	8.7	7.4
	24gr120	2769	2.30	0	2.34	0	0.66	0	0.32	*	*	41.9
	25pr124	36605	2.89	0	2.84	0	0.68	0	0.26	0.43	12.2	25.9
	26bier127	72418	3.02	0	3.35	0	0.78	0	0.28	5.55	36.1	23.6
	28pr136	42570	4.17	0	4.23	0	0.79	0.16	0.36	1.28	12.5	43
	29pr144	45886	5.38	0	5.42	0	1	0	0.44	0	16.3	8.2
	30kroA150	11018	5.27	0	5.95	0	0.98	0	0.32	0	17.8	100.3
	30kroB150	12196	4.61	0	5.02	0	0.98	0	0.71	0	14.2	60.6
	31pr152	51576	4.45	0	5.24	0	0.97	0	0.38	0.47	17.6	94.8
	32u159	22664	5.53	0	5.58	0	0.98	0	0.55	2.6	18.5	146.4
	39rat195	854	10.42	0	11.01	0	1.37	0	1.33	0	37.2	245.9
	40d198	10557	8.72	0	10.15	0	1.63	0.07	1.47	0.6	60.4	763.1
	40kroA200	13406	6.74	0	10.41	0	1.66	0	0.95	0	29.7	187.4
	40kroB200	13111	8.78	0	10.81	0.05	1.63	0.01	1.29	0	35.8	268.5
	45ts225	68340	35.31	0.04	31.45	0.14	1.71	0.28	1.09	0.61	89	37875.9
	46pr226	64007	6.92	0	8.25	0	1.54	0	1.09	0	25.5	106.9
	53gil262	1013	25.12	0.14	24.34	0.45	3.64	0.55	3.05	5.03	115.4	6624.1
	53pr264	29549	16.64	0	18.27	0	2.36	0.09	2.72	0.36	64.4	337
	60pr299	22615	20.19	0	21.25	0.05	4.59	0.16	4.08	2.23	90.3	812.8
	64lin318	20765	24.89	0	26.33	0	8.08	0.54	5.39	4.59	206.8	1671.9
	80rd400	6361	38.33	0.42	32.21	0.58	14.58	0.72	10.27	1.23	403.5	7021.4
	84fl417	9651	21.9	0	31.63	0.04	8.15	0.06	6.18	0.48	427.1	16719.4
	88pr439	60099	56.46	0	42.55	0	19.06	0.83	15.09	3.52	611	5422.8
	89pcb442	21673	76.64	0.19	62.53	0.01	23.43	1.23	11.74	5.91	567.7	58770.5
	Averages	0.001	9.12	0.02	10.12	0.03	2.69	0.11	1.77	0.98	83.09	3356.47
	Trials	1		5		5		5		1		1

http://www.tsp.gatech.edu/concorde/DOC/index.html

Computational Results

The algorithm was coded in C++ and run on an Intel Pentium IV 2.00 Ghz and 2.0 GB RAM under Linux/Debian. Instances used are part of the GTSPLIB library 2 which proposes a set of 65 instances. Among these instances, we have selected 54 instances defined in [START_REF] Fischetti | A Branch-and-Cut algorithm for the Symmetric Generalized Traveling Salesman Problem[END_REF] and used for comparison in most previous papers ([20, 18, 9, 22]). In these instances, clusters contain cities, generally 5, located in a same geographical area. The number of clusters varies between 10 and 217.

The optimal solutions is always known (provided by the Branch & Cut algorithm from Fischetti et al. [START_REF] Fischetti | A Branch-and-Cut algorithm for the Symmetric Generalized Traveling Salesman Problem[END_REF]) for the selected instances with 10 ≤ m ≤ 89. For the remaining instances (99 ≤ m ≤ 217), Silberholz and Golden [START_REF] Silberholz | The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach[END_REF] provide best known results, which in fact are the average results on 5 trials for their algorithm and Snyder and Daskin's algorithm. It is important to note that the value of the best solution found by these algorithms for these instances is not available.

For all experiments, we set the number of individuals per population (N ) to 50, the number of crossovers (2 × k) to 30, the maximum number of iterations (N 1 ) to 100 and the maximum number of iterations without improving the best solution (N 2 ) to 10 and the probability of mutation (µ) to 0.05 (which is the value found in [START_REF] Silberholz | The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach[END_REF]). The computational results presented are the mean results obtained through 5 attempts for each instance.

Table 1 evaluates the performances of our algorithm regarding the gap with optimal solutions or best known solutions. The column headings are defined as follows:

• instance: the name of the test problem; the digits at the beginning of the name give the number of clusters, those at the end give the number of nodes;

• best: the optimal objective value when known or the best known averaged 2 GTSPLIB is available at the address http://www.cs.rhul.ac.uk/home/zvero/GTSPLIB/ 16 solution value;

• value : the value of our algorithm for one trial;

• CPU : the CPU time in seconds for one execution of our algorithm;

• ♯opt: the number of trials, out of five, for which our algorithm found the optimal solution (when known);

• mean gap: the mean gap of our algorithm above the optimum or the best known averaged solution (percentage);

• min gap: the minimal gap of our algorithm above the optimum or the best known averaged solution (percentage);

• max gap: the maximal gap of our algorithm above the optimum or the best known averaged solution (percentage);

• CPU time: the mean CPU time in seconds for one execution of the algorithm.

Results written in bold represent cases for which the solution we found is equal to the optimal one or improve the best known averaged solution.


S Allaoui

A V Duong

G Hivet

J Launay
email: jean.launay@univ-orleans.fr

V Valle

La mesure des déformations pour l'étude du comportement et la mise en forme des renforts de composites

Keywords: RTM, corrélation d'images, suivi de marqueurs 1

Nous faisons ici le bilan de campagnes d'essais mécaniques sur des renforts secs de composites réalisées au LMSP, au cours desquelles les déformations ont été mesurées par des méthodes optiques. La nature des renforts conduit dans certains cas à utiliser la corrélation d'images et dans d'autres le suivi de marqueurs. Dans tous les cas il est nécessaire d'avoir un marquage adapté à l'étude de ces matériaux. Il faut éviter le fractionnement des marqueurs à deux échelles : celle des fibres puis celle des mèches. La brillance des fibres gêne souvent les mesures. Ces problèmes techniques résolus, ces méthodes permettent d'obtenir des résultats très intéressants pour l'étude de ces matériaux.

Introduction

Pour fabriquer des pièces en matériaux composites il faut réaliser un compromis entre des résistances mécaniques et des rigidités spécifiques importantes, des cadences de production suffisantes, le respect des conditions environnementales (l'émission des composés organiques) et le prix de revient des pièces. Les procédés de type RTM (Resin Transfert Moulding) répondent assez bien à ces préoccupations ; ils consistent à mettre en forme le renfort sec puis à injecter une résine thermodurcissable à travers le renfort, dans un moule. La fabrication de composites obtenus par emboutissage de tissus comportant un mélange de fibres de verre et de thermoplastique répond également à ces exigences. La mise au point de ces procédés de fabrication, pour les pièces devant répondre à des exigences de performances précises, justifie l'utilisation d'outils de simulation [START_REF] Boisse | Finite element simulations of textile composite forming including the biaxial fabric behaviour in[END_REF]. La performance de ces outils nécessite d'une part de connaître les caractéristiques mécaniques des matériaux, d'autre part d'être validés sur des cas tests de mise en forme. Les essais mécaniques sur les renforts ont été facilités par l'utilisation de méthodes optiques pour la mesure des déformations [START_REF] Boisse | Analyses of fabric tensile behaviour: determination of the biaxial tension-strain surfaces and their use in forming simulations in[END_REF][START_REF] Dumont | Mesures de champs pour des essais de cisaillement sur des renforts tissés in Mécanique & Industries[END_REF]. Ces méthodes sans contact, permettant des mesures de champ à des échelles variables sont très bien adaptées à l'étude de ces matériaux. La corrélation d'images et 2 le suivi de marqueurs [START_REF] Garcia | A combined temporal tracking and stereo-correlation technique for accurate measurement of 3D displacement : application to sheet metalforming[END_REF][START_REF] Bretagne | Development of the marks tracking technique for strain field and volume variation measurements in[END_REF]) sont deux techniques complémentaires qui permettent d'obtenir des résultats adaptés au type d'essais et aux renforts concernés.

2

Mise en forme des renforts de composites

Les différents types de renforts étudiés

Les renforts étudiés au LMSP pour la réalisation de composites à partir de mise en forme dans un système poinçon-matrice, sont :

• Des tissus de fibre de verre, carbone ou aramides classiques (taffetas, sergés).

• Des renforts à base de fibres de carbone, avec des armures plus complexes.

• Des tissés de fibre de verre associés à des fibres de thermoplastiques (noires ou blanches) comme le Twintex® (figure 1). Le comportement mécanique de ces matériaux est obtenu à partir d'essais de traction biaxiale et de cisaillement plan. Ces données sont nécessaires à la simulation de la mise en forme [START_REF] Boisse | Importance of in-plane shear rigidity in finite element analyses of woven fabric composite preforming in[END_REF].

Tous les renforts ne sont pas adaptés à la réalisation de pièces, par le procédé RTM. La perméabilité du renfort compacté doit rester suffisante pour que les pressions d'injection de la résine ne soient pas trop grandes. Ces pièces, soumises à des sollicitations importantes, auront souvent des épaisseurs de plusieurs millimètres. Il est donc également avantageux d'utiliser des renforts de masse surfacique assez grande, pour réduire si possible le nombre de plis.

Parmi les renforts adaptés au RTM, on trouve des matériaux tissés épais (appelés parfois 2,5d) et des non tissés. Les renforts tissés de type 2.5d, sont constitués d'au moins deux rangées de mèches de chaîne assemblées de façon complexe par des mèches de trame. La surface visible de ces renforts présente des variations d'épaisseur de l'ordre du millimètre (figure 1). Les non tissés, appelés NCF (Non Crimp Fabric), sont constitués de deux ou plusieurs rangées de mèches orientées symétriquement par rapport au plan moyen et cousues les unes avec les autres (Lomov et al. 2001[START_REF] Lomov | Carbon composites based on multiaxial multiply stitched preforms. Part 3: Biaxial tension, picture frame and compression tests of the preforms in[END_REF]. Ces renforts se manipulent plus difficilement que les tissés ; leur surface est plate et brillante et comporte des fils de couture très visibles et régulièrement disposés (figure 1).

FIG. 1 -Tissés et non tissés : Twintex ®, renforts de carbone 2.5 D et NCF

Essais sur les renforts tissés

La simulation de la mise en forme des renforts prend actuellement en compte le comportement en traction biaxiale, cisaillement plan [START_REF] Boisse | Importance of in-plane shear rigidity in finite element analyses of woven fabric composite preforming in[END_REF]. Un dispositif de traction biaxiale a spécialement été conçu pour utiliser des méthodes optiques de mesure des La mesure des déformations par corrélation d'images, sur des renforts tissés de carbone ou de Twintex® nécessite de déposer un mouchetis de peinture ; la surface visible du renfort ne possède pas naturellement de motifs suffisamment Les mèches sont rectilignes ou régulièrement torsadés et leur tissage est périodique ; on note également dans certains cas des vides au croisement de deux mèches. Cette technique fonctionne très bien pour mesurer les champs de déplacement et de déformation en traction biaxiale ou en cisaillement. Elle a permis en particulier, avec des objectifs adaptés, de bien mettre en évidence la cinématique des mèches pour l'essai de cisaillement [START_REF] Dumont | Mesures de champs pour des essais de cisaillement sur des renforts tissés in Mécanique & Industries[END_REF]) (figure 3) et l'apparition de l'angle de blocage conduisant à l'apparition de plis. Cependant lorsque les déplacements deviennent trop grands, le mouchetis se dégrade et ne permet plus le calcul des déformations en se référant à l'image initiale. De même, lorsqu'il est nécessaire de traiter un grand nombre d'images comme c'est le cas pour des essais de routine en traction biaxiale, les temps de calcul peuvent devenir importants ; la méthode de suivi de marqueurs devient alors plus intéressante [START_REF] Bretagne | Development of the marks tracking technique for strain field and volume variation measurements in[END_REF].

FIG. 3 -Essais de cisaillement au cadre d'un tissu de verre ; mouvement et déformations des mèches au cours de l'essai 4

Mesure des déformations par suivi de marqueurs

Pour la méthode de suivi de marqueurs, le repérage se fait en déposant des points de peinture d'une couleur complémentaire de celle du renfort, en des endroits stratégiques ; le diamètre de ces points doit être inférieur à la largeur des mèches pour éviter leur détérioration pendant l'essai. On peut ainsi par exemple mesurer le déplacement ou la déformation d'une ou plusieurs mèches (figure 4). Les temps de calculs sont très courts ; ils permettent même d'avoir des résultats en temps réel. On peut également jouer sur la nature du marqueur et l'éclairage. La mesure des déformations sur des NCF de carbone, très brillants, possédant des rangées de fils de couture blancs régulièrement espacés, est rendue possible avec cette technique en utilisant des marqueurs de peinture fluorescente éclairés en lumière ultraviolette. L'utilisation d'un mouchetis ou de marqueurs classiques n'est pas possible dans ce cas.

FIG. 4 -Essais de cisaillement au cadre sur un tissu 2.5d ; représentation de l'effort appliqué sur le cadre en fonction de la variation angulaire de la mèche repérée par les marqueurs 1-4

La simulation de la mise en forme des renforts de composites nécessite également des essais de validation. Ces essais consistent à emboutir un renfort et à mesurer les déformations à la surface de la pièce obtenue par une méthode stéréoscopique. Le suivi de marqueurs est dans ce cas une solution appropriée car le marquage du tissu par des points est ce qui résiste le mieux à la mise en forme.

Le dispositif d'emboutissage est constitué d'un poinçon et d'une matrice associée ; pour obtenir des images lors de la mise en forme, on utilise une matrice sans fond, ce qui n'est pas trop différent des situations réelles.

Le tissu utilisé dans l'exemple présenté est un 2.5d de carbone dont une zone est recouverte de marqueurs. Après calibrage du système, le renfort est placé au dessus du poinçon, entre la matrice et le serre flanc. On enregistre avec les deux caméras, des images provenant de la zone comportant des marqueurs visibles à l'état initial puis progressivement d'autres images comportant des marqueurs qui se trouvaient initialement masquées sous la matrice et le porte matrice. Ces zones sont visibles sur les cotés de la pièce (figure 5b). Une fois l'essai terminé, la forme est démoulée (figure 5c).

Le traitement des images prises aux différents instants est réalisé avec Deftac 3D développé au Laboratoire de Mécanique des Solides de Poitiers. Il permet de remonter à la position instantanée de chaque point marqué sur le tissu puis aux déformations locales (figure 6).

Conclusions

Les méthodes optiques de mesure des déformations sont parfaitement bien adaptées aux tests mécaniques sur les renforts de composites ou lors de leur mise en forme. Ce sont des méthodes de mesures sans contact qui permettent de mesurer des champs à diverses échelles suivant les objectifs utilisés. Le choix entre la corrélation d'images et le suivi de marqueurs dépend des applications et du type de renfort. Le suivi de marqueurs est bien adapté lorsqu'il s'agit de mettre en évidence des déformations de mèches individuelles.

  FIG. 2 -Traction biaxiale et bias test sur carbone 2.5d ; cisaillement au cadre sur Twintex

  FIG. 5 -Emboutissage d'une préforme carrée en tissu sec.


Philippe Laurençot
email: laurenco@math.univ-toulouse.fr

Benoît Perthame
email: benoit.perthame@upmc.fr

Exponential decay for the growth-fragmentation/cell-division equation

Keywords: Growth-fragmentation equations, cell division, polymerisation process, size repartition, convergence to equilibrium, temporal rate of convergence AMS Class. No. 35B40, 45K05, 82D60, 92D25

We consider the linear growth-fragmentation equation arising in the modelling of cell division or polymerisation processes. For constant coefficients, we prove that the dynamics converges to the steady state with an exponential rate. The control on the initial data uses an elaborate L 1norm that seems to be necessary. It also reflects the main idea of the proof which is to use an anti-derivative of the solution. The main technical difficulty is related to the entropy dissipation rate which is too weak to produce a Poincaré inequality.

Introduction

We consider the growth-fragmentation (or cell division) equation

     ∂ ∂t n(x, t) + ∂ ∂x n(x, t) + kBn(x, t) = B ∞ 0 κ(x, y)n(y, t)dy, n(x = 0, t) = 0, (1)
together with an initial condition n(x, t = 0) = n 0 (x) ∈ L 1 (0, ∞). Here, the number k > 1 represents the average number of pieces after fragmentation, while B > 0 measures the relative intensity of the fragmentation process versus the growth process and x → κ(x, y) gives the size repartition after fragmentation of a polymer (or division of a cell) of size y. Throughout this paper, the fragment distribution function κ is assumed to enjoy the following properties:

κ(x, y) = 0 for 0 < y < x,

These assumptions are usual in modelling fragmentation phenomena [START_REF] Perthame | Transport Equations Arising in Biology[END_REF] and lead to two balance laws for the number of fragments ∞ 0 n(x, t)dx and the total mass x n(x, t)dx + (k -1)B ∞ 0

x n(x, t)dx = ∞ 0 n(x, t)dx = ̺ for all t ≥ 0.

(

) 5
These are instrumental for the existence theory of weak solutions. The evolution equation ( 1) is already renormalised so that zero is the first eigenvalue of the underlying linear integro-differential operator. Indeed, recall that, under fairly general assumptions on κ that were stated for instance in [START_REF] Ph | Existence of a solution to the cell division eigenproblem[END_REF][START_REF] Perthame | Transport Equations Arising in Biology[END_REF], there exists a unique steady state

N ∈ L 1 (0, ∞) satisfying        ∂ ∂x N (x) + kBN (x) = B ∞ 0 κ(x, y)N (y)dy, N (x = 0) = 0, N > 0, ∞ 0 N (x)dx = 1. (6)
In addition, convergence of solutions n to (1) with initial number of fragments ̺ towards ̺N is established in [START_REF] Ph | General relative entropy inequality: an illustration on growth models[END_REF]Section 4] under suitable assumptions on κ but without providing a rate of convergence (see also [START_REF] Perthame | Transport Equations Arising in Biology[END_REF]Chapter 4]). These convergence results are based on the analysis of the entropy dissipation that we recall in Section 2. However, an estimate on the time needed to reach the steady state is of importance: in particular, an exponential rate of convergence guarantees that the steady state is reached fast enough to be observed in practice. Another motivation to investigate the rate of convergence is the study of the stability of steady states in nonlinear cases, at least in weakly nonlinear regimes. Such nonlinear models are met for example in prion dynamics [START_REF] Calvez | Size distribution dependence of prion aggregates infectivity[END_REF][START_REF] Greer | A mathematical analysis of the dynamics of prion proliferation[END_REF][START_REF] Laurenc | Well-posedness for a model of prion proliferation dynamics[END_REF], cell division with finite resources [START_REF] Metz | Formulating models for structured populations[END_REF][START_REF] Perthame | Transport Equations Arising in Biology[END_REF], network communications [START_REF] Baccelli | A mean field model for multiple TCP connections through a buffer implementing RED[END_REF] and many other fields. There are two particular cases where an exponential decay is proved. The first is equal mitosis equations (each cell divides in two cells of the same size) which corresponds to the choice κ(x, y) = 4δ(y -2x) (see Section 2), and the method of proof in [START_REF] Perthame | Transport Equations Arising in Biology[END_REF][START_REF] Perthame | Exponential decay for the fragmentation or cell-division equation[END_REF] is extended here. The second is the case of age structured equations which is very particular and more classical because it corresponds to usual modelling; it corresponds to the formal limit σ → 0 in the case of general mitosis below in Section 2 and the exponential decay rate is known even the case of non-constant coefficients, see [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF][START_REF] Gwiazda | Invariants and exponential rate of convergence to steady state in the renewal equation, Markov Process[END_REF][START_REF] Metz | Formulating models for structured populations[END_REF].

The aim of this note is to show that such an exponential decay is actually valid for a broader class of fragment distribution functions κ, namely those satisfying the positivity condition

β(x, y) := - ∂ ∂y x 0 κ(z, y)dz ≥ 0, (7)
in addition to (2) and (3). Below we give several examples for which these properties are met. The interest of our result is not only to extend the exponential trend to equilibrium to a wider class of data but also to explain the general structure by the positivity property in [START_REF] Gwiazda | Invariants and exponential rate of convergence to steady state in the renewal equation, Markov Process[END_REF]. The semi-norm on the initial data that comes out from our analysis is defined by

|||n||| := ∞ 0 ∂M ∂x (x) + kBM (x) -B ∞ 0 β(x, y)M (y)dy dx + (k + 1)B ∞ 0 |M (x)|dx (8) with M (x) = x 0 (n(z) -̺ N (z))dz and ̺ = ∞ 0 n(y)dy (following the notation introduced in (4)).
Theorem 1.1 With assumptions ( 2), ( 3), ( 7) and an initial condition satisfying |||n 0 ||| < ∞, the corresponding solution n to (1) satisfies

∞ 0 |n(x, t) -̺N (x)|dx ≤ |||n 0 ||| e -(k-1)Bt for all t ≥ 0. ( 9
)
Up to our knowledge it is not possible to obtain exponential decay with only control of L p -norms on the initial data (even though we are not aware of an explicit counterexample). This is related to the main difficulty in analysing the decay rate; the entropy dissipation is too weak to produce a Poincaré inequality. We explain this in more details in Section 2. This is usual and the case of Fokker-Planck equations and "hypocoercive" equations are other examples [START_REF] Desvillettes | On the trend to equilibrium in spatially inhomogeneous entropy-dissipating systems: the linear Fokker-Planck equation[END_REF][START_REF] Villani | Hypocoercive diffusion operators, Boll. Unione Mat[END_REF].

The outline of the paper is as follows. In the next section, we give some examples where the assumptions ( 2), ( 3), [START_REF] Gwiazda | Invariants and exponential rate of convergence to steady state in the renewal equation, Markov Process[END_REF] are satisfied. Then we prove Theorem 1.1. The proof uses an integral change of unknown which has already been used in [START_REF] Ph | Convergence to self-similar solutions for a coagulation equation[END_REF][START_REF] Perthame | Transport Equations Arising in Biology[END_REF][START_REF] Perthame | Exponential decay for the fragmentation or cell-division equation[END_REF] for similar purposes (see also [START_REF] Fournier | Well-posedness of Smoluchowski's coagulation equation for a class of homogeneous kernels[END_REF][START_REF] Laurenc | Well-posedness for a model of prion proliferation dynamics[END_REF][START_REF] Niethammer | Well-posedness for measure transport in a family of nonlocal domain coarsening models[END_REF] where it is applied to the uniqueness issue for related models). More precisely, we study the equation solved by an anti-derivative of the solution to [START_REF] Baccelli | A mean field model for multiple TCP connections through a buffer implementing RED[END_REF]. A crucial point here is that it satisfies a closed equation, a property due to the constant fragmentation coefficient kB. We gather several remarks in the last section.

Examples and entropy dissipation

We present here several standard examples of coefficients κ(x, y) that our method is able to handle. We also recall the relative entropy associated with the equations at hand and indicate why a Poincaré inequality cannot hold true.

Equal mitosis. The most general model describing cell division relies on the choice

κ(x, y) = 4δ(y -2x) = 2δ(x -y/2), k = 2, (10)
that is, each cell divides in two cells of equal sizes. Assumptions ( 2) and ( 3) are obviously satisfied. Furthermore, we can compute

x 0 κ(z, y)dz = 21 I {x≥y/2} = 21 I {y≤2x} , β(x, y) = 2δ(y -2x) = δ(x -y/2),
and ( 7) is satisfied.

Uniform fragmentation. This is the simplest and most standard model for (physical or biological) polymers. It assumes uniform distribution of the fragments after each fragmentation event, i.e.,

κ(x, y) = 2 y 1 I {x≤y} , k = 2. ( 11
)
Assumptions ( 2) and ( 3) are again obviously satisfied. In addition,

x 0 κ(z, y)dz = 2 min{x, y} y , β(x, y) = 2 x y 2 1 I {y>x} ,
and ( 7) is also satisfied.

General

Mitosis. An extension of equal mitosis is to take, for some parameter σ with 0 < σ ≤ 1/2,

κ(x, y) = 1 σ δ y - x σ + 1 1 -σ δ y - x 1 -σ = δ(x -σy) + δ(x -(1 -σ)y). (12)
Assumptions ( 2) and ( 3) are clearly fulfilled, still with k = 2, and

x 0 κ(z, y)dz = 1 I {x≥σy} + 1 I {x≥(1-σ)y} = 1 I {y≤x/σ} + 1 I {y≤x/(1-σ)} , β(x, y) = δ y - x σ + δ y - x 1 -σ = σδ(x -σy) + (1 -σ)δ(x -(1 -σ)y).
Therefore ( 7) is again satisfied.

Homogeneous fragmentation. This generalisation of uniform fragmentation consists in using

κ(x, y) = (2 + α) x α y 1+α 1 I {x≤y} , k = 2 + α 1 + α . (13)
for some α > -1 and satisfies ( 2) and (3). Also All these examples illustrate the main difficulty in order to prove the exponential decay of solutions and why entropy methods are not enough. We recall from [START_REF] Ph | General relative entropy inequality: an illustration on growth models[END_REF][START_REF] Perthame | Transport Equations Arising in Biology[END_REF][START_REF] Villani | Hypocoercive diffusion operators, Boll. Unione Mat[END_REF] and the references therein that the relative entropy inequality for equation (1) reads

d dt ∞ 0 N (x)H n(x, t) N (x) dx = -D H [n(t)] D H [n] := B ∞ 0 ∞ 0 κ(x, y)N (y) H n(y) N (y) -H n(x) N (x) -H ′ n(x) N (x) n(y) N (y) - n(x) N (x) dx dy.
For a convex function H this is a non-negative quantity and this entropy inequality is usually enough to prove the strong convergence of n(t) to ̺N in a norm that depends on the choice of H. However the simplest method to prove exponential decay is through a Poincaré inequality (whenever available) which asserts the existence of ν > 0 such that

ν ∞ 0 N (x)H n(x) N (x) dx ≤ D H [n],
for all functions n satisfying ∞ 0 n(x)dx = 0. The usual setting for the quadratic entropy H(r) = r 2 is to say that u = n/N satisfies

ν ∞ 0 N (x)u(x) 2 dx ≤ D 2 [u] := B ∞ 0 ∞ 0 κ(x, y)N (y) u(x) -u(y)
2 dx dy, whenever ∞ 0 u(x)N (x)dx = 0. As far as we know, the validity of such an inequality is unclear and it is actually false in the case of equal mitosis. Indeed, in that case, κ is given by ( 10) and the right-hand side D 2 [u] is

D 2 [u] = 4B ∞ 0 N (2x) u(x) -u(2x)
2 dx, which clearly vanishes for the class of functions that satisfy u(x) = u(2x) for all x ∈ (0, ∞): such functions are obtained from a given bounded function φ defined on [START_REF] Baccelli | A mean field model for multiple TCP connections through a buffer implementing RED[END_REF][START_REF] Calvez | Size distribution dependence of prion aggregates infectivity[END_REF] by setting u(x) = φ(x/2 j ) for x ∈ [2 j , 2 j+1 ) and j ∈ Z.

3 Proof of Theorem 1.1

As already mentioned, the proof uses an integral change of unknown which is our starting point.

Step 1. (change of unknown function) Let n be a solution to (1) and set

M (x, t) = x 0 [n(z, t) -̺N (z)]dz for (x, t) ∈ [0, ∞) 2 .
It satisfies M (0, t) = M (∞, t) = 0 thanks to the conservation of the number of fragments (4) which implies

∞ 0 [n(z, t) -̺N (z)]dz = ∞ 0 n 0 (z)dz -ρ ∞ 0 N (z)dz = 0.
The motivation for using M is that it satisfies a closed equation of the same type, namely,

     ∂ ∂t M (x, t) + ∂ ∂x M (x, t) + kBM (x, t) = B ∞ 0 β(x, y)M (y, t)dy, M (x = 0, t) = 0. ( 14
)
Indeed, integrating the first equation in ( 1) over (0, x), x ∈ (0, ∞), we obtain

∂ ∂t M (x, t) + ∂ ∂x M (x, t) + kBM (x, t) = B x z=0 ∞ y=0 κ(z, y)n(y, t)dydz = B ∞ y=0 ∂ ∂y M (y, t) x z=0 κ(z, y)dzdy = B ∞ y=0 - ∂ ∂y x z=0 κ(z, y)dz M (y, t)dy = B ∞ 0 β(x, y)M (y, t)dy.
Step 2. (Property of β) To proceed further, we need a specific property of β, namely

y x=z dxdz + k = - ∂ ∂y y z=0 (y -z)κ(z, y)dz + k = - ∂ ∂y [(k -1)y] + k and thus ∞ 0 β(x, y)dx = 1. ( 15
)
Step 3. (Exponential decay of M ) We now argue on the function M . Owing to the positivity (7) of β, we infer from ( 14) that

∂ ∂t |M (x, t)| + ∂ ∂x |M (x, t)| + kB|M (x, t)| ≤ ∞ 0 β(x, y)|M (y, t)|dy.
After integration of the above inequality with respect to x over (0, ∞), we deduce from (15) that

d dt ∞ 0 |M (x, t)|dx + kB ∞ 0 |M (x, t)| ≤ ∞ 0 ∞ 0 β(x, y)|M (y, t)|dydx ≤ B ∞ 0 |M (x, t)|dx,
and thus

∞ 0 |M (x, t)|dx ≤ e -(k-1)Bt ∞ 0 |M (x, 0)|dx for t ≥ 0.
Step 4. (Exponential decay of n) To transfer the exponential decay to the solution n itself is not always possible, see for instance the coagulation case [START_REF] Ph | Convergence to self-similar solutions for a coagulation equation[END_REF]. Here, we can follow [START_REF] Perthame | Exponential decay for the fragmentation or cell-division equation[END_REF] and argue as follows. We first notice that ∂M /∂t satisfies the same equation as M . Therefore Step 3 and ( 14) also give

∞ 0 ∂M ∂t (x, t) dx ≤ e -(k-1)Bt ∞ 0 ∂M ∂t (x, 0) dx ≤ e -(k-1)Bt ∞ 0 ∂M ∂x (x, 0) + kBM (x, 0) -B ∞ 0 β(x, y)M (y, 0)dy dx.
Next, owing to [START_REF] Gwiazda | Invariants and exponential rate of convergence to steady state in the renewal equation, Markov Process[END_REF] and ( 15), we have

∞ 0 ∞ 0 β(x, y)M (y, t)dy dx ≤ ∞ 0 |M (y, t)| ∞ 0 β(x, y)dxdy = ∞ 0 |M (y, t)|dy. (16)
As a consequence, ( 14) also reads

n(x, t) -̺N (x) = - ∂M ∂t (x, t) -kBM (x, t) + ∞ 0 β(x, y)M (y, t)dy,
and we conclude with the help of ( 16) that The fragment distribution function κ is still assumed to fulfil the properties (2), ( 3), [START_REF] Gwiazda | Invariants and exponential rate of convergence to steady state in the renewal equation, Markov Process[END_REF], and the velocity τ is required to satisfy

τ (x) ≥ τ m > 0 ϑ := (k -1)B -sup x∈(0,∞) ∂τ ∂x (x) > 0.
Under these assumptions, the exponential decay rate is e -ϑt . Indeed, the equation on M is

     ∂ ∂t M (x, t) + τ (x) ∂ ∂x M (x, t) + kBM (x, t) = B ∞ 0 β(x, y)M (y, t)dy, M (x = 0, t) = 0.
Therefore, proceeding as in the third step of the proof of Theorem 1.1, we have

d dt ∞ 0 |M (x, t)|dx + (k -1)B ∞ 0 |M (x, t)|dx = ∞ 0 |M (x, t)| ∂τ ∂x (x)dx.
The decay rate for M follows directly from this equality. The positive bound from below required on τ is next used to transfer this decay rate on n, arguing as in the fourth step of the proof of Theorem 1.1.

(c) The exponential decay rate in Theorem 1.1 seems to be optimal: indeed, consider the case where κ is given by (10) (equal mitosis), that is, κ(x, y) = 4δ(y -2x) = 2δ(x -y/2), and introduce the function ξ defined by ξ(x) := 1 2

∂N ∂x x 2 ,
x ∈ (0, ∞).

Owing to the properties of N given in [START_REF] Greer | A mathematical analysis of the dynamics of prion proliferation[END_REF] and the specific choice of κ, it is straightforward to check that (x, t) -→ e -Bt ξ(x) is the solution to (1) with initial condition ξ and the integral of ξ vanishes. Consequently, given ̺ > 0, n(x, t) = ̺N (x) + e -Bt ξ(x) is the solution to (1) with initial condition n 0 = ̺N + ξ and

y 0 κ

 0 (x, y)dx = k, y 0 xκ(x, y)dx = y.

x 0 κ

 0 (z, y)dz = k min{x, y} 1+α y 1+α , β(x, y) = (2 + α) x 1+α y 2+α 1 I {y>x} ,and (7) is again fulfilled.

  Owing to[START_REF] Villani | Hypocoercive diffusion operators, Boll. Unione Mat[END_REF] and its definition in[START_REF] Ph | Convergence to self-similar solutions for a coagulation equation[END_REF], the semi-norm actually satisfies|||n 0 ||| ≤ |||n 0 ||| is thus dominated by the W 1,1 -norm of M (., 0).(b) Theorem 1.1 can be extended to growth-fragmentation equations with non-constant velocity x)n(x, t)) + kBn(x, t) = B ∞ 0 κ(x, y)n(y, t)dy, n(x = 0, t) = 0.

  , t) -̺N (x)| dx = e -Bt ∞ 0 |ξ(x)|dx (recall that k = 2 in that case). (d) Similarly, when κ(x, y) = 21 I {x≤y} /y (which corresponds to uniform fragmentation, see (11)), the equilibrium N is known explicitly and given by N (x) = 4B 2 xe -2Bx for x ≥ 0. Introducing η(x) := x(Bx -2)e -Bx for x ≥ 0, one readily checks that (x, t) -→ e -Bt η(x) is the solution to (1) with initial condition η. Observe that the integral of η vanishes. As in the previous case, given ̺ > 0, n(x, t) = ̺N (x) + e -Bt η(x) is the solution to (1) with initial condition n 0 = ̺N + η. Since ∞ 0 |n(x, t) -̺N (x)| dx = e -Bt ∞ 0 |η(x)|dx, and k = 2, this example also yields the optimality of the decay rate obtained in Theorem 1.1 for that particular case.