Sergei Tucker

Fabien Chmutov

Vignes-Tourneret

T W Mansour

Tucker

ON A CONJECTURE OF GROSS, MANSOUR AND

Keywords: 2010 Mathematics Subject Classification. 05C10, 05C65, 57M15, 57Q15 Ribbon graphs, partial duality, partial-dual genus polynomial, Gross-Mansour-Tucker conjecture

Partial duality is a duality of ribbon graphs relative to a subset of their edges generalizing the classical Euler-Poincaré duality. This operation often changes the genus. Recently J. L. Gross, T.

Ribbon graphs and partial duality

A ribbon graph topologically can be regarded as a regular neighborhood of the graph cellularly embedded into a closed surface. Then the neighborhoods of vertices and edges represent vertexdiscs and edge-ribbons. A component of the complement of the ribbon graph is called a facedisc. The formal definition is the following: Definition 1.1. A ribbon graph G is a surface with boundary represented as the union of two sets of closed topological discs called vertex-discs V (G) and edge-ribbons E(G), satisfying the following conditions:

• the vertex-discs and edge-ribbons intersect by disjoint line segments;

• each such line segment lies on the boundary of precisely one vertex-disc and precisely one edge-ribbon; • every edge-ribbon contains exactly two such line segments.

The last condition allows us to view each edge-ribbon as a topological rectangle (ribbon) attached to vertex-discs by two opposite sides. The face-discs are assumed to be discs which are glued to each of the boundary component of the ribbon graph to get a closed surface Σ G .

In this paper we are dealing with orientable ribbon graphs only. Also this paper deals a lot with one-vertex ribbon graphs which we will encode by chord diagrams following the common practice in knot theory [START_REF] Chmutov | Introduction to Vassiliev Knot Invariants[END_REF]Sec.4.8]. Namely we attach a vertex-disc to the circle of a chord diagram and thicken the chords to narrow edge-ribbons. Here is an example

= = G, Σ G =
This ribbon graph has two boundary components. The corresponding closed surface Σ G has thus two face-discs and its Euler characteristic is equal to χ(Σ G ) = 1 -3 + 2 = 0. This is a torus and the genus of G is equal to 1. Partial duality of ribbon graphs was introduced in [Ch09] under the name of generalized duality. Then it was further studied and developed in papers [VT09, Mo10, Mo11, EMM12, BBC12, Mo13, HM13, CVT14, EZ17, GMT20, YaJi20]. We refer to [START_REF] Ellis-Monaghan | Graphs on Surfaces: Dualities, Polynomials, and Knots[END_REF] for an excellent exposition.

Definition 1.2. For a ribbon graph G and a subset of its edge-ribbons A ⊆ E(G), the partial dual G A of G relative to A is a ribbon graph constructed in the following way. The vertex-discs of G A are bounded by connected components of the boundary of the spanning subgraph of G containing all the vertices of G and only the edges from A. The edge-ribbons of E(G) \ A are attached to these new vertices exactly at the same places as in G. The edge-ribbons from A become parts of the new vertex-discs now. For an e ∈ A we take a copy of e, e , and attach it to the new vertex-discs in the following way. The rectangle representing e intersects with vertexdiscs of G by a pair of opposite sides. But it intersects the boundary of the spanning subgraph, that is the new vertex-discs, along the arcs of the other pair of its opposite sides. We attach e to these arcs by this second pair. The copies of the first pair of sides in e becomes the arcs of the boundary of G A .

The following figure illustrates this definition for the case of an edge e connecting different vertices (the boxes with dashed arcs mean that there might be other edges attached to these vertices). We see that partial duality relative to single edge e ∈ E(G) changes the structure of vertices attached to the edge-ribbon e. Namely, if there were two separate vertex-discs attached to e in G, then they merge together to single vertex-disc attached to the corresponding edge-ribbon e in G {e} , and vice versa. A careful analysis of the orientation of the boundary of the ribbon graphs following the arrows on the above picture shows that a similar rearrangement happened with the face-discs. We formulate it as a lemma.

Lemma 1.3. If the edge-ribbon e ∈ E(G) was attached to two distinct vertex-(resp. face-) discs of G, then in the ribbon graph G {e} these discs will merge together into a single vertex-(resp. face-) disc of G {e} attached to the corresponding edge-ribbon e ∈ E(G {e} ). Backwards, if e ∈ E(G) was attached to a single vertex-(resp. face-) disc of G, then in the ribbon graph G {e} it will be split into two vertex-(resp. face-) discs of G {e} attached to the corresponding edge-ribbon e ∈ E(G {e} ).

According to the lemma there are four types of edges depending on the attachment to the vertex-and face-discs. The impact of partial duality relative to a single edge e on the genus g(G) depends on the type. These four types correspond to the upper four rows (oriented case) of Table 1.1 of [START_REF] Gross | Partial duality for ribbon graphs, I: Distributions[END_REF]. We will follow the notation of [START_REF] Gross | Partial duality for ribbon graphs, I: Distributions[END_REF] denoting each type with two letters p or u, where p stands a proper edge connecting distinct vertices and u stands for an untwisted loop. The second letter indicates the similar properties of the corresponding edge of the dual graph.

Type pp. e is attached to different vertices v 1 = v 2 and to two different faces f 1 = f 2 . In this case the partial duality relative to e merges the vertices and the faces and creates a loop e attached to the resulting vertex and resulting face. So the genus g(G) will be increased by 1, and the corresponding edge-ribbon e in G {e} falls into Type uu.

Type uu. e is a loop attached to a single vertex v 1 = v 2 and to a single face f 1 = f 2 . The partial duality splits the vertex and the face into two vertices v 1 , v 2 and two faces f 1 , f 2 . The edge e returns to Type pp, decreasing the genus g(G) by 1.

Type pu. e is attached to two different vertices v 1 = v 2 but to a single face f 1 = f 2 . The partial duality relative to e merges the vertices but split the face into two faces f 1 , f 2 . The genus g(G) stays the same, and the corresponding edge-ribbon e in G {e} falls into Type up.

Type up. e is a loop attached to a single vertex v 1 = v 2 and to two different faces f 1 = f 2 . The partial duality splits the vertex and merge the faces. The edge e returns to Type pu and the genus g(G) stays the same.

The next figures illustrate partial duality for these four types. -------------------------------→ Type uu --------------------------------→ Type up

Type pp v 1 v 2 f 1 f 2 v 1 = v 2 , f 1 = f 2 g --
v 1 = v 2 f 1 = f 2 v 1 = v 2 , f 1 = f 2 g + 1 Type pu v 1 v 2 f 1 = f 2 v 1 = v 2 , f 1 = f 2 g -
v 1 = v 2 f 2 f 1 v 1 = v 2 , f 1 = f 2 g Figure 1.
Types of edges in partial duality 2. The Gross-Mansour-Tucker conjecture In [GMT20] J. L. Gross, T. Mansour, and T. W. Tucker introduced the partial-dual orientable genus polynomial ∂ Γ G (z) as a generating function of the numbers of partial duals of G of the given genus:

∂ Γ G (z) := A⊆E(G) z g(G A )
where g(G A ) stands for the orientable genus of G A , namely half its Euler genus. The ribbon-join operation G 1 ∨G 2 on ribbon graphs G 1 and G 2 was introduced by I. Moffatt [START_REF] Moffatt | Separability and the genus of a partial dual[END_REF]. To obtain G 1 ∨ G 2 glue together a vertex-disc of G 1 and a vertex-disc of G 2 along some arcs on their boundaries between consecutive ends of the end of edge ribbons to get a new vertex disc of G 1 ∨ G 2 . For one vertex ribbon graphs this operation is the standard multiplication of corresponding chord diagrams, see [CDM12, Sec. 4.4.2]. Obviously the result is not unique, it depends on choice of vertices and arcs. But, since the partial dualities of factors G 1 and G 2 are independent, namely

∀E 1 ⊂ E(G 1 ), E 2 ⊂ E(G 2 ), (G 1 ∨ G 2 ) E1∪E2 = G E1 1 ∨ G E2 2 , the polynomial ∂ Γ G (z) is multiplicative with respect to this operation, ∂ Γ G1∨G2 (z) = ∂ Γ G1 (z) • ∂ Γ G2 (z).
J. L. Gross, T. Mansour, and T. W. Tucker formulated the following conjecture. GMT-conjecture. [GMT20, Conjecture 3.1] There is no orientable ribbon graph having a non-constant partial-dual genus polynomial with only one non-zero coefficient.

They noted that if G is a tree, which implies that its genus is 0, all partial duals of G also will be of genus 0. That means for a tree with n edges, ∂ Γ G (z) = 2 n . This explains the exclusion of constants from the conjecture.

Q. Yan, X. Jin [START_REF] Yan | Counterexamples to a conjecture by Gross, Mansour, and Tucker on partial-dual genus polynomials of ribbon graphs[END_REF] found a family of counterexamples to the GMT-conjecture. They used the one-vertex ribbon graphs B n with n edge-ribbons every two of which are interlaced along the boundary circle of the vertex. These are the corresponding first chord diagrams.

B 1 = , B 2 = , B 3 = , B 4 = , B 5 = , . . .
An intersection graph of a chord diagram [CDM12, Sec.4.8] is a graph whose vertices correspond to the chords and two vertices are connected by an edge if the corresponding chords intersect. The ribbon graphs B n can be characterized as one-vertex ribbon graphs for which chord diagrams have the complete graph K n as the intersection graph.

It was proved in [YaJi20, Theorem 22] that for odd values of n, ∂ Γ Bn (z) = 2 n z n-1 2 , thus providing the counterexample to the GMT-conjecture.

Example 2.1. To demonstrate that the even values of n do not work, we need to check the attachment of edge-ribbon to the face-discs. For that we double each chord modeling the boundary sides of the corresponding rectangles and look for the boundary components we obtain. For example,

B 2 =
We can see a single immersed curve representing the boundary of the ribbon graph B 2 . Each boundary component is a circle to which a face-disc is supposed to be glued in to form a closed surface. In this case we have only one face-disc. So each ribbon of B 2 is attached to the same face. Hence it is of Type uu, and the partial dual relative to each would change the genus. Consequently, the partial-dual genus polynomial would have more than one term. Meanwhile for odd values of n, for example n = 3, each ribbon would be attached to different boundary components:

B 3 =
We would have two immersed curves, so we would have corresponding two face-discs, and each edge ribbon would be attached to different face-discs. That means they are of Type up and the partial duality relative to a single edge would not change the genus. To complete the calculation of [START_REF] Yan | Counterexamples to a conjecture by Gross, Mansour, and Tucker on partial-dual genus polynomials of ribbon graphs[END_REF] we would need to check that all edge-ribbons will stay withing Types pu and up after performing partial dualties.

By the multiplicativity property, the partial-dual genus polynomial of the ribbon-join of B n 's with odd n's also will be a monomial. In fact, even for trees, the total duality gives the one-vertex ribbon graph for which the chords of its chord diagram do not intersect each other. So it is a crossing-less matching of 2n points on a circle. As such it is a ribbon-join of n copies of B 1 . Therefore, all the know examples of one-vertex ribbon graph with a monomial as the partial-dual genus polynomial consist of ribbon-joins of various B n 's with odd values of n. Our main theorem claims that these are the only counterexamples to the GMT-conjecture.

Main result

We call a connected ribbon graph G join-prime if it cannot be represented as the ribbon-join of two graphs G 1 , G 2 with at least one edge-ribbon each:

G = G 1 ∨ G 2 .
Theorem 3.1. For any join-prime ribbon graph different from partial duals of B n 's with odd values of n, there are partial duals of different genus.

One can observe that there are exactly two graphs in the partial dual class of B n . Namely B n itself and its partial dual relative to one edge-ribbon. Partial duality relative to two edges of B n will return to B n back. So, for any join-prime ribbon graph different from these two the GMTconjecture holds. Moreover, from the multiplicativity of ∂ Γ with respect to the join operation, Theorem 3.1 implies that the only orientable ribbon graphs having a non-constant partial-dual genus polynomial with only one non-zero coefficient are partial duals of joins of B n 's with n odd.

Remark. The non-orientable counterpart of the Gross-Mansour-Tucker conjecture has been treated by Maya Thompson (Royal Holloway University of London). She proved that the only nonorientable ribbon graphs having non-constant partial-dual genus polynomial with only one non-zero coefficient are partial duals of the one-vertex ribbon graph with one twisted edge. Moreover, a preprint by Q. Yan and X. Jin [START_REF] Yan | Partial-dual genus polynomials and signed intersection graphs[END_REF] posted recently contains in particular proofs of both the orientable and non-orientable cases.

A one-vertex ribbon graph is join-prime if and only if the intersection graph of the corresponding chord diagram is connected.

Our proof of Theorem 3.1 is based on the following Lemma.

Lemma 3.2. Let G be a one-vertex join-prime ribbon graph and e ∈ E(G). If for all subsets

A ⊆ E(G), g(G) = g(G A ) then (1) e is attached to different face-discs f 1 = f 2 .
That is e has to be of Type up.

(2) Any edge-ribbon interlaced with e is attached to the same face-discs f 1 and f 2 .

(3) Any edge-ribbon not interlaced with e is attached to a pair of face-discs different from {f 1 , f 2 }.

Proof of the Lemma. Since g(G) = g(G {e} ), the edge-ribbon e has to be of Type up. The same is true for any edge-ribbon of G. This proves (1). Let e 1 be an edge-ribbon interlaced with e and attached to two different face-discs f 3 and f 4 . Then on the partial dual G {e} the corresponding edge e 1 will connect two different vertices. If we want the genus to stay the same, g(G) = g(G {e,e1} ), the edge e 1 has to be of Type pu in G {e} . This means it has to be attached to the same face-disc of G {e} . In other words the faces f 3 and f 4 merge to each other in G {e} . But the only change in the structure of faces under the partial duality relative to e is that the faces f 1 and f 2 merge to a single face. This implies {f 3 , f 4 } = {f 1 , f 2 }, which proves (2). In a similar way, let e 2 be an edge-ribbon not interlaced with e and attached to two different face-discs f 5 and f 6 . Then, after the partial duality relative to e, e 2 is still a loop attached to one of the two vertices of G {e} . So it has to be of Type up in G {e} which means that f 5 = f 6 in G {e} . But this partial duality merges f 1 and f 2 . So, {f 5 , f 6 } = {f 1 , f 2 }, which proves (3).

Proof of the Theorem. Since every connected ribbon graph has a one-vertex graph as partial dual, we assume that G is a one-vertex join-prime ribbon graph with n edge-ribbons and such that g(G) = g(G A ) for all subsets A ⊆ E(G). Let D G be the corresponding chord diagram. We also assume that the intersection graph of D G is different from the complete graph K n . Then there is a path of length 2 in the intersection graph. Let e 2 , e 1 , e 3 be the vertices of the path. They correspond to chords of D G such that the chord e 1 intersects both e 2 and e 3 , but e 2 and e 3 do not intersect each other. So, the chord diagram D G looks like this

D G = ,
where the dashed circle means that there might be other chords with end points on these arcs. In terms of the ribbon graph G, the edge-ribbon e 1 is interlaced with both e 2 and e 3 , but the edgeribbons e 2 and e 3 do not interlace. Every edge-ribbon has to be of Type up, that is attached to two different face-discs. Let {f 1 , f 2 } (resp. {f 3 , f 4 } and {f 5 , f 6 }) be the pair of face-discs attached to e 1 (resp. e 2 and e 3 ). Then according to case (2) of the Lemma,

{f 3 , f 4 } = {f 1 , f 2 } = {f 5 , f 6 }.
But this contradicts case (3) of the lemma according to which {f 3 , f 4 } = {f 5 , f 6 }. This means that any two vertices have to be actually adjacent. This implies that the intersection graph has to be the complete graph K n which proves the Theorem.

T. W. Tucker indicated that the theorem can be reformulated in the following ways.

Corollary 3.3. The only join-prime ribbon graph G where all edges have Type up is a one-vertex ribbon graph with an odd number of edges where every loop interlaces with every other loop.

Or in the dual form:

Corollary 3.4. The only join-prime ribbon graph where all edges have Type pu is the dipole on an odd number of edges where the rotation at one vertex is the opposite of the rotation at the other vertex. (i.e. the Petrie dual of the standard dipole in the sphere).

Future research

• The paper [START_REF] Gross | Partial duality for ribbon graphs, I: Distributions[END_REF] contains another very interesting Conjecture 5.1 that the sequence of coefficients of ∂ Γ G (z) is log-concave as well as analogous conjectures for the partial-dual Euler-genus polynomial in the non-orientable case. • The paper [START_REF] Chmutov | Partial Duality of Hypermaps[END_REF] generalizes partial duality to hypermaps. It would be interesting to find (and prove) the analogous conjectures for hypermaps. • Ribbon graphs may be considered from the point of view of delta-matroids [START_REF] Chun | Matroids, delta-matroids, and embedded graphs[END_REF].

In this way the concepts of partial duality and genus can be interpreted in terms of deltamatroids. It would be interesting to know whether the partial-dual genus polynomial and the related conjectures would make sense for general delta-matroids.

  Partial duality relative to a loop acts on this figure backwards, from right to left. In the example from previous page the partial duality relative to middle loop gives: , a graph cellularly embedded into a sphere.Partial duality relative to a set of edges can be done step by step one edge at a time. Partial duality relative to the whole set of edges E(G) is the classical Euler-Poincaré duality. Partial duality relative to a spanning tree produces a one-vertex ribbon graph which can be encoded by a chord diagram.

Acknowledgment

We are very grateful to J. L. Gross and T. W. Tucker for numerous comments on the preliminary draft of this paper and to the anonymous referees the suggestions of whom greatly improved the exposition.


N Zbiri
email: zbiri@iup.univ-evry.fr

Z Mans

Control of an Aerospace Launcher

Keywords: launcher, guidance, LQG control

This research is within the framework of the PERSEUS project proposed by the CNES (Centre National d'Etudes Spatiales). Its aim is to develop new concepts for the attitude control of space modules. This article presents a first study as well as the results of a robust LQG control system that allows stable and satisfactory performance for the attitude of a rigid launcher.

INTRODUCTION

Automatic guidance of airplanes, missiles and space vehicles, satellite stability and robot control constitute a privileged field of application for advanced automation methods. For future needs of the CNES and within the framework of the PERSEUS project, it will be useful to develop appropriate methodologies for piloting space vehicle launchers. It is important to use a model for a launcher whose complexity is compatible with the development of piloting rules. In order to achieve this goal, a good understanding of the system is needed including the location of its non linearities, the variation range for its in-flight parameters, and the importance of coupling between the 3 axes of motion.

The launcher is a complex, nonlinear, unstable multivariable system with parametric and dynamic uncertainties. It is also a high order system due to its flexible modes. The main objective for the development of a control law is to confer to the system properties it does not naturally have or to reinforce those properties if they already exist. Several control methods have been proposed in the literature. Wang and Stengel, have developed a robust nonlinear control system based on a model in which the thrust is constant and independent from the aerodynamic attitude [l]. Xu et Ioannou, have adapted their method by including the presence of uncertainties [START_REF] Xu | Adaptive sliding mode control design for a hypersonic flight vehicle[END_REF]. In [START_REF] Bolender | A Non-Linear Model for The Longitudinal Dynamics of a Hypersonic Air-breathing Vehicle[END_REF], the model used is closely dependant on the launcher's geometry which makes their method difficult to generalize. The model used in [START_REF] Arzelier | Multiobjective ",Impulseto peak synthesis : Application to the control of an aerospace launcher[END_REF] was used as a reference in the work described in this article. The work presented here is about the development of a robust control system that limits the aerodynamic incidence of a rigid launcher. Indeed, a stronger incidence leads to stronger bending forces that may destabilize the launcher. However, incidence is not measurable.

In this study, an LQG controller allows estimation of the incidence and stabilization of the launcher about a zero incidence. This article is organized in five sections as follows:

In the second section, some general concepts as well as some characteristics (piloting loop and guidance) of the launcher are presented along with its model. The third section presents the development of a LQG control system is to provide stability for the launcher's attitude about a zero incidence. The results of a computer simulation will be presented and discussed in the fourth section of this article. Finally, the conclusion of this work and future prospects are given in the last section.

MODELLING THE LAUNCHER

From a complete model, several simplified models have been developed in the literature [1-3]. Besides the launcher's dynamics which are nonlinear, other elements act on the control chain: sensors, actuators, and the computer. These elements may induce nonlinearities in the model. For example, hydraulic, electric or hybrid actuators have limited range, velocity saturation, or hysteresis effects. However, it is not necessary to use nonlinear models in the design phase of the piloting control system. Motions of the launcher are sufficiently slow and angular variations are sufficiently small to justify the use of convenient linear approximations of the dynamics. It is therefore necessary to develop a dynamic model that combines realism and simplicity. The launcher is considered to be a rigid structure. The problems associated with modelling the launcher's flexible modes will not be addressed. However, the effects of the fl exible modes are in general considered as disturbances that can be added to the measurements in the control system [START_REF] Alazard | Commande robuste des structures fl exibles: applications aeronautiques et spatiales[END_REF].

It is assumed that the motions in each plane (pitch, roll and yaw) are sufficiently decoupled to be considered independently. In other words, if the motion about all three axes is to be controlled, three controllers should be implemented, one for each axis.

Due to the launcher's symmetry, motions about the yaw and roll axes can be controlled using the same system. The 3-dimensional model can then be replaced by a 2-dimensional model without any loss of generality. Therefore, this study concentrates on controlling the pitch motion of the launcher only. Figure 1 shows the motion of the launcher and the forces applied on it.

"

The motion along the trajectory is assumed to be straight and linear. Motions about the center of mass are small. The flexible modes are considered as disturbance inputs in the control system. The rocking effect of the propellant fuel is neglected.

The dynamic equations of the launcher allow us to determine a state space model that leads to the development of an appropriate and more robust control system for the launcher. The following inputs and outputs will be considered: In order to obtain a useful working model for piloting the launcher, the following assumptions must be made concerning its dynamics, as well as the control parameters:

"�(:.J am[+}['.] •

the system state representation is given by: where:

Or, in matrix form, as:

x� [ :] � 0 1 0 0 0 A6 -az 1 -!!J_ v. v. 0 X+ Ki � M*V, (1)
(2)

0 (3) OJ [�] v.
The launcher is a non stationary system. Its physical characteristics (position, mass, inertia) and its aerodynamic parameters vary according to its flight. Typical curves describing the variation of the coefficients A6, K1 a1 and a2 are shown in figure 2 [4]. These coefficient curves are those of the Ariane 4 rocket but they have the same shapes and the same orders of magnitude as those obtained from the Ariane 5 rocket.

DESIGN OF THE LQG CONTROL

The state representation (3) can take the form:

{x = Ax+ B1 fJ + v y = Cx+w ( 4
)
where v = Birw and ()) is the noise for the sensor measurements. They will be considered as white noise, centered with variance v > 0 and m > 0.

The measurable variables are the pitch angle e , and the pitch velocity e obtained with the help of an inertial sensor and a gyro. The output matrix can then be written as:

C=[� 0 �]
One difficulty encountered in the control of the launcher is that the incidence, a variable to be controlled, is not measurable. The solution is to improve the state model using a state estimator. The use of the LQG control method is thus necessary for this application.

It can be verified that:

rank [B1 AB1 A2B1 ] =rank [C CA CA2 ] =3
Therefore, the system is controllable and observable.

Reconstruction of the state vector

The estimate x is determined by a Kalman fi lter optimized by minimizing the quadratic norm of the estimation error. Its state equation is given by:

ic =Ax+ B J 3 + K(y-Cx) ( 5
)
where the fi lter gain is determined by the following expression:

K =PCTW- 1 ( 6
)
where the matrix P is obtained by solving the Ricatti equation :

AP+PAT +V-PCTw-1CP = 0 (7)

By using the estimated state vector x , it is possible to fi nd the optimal controller that minimizes the quadratic criterion:

w J = f (xTQx + ur Ru)dt (8)
where Q and R are diagonal weight matrices. The control input is therefore given by: u = -Lx

The gain matrix L is computed by using the expression:

L=W1Brp (9)
where Pis a symmetric definite positive matrix solution of the Ricatti equation :

(10)

SIMULATION RESULTS

Computer simulations are conducted by using the values A6min and A6max retrieved from the curves of figure 2.

At first, the wind disturbance is not considered. The results for the simulations are given by the curves in Figure 3 for A6min and the curves of Figure 4 for A6max. : : : : : : : : : It is important to note that without considering the disturbance effects, the curves for both cases are similar for all three state variables ( e,e,i). It is however worth noticing that the time performance criteria (overflow and response time) are different. It has also been observed that the system behavior remains stable for intermediate values of A6 but this article does not discuss this observation for lack of space. What is discussed here is that for variations of the characteristic parameter A6 from its minimal value to its maximal value, the LQG controller provides stability of the launcher's attitude. In a fi rst study, this allows the development of a control system without considering the non stationarity of the launcher.

�-01 --�--�-.---: ---: --�--�--�--�-- i= -�--� -! ---! ---! --�--�--�--�-- i(t)

Disturbance Rejection

The system represented by equation ( 2) is influenced by the wind. This disturbance, the rate of change of the wind, can be considered to be a wind burst, as described by Figure 5. For A6max , the disturbance appears at t = 15 s, when steady state is reached. For A6m in , a similar disturbance is also introduced in steady state at t = 45 s.

The simulation results obtained are shown on Figures 6 and7. The state variables of the system are affected by the wind disturbance. However, the disturbance effects are quickly weakened in the two cases described in both figures. It is shown that the LQG controller allows the attitude of the launcher to be stable about a zero incidence while eliminating the effect of a wind disturbance.

--� -� -t--� --:--..:--i -�--•-; DilITT """" ... .,. .. The results of the simulation that we presented show the LQG system ability to control the attitude of a launcher while rejecting the effect of a constant disturbance due to the wind. The nonstationarity of the system has been partly taken into account by considering values included between the maximum and minimum values of the characteristic coefficientA6 of the launcher.

. ... ' •• t•••�-: +��•-• 1'--- r-• --- � J •••• ,, -J - 1, --- •l I: •-� ---1 ---+ --t •••r • --�--- .. j • • • t•• ••:•• .. ;. .. • r• •• �•-• ' -1---1---t-•-f ••[•--
The LQG controller stabilise the launcher's attitude by maintaining its incidence angle close to zero. However, the model is considered linear. Further studies are pursued to develop a more robust guidance system, taking in consideration the system non linearities, especially the launcher parameters' variations.

Fig. 1 .

 1 Fig. 1. Forces exerted on the launcher in the pitch plane. Notations: V: absolute velocity v . : relative velocity v w : wind velocity z : drift velocity along the pitch axis i : incidence of the vehicle /3 : deflection of the tailpipe e : pitch angle ('attitude) aw: angle between v and vr c x : aerodynamic drag coefficient c z : aerodynamic lift coefficient R x : drag force Rz: lift force Fa, engine thrust M: instantaneous mass of the launcher Pd : dynamic pressure S : reference surface of the launcher LF : arm of the aerodynamic control lever Lr : arm control lever of the propulsion force

Fig. 2 .

 2 Fig. 2. Variation curves for A6 , K1 a1 and a 2 •

Fig. 3 .

 3 Fig. 3. State variable curves for A6min B(t)

Fig. 4 .

 4 Fig. 4. State variable curves for A6max

Fig. 5 .

 5 Fig. 5. Wind dis turbance.

Fig. 6 .

 6 Fig. 6. State variables curves for A6m in

.

Fig. 7 .

 7 Fig. 7. State variables curves for A6max•


Quentin Plantec

Pr Pascal Le Masson

Pr Benoit Weil

ANOTHER WAY TO GET THE NOBEL PRIZE: THE ROLE OF THE INDUSTRY IN THE EMERGENCE OF NEW SCIENTIFIC BREAKTHROUGHS

Since the 1980s, most industrial corporations cut-off their investments in fundamental research activities. While the benefits for scientists of interacting with the industry have been demonstrated many times, (1) how much scientific breakthroughs are still emerging, in modern science, from scientists engaged with the industry, and (2) how this would affect ex-post knowledge diffusion are yet to be documented. To do so, we explored the extent to which scientists from the quasi-complete cohort of Nobel laureates in Physics, Medicine, and Chemistry were engaged with industrial corporations for their breakthrough discoveries. We designed a unique dataset of their ties with the industry based on affiliations review of 84,423 academic papers and applicant review of 5,207 patent families. First, we showed that one-fifth of the studied cohort of Nobel laureate was engaged with the industry at the date of their breakthrough discovery. More importantly, this share is still increasing. During the last period of observation, more than one of two laureates belong to this category. Second, while those scientific discoveries were partly made possible thanks to those Nobel laureates' industrial partners, the laureates' subsequent knowledge was not bound to their initial sets of partners. Indeed, those laureates experienced similar knowledge diffusion-to-industry rates than other laureates but higher academic production rates and diffusion-to-academia rates. Finally, we claim that the extent to which scientific new knowledge still emerges in relation to industrial contexts in modern science has been under-evaluated and open rooms for further research.

. This literature is of crucial interest to explore the relationship

between academic engagement and scientific breakthrough discoveries because we have "only tentative evidence on the effect of engagement on […] the potential for breakthroughs increases." [START_REF] Perkmann | Academic engagement: A review of the literature 2011-2019[END_REF].

While the role of the industry in the early emergence of scientific breakthroughs has been documented through questionnaires or case studies (e.g. D 'Este & Patel, 2007;[START_REF] Evans | Industry Induces Academic Science to Know Less about More[END_REF][START_REF] Narayanamurti | Cycles of Invention and Discovery: Rethinking the Endless Frontier[END_REF][START_REF] Stokes | Pasteur's Quadrant. Basic science and technological innovation[END_REF], the "backward link" (D'Este & Perkmann, 2011: 330) of being engaged with the industry on fundamental research activitiesparticularly for breakthrough discoveriesis still underappreciated [START_REF] Perkmann | Academic engagement: A review of the literature 2011-2019[END_REF] and contentious [START_REF] Murray | The Oncomouse That Roared : Hybrid Exchange Strategies as a Source of Distinction at the Boundary of Overlapping Institutions[END_REF]. On the one hand, some scholars claimed that engaged academics might suffer from publications restrictions or additional delays to contribute to open-science due to secrecy and patenting activities [START_REF] Blumenthal | Relationships between Academic Institutions and Industry in the Life Sciences -An Industry Survey[END_REF][START_REF] Czarnitzki | Delay and secrecy: Does industry sponsorship jeopardize disclosure of academic research?[END_REF]. On the other hand, the industry may also be a valuable source of skills, materials, equipment, resources, and ideas to fuel fundamental research (eg. [START_REF] Ankrah | Asking both university and industry actors about their engagement in knowledge transfer: What single-group studies of motives omit[END_REF][START_REF] Banal-Estañol | The double-edged sword of industry collaboration: Evidence from engineering academics in the UK[END_REF][START_REF] D'este | Why do academics engage with industry? The entrepreneurial university and individual motivations[END_REF][START_REF] Gulbrandsen | Industry funding and university professors' research performance[END_REF][START_REF] Lee | The sustainability of university-industry research collaboration: An empirical assessment[END_REF][START_REF] Mansfield | Academic Research Underlying Industrial Innovations : Sources , Characteristics , and Financing[END_REF][START_REF] Siegel | Assessing the impact of organizational practices on the relative productivity of university technology transfer offices: An exploratory study[END_REF]. Scientific activities performed in industrial contexts also conduct researchers to be more interested in the "usage" of their fundamental breakthroughs, a phenomenon that has been associated with higher research performances in specific contexts, in relation with the Pasteur Quadrant [START_REF] Goldstein | Simultaneous pursuit of discovery and invention in the US Department of Energy[END_REF][START_REF] Narayanamurti | Cycles of Invention and Discovery: Rethinking the Endless Frontier[END_REF][START_REF] Stokes | Pasteur's Quadrant. Basic science and technological innovation[END_REF][START_REF] Tijssen | Anatomy of use-inspired researchers: From Pasteur's Quadrant to Pasteur's Cube model[END_REF]. Furthermore, industry-university interactions may also conduct more efficient specialization between researchers and their industrial partners, particularly for scientific breakthroughs with commercial potential, with positive effects on follow-on research and researchers' performances [START_REF] Bikard | When Collaboration Bridges Institutions : The Impact of University -Industry Collaboration on Academic Productivity[END_REF].

Hence, due to the structural changes in the science-industry ecosystem (i.e. withdrawal of leading firms on fundamental research activities and the development of open-innovation), as well as the need to disentangle both adverse and positive effects of academic engagement with the industry on academics' research activities, (1) to what extent scientific breakthroughs are still emerging from academics engaged with the industry and (2) how this would affect knowledge diffusion of those academics, are yet to be documented. Here, we take a step towards filling these gaps by assessing the magnitude and evolution of academic engagement with the industry in relation to new scientific discoveries from scientists awarded with the Nobel Prize. We also explored the effects of such an engagement with the industry on the follow-on (future) laureate knowledge diffusion towards academia and the industry. We acknowledged that in the long run, Nobel laureates constituted an adequate proxy of fundamental scientific activities evolution and, can help us better understand modern science dynamics [START_REF] Jones | The burden of knowledge and the "death of the renaissance man": Is innovation getting harder?[END_REF].

CONCEPTUAL BACKGROUND

In this section, we derive assumptions on the relation between academic engagement and scientific breakthroughs and its effects on subsequent academics' knowledge diffusion. As it is a short paper, we only provide our different assumptions.

Academic engagement and scientific breakthroughs

Hypothesis 1: a significant share of Nobel laureates (beyond the well-known IBM and Bell Laboratories cases) benefited from their engagement with the industry for their scientific breakthrough discovery for which they were awarded the Nobel Prize.

Academic engagement and post-discovery performances:

Hypothesis 2.a / b : Nobel laureates who benefited from their engagement with the industry for their scientific breakthroughs are suffering from a negative (b. positive) effect on their ex-post publication performances (number and quality). Hypothesis 3.a / b. Nobel laureates who benefited from their engagement with the industry for their scientific breakthroughs are (b. not) shifting their research towards a more applied orientation, with then an increase of the research diffusion to industry rate.

METHODOLOGY & DATA

Identification of Nobel laureates who benefited from their engagement with the industry for their scientific breakthroughs

In order to identify the Nobel laureates that have been engaged with the industry and benefited from those interactions for their breakthrough discoveries, we developed a dedicated method. To do so, we used [START_REF] Li | A dataset of publication records for Nobel laureates[END_REF] public dataset that comprising of an extensive list of 89,311 academic papers written by 92.4% of all the Nobel laureates in Chemistry, Medicine and Physics between 1900 and 2016. They also provided the identification of the specific scientific paper (ie. Prize Paper) that led each laureate to be awarded the Nobel Prize. We called Period 0, the period between the first academic paper of a given laureate and his/her Prize Paper; Period 1, the period between his/her Prize Paper, and the Nobel award1 .

Hence, we consider the potential interactions with the industry that the laureate may have experienced before or at the date of the Prize Paper publication (i.e. Period 0). We designed a unique dataset that relied on a review of laureates' ties with the industry based (1) on a careful examination of authors' affiliations and funding organizations of all papers written by Nobel laureates as well as (2) a review of all assignee organizations of patents filed by laureates. Previous research showed that affiliations of authors of academic papers or patent's assignee organizations could be used as a proxy to measure ties with the industry and, therefore, academic engagement (eg. [START_REF] Abramo | University-industry collaboration in Italy: A bibliometric examination[END_REF][START_REF] Abramo | Assessing public-private research collaboration: Is it possible to compare university performance[END_REF][START_REF] Arora | The decline of science in corporate R&D[END_REF][START_REF] Arts | Taste for science, academic boundary spanning, and inventive performance of scientists engineers in industry[END_REF][START_REF] Calvert | University-industry research collaborations in the UK: bibliometric trends[END_REF][START_REF] Tijssen | Co-authored research publications and strategic analysis of public-private collaboration[END_REF].

Here, we called industry-inspired researchers the laureates that had ties with the industry before or at the date of their breakthrough discoveries. The procedure is summarized in Figure 1 below. All publication's data are finally gathered at the laureate level for each period (panel structure) and normalized.

Patent of Nobel laureates and ties with the industry analysis

Previous literature showed that patents filed by academics could help to define ties with the industry, in particular by analyzing the applicant of the patent (e.g. [START_REF] Balconi | Networks of inventors and the role of academia: An exploration of Italian patent data[END_REF][START_REF] Balconi | University-industry interactions in applied research: The case of microelectronics[END_REF][START_REF] Crescenzi | Academic inventors: collaboration and proximity with industry[END_REF]. Here, we collected data from the PATSTAT database2 , and we looked for patents filed by inventors with exact similar names and surnames than those from the list of Nobel laureates' academic publications. To control for the issue of reduplicated names, we adopted a conservative approach with cross-checked on Wikipedia, Nobel.org and in the academic publication's affiliations of the laureates or its co-authors. The final dataset comprises 5,219 patent families, including 3,001 filled for company applicants and 2,394 filled for the university-like applicants.

Nobel laureates' research orientation

To proxy research orientation towards basic or applied research, we explored how the industry relies on laureate's academic papers when filing patents. Hence, scholars have extensively used this proxy of Scientific Non-Patent Literature (SNPL): academic papers that are cited by the inventor or the examiner of a given patent application in order to demonstrate the newness of the invention, since the seminal work of [START_REF] Narin | The increasing linkage between U.S. technology and public science[END_REF]. Here, we relied on the [START_REF] Marx | Reliance on science: Worldwide front-page patent citations to scientific articles[END_REF] dataset, who conducted an in-depth analysis to disentangle citations to academic papers in patents filled in the USPTO, OEB, and through the PCT procedure. After crossing the database on Nobel laureates' publications and SSNPL, we showed that 13,935 academic papers wrote by Nobel Prize laureates in our sample are cited in 68,361 specific patent applications. All SNPL data are finally gathered at the laureate level for each period (panel structure) and normalized.

EXPLORING THE COHORTS OF NOBEL LAUREATES THAT WERE INSPIRED BY INDUSTRY

In this section, in relation to Hypothesis 1, we explored the extent to which some Nobel laureates were inspired by the industry for their fundamental discovery.

We computed in Table 1 the number of Nobel Prize's laureates with ties with the industry before the publication of their prize paper, split by channel and discipline. We also analyzed the evolution through time of the share and number of industry-inspired Nobel laureates across the sample's whole cohort of laureates. We reviewed the share of Nobel laureates that had ties with industry before their prize paper based on the date of award per decade basis (Figure 2)

and by analyzing the split per discipline (Figure 3).

INDUSTRY INSPIRATION EFFECTS ON NOBEL LAUREATES' ACADEMIC FOLLOW-ON RESEARCH

Variables and descriptive statistics

To test Hypothesis 2 and Hypothesis 3, our objective is to define if during the period following the publication of the Prize paper by a given laureate, being inspired by the industry during period 0 conduct to significant differences in terms of follow-on academic performances and orientations of research with those that were non-engaged. Our data set is a panel with two periods: period 0 and period 1 (Figure 1).

Therefore, we used a Difference-in-Difference (D-i-D) model. The D-i-D variable is a dummy equal to 1 during the tested period, here the period 1 and for treated laureate only, and 0 otherwise. The variables definitions in Table 2. The age of the Nobel laureate when he or she was awarded with the Nobel prize. Treated A dummy variable equal to 1 if the laureate was industry-inspired before the publication of its Nobel's paper, 0 otherwise Difference-in-difference A dummy variable equal to 1 if the laureate was industry-inspired before the publication of its Nobel's paper and during the period after the publication of the Nobel's paper of the laureate and before being awarded with the Nobel prize (i.e. period 0).

Estimation

Formally, we used the following regression equation to estimate the effect of inspiration by the industry on the cohort of laureates, with 𝑌 𝑖 a given Dependent Variable for laureate I and 𝑋 𝑖 a vector of controls variables:

𝑌 𝑖 = 𝑓(𝛽 1 𝐷𝑖𝐷 𝑖 + 𝛽 2 𝑡𝑟𝑒𝑎𝑡𝑒𝑑 𝑖 + 𝛽 3 𝑝𝑒𝑟𝑖𝑜𝑑 𝑖 + 𝛼𝑋 𝑖 + 𝜀 𝑖 )
Since the Dependence Variables of our models are a count of scores (non-negative integers), ranging from 0 to many, we used a Negative Binomial Regression (NBR) as a means of estimation and by controlling for period exposure (e.g. [START_REF] Baba | How do collaborations with universities affect firms' innovative performance? The role of "Pasteur scientists" in the advanced materials field[END_REF][START_REF] Zucker | Star scientists and institutional transformation: Patterns of invention and innovation in the formation of the biotechnology industry[END_REF]. Then, the results of the estimation are reported in First, we showed that regarding Hypothesis 2, industry-inspired laureates for their Prize paper have a premium in terms of follow-on academic papers. On the one hand, they publish more papers in period 1 that they would have done without industry inspiration and more papers than their peers. On the other hand, those results stand by taking into account the quality of the publications. Hence, we accept Hypothesis 2.b and reject Hypothesis 2.a. Second, we showed that regarding Hypothesis 3, industryinspired laureates have been prone to a greater orientation towards applied research than they would have done without being engaged with the industry in Period 0. Nevertheless, there are no significant differences between the orientations towards applications than their peers who were not engaged in period 0. Then we reject Hypothesis 3.a and accept Hypothesis 3.b.

Finally, models 1-4, and 1-6 showed that the non-industry-inspired laureates in period 1 are catching up with the industry-inspired laureates in terms of the number of patent families filled in period 2, associated impacts measured by patent citations, and number of distinct industrial partners.

Nevertheless, industry-inspired laureates still get a premium regarding the rest of the cohorts in terms of direct industrial impact through patent filling and the number of their industry partners.

DISCUSSION

This research's primary motivations were to explore the relation between academic engagement and scientific breakthroughs, which ultimately shed light on the industry's role in the early emergence of new radical scientific knowledge.

First, our essential contribution is to establish that despite the significant cut-off of corporate laboratories on fundamental research from the 1980s, the share of industry-inspired laureates to be awarded is mainly increasing. The industry has inspired more than one of two laureates for their breakthrough discoveries in the last observation period. We demonstrated that this phenomenon is discipline-dependent: more laureates are industry-inspired in Physics and Chemistry than in Medicine, even if we recently observed a catch-up phase. Finally, while The Bell Laboratories or IBM are well known for concentrating many Nobel laureates, many other industrial companies had influenced Nobel laureates. Second, we showed that despite that industry-inspired Nobel laureates' scientific breakthroughs were partly made possible thanks to their industrial partners, their subsequent knowledge was not bound to these initial sets of partners. Those laureates experienced similar knowledge diffusionto-industry rates than other laureates but higher academic production rates and diffusion-to-academia rates. It also means this industry-inspiration do not lead to a more remarkable shift towards applied research than their Nobel laureates' peers.

Our findings contribute to the literature on academic engagement. While it was previously showed that academic engagement is widely practiced across all disciplines [START_REF] Cohen | Links and Impacts: The Influence of Public Research on Industrial R and D[END_REF][START_REF] Hughes | The Changing State of Knowledge Exchange: UK Academic Interactions with External Organisations 2005-2015[END_REF], we bring evidence that (1) it constitutes a reality also for the most incredible scientific advances in science and (2) academic engagement is becoming more and more practiced by scientists who made major scientific breakthroughs. Our results regarding the comparison of academic performances and post-Prize Paper behaviors between industry-inspired laureates and non-industry inspired ones also complement previous literature findings. Hence, first, we noticed that industryinspired laureates published a higher number of articles in period 0 than their peers, which echoes the finding that academics with more publications are more prone to be engaged with industry (e.g. [START_REF] Gulbrandsen | Industry funding and university professors' research performance[END_REF][START_REF] Tartari | In good company: The influence of peers on industry engagement by academic scientists[END_REF]. We also found that industry-inspired laureates published more follow-on papers than their peers, even when considering the quality of those publications. It matches with a robust line of works claiming that one consequence of academic engagement is an increase in the number of publications (e.g. [START_REF] Blumenthal | Relationships between Academic Institutions and Industry in the Life Sciences -An Industry Survey[END_REF][START_REF] Gulbrandsen | Industry funding and university professors' research performance[END_REF][START_REF] Hottenrott | Fishing for complementarities: Research grants and research productivity[END_REF]. The quality of those publications remained unclear, but our finding showed that for star scientists it has a positive effect, which is aligned with [START_REF] Bikard | When Collaboration Bridges Institutions : The Impact of University -Industry Collaboration on Academic Productivity[END_REF] and [START_REF] Hottenrott | Fishing for complementarities: Research grants and research productivity[END_REF] findings on non-star scientists. Finally, we also contributed to the literature by demonstrating that industry-inspired laureates did not have a more excellent orientation towards applied research than their non-industry-inspired peers. In contrast, it has been highlighted as a common drawback of academic engagements (e.g. [START_REF] Blumenthal | Relationships between Academic Institutions and Industry in the Life Sciences -An Industry Survey[END_REF]. It seems that those Nobel laureates were able to maintain their orientation towards basic research by continuously be engaged with their industrial partners, including for commercialization activities measured through filled patents or for collaborative research projects (co-publications).

Figure 1 -

 1 Figure 1 -Treated Nobel laureate identification process

Figure 2 -Figure 3 -

 23 Figure 2 -Evolution of share of industry-inspired Nobel laureates per decade by date of award

Table 1 -

 1 Treated Nobel laureates split by ties with industry types and disciplines

  Age at Nobel's paper publication The age of the Nobel laureate when he or she published the Nobel's paper. Age at Nobel Prize winning

	Variable	Definition
	Nbr. academic publications	Total number of academic papers published by the laureate in a given period.
	Nbr. academic publications -	Total number of academic papers published by the laureate in a given period,
	Scholarly citations weighted	weighted by the number of follow-on received academic citations.
	Nbr. academic publications -	Total number of academic papers published by the laureate in a given period,
	SNPL citations weighted	weighted by the number of follow-on citations of those papers in patents.
	Nbr. patent families	Total number of patent families filled by the laureate in a given period.
	Nbr. patent families -Patent	Total number of patent families filled by the laureate in a given period weighted by
	citations weighted	the number of follow-on citations by other patents.
	Nbr. industry partners	Total number of distinct indusrial company that interacted with the laureate in a
		given period.
	Period	A dummy variable equal to 0 the period before the publication of the Nobel's paper
		of the laureate and 1 the period
	Period duration	Count of the number of distinct years for a given period of the laureate.
	Born year	Date of birth of the laureate.
	US-born laureates	A dummy variable equal to 1 if the laureate is born in the US, 0 otherwise.
	Female laureate	A dummy variable equal to 1 if the laureate is a female, 0 otherwise.
	Chemistry Nobel	A dummy variable equal to 1 if the laureate was awarded with the Chemistry Nobel
		prize, 0 otherwise.
	Medicine Nobel	A dummy variable equal to 1 if the laureate was awarded with the Medicine Nobel
		prize, 0 otherwise.
	Physics Nobel	A dummy variable equal to 1 if the laureate was awarded with the Physics Nobel
		prize, 0 otherwise.

Table 2 -

 2 Variable definition

Table DV

 DV

		= Nbr.	DV = Nbr.	DV = Nbr.	DV = Nbr.	DV = Nbr.	DV = Nbr.
			academic	academic	patent	patent	industry
		publications	publication -	publications	families	families -	partners
			Scholarly	-SNPL		Patent
			citations	citations		citations
			weighted	weighted		weighted
		(1-1)	(1-2)	(1-3)	(1-4)	(1-5)	(1-6)
	Difference-in-	0.312***	0.660***	1.021***	-0.507	-1.765***	-16.26***
	difference treated vs.	(0.109)	(0.133)	(0.386)	(0.438)	(0.546)	(0.205)
	untreated (0/1)
	Treatment	0.281*** (0.0966)	-0.211 (0.144)	-0.542* (0.309)	2.421*** (0.433)	3.634*** (0.711)	17.61*** (0.161)
	Period	0.557*** (0.0576)	0.0833 (0.0801)	0.105 (0.352)	1.643*** (0.353)	3.084*** (0.369)	16.77*** (0.161)
	Born year	0.0154*** (0.00173)	0.0331*** (0.00342)	0.0824*** (0.00530)	0.0509*** (0.00966)	0.0998*** (0.0156)	0.0350*** (0.00375)
	US-born laureate	-0.210*** (0.0802)	-0.168* (0.0966)	-0.284 (0.264)	-0.192 (0.345)	-0.217 (0.359)	-0.318** (0.124)
	Female laureate	-0.563*** (0.165)	-0.600*** (0.155)	-1.284*** (0.367)	-0.101 (0.942)	-1.316 (0.862)	-0.913** (0.377)
	Chemistry Nobel	0.692*** (0.101)	0.290** (0.134)	1.564*** (0.272)	0.661* (0.362)	0.774 (0.490)	0.0534 (0.150)
	Medicine Nobel	0.397*** (0.0994)	0.410*** (0.123)	1.955*** (0.342)	0.427 (0.382)	1.099* (0.563)	-0.129 (0.175)
	Age at Nobel's paper	0.00478	0.00931	0.0550***	-0.00401	0.0826***	0.00369
	pub.	(0.00597)	(0.00750)	(0.0145)	(0.0210)	(0.0239)	(0.01000)
	Age at Nobel Prize	-0.00154	-0.0171***	-0.0227*	0.0591***	0.00768	0.0102
	winning	(0.00373)	(0.00496)	(0.0123)	(0.0165)	(0.0206)	(0.00695)
	Constant	-33.23*** (3.371)	-66.15*** (6.573)	-164.3*** (9.813)	-107.3*** (18.94)	-204.1*** (30.87)	-87.89*** (7.382)
	Exposure -time period	Yes	Yes	Yes	Yes	Yes	Yes
	Log-pseudolikelihood	-1021.9801	-1121.1657	-913.46381	-623.8026	-480.60184	-845.77287
	Wald chi-squared	468.46***	281.93***	482.11***	220.98***	211.84***	575.87***
	Nbr. treated	108	108	108	108	108	108
	Nbr. laureates	518	518	518	518	518	518
	Observations	1,004	1,004	1,004	1,004	1,004	1,004
	Robust errors clustered to laureate id in parentheses, * p<0.1, ** p<0.05, *** p<0.01

Table 3 -

 3 Negative Binomial RegressionNobel career trends and the set of controls. Nevertheless, our key objective to answer Hypothesis 2 and Hypothesis 3 is to compare industry-inspired laureates vs. other laureates in period 1.Then, we need to test if 𝛽 1 + 𝛽 2 ≠ 0 which would mean that industry's inspiration for Paper Prize conduct laureates to come up with different estimated mean for a given dependent variable. The results are presented in Table4.

		DV = Nbr.	DV = Nbr.	DV = Nbr.	DV = Nbr.	DV = Nbr.	DV = Nbr.
		Academic	academic	academic	patent	patent	industry
	Chi-squared test:	publications	publication -	publications	families	families -	partners
	𝛽 1 + 𝛽 2 = 0		Scholarly citations	-SNPL citations		Patent citations
			weighted	weighted		weighted
		(1-1)	(1-2)	(1-3)	(1-4)	(1-5)	(1-6)
	𝛽 1 + 𝛽 2	0.593	0.449	0.480	1.914	1.869	1.346
	Chi-squared	22.87	8.99	3.49	26.14	17.11	51.94
	Prob > chi-squared	0.0000	0.0027	0.0618	0.0000	0.0000	0.0000
	Status	Reject	Reject	Accept	Reject	Reject	Reject
	Acceptance or rejection decision is based on a 5% confidence intervals ratio.

Based on our regression, our D-i-D model showed that the effect of being inspired by the industry has a significant impact on the career trajectory of those Nobel Prize laureates. Indeed, the D-i-D estimator in each model indicates the magnitude of this effect on DV by taking into account ex-ante

Table 4 -

 4 Mean difference test estimation of DV in period 1

The period post-Prize has been excluded to avoid issues related to distortions of the results following the fact that the laureate become more famous and can received additional solicitations and can be diverted from research.

Spring 2019 version


Mathurin Soh
email: mathurinsoh@gmail.com

Baudoin Nguimeya Tsofack

Clémentin Tayou Djamegni

Nabil Gmati

Mathieu Roche

Tri Nguyen

Laurent Debreu

Multi-Ant Colony Heuristic Approach To Solving The Traveling Salesman Problem

Keywords: Ants, Colony, Heuristic, Multi-colony, Traveling Salesman Problem

In this paper, we propose a new approach to solving the Traveling Salesman Problem (TSP), for which no exact algorithm in litterature is known to find a solution in polynomial time. The proposed approach is based on Ants Colony Optimization. It puts several colonies in competition to find improved solutions (in execution time and solution quality) to large TSP instances, and allows efficient exploration of the range of possible solutions. The results of experiments show that the approach leads to better results compared to other heuristics from the literature, especially in terms of quality of solutions obtained and execution time.

I INTRODUCTION

The Traveling Salesman Problem, TSP for short, is one of the most common combinatorial optimization problems. TSP is a classical problem which, has been studied in the field of operations research and computer science since the beginning of the years 1950. Its statement is simple, and yet it remains one of the most difficult problems in operations research because it is considered NP-difficult [START_REF] Rego | Traveling salesman problem heuristics: Leading methods, implementations and latest advances[END_REF]. As a result, a large number of techniques were developed to solve this problem. Much of the work on TSP is only motivated not by practical applications, but rather by the fact that it provides a framework ideal for study platforms of general methods that can be applied to a wide range of combinatorial optimization problems. In the TSP, a number of cities are indicated and linked to others by arcs. A salesman starts his tour from any city and travelling only once to each city, and returns to the starting city once again. The idea of the problem is to find the shortest route for the salesman from a given city, visiting n cities once and then finally returning to the city of origin.

Despite the multitude of methods available to solve the fundamental or applied TSP, none of the methods to date have been successful in resolving large instances [START_REF] Rego | Traveling salesman problem heuristics: Leading methods, implementations and latest advances[END_REF][START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF]. Indeed one is generally confronted with a combinatorial explosion and a limitation of computers memory resources when the size of the instances increases. However, problems related to TSP are increasing frequent in our society and must be resolved. For most TSP large instances, the optimal solution is seldom achieved even by the most effective and up-to-date heuristics. In this work, we are interested in solving TSP using Ant Colony Optimzation (ACO). We propose a new ACO-based heuristic solution to this problem, using several colonies of ants. In the rest of this paper, we present in section 2, we present the TSP, a mathematical formulation and we give some applications. Section 3 is devoted to the problem statement. A review of litteraure on solving TSP by heuristics is given in section 4, Our contribution is presented in section 5. Section 6 is dedicated to experimental results, elucidated from tests and discussions that are performed with TSP instances from the TSPLIB library. Section 7 concludes our work.

II THE TRAVELING SALESMAN PROBLEM

The Traveling Salesman Problem (TSP) is defined as follows: given n points (cities) and the distances between each point, find a path of minimum total length that passes exactly once through each point and returns to the starting point [START_REF] Rego | Traveling salesman problem heuristics: Leading methods, implementations and latest advances[END_REF][START_REF] Teti | Heuristiques du problème du voyageur de commerce[END_REF]. The distance can also be seen as the cost in general. This combinatorial optimization problem, therefore, consists in searching for the best solution among several possible choices. However, it is easy to state but difficult to solve. The problem is to determine a turn or Hamiltonian circuit, i.e. passing once and only once through the n cities, and that is of minimum cost. It is classified as a NP-difficult problem [START_REF] Rego | Traveling salesman problem heuristics: Leading methods, implementations and latest advances[END_REF][START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF], because there is no known method of resolution that provides exact solutions in reasonable time for large instances (large number of cities) of the problem.

Formulation

Mathematically, the Traveling Salesman Problem can be formulated as follows: Let n cities and C ij , the cost or distance corresponding to the trip i → j. Let the variable X ij , which is 1 if the tour contains the trip i → j, and 0 otherwise. The problem is written as [START_REF] Stuetzle | The Traveling Salesman Problem: State of the Art, TUD SAP AG Worshop on Vehicle Routing[END_REF]:

                           M inZ = n i=1 n j=1 C ij X ij n J=1 X ij = 1 ∀i n i=1 X ij = 1 ∀j n i∈Q n j∈Q X ij ≥ 1 ∀Q X ij ∈ {0, 1}∀i, ∀j (1)
where Q represents a subset of 1,..., n and its complement. The constraints (c) express that the permutation of the n cities must be a trick, i.e. no subtower can exist.

TSP Applications

Globally, the TSP provides an example of a study of an NP-complete problem whose solution methods can be applied to other discrete mathematics problems. It has several real life applications even in its purest formulation, such as planning, manufacture of microchips, transportation, networks, computer wiring, vehicle routing, job-shop scheduling and logistics. For example, to find the shortest route for school buses or, in industry, to find the shortest distance that the mechanical arm of a machine must travel to drill holes in a printed circuit board.

III THE PROBLEM STATEMENT

Existing algorithms for solving the TSP are not efficient enough. As the number of cities increases, the time or space required to solve the problem increases exponentially. The ant colony system solves the problem in a reasonable time and produces optimal solutions [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF]. But when the dimension of the problem increases, it takes a long time to produce the result which is often not optimal. Thus, a modification is needed to solve large instances of the traveling salesman problem. In this work, we propose an approach for solving the TSP based on an ant colony optimization heuristic (OCF) in which several colonies are put in competition to find competitive results and able to minimize the known execution times or to give optimal or near optimal solutions to the instances whose solution remains difficult to reach by current methods. This new approach would allow to explore more efficiently the ranges of possible solutions, and to determine the satisfactory iteration techniques to build as quickly as possible the path leading to the optimal solution among thousands of possible paths. We are particularly interested in the multi-colony approach for several reasons: First, we wish to offer a greater exploration in terms of the possibility First, we want to offer a greater exploration in terms of deployment possibilities of the ants, which was not the case with a single colony. Second, we want to obtain a multiplicity of potential solutions to the problem during the optimization during the optimization process. Third, we want to obtain good solutions more quickly, due to the good solutions, because of the competition at the colony level.

IV REVIEW OF ART

Several approaches ranging from exact to approximate methods, have been used to address the TSP. The simplest approach is the exact methods approach, which consists of listing all possible solutions and taking the best solution. These exact approaches are effective only for small instances where the explicit enumeration of solutions is possible in reasonable time [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF][START_REF] Chauhan | Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach[END_REF]. For large instances, most of the work is based on heuristic and meta-heuristic methods. In literature, there are two types of heuristics: Those that build a tour from scratch and those that are effective at improving an existing tour called Tour Enhancement Heuristics. Research into heuristic methods for solving TSP has included Dorigo and al results [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF][START_REF] Stuetzle | The Traveling Salesman Problem: State of the Art, TUD SAP AG Worshop on Vehicle Routing[END_REF] who, inspired by the collective behaviour of ants and their similarities with TSP, proposed the first ant colony algorithm for TSP: "'the natural Ant System (AS)". Unfortunately, the purely probabilistic choice of the AS makes it less efficient in terms of diversification, thus favoring the risks of premature convergence. To improve the performance of AS on large problems, Dorigo et al [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF], modify the AS transition rule to provide a better balance between exploring new areas of the solution space and exploiting the accumulated knowledge of the problem to intensify the solution. To this end, they introduce a new rule that depends on a q 0 (0 < q 0 < 1) parameter. Q is a randomly generated number, evenly distributed between [0.1]. With this new version, the choice of the next cities is not only probabilistic but also according to a q parameter. The resulting algorithm is called ACO [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF]. Only ACO has shown some weaknesses in terms of explorig new areas and intensify solutions.

Beside these so-called construction heuristics, we have improvement heuristics such as the Kopt Heuristic (K = 2, 3, ...) which improves solutions by testing whether permutations of k paths produce more optimal rounds [START_REF] Rego | Traveling salesman problem heuristics: Leading methods, implementations and latest advances[END_REF] or the heuristic of Lin-Kernighan (LK) [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF] which is an improvement of the K-opt heuristic with k variables, or the Lin-Kernighan heuristic modified by Helsgaun (LKH). These heuristics efficiently improve solutions starting from an already known solution. Another class of heuristics is hybrid heuristics, which has become increasingly popular in recent years. These hybrid heuristics can be divided into several groups. On one side we have the hybridization of construction heuristics. between them, which consists in replacing a mechanism of one heuristic by a mechanism of another heuristic, to make up for what is limited in one by what is seen as an advantage in the other. In this regard, we can quote hybridization (AG-ACO) done in the works [START_REF] Soh | Algorithmes hybrides pour la résolution du problème du voyageur de commerce[END_REF][START_REF] Teti | Heuristiques du problème du voyageur de commerce[END_REF]. On the other hand, we have the hybridization of construction heuristics (AG, ACO ...) with the Local Search heuristics or Improvement heuristic(LK, LKH, RL). An example of this technique is the one produced in [START_REF] Teti | Heuristiques du problème du voyageur de commerce[END_REF]. This work proposes two hybrid heuristics named "AG-LK" and "ACS-LK" for solving the TSP. The first results from the hybridization of a Genetic Algorithm (AG) and the heuristic (LK) while the second hybridizes the ant colony algorithm (ACS) and the heuristic(LK). However, the authors use only one colony. The results obtained from this experiment have sufficiently demonstrated the efficiency of these hybrid approaches on several instances of TSP [START_REF] Teti | Heuristiques du problème du voyageur de commerce[END_REF]. Unfortunately, the resolution time resulting from this experiment remains enormous. To improve the efficiency of the hybrid heuristics, Soh and al proposed and implemented in [START_REF] Soh | Algorithmes hybrides pour la résolution du problème du voyageur de commerce[END_REF], two hybrid heuristics for TSP. The first one between a Genetic Algorithm (GA) and the heuristic (LKH) which is an improvement of LK by Helsgaun [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF] and the second one between the Ant Colony System algorithm (ACS) and the heuristic (LKH). The resulting heuristics were called respectively "AG-LKH" and "ACS-LKH".

As we can see, due to its real life applications, solving the TSP is a permanent quest in the field of computer science, especially in operations research. Several authors have already worked in this direction by approaching various approaches, as this art review clearly shows. None of these methods has been able to overcome TSP. In the following section, we propose a new hybrid heuristic for TSP.

V MULTI-ANT COLONY OPTIMIZATION APPROACH

Basic idea

To achieve the above objectives, we present the basic ACO proposed by Dorigo et al in [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF]. We then modify this algorithm using multiple colonies. This leads us to a new version that we call Multi Ant Colonies Optimization (MACO). MACO proposes a new way to iterate ants from different colonies by defining more or less one iteration step to optimize the decision of the artificial ants to take preferably the right paths while avoiding the pitfalls of the local optimum. Strategies exchanges or communication between ants during their movements will be done in real time in order to help ants detect failures or wrong paths as quickly as possible. The updating of pheromones by ants is done as in the ACO [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF].

Description or Mechanism of ACO Approaches

For the study, we consider that our problem is modeled in the form of a graph. Each node of the graph represents a city or task to be performed, d ij the distance between cities i and j, and the couple (i, j) the path between these two cities. We will also consider the following:

• The ant represents a solution to the problem at hand; • Computer pheromones are values associated with found solutions. These values depend on the quality of the solutions.

Step 1: Build a path for each ant (Solution)

To move from one node (city) of the graph to another, the iteration and movement of the ants is as follows: Initially (at time t = 0), the algorithm sets m ants to n cities and the intensity of the trace for all city pairs (i, j) is set to a small positive T o value in the pheromone matrix. A taboo list is maintained to ensure that a city cannot be visited twice during the same tour. Each ant k will therefore have its own list of Vk-taboo cities that will keep in memory the cities already visited. During an iteration of the algorithm, several ants take turns visiting a sequence of cities.

One cycle (N C) is finished by the time the last of the m ants have finished building.

At t =0, from a sequence of cities already visited, each ant k chooses the next city to add to its list Vk-taboo using a probabilistic rule whose formula is given in equation [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF].

η ij = 1 d i j p k ij = [η ij ] β [τ ij (t)] α Σu∈v k [η iu ] β [τ iu (t)] α (2)
τ ij (t + 1) = ρP k ij (t) + τ ij (3)
It's based on a compromise between visibility (η ij ) and the amount of pheromone (t ij ) present between i and j. The parameters α and β are used to determine the relative importance of track intensity and visibility, respectively in the construction of a solution. This mode of iteration allows to privilege the shortest paths since ants will need fewer iterations to get to the end.

Step 2: Pheromone deposition and solution evaluation

When an ant moves from city i to city j, it leaves a certain amount of pheromone (value) on the arc (i, j). A so-called pheromone matrix records information about the use of the (i, j) arc. At each stage of the round, the matrix is updated so that the greater the use of the (i, j) arc in the past, the more pheromone it has been used, the higher the probability that these arcs will be used again in the future. In this version of ACO, it says, there is an overall update of the pheromone trace intensity after each transition based on the assessment solutions found. For example, an ant moving from node i to j will be able to signal the following ants that are arriving in i if the displacement in j is a justified displacement. Equation (4) allows the pheromones to be updated.

τ ij (t + 1) = ρτ ij (t) + τ ij (4)

Ant Colony Optimization algorithm (ACO)

The Ant Colony Optimization procedure is stated in algorithm V.1

Description of Idea approach MACO

Our approach called MACO is based on ACO approaches with the difference that MACO uses several ant colonies to allow a better exploration of the paths and optimizes the solutions found by another LKH improvement heuristic. Indeed, one of the major flaws in single colony [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF] ACO is the difficulty for the colony to be able to explore efficiently the solution ranges especially for large instances. With MACO, we intend to solve the problem using several colonies.

We put several colonies of artificial ants in competition with each other depending on the size of the problem to win in terms of exploring solutions. In this way, the different colonies build their tour independently and collaborate through a kind of shared memory (global pheromone matrix) by stimulating a pseudo-parallelism to reach the common goal. Indeed, each colony is placed in a departure city, a travel step is authorized for each colony in turn. If an ant belonging to a colony during its iteration finds a better solution than the one known by the other ants in the different colonies, it quickly informs the others by updating the solution through the global communication matrix. To optimize the solution time, information about the pheromone matrix is given in real time immediately after each transition and not delayed.

The different colonies of the MACO algorithm are independent and build their solutions independently. while working closely together to achieve the final goal through communication mechanisms made possible by a communication matrix and values called pheromone.

Each colony (the ants) represents a solution to the problem being treated. The pheromone matrix is common to all colonies. It is used as a shared memory to allow the ants to communicate with each other to guide each other's search. This matrix is dynamic and is used by the colonies to incrementally build solutions. Each ant has a simple behavior, but the exchanges between ants are made by the intermediary of of the pheromone matrix, allow the gradual production of a solution that is close, if not optimal. Ants communicate indirectly via dynamic modifications of the pheromone tracks and thus build a solution to a problem, based on their collective experiences.

Description of the steps of the MACO algorithm

Step 1: Initializing the algorithm: Initially, there's no pheromone on the arcs. The global pheromone matrix is initialized with 0 values for each pair of nodes. To initialize this matrix for the first time, the ants move randomly and in parallel per colony and build their first round. Each colony has its own local communication matrix. Once all the points have been visited, the ants return to their starting point (city). At the end of this first stage, the ants modify the global communication matrix by updating its entries with the best colony found (the best solution at the end of a tour).

Step 2: Construction of solutions: After the initialization phase, from this sequence of cities already visited, within the different colonies, the ants move this time on the different nodes of the graph according to a probability and therefore the equation is that of formula [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF]. It allows the colonies to favour the shortest paths during the different iterations. During a tour, each ant k of a colony L records in its taboo list (memory) the list of cities already visited. The new probabilistic formula for selecting a node by the ant k of colony L is defined by the expression p k,l ij [START_REF]Traveling Salesman Problem Library[END_REF]. This probability is modeled on the one used in the ACO heuristic [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF] described above.

p k,l ij (t) = [η ij ] β [τ ij (t)] α Σu∈v k l [η iu ] β [τ iu (t)] α if j ∈ v k l 0 else (5)
where v k l is the set of nodes (cities) not visited by ants in colony L.

Description of the Pheromone Matrix:

It's an array of i rows and j columns. At t = 0 each entry of the matrix is initialized with the value 0. τ ij (t) represents the intensity of the pheromones on the (i, j) edge at the t cycle.

During the construction of a path, after each transition of an ant k belonging to a colony L, ants from different colonies use directly the global communication matrix to communicate and immediately update pheromones as they evolve. The pheromone matrix evolution equation is described in equation ( 6) by :

τ ij (t + 1) = ρτ ij (t) + τ ij (6)
Equation ( 6) is the same as equation (3) in ACO [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF]. The main purpose of updating after each transition is to simulate a kind of parallelism in order to save computing time by giving the information on the global communication matrix in real time and not in delayed time. As in ACO, to reduce failures, pheromones evaporate [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF]. The pheromones have to be reduced (value) on each path depending on the quality of the solution. This allows the ants after a certain time to avoid taking certain paths that can lead to failure. This characteristic is modeled via the parameter ρ (0 <ρ <1) . The evaporation equation of the pheromone matrix is described by the formula [START_REF] Bp | Parallélisation d'un algorithme d'optimisation par Colonies de Fourmis pour la résolution dun problème d'ordonnancement industriel[END_REF].

τ ij (t + 1) = (1 -ρ)τ ij (t) (7)
The inverse of the distance between cities η ij = 1 C i j called visibility is a static information used to guide ants to nearby cities and avoid cities that are too far away. The parameters α and β are used to determine the relative importance of the ant's presence in the area. the intensity of the trace and the visibility in the construction of a solution. This is based on a trade-off between visibility (η ij ) and the amount of pheromone (t ij ) present between i and j at cycle t. These parameters are the same as those used in ACO [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF]. Each colony corresponds to a potential solution to the problem, i.e. a complete tour. When recovering a solution, each ant in the different colonies provides part of the solution to the problem. The assembly of the different sub-solutions provides the solution to the original problem. If at a given time t all the ants in a colony have the same solution, the iterations are stopped. The procedure finally obtained for optimization by multi-colony ants is the algorithm V. Complexity of MACO Algorithm The study of the complexity of our MACO algorithm is done by subdividing the algorithm into 4 sections to calculate the complexity.

-Initialization: Since we have assumed a total interconnection between cities, we have a complexity of O (n 2 + m. L).

The Constructions of the path, and progressive deposition of pheromones plus evaluation of solutions: Complexity O (n 2 . m. L).

Pheromone Evaporation:in the Complexity is O (n 2 ).

-Evaluating paths after each transition: Complexity O (n.m.L). For the L colonies, we compare the towers of m ants in each colony. Each tower has a length of n elements.

In summary, we obtain the global complexity by adding the complexity of step 1, to the product of the total number of rounds (i.e. NCmax ) by the global complexity of steps 2 to 4. This gives O(n 2 + m.L + N Cmax.n 2 . m.L). or finally O(NCmax . n 2 . m.L)

VI EXPERIMENTAL RESULTS -DISCUSSIONS AND INTERPRETATION

In order to demonstrate the performance of the approach we propose, we perform computer simulations on a machine with the following characteristics: Intel Dual core, 2Ghz processor, 2Gb RAM, Kali Lunix operating system. In all the experiments in this section, we define as starting parameters in a first time m = 100 and L = 10, then in a second time m = 100 and L = 50. These experiments are carried out on the reference problems Lin105, Pr124, LIN318, att532, ALi535, rat783, std1655, Vm1748, pr2392, Usa13509 and pla33810 all from the TSPLIB library [START_REF]Traveling Salesman Problem Library[END_REF] with available TSP instances.

With the same conditions, we subjected them to our heuristics and compared the results obtained with the best current heuristics for TSP at the time of testing. Several simulations (100 in total) allowed us to assess the relevance and effectiveness of our approach. By making a comparative study between the MACO heuristic with the basic AS heuristic and ACS obtained by Dorigo [START_REF] Rego | Traveling salesman problem heuristics: Leading methods, implementations and latest advances[END_REF] as well as ACS-LK one of the best heuristics for the TSP from the literature proposed in [START_REF] Teti | Heuristiques du problème du voyageur de commerce[END_REF] or those obtained in [START_REF] Soh | Algorithmes hybrides pour la résolution du problème du voyageur de commerce[END_REF] (AG -LKH, ACS -LKH) and under identical test conditions we obtain the results of Figures 1, 2, 3 and 4 respectively. In the results presented in figure 3, the green lines represent the cases where the gains observed with MACO are related to costs and turnaround times. The brown lines symbolize the cases where the observed gain is only at the level of execution time, the optimal solution having already been reached. We note a better execution time for MACO compared to those obtained so far with the best algorithms (ACS-LK, AG-LK, ACS-LKH, ACS) at the time of the tests. We also obtain a better and always optimal cost compared to the best solutions known so far with Figures 5 and6 present a comparison of the performance of our approach compared to the improved AG -LKH and ACS -LKH approaches, using the above-mentioned reference problems and terms of solution quality and runtime respectively.

The results of our experiments clearly show the superiority of our algorithm over others, especially in terms of solutions quality and in terms of time taken to reach this optimal solution. However, for some of the instances for which we do not yet know a solution, our approach could not give an optimal solution.

VII CONCLUSION AND PERSPECTIVES

In this work, we proposed a new multi-colony ant heuristic (MACO) to improve the search for optimal solutions to TSP and in optimal time. The proposed MACO algorithm is based on the use of several ant colonies. It shows clear improvements in both cost and execution time, proving that it is much more competitive than the best time heuristics for TSP. A limitation related to our multi-colony approach will probably be the increase in execution time needed to find a solution in some cases, or the use of much more resources (memory and processor). We believe that parallelization of the ACS [START_REF] Dorigo | Ant Colony Optimization: Overview and Recent Advances[END_REF] or MACO algorithm would be a considerable contribution to metaheuristics to reduce TSP resolution times.

VIII BIOGRAPHY

Mathurin Soh is a senior lecturer at University of Dschang, Cameroon. He holds a PhD in software engineering with a focus on software localizability. His researches interests include combinatorial optimization problems, formal methods of software localization.

Baudoin Nguimeya Tsofack is a PhD student at University of Dschang, Cameroon. He holds a Master's Degree in Computer Science. His research interests include combinatorial optimization problems and especially algorithms for Travelling Salesman Problems.

Clémentin Tayou Djamegni, is Full Professor in Computer Science at University of Dschang, Cameroon. He is currently Head of computer science department at Fotso Victor University Institute of Technology, Bandjoun, Cameroon. He has published many papers in various reputed Journals, National International Conferences. He has proposed two solvers for the Parallel Track SAT competition, wining the second prize in 2020 and 2018. He serves as a reviewer in many international journals and is involved with a number of conferences as committee members.

Algorithm V. 1

 1 Ant Colony Optimization algorithm Inputs m : number of ants per colony n : number of cities 1 k for each of steps 13 Insert the solution k in the TabooList 14 Update globally the trace according to the best solution of the cycle 15 NC:= NC + 1 5.3 Multi-Ant Colony ACO Approach (MACO)

  For K from 1 to m 7 Construction of a tour by each ant at random 8 Gradual deposition of pheromones in the dij matrix of each colony 9 Evaluation and selection of the best colony 10 Initialize the Dij matrix with the best colony 11 Vi to be added to the current tour with formula(1) 16Evaluate the solution of the ant K on route ( i , j ) 17 Update globally the trace according to city pair ( i , j ) if it 's better than 18 the previous ants according to formula 5 and 6 ( evaporation ) 19 Insert as you go ( i , j ) in the taboo list so as to construct gradually solution K 20 S:= Best solution (Each colony provides a partial solution )

Figure 1 :

 1 Figure 1: Results AS

Figure 2 :

 2 Figure 2: Results ACS-DORIGO [2]

Figure 3 :

 3 Figure 3: Comparison of MACO algorithm with ACS-LK hybrid algorithm

Figure 4 :

 4 Figure 4: Comparison MACO algorithm with ACS-LKH and AG-LKH algorithms

Figure 5 :Figure 6 :

 56 Figure 5: Comparison MACO, AG-LKH, ACS-LKH in terms of solution quality

2

  Algorithm V.2 MACO Algorithm. Inputs m: number of ants per colony, L:Number of colonies, n:number of cities

	1 Nc:=0
	2 Dij:=0	// Global matrix
	3 dij :=t0	// local matrix of pheromones
	4	Initialize t0 // with each ant 's home city
	5 Place each colony randomly in a starting point ( city )
	6