Florent Robert
email: florent.robert@efiautomotive.com

Mohamed Bensetti

Filipe Vinci

Laurent Santos

Philippe Dufour

Dessante

L Dufour

Multiphysics Modeling and Optimization of a Compact Actuation System

published or not. The documents may come   L'archive ouverte pluridisciplinaire



Abstract-This paper describes a methodology for the optimization of complex actuation systems, using analog simulations and an evolutionary algorithm. Our proposal consists on the development of an automated design framework that helps the designer to quickly complete a pre-sizing step while ensuring that multi-domain requirements are met within short development times typical of automotive industry. Multiphysics constraints can be handled, allowing the sizing of a complete automotive mechatronic system. The effectiveness of the methodology is demonstrated in the case of an exhaust gas recirculation (EGR) valve. Electrical, mechanical, thermal and magnetic requirements are met while a minimal volume is reached.

Index

Terms-Automotive, Electrical Drive, Optimization, Multiphysics, Smart actuator, System.

I. INTRODUCTION

AR manufacturer are expected to design cleaner and more efficient vehicles than in the past. International standards, such as EURO6 [1], impose tougher pollutant emission limits. Consumers are looking for greater comfort and fuel efficiency. To meet these challenges, cars have become increasingly complex platforms integrating many subsystems. These subsystems must satisfy the required purposes, coexist with all others and to be optimally designed. Compact actuators are one of such a subsystem that is widely used in automotive applications. The design of these actuators entails the concurrent development of the electromechanical assembly (actuator), power electronics converter, EMC (Electro Magnetic Compatibility) filter and loop control algorithm. This is a challenging task, for each of these is typically handled in separated modeling domains.

The literature abounds with examples where optimization algorithms are used for the design of elementary functional subsystems. In [START_REF] Gutfrind | Analytical study of an optimized limited motion actuator for automotive application used in engine combustive flow regulation[END_REF], authors succeeded in sizing a DC machine dedicated to an automotive application. Furthermore, in [START_REF] Bendali | Design with optimization of an interleaved buck converter for automotive application; effect of the EMC constraint[END_REF], a power converter is defined using an optimization algorithm, taking into account the EMC constraints. These studies report some interesting results and they outline a global approach which can be adopted by engineers in their daily tasks. In both cases, the analytical approach allows a relatively fast simulation run. This feature is all the most important in the sizing of a global system, where many parameters and interactions must be considered. However, the sizing of the machine and the converter are rarely considered simultaneously in the same approach.

Nevertheless, optimization of a multiphysics system by simulation remains difficult and expensive, since each simulation run takes significant computing time, and an optimization process relies on a huge number of runs. The computing time needed by an optimization algorithm for sizing of complex multiphysics system is generally regarded as prohibitive for industry adoption. Considering the current time to market expectations in the automotive industry, a designer should be able to pre-size the system in less than one week. Using optimization algorithms, a shorter development time is to be hoped, while achieving a greater accuracy due to the extent of the physical domains considered. Although the time spent to create and validate a model can appear to be a hindrance to the adoption of our automated approach, once the generic models are integrated into the multiphysics framework, any user can confidently pre-size similar parts.

In this paper, the authors show how an optimization process can be effectively applied to the sizing of a complete actuation system. This is a kind of multiphysics system because it must satisfy constraints and requirements across several physical domains. The effectiveness of the methodology is demonstrated in the case of an exhaust gas recirculation (EGR) valve.

In the following section, the EGR valve function and structure are described, the hypothesis used in our modeling are discussed and several physical models are introduced. In the third section, the optimization algorithm is applied in order to minimize the volume of the system under thermal and performances constraints, simultaneously taking into account EMC requirements. Lastly, the optimization results are discussed.

philippe.dessante@centralesupelec.fr; mohamed.bensetti@centralesupelec.fr).

F. Vinci dos Santos is with the Chair on Advanced Analog Systems at CentraleSupélec, Gif-sur-Yvette, 91192 France (e-mail: filipe.vinci@centralesupelec.fr). The EGR valve is an eloquent example of a complex compact actuator. The primary function of this device is to reduce the amount of nitrogen oxide particles at the Internal Combustion Engine (ICE) outlet by substituting exhaust gases for a part of the intake fresh air. An electromechanical device is used to obtain EGR flow air requested by the vehicle computer. This paper uses the optimization of the EGR valve to illustrate a sizing methodology that handles complex multiphysics problems by applying an evolutionary algorithm and parallel computing.

Multiphysics modeling and optimization of a compact actuation system

The topology of the EGR valve is illustrated in Fig. 1. The amount of exhaust gases injected is controlled using a flap (the load), driven by a DC motor coupled to a gear. This actuator is driven by a DC-DC converter (an H-bridge), with power supplied by the car battery. A control algorithm, implemented on a microcontroller, modulates the duty cycle of the H-bridge so that the position of the flap is regulated. The pulsed modulation generates conducted electromagnetic interferences on the supply lines that must be suppressed by the addition of an EMC filter.

Automotive components are often exposed to harsh thermal environment [START_REF] Ohadi | Thermal management of harsh environment electronics[END_REF]. In the case of the EGR valve, the exhaust gases flowing through the device and the proximity of the ICE result in a high ambient temperature. This forces us to consider the thermal behavior of our system in its environment to be of utmost importance. Several physical domains must be considered simultaneously by the optimization process in order to find the best solution. In this paper, the process will aim at the volume minimization of the system. To maximize the embedded power density allows for integration within strictly constrained space conditions in the vehicle, which poses a major challenge in automotive industry.

The system volume is mainly due to the machine and its transmission. Transmission will be considered as a fixed parameter even if its sizing could be treated with the same optimization with an appropriate modeling. However, the machine volume can be reduced, only if its electrical current is increased. This current will not affect significantly the size of the converter itself, but it can impact the size of the filter, as well as the switching frequency. For this reason, the objective will be the reduction of the sum of the filter and the machine volumes.

The number of equations and couplings is too large to allow solving for an optimized set of parameters using a classic approach. Fig. 2 shows the modeled domains and how they are coupled in our system. A Differential Evolution (DE) algorithm [START_REF] Price | Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series)[END_REF] is chosen to optimize the system as gradient methods cannot be used on such complex coupled models. Moreover, a non-deterministic approach allows us to reach a global optimal solution rather than a local optimum.

In the next subsections, each model will be detailed.

A. Electrical model

The electrical model illustrated on Fig. 3 is divided into two parts. The first part concerns the DC machine: an inductor LMotor in series with a resistor RMotor are representative of the lowfrequency impedance of the machine. The mechanical reaction introduces the counter electromotive force EMF. However, the actuator is considered to be in locked-rotor state. This assumption is consistent with the expected functional behavior of the system since it is supposed to maintain a position. The current absorbed by the motor and the value of the equivalent resistor are the basis for the evaluation of the Joule losses due to the DC motor.

The second part of the model represents the power converter. An averaged model is sufficient to provide the electrical outputs and the various losses in the electrical system. The converter voltages and currents are linked by a simple linear relation involving the duty cycle α. The value of this parameter is given by the control model. An equivalent series resistance RESR is added to take into account the voltage drop between the battery voltage Ubattery and the input voltage seen by the converter, Uin. The DC-DC converter model includes a serial resistance at its output, RMOSFET, to represent the voltage drop due to the MOSFET on-state resistance.

B. Thermal model

Our application utilizes some simplifications and hypothesis in the thermal model. Temperature differences cause air movements, promoting heat transfer. Due to the small size of the system and to the fact that the rotor is in a static locked state, the convection will be neglected. For the same reasons, radiation will be neglected even if this assumption could be a source of error, as stated in [START_REF] Wang | Electronics packaging simplified radiation heat transfer analysis method[END_REF]. Hence, heat transfer will be modeled as conduction. Because of the lack of information at the pre-sizing step, contact thermal resistances are not considered.

The H-bridge structure is composed of four power MOSFET switches. Heat flux produced by the switches is evacuated through the PCB and by natural convection. Conduction and switching losses in the MOSFETs are calculated according to classical equations based on the components characteristics and the switching frequency. The study context considers copper losses (Joule heating) in the motor windings, defined by the coil turn number and the winding dimensions, all other kinds of heating sources in the machine are ignored.

The various parts of the DC motor and the H-bridge were modeled using thermal resistances and thermal capacities, assembled in 3D, as shown on Fig. 4. The implementation (using an LTspice IV hierarchical netlist) contains hundreds of nodes. Both motor and converter models are coupled through a 3Dbox, which represents the plastic package of the whole system. The box surfaces, the DC motor and the converter are airspaced. The outer temperature (ambient temperature) has to be fixed by the designer, and the heat transfer between the box and its environment is modelled by convection. Electrical and thermal data were collected on an industrial prototype to validate the relevance of the electro-thermal model introduced in this subsection and the previous one.

The measurements were performed at a 22°C ambient temperature. The converter and the DC motor were supplied in an open-loop configuration, with a locked-rotor state. The duty cycle was approximately 0.21 under a supply voltage of 12V. The whole system was packaged as shown on the Fig. 5. The evolution of the motor current and voltage must be compared to a measurement result, since these are the sources of the main losses in the system, and thus the input data for the thermal model: the results are shown in Fig. 6.

The temperatures obtained by simulation and experimental measurement on the motor case and on the MOSFET packages can be compared using Fig. 7. Overall, experimental and simulation results match satisfyingly. However, the evaluation of the MOSFET package temperature is well below the measured value. Our modeling hypotheses introduced above are clearly too coarse w.r.t. local thermal phenomena (convection and radiation) at the MOSFET scale. This is the most likely explanation for this discrepancy.

C. Magnetic model

DC motor performances are influenced by its thermal environment, through the behavior of the permanent magnets. A simple linear analytical model, based on [START_REF] Gutfrind | Analytical study of an optimized limited motion actuator for automotive application used in engine combustive flow regulation[END_REF], is used to take into account the temperature of the magnets extracted from the thermal model to deduce the torque constant available in the motor. Equation (1) takes into account the impact of the temperature on the magnet behavior. The flux density of the magnet Br is given in (1) as an affine function of the temperature Temp, with an offset Br offset and a slope Br slope . 𝐵 𝑟 = 𝐵 𝑟 𝑜𝑓𝑓𝑠𝑒𝑡 + 𝑇𝑒𝑚𝑝. 𝐵 𝑟

𝑠𝑙𝑜𝑝𝑒

(1) 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 9 0 0 0 1 1.5 The flux density in the air gap Be can be deduced from Br using [START_REF] Gutfrind | Analytical study of an optimized limited motion actuator for automotive application used in engine combustive flow regulation[END_REF].

𝐵 𝑒 = 𝐵 𝑟 . 𝑒 𝑎 𝜇 𝑎 . 𝑒 𝑚𝑎𝑔𝑛𝑒𝑡 + 𝑘 𝑒𝑎 . 𝑒 𝑎 (2)
Where ea and emagnet are respectively the air gap and the magnet thicknesses. μa is the relative permeability of the magnet and kea is the concentration coefficient of the magnetic flux φ. Then, φ can be deduced using the equation (3). 𝜑 = 𝐵 𝑒 . 𝑇 𝑎 . 𝜋. 𝑟 𝑒𝑟 . 𝑙 𝑟𝑜𝑡𝑜𝑟 [START_REF] Bendali | Design with optimization of an interleaved buck converter for automotive application; effect of the EMC constraint[END_REF] Where the aperture angle of the induction pole intervenes through the coefficient Ta.π. rer and lrotor are respectively the radius and the length of the rotor. Finally (4) gives the torque constant where n is the number of winding turns in the motor.

𝐾 𝑡 = 𝜑. 𝑛 2. 𝜋 (4)

D. Mechanical model

Simple analytical equations allow the connection between the electrical characteristic of the DC motor and its mechanical behavior. The torque Tmotor can be deduced from the torque constant Kt and the current in the motor Imotor, according to [START_REF] Price | Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series)[END_REF].

𝑇 𝑚𝑜𝑡𝑜𝑟 = 𝐾 𝑡 . 𝐼 𝑚𝑜𝑡𝑜𝑟 (5)
The motor speed ωmotor, the resistive torque Tres and the motor torque are linked by [START_REF] Wang | Electronics packaging simplified radiation heat transfer analysis method[END_REF], where Jmec is the mechanical total inertia seen by the motor shaft.

𝑑𝜔 𝑚𝑜𝑡𝑜𝑟 𝑑𝑡 = 𝑇 𝑚𝑜𝑡𝑜𝑟 + 𝑇 𝑟𝑒𝑠 𝐽 𝑚𝑒𝑐 [START_REF] Wang | Electronics packaging simplified radiation heat transfer analysis method[END_REF] Then the position of the flap can be deduced easily using [START_REF]CISPR25: Radio Disturbance Characteristics for the Protection of Receivers Used on Board Vehicles. Boats and on Devices-Limits and Methods of Measurement[END_REF].

𝜃 𝑓𝑙𝑎𝑝 = 1 𝑟𝑒𝑑 . ∫ 𝜔 𝑚𝑜𝑡𝑜𝑟 . 𝑑𝑡 (7)
Where red is the reduction ratio of the gear.

E. Control model

Implementing an EGR control loop enables the designer to check key design requirements of the system, such as the response time, static or dynamic position errors. A typical control system has been implemented in our model: a Proportional Integrator (PI) control with a filtered input. In our case, the objective is to monitor the position of the flap. The control parameters are defined using the system parameters. The time constant of the control Ti is deduced from the time constant of the system TΣ using [START_REF] Bensetti | Thermal effect modeling on passive circuits with MLP neural network for EMC application[END_REF].

𝑇 𝑖 = 10. 𝑇 𝛴 = 10. 𝑅 𝑚𝑜𝑡𝑜𝑟 . 𝐽 𝑚𝑒𝑐 𝐾 𝑡 2 (8)
If the DE algorithm changes the geometry of the machine, the value of Jmec, Kt or Rmotor, then the control parameters are recalculated. The static gain H0 is given in [START_REF] Diouf | Wideband Impedance Measurements and Modeling of DC Motors for EMI Predictions[END_REF].

𝐻 0 = 1 𝐾 𝑡 . 𝑟𝑒𝑑 (9)
Finally, the proportional term Kp of the control is calculated thanks to [START_REF] Robert | Multi-physics optimization of a smart actuator for an automotive application[END_REF], where Tresp is the expected response time of the system. The system must meet a mission profile, depicted on Fig. 8.

𝐾 𝑝 = 10 𝑇 𝑟𝑒𝑠𝑝 . 𝐻 0 [START_REF] Robert | Multi-physics optimization of a smart actuator for an automotive application[END_REF] Fig. 8. Position mission profile defined for the EGR valve.

F. EMC model

Automotive systems engineer wish to benefit from an early integration of the EMC constraints in their design process. Nowadays, the control of automotive electromagnetic interference is essential. Conducted interferences have to be maintained within the limits allowed by EMC standards. Our automotive application is subject to the CISPR25 EMC standard [START_REF]CISPR25: Radio Disturbance Characteristics for the Protection of Receivers Used on Board Vehicles. Boats and on Devices-Limits and Methods of Measurement[END_REF], which addresses a frequency range from 150kHz to 108MHz.

Filtering is a widely used approach where the potential victim is protected against the interferences thanks to an EMC filter. However the filtering components (inductors and capacitors) can account for a large part of the total volume of the product: the lower the frequency to filter, the larger the component is. Ignoring the EMC constraints during the development process can lead to a functional product, but which does not meet the normative requirements. Therefore the whole sizing has to be reconsidered or a bulky filter has to be inserted, posing the risk of sacrificing the compactness of the system.

For this reason, our study aims at limiting the interference emitted within a frequency range from150kHz to 10MHz, in order to avoid this EMC compliance risk. Beyond this limit of 10MHz, the EMC filter can be unobtrusively sized without particular precautionary measure concerning the volume of the components. Passive components are characterized using a Vector Network Analyzer (VNA) [START_REF] Bensetti | Thermal effect modeling on passive circuits with MLP neural network for EMC application[END_REF], and their impedances, deduced from these measurements, are matched to equivalent models, as illustrated in Fig. 9. PCB and wiring parasitic impedances are not considered, given the frequency domain addressed in this study. Our approach uses a direct simulation in the frequency domain, implemented in the LTspice IV simulator. The interference sources are modeled by equivalent current and voltage sources.

The brushed DC motor and the MOSFET components are the main interference sources because of their switching behaviors. However, the DC motor is considered to be in locked-rotor state. Consequently, it is modeled as a passive impedance (measured with a VNA) and matched to the equivalent model given in Fig. 9 [START_REF] Diouf | Wideband Impedance Measurements and Modeling of DC Motors for EMI Predictions[END_REF].

MOSFET are assimilated to a variable resistance (RDSon/ RDSoff in on/off-states), associated with a parasitic serial inductor and a parasitic parallel capacitor. This complexity level is sufficient to deal with our restricted frequency range. In the frequency domain, this amounts to injecting a trapezoidal waveforms as interference sources. The corresponding Laplace transform is given in (11).

𝑉 ).𝑝 )

(11)
Where A is the magnitude of the signal, trise and tfall are respectively the rise time and the fall time of the interference waveform. T is the switching period and τ is the time during which the signal is greater than A/2. To model the electrical power supply system of the vehicle, a Line Impedance Stabilization Network (LISN) is necessary. The LISN filter is implemented in our model using the device datasheet model as shown in the schematic of Fig. 12. To limit the conducted interference emitted by the system, a Gamma EMC filter is placed at the input of the H-bridge, also illustrated in Fig. 12.

The interference level obtained by the simulation of the model introduced in Fig. 12 is compared to the interference measured on an experimental prototype. The result is given in Fig. 10, which depicts the interference as signal Vp+. In this comparison, the Gamma filter is removed in both experimental and simulation systems. The results match up to 1MHz, and the simulation is representative of the experimental results up to 3MHz. To obtain good agreement beyond this frequency, the model would need further refinement.

G. Simulation

The models introduced in this section were coupled together. Some key variables are exchanged, as depicted in Fig. 2. The widely spread time constants in the system would increase prohibitively the computing time of a simulation run. For this reason, a relaxation method is used to simulate the thermal behavior separately from the evaluation of the other domains. The relaxation, illustrated in Fig. 11, allows one to run a simulation of the thermal model apart from the other models, and it provides the electrical model with updated temperatures. Then, corresponding losses are deduced and the thermal model is computed again. This loop tends to converge, and the losses and the temperatures are considered to be solved when their values do not vary anymore in a given tolerance range.

III. OPTIMIZATION

A. Optimization cost, constraints and parameters

The objective of our optimization is to minimize the geometrical size of the system. Three components are taken into account to calculate the global volume of the system: the DC motor, the power electronics converter and the EMC filter. Both DC motor and power converter are considered into the same box: the package. The remaining space in the box would be used to integrate the mechanical gear and the various mechanical elements that are not represented in our model. The volume of the filter is added to the volume of the box and the sum of these components is the objective function to be minimized in our optimization, as detailed in (12).

𝑉𝑜𝑙𝑢𝑚𝑒 = 𝐿 𝑏𝑜𝑥 . ℎ 𝑏𝑜𝑐 . 𝑒 𝑏𝑎𝑥 + 𝑉 𝐿 + 𝑉 𝐶 (12)

Where Lbox, hbox, and ebox are respectively the length, the height and the depth of the package which contains the DC motor and the power converter. VL and VC are the volumes of, respectively, the inductor and the capacitor of the EMC filter.

Several constraints are considered. First, the capability of the system to meet the functional requirements must be ensured. The system is expected to respect the mission profile defined on Fig. 8. The response time at 90% of the final value must be less than 150ms. This criterion is evaluated during the step input at time=6s. Moreover, the dynamic error of the flap position during the ramp phases (between time=0.5s and time=5.5s) must be less than 3%. In order to limit the mechanical torque ripple, the current ripple in the DC machine must be less than 10% of the current mean value. Thermal constraints must be considered too. The first one concerns the magnet temperature in the machine. To limit the loss of performances due to their increasing temperature, a maximal magnet temperature of 140°C is imposed. To avoid the risk of damage in the power converter, the MOSFET case temperature should not exceed 80°C. Although this constraint may seem severe, it allows to anticipate the situation where the MOSFET selected later frequently presents poor performances (high on-state resistance, high junction-to-case thermal resistance), because of availability or lower cost.

The last constraint concerns the compliance with the EMC standard (CISPR25). The conducted interference must stay below the maximal value allowed by the standard.

To meet these multiphysics constraints, the DE algorithm can change several parameters. Two of them are geometrical distances: the distance L between the converter and the DC machine, and the thickness of the magnet, emagnet. The increase of L can limit the heating of the MOSFET due to the losses in the machine. The increase of emagnet would allow to reduce the current needed by the machine to respect the mission profile, and so the heating in the converter. In both cases, these benefits are counter-balanced by an increase of the global volume. Other geometrical spaces were also considered, but a previous study [START_REF] Robert | Multi-physics optimization of a smart actuator for an automotive application[END_REF] showed that all the distances between the converter and the package on one hand, and the machine and the package on the other hand, would be reduced to their minimal value by the optimization. To limit the number of parameters, they are all set to 1mm.

A third sizing parameter is considered: the switching frequency of the converter fswitch. The switching losses increase with the frequency but the current ripple and the EMC filter size decrease. The optimization of this parameter should allow the tool to reach an interesting trade-off.

Finally, two other parameters are considered in this optimization: the inductor and the capacitor used in the EMC filter. These components are selected among components referenced in the circuit parts databases, created from experimental characterization. For the purposes of this study, 41 capacitors and 18 inductors were stored, all compliant with automotive specifications (temperature range).

The minimum, maximum and initial values of the parameters are given in the Table I. The maximum and minimum values are set according to the technical feasibility, the mechanical tolerances and the maximum values available in the database. The initial parameter setting must respect the constraints. A large value for L tends to decrease the MOSFET heating, and a maximal emagnet tends to decrease the current, and so the MOSFET heating. A maximal switching frequency will limit the current ripple, but stronger filtering is necessary to limit the EMC interferences. Given the initial settings respecting the constraints, then the volume must be reduced. An evolutionary algorithm based on DE is used to search for the system's optimum value. The settings of the optimization are as follows: the population includes 50 individuals, the cross factor is 0.9, the mutation coefficient is 0.6 and a maximum number of iteration is 1500 (shutoff parameter in case of nonconvergence or slow convergence).

B. Multiphysics optimization of the system

The computing time of the whole optimization is two days. However, mean simulation time is not significant, since the electro-thermal relaxation loop can lead to several simulations for a given set of parameters. Moreover, the constraints with the lower computation cost are checked first to prevent the algorithm from running the heavier simulations with unacceptable solutions. This strategy tends to increase the computing time of a generation as the optimization converges towards the optimal solution. In any case, two days represents a significant improvement compared to the effort that would be needed for pre-sizing an EGR without optimization process, with a comparably degree of accuracy. Nevertheless, this computing time could be easily reduced using parallelization, since the main simulation software is LTspice IV, which can profit cheaply from virtualization of computing nodes, in the cloud.

The Table I gives the optimal parameters found and the optimal volume of the system. The optimal solution shows reduced distances L and emagnet in comparison with the initial values. Concerning the choice of the filter components, the database contains commercially available values: our algorithm uses continuous values and the components with the nearest value in the database are chosen and, then, used in the simulation. Thus the optimal values for the capacitor and the inductor (respectively 5.6µF and 4.31µH) lead to the closest components in the database, whose values are respectively 4.7µF and 4.7µH . The switching frequency is reduced from 200kHz to 30kHz.

This optimal solution meets the various constraints in the system. To determine the influence of the temperature on these constraints; five evaluations of the performances are done at five different instants during the thermal simulation. Fig. 13 shows the copper temperature in the DC motor and the five points in time selected. The complete thermal simulation time is 4000s, which corresponds to the time needed to reach the thermal steady state in the case where the geometrical parameters tend to maximize the volume.

The optimal system complies with the thermal constraints. Fig. 13 shows that the magnet temperature is always less than 140°C, and the MOSFET case temperatures do not exceed 80°C. The limiting constraint is the MOSFET temperature, whereas the weakness of the thermal model on this very point has been highlighted. For this reason, it is deemed necessary to keep a significant safety margin concerning the value of the constraint. Given the losses level in the component, we know the component can tolerate a case temperature of up to 110°C, but the inaccuracies in our thermal modeling prompts us to limit this temperature to 80°C. An improved thermal model would possibly make the optimal selection of the MOSFET part more realistic.

Whatever the thermal conditions during the profile, the response time is 115ms, and thus less than 150ms. Dynamic error is less than 2.4%, and thus less than the 3% maximum error. The values reached by the parameter L during the optimization explains why the MOSFET temperature are exactly at the limit given by the constraint. Fig. 14 shows the current in the DC motor. The ripple is 143mA, and the mean value is 1.427A. The relative current ripple is then 10%, so it matches with the limit given by the constraint. As far as possible, the optimization leads to the reduction of the switching frequency, helping the EMC interference reductions. Indeed, Fig. 15 shows that the interference obtained is below the limits required by the standards. To obtain this interference spectrum, the choice of the filter components is essential. One can observe in Fig. 15 that without the optimal filter, the interference would exceed the CISPR25 (class 5) standard limit, at 150kHz. Each time correspond to an increase of the magnet temperature of a fifth of the global magnet heating. The response time is still 115ms at any moment and does not depend on the temperature.

As expected, the filter given by the optimization algorithm is one of the most compact filters possible with the available components. It is composed of a capacitor of 4.7µF in a Surface Mounted Device package, and an inductor of 4.7µH. The global volume of the filter is mainly due to the inductor. The filter volume is 1.22cm 3 , whereas the global volume of the system is 371.46cm 3 . Thus the filter represents only 0.33% of the system volume.

This observation leads one to realize that the parameters emagnet and L are of utmost importance for the definition of the global volume. The tool had no prior information of this. Nevertheless, our approach assures the designer that the filter obtained is one of the smallest possible, given the parts database considered. Indeed, the 738 possible filters have been simulated and their volume is represented on Fig. 16, as a function of the margin available with respect to the standard limit. The optimization algorithm found a filter of minimal volume without consideration for the margin maximization. A biobjective optimization could be an interesting improvement to the method.

IV. CONCLUSIONS

We can conclude that the optimization algorithm solved the trade-off to size the system. The feasibility of applying an evolutionary algorithm to pre-size a multiphysics system typical of automotive applications has been demonstrated. It is important to note that the effectiveness of the approach is linked to the quality of the various models, and the strategy employed to couple them into a global simulation. More accurate modeling can lead to a fine-tuning optimization run for parameter determination.

But inherent precision is not sufficient: the multiphysics approach requires a consistent precision level among the modeled domains. Indeed, accuracy leads to increased computing times, but accurate inputs from one domain for less accurate models in another can be considered as a waste of time.

For this reason, an improvement in this optimization approach could be to raise the global precision of the various models. Because of the computing time resulting from this, an adaptive parallelization of the simulation run should be considered. Gradual accuracy optimizations could be used to reduce progressively the search space, using models with varying degrees of complexity.

Lastly, the impact of the optimization in a pre-sizing step on the industrial final product remains an open question. Indeed, several constraints such as costs, availability, obsolescence, or reliability can affect the ultimate design. From an industrial point of view, the integration of these constraints into the same global approach would constitute the ultimate goal to achieve.

Fig. 1 .

 1 Fig.1. EGR valve as a compact actuation system.

Fig. 2 .

 2 Fig. 2. Interaction between the various models.

Fig. 3 .

 3 Fig. 3. Electrical linear modeling.

Fig. 4 .

 4 Fig. 4. System topology and elementary thermal volumes.

Fig. 5 .

 5 Fig. 5. Top left: actuator with thermocouples inserted through the package. Bottom left: closed 3D drawing. Right: exploded view.

Fig. 6 .

 6 Fig. 6. DC motor current and voltage. Comparison between measurements and simulation results.

Fig. 7 .

 7 Fig. 7. DC motor case temperature and MOSFET case temperature. Comparison between measurements and simulation results (H-B means H-bridge).

  Measure 2 -Machine Measure 3 -Machine Simulation -Machine Simulation -H-B 1 and 2 Measure H-B 1 Mesure H-B 2

Fig. 9 .

 9 Fig. 9. Equivalent models of passive components for high frequency simulation.

Fig. 10 .

 10 Fig. 10. Measured and simulated interference spectra.

Fig. 11 .

 11 Fig. 11. Electrothermal simulation using a relaxation approach.

Fig. 12 .

 12 Fig. 12. EMC model of the H-bridge converter associated with the DC motor, the Gamma filter and the LISN.

Fig. 13 .

 13 Fig. 13. Mission profile matching with simulation results at five different times.

  perturbations: CISPR25 standard limit and the system perturbations with and without EMC filter Standard System with filter System without filter

Fig. 16 .

 16 Fig. 16. Volume of the 738 filters as a function of the deviation from the standard. The volume discretization is due to the preponderance of the inductor volume.


Frédéric Chapoton

Sefi Ladkani

Baptiste Rognerud

On derived equivalences for categories of generalized intervals of a finite poset

Keywords:

We study two constructions related to the intervals of finite posets. The first one is a poset. The second one is more complicated. Loosely speaking it can be seen as a poset with some extra zero-relations. As main result, we show that these two constructions are equivalent at the level of derived categories.

Introduction

Let k be a commutative ring with unit. There are various equivalent definitions of the notion of representation of a poset over k. One can look at representations of the Hasse diagram of the poset viewed as a quiver with the relations of total commutativity, or at modules over the so-called incidence algebra of the poset. An alternative definition is to use a functor category. To a poset (Y, ) one can associate a finite category C Y where the objects are the elements of Y and there is a unique morphism between y and y ′ if and only if y y ′ . It is well-known that the category of covariant functors from C Y to the category of k-vector spaces is equivalent to the category of right modules over the incidence algebra of Y . Moreover, it is also classical that if kC Y is the k-linearization of C Y , then the category of functors from C Y to the category of all k-modules k-Mod is equivalent to the category of k-linear functors from kC Y to k-Mod.

Definition 1.1. Let k be a commutative ring and (Y, ) be a poset. The category of k-linear functors from kC Y to k-Mod is denoted F Y,k .

Note that the study of these functor categories is very different from another kind of "representation of posets", that was considered by Nazarova, Kleiner and others (See [START_REF] Simson | Linear representations of partially ordered sets and vector space categories, volume 4 of Algebra, Logic and Applications[END_REF] for more details), which involves a non-abelian subcategory of the category of modules over a one-point extension of the Hasse diagram.

Since the category k-Mod is abelian, the category F Y,k inherits an abelian structure. In particular, one can consider the bounded derived category D b (F Y,k ) of this abelian category. With a slight abuse of notation, we call it the derived category of the poset.

Numerous invariants of the poset can be read inside the derived category such as its cardinality or its number of connected components. It is also the good setting for the study of the Coxeter transformation and the Coxeter polynomial of finite posets (See [START_REF] Ladkani | On derived equivalences of categories of sheaves over finite posets[END_REF] for more details). If two finite posets share the same derived category, then they have the same Coxeter polynonial. Using a computer, it is then easy to find many examples of finite posets with the same Coxeter polynomial, and one can wonder if they also share the same derived category.

In this spirit, there is an interesting conjectural example in the theory of Tamari lattices. It is conjectured by the first author that the Tamari lattice is derived equivalent to the poset of Dyck paths (See [START_REF] Chapoton | On the categories of modules over the Tamari posets[END_REF] for more details). In the same context, we propose another conjecture involving the derived category of the poset of Dyck paths (See Conjecture 3.7).

There are various tools that can be used to check if two posets share the same derived category (see [START_REF] Ladkani | On derived equivalences of categories of sheaves over finite posets[END_REF] or [START_REF] Ladkani | Universal derived equivalences of posets[END_REF] for some explicit constructions). Unfortunately, there are no (known) algorithm and it is most of the time difficult to build such derived equivalences.

One of the difficulties comes from the fact that the derived category of a finite poset may also be equivalent to the derived category of a ring with a-priori no relation with posets. For example the poset 1 < 2 < 3 is derived equivalent to the quotient of the path algebra of the quiver 1 → 2 → 3 by the ideal generated by the path of length two.

In this article we will focus on the set of intervals of finite posets. We start with two possible definitions of categories of intervals of a poset. The first definition is a poset, denoted Γ and viewed as a category. On the other hand, the second category, denoted by kΓ 0 , is not the category of a finite poset. It is, in some sense, the category of a poset with some extra zero-relations. More formally, the category of k-linear representations of kΓ 0 is equivalent to the category of modules over an algebra which is a quotient of the incidence algebra of Γ by zero-relations. The main result of the article is that the categories of k-linear representations of Γ and kΓ 0 are derived equivalent. This result is obtained as a special case of a slightly more general construction, that we illustrate with a few examples.

This general construction takes as starting point a pair of posets X, Y and a morphism from Y to the distributive lattice of lower ideals in X. In fact, we think that it might be seen as a very special case of some derived equivalences obtained by Asashiba, which has considered the so-called Grothendieck construction in [START_REF] Asashiba | Gluing derived equivalences together[END_REF]. Our results are much more elementary and concrete, with a shorter proof and provide an explicit and simple tilting complex. One can hope to apply them in many combinatorial contexts.

The category of intervals kΓ 0 seems to be a good intermediate object when one wants to produce derived equivalences between finite posets. As applications, we prove that the Auslander algebra of a linear order A n is derived equivalent to the incidence algebra of the poset of intervals of A n . Together with results of the second author, this proves that the rectangle poset A 2n+1 × A n is derived equivalent to the triangle poset of intervals of A 2n . Finally, we investigate the relations between the derived category of the poset of (a, b)-rational Dyck paths and the poset of lattice paths in the (a, b)-rectangle. Definition 2.1. The set Int(X) with this particular partial order is called the poset of intervals of X.

Notations. If

Remark 2.2. There is another natural partial order on the set Int(X) which is given by the inclusion of the intervals. However, with this partial order, the resulting endofunctor of the category of finite posets behaves less nicely. For example, it does not commutes with the duality. One can see that this poset is not equivalent to the poset that we consider in this article, even at the level of derived categories.

If [a, b] is an interval of X, then we have an indecomposable functor M a,b in F X,k defined on the objects by:

M a,b (x) = k if a x b, 0 otherwise. If α : x → y is a morphism in kC X , then M a,b (α) = α if a x y b and M a,b (α) = 0 otherwise.
Definition 2.3. Let X be a finite poset and k be a commutative ring. We let Int 0 k (X) be the category where the objects are the intervals of X and,

Hom Int 0 k (X) ([c, d], [a, b]) := Hom F X,k M a,b , M c,d
. Note that we applied an 'op'-functor on each set of morphisms.

Lemma 2.4. Let X be a finite poset, let k be a commutative ring. Then

Hom F X,k (M a,b , M c,d ) = k if c a d b, 0 otherwise.
Proof. If there is a non-zero morphism φ between M a,b and M c,d , then the intersection [a, b] ∩ [c, d] is non-empty. Let x be an element of this intersection. Since φ is a natural transformation, the following diagram commutes:

M a,b (x) = k φx / / M c,d (x) = k M a,b (a) = k φa / / O O M c,d (a). O O
This implies that M c,d (a) = 0. So we have c a d. Similarly, the following diagram commutes:

M a,b (d) φ d / / M c,d (d) = k M a,b (x) = k φx / / O O M c,d (x) = k. O O So, M a,b (d) = 0. This implies that a d b. Conversely, if c a d b, then the morphism φ defined by φ z = Id k for every a z d is a natural transformation from M a,b to M c,d .
In other terms, we have a combinatorial description of Int 0 k (X):

Corollary 2.5. Let X be a finite poset. Let k be a commutative ring. Then Int 0 k (X) is the category where the objects are the intervals of X and the morphisms are:

Hom Int 0 k (X) ([a, b], [c, d]) = k if a c b d, 0 otherwise.
The composition is given by scalar multiplication.

It is easy to see that the categories of k-linear representations of kInt(X) and Int 0 k (X) are not equivalent. This is already the case when X = -→ A 2 . However, we will see that they share the same derived category.

Generalized intervals of a finite posets

Let (X, ) be a finite poset. For an element x ∈ X, we let

[., x] = {x ′ ∈ X ; x ′ x}. A subset Z ⊆ X is closed if [., x] ⊆ Z for every x ∈ Z.
We denote by J (X) the poset of closed subsets of X partially ordered by inclusion. Note that a closed subset of X is also called an ideal of X.

Let X and Y be two finite posets. Let F : Y → J (X) be an order-preserving map. In other words, for y ∈ Y there is a closed subset F (y) of X such that F (y) ⊆ F (y ′ ) whenever y y ′ . Consider Γ the poset defined by

Γ = y∈Y F (y) × {y} ⊆ X × Y
with the partial order induced from that of the product X × Y . In other terms, the elements of Γ are pairs (x, y) where y ∈ Y and x ∈ F (y), with (x, y) (x ′ , y ′ ) ⇔ x x ′ and y y ′ .

The elements of Γ are called generalized intervals for the data (X, Y, F ).

Let us consider the k-linear category kΓ 0 where the objects are the pairs (x, y) such that y ∈ Y and x ∈ F (y) and the morphisms are given by

Hom kΓ 0 (x, y), (x ′ , y ′ ) = k if x x ′ , y y ′ and x ′ ∈ F (y), 0 otherwise.
The composition is given by the scalar multiplication.

Definition 2.6. Let X and Y be two finite posets and F : Y → J (X) be an order preserving map. Let k be a commutative ring. Then, we denote by F Γ 0 ,k the category of functors from kΓ 0 to k-Mod.

Remark 2.7. This setting is a generalization of the two previous constructions for the intervals of a given poset X. Indeed, if X = Y = Z and F : X → J (X) is the map defined by

F (x) = [•, x], then Γ = Int(X) and kΓ 0 ∼ = Int 0 k (X).
3 Main result and applications

Main Theorem

Theorem 3.1. Let k be a commutative ring. Let X and Y be two finite posets and F : Y → J (X) be an order preserving map. Then, there is a triangulated equivalence between

D b F Γ,k and D b F Γ 0 ,k .
Remark 3.2. We postpone the proof until Sections 4 and 5.

Let us give an equivalent formulation of Γ and the category kΓ 0 which is easier to manipulate. Let X, Y and Z be three finite posets with order preserving maps f : X → Z and g : Y → Z. Consider the poset

Γ = {(x, y) ∈ Z ; f (x) Z g(y)} with partial order induced from X × Y .
Let kΓ 0 the category where the objects are the elements of Γ and the morphisms are given by

Hom kΓ 0 (x, y), (x ′ , y ′ ) = k if x X x ′ , y Y y ′ and f (x ′ ) Z g(y), 0 otherwise.
Let X and Y be two finite posets and F : Y → J (X) be an order preserving map. We set Z = J (X), the map f : X → J(X) is defined by f (x) = [•, x] and g = F . Then, the condition on a pair (x, y)

∈ X × Y that f (x) Z g(y) means that [•, x] ⊆ F (y). Since F (y) is closed, this is equivalent to the condition x ∈ F (y).
Conversely, let X, Y and Z be three finite posets. Let f : X → Z and g : Y → Z be two order preserving maps. Then, for y ∈ Y , we let

F (y) = {x ∈ X ; f (x) Z g(y)}.
Since f is order preserving, the set F (y) is closed and since g is order preserving, we have F (y) ⊆ F (y ′ ) whenever y Y y ′ . The condition on a pair (x, y) ∈ X × Y that f (x) Z g(y) is equivalent to the condition that x ∈ F (y).

Example 3.3. As first application, we consider some simple cases.

1. Let X = {1, 2, 3} such that 1 < 3 and 2 < 3. Let Y = {a, b, c, d} such that a < b < c < d. Let Z = {i, j, k} such that i < j < k. The morphism f is defined by f (1) = i, f (2) = j and f (3) = k. The morphism g is defined by g(a) = i, g(b) = j, g(c) = g(d) = k. Then the Hasse diagram of Γ is (1, a) / / (1, b) / / (1, c) / /
(1, d)

(3, c) / / (3, d) (2, b) / / (2, c) / / O O (2, d) O O
For kΓ 0 we have the following presentation with generators and relations of the category (1, a)

/ / (1, b) / / 0 # # (1, c) / /
(1, d)

(3, c) / / (3, d) (2, b) / / 0 ; ;
(2, c)

/ / O O (2, d) O O
where the dotted arrows are zero relations.

2. It is particularly interesting to consider the more symmetric case where Y = Z and g = Id Y . Then

Γ = {(x, y) ∈ X × Y ; f (x) Y y}
and the category kΓ 0 has morphisms:

Hom kΓ 0 (x, y), (x ′ , y ′ ) = k if x X x ′ , y Y y ′ and f (x ′ ) Y y, 0 otherwise.
Let P = {1, 2, 3} where 1 < 3 and 2 < 3. Let X be the poset of 2-chains of P and Y be the poset of 3-chains of P . We let f : X → Y to be the morphism that sends a chain i j to i i j. Then, the Hasse diagram of Γ is

• / / • / / • • o o • o o • / / O O • O O • O O • O O o o • / / O O • O O • O O • O O o o • O O • O O
For kΓ 0 we have a presentation by generators and relations

• / / • / / • • o o • o o • / / O O • O O 0 ? ? • O O 0 _ _ • O O o o • / / O O • O O • O O • O O o o • O O 0 ? ? • O O 0 _ _
More generally, if l ∈ N, one can defined simplicial morphisms between the poset of l-chains of P and the poset of l + 1-chains of P , by duplicating or forgetting the element at a fixe position of the chains. This will give similar diagrams.

Special case of intervals

For the specific case of the intervals of a finite poset, we have Corollary 3.4. Let X be a finite poset. Let k be a commutative ring. Then, the category F Int(X),k is derived equivalent to the category F Int 0 k (X),k . It was shown by the second author that the poset A 2n+1 × A n is derived equivalent to the stable Auslander algebra of the quiver ---→ A 2n+1 . The poset A 2n+1 × A n can be viewed as a rectangle, and the stable Auslander algebra of the quiver ---→ A 2n+1 with linear order can be seen as a triangle. However, there are some zero-relations in the Auslander Reiten quiver that come from the almost split sequences where the left and the right terms are two simple modules. Using Theorem 3.1, we can remove these zero-relations.

Corollary 3.5. Let n ∈ N and k be an algebraically closed field. Then, the poset

A 2n+1 × A n is derived equivalent to the poset Int( --→ A 2n ).
Proof. By Corollary 1.12 of [START_REF] Ladkani | On derived equivalences of lines, rectangles and triangles[END_REF], the poset A 2n+1 × A n is derived equivalent to the stable Auslander algebra of k ---→ A 2n+1 . Because we consider a linear order on A 2n+1 , it is easy to see that the stable Auslander algebra of k ---→ A 2n+1 is isomorphic to the usual Auslander algebra of k --→ A 2n . Now, for m ∈ N * , we consider the Auslander algebra of A m with ordering m < m -1 < • • • < 1. Let Q be the Auslander Reiten quiver of kA m viewed as a category. Let I be the category Int 0 k ( -→ A m ). There is a functor from I to Q which can be described as follows. The interval [i, j] is sent to the indecomposable kA m module with support [i, j], denoted M [i,j] . If [i, j] [k, l], then the corresponding basis element is sent to the irreducible morphism between the indecomposable modules M [i,j] and M [k,l] .

If i = j, then the equality of the morphisms [i, j]

→ [i + 1, j] → [i + 1, j + 1] and [i, j] → [i, j + 1] → [i + 1, j + 1] corresponds via φ to the mesh relation M [i,j] : : ✉ ✉ ✉ ✉ ✉ ✉ ✉ ✉ ✉ $ $ ■ ■ ■ ■ ■ ■ ■ ■ ■ M [i+1,j+1] = τ -1 (M [i,j] ) M [i,j+1] 6 6 • • • • • • • • • • • • • and the zero-relation [i, i] → [i, i + 1] → [i + 1, i + 1] in Int 0 k (A k ) corresponds to the mesh relation 0 / / M [i,i] / / M [i,i+1] / / M [i+1,i+1] = τ -1 (M [i,i] ) / / 0.
It is now easy to see that this functor is an equivalence of categories. In particular, the category of modules over the Auslander algebra of A m is equivalent to the category of k-linear functors from Int 0 k (

-→ A m ) to k-Mod. In conclusion, the poset A 2n+1 × A n is derived equivalent to Int 0 k ( --→ A 2n
). The result follows from Theorem 3.1. Remark 3.6. It is well-known that any two different orientations of a Dynkin diagram of type A are derived equivalent. The stable Auslander algebra of two different orientations are also derived equivalent (see Section 1.5 of [START_REF] Ladkani | On derived equivalences of lines, rectangles and triangles[END_REF]). This implies that the poset of intervals Int(A 2n ) of a linear orientation of A 2n is derived equivalent to the stable Auslander algebra of A 2n+1 for any orientation. However, It is wrong that two different orientations of A 2n lead to derived equivalent posets of intervals. In the particular case where a = 2, the tools developed here together with results of the second author can be used in order to check this conjecture. Proof. If λ is a lattice path in the rectangle 2 × b, we denote by I(λ) the pair (j, i) where i is the abscissa of the first vertical move of the path and j is the abscissa of the second vertical move. The path is characterized by the pair I(λ). There are b+1 2 different (2, b)-Dyck paths that corresponds to the pairs (0, 0), (1, 0), • • • , ( b-1 2 , 0). Moreover, the partial order of the paths is given by (

Application to the poset of rational Dyck paths

b-1 2 , 0) < • • • < (1, 0) < (0, 0). In other words, Dyck 2,b ∼ = A b+1 2 . If (j, i)
is the pair I(λ) of a lattice path, it is clear that i j. In particular I(λ) can be seen as an interval of A b+1 ordered by decreasing order. If λ 1 and λ 2 are two paths, it is easy to see that λ 1 λ 2 if and only if I(λ 1 ) I(λ 2 ) in the poset of intervals. This shows that L 2,b is isomorphic to the poset of intervals of A b+1 . The result follows from Corollary 3.5.

Representations of a finite poset

Let k be commutative ring. Let Y be a finite poset. The category F Y,k is abelian. The abelian structure is point-wise. More precisely, it is defined on the evaluations of the functors. For y ∈ Y , there is an obvious functor, denoted by ev y from F Y,k to k-Mod that sends a functor F to its value F (y). This functor is clearly exact.

For y ∈ Y , we let P y := Hom kC Y (y, -). By Yoneda's Lemma, we have

Hom F Y,k Hom kC Y y, -, -∼ = ev y .
In particular, the functor P y is projective. Similarly, the functor I y := Hom kC Y (-, y) * is an injective functor. More precisely, the evaluations of these functors are

P y (z) = k if y z, 0 otherwise, I y (z) = k if z y, 0 otherwise.
Lemma 4.1. Let Y be a finite poset and k be a commutative ring. Let x and y ∈ Y . Then,

Hom F Y,k P x , P y = Hom F Y,k I x , I y = k if y x, 0 otherwise.
Proof. These are straightforward applications of Yoneda's Lemma.

Let X and Y be two finite posets and F : Y → J (X) be an order preserving map. For y ∈ Y , we let i y : F (Y ) → Γ be the map that sends x ∈ F (y) to (x, y) ∈ Γ. This is an order preserving map, so the pre-composition by i y gives a functor i -1 y :

F Γ,k → F F (y),k . More explicitly, if φ ∈ F Γ,k , then i -1
y (φ) is the functor that sends x ∈ F (y) to the kmodule φ(x, y). The functor i -1 y is clearly exact and by usual arguments it has a left and a right adjoint which can be described as particular coend and end (for more details see Theorem 1, Section 4 of Chapter X of [START_REF] Lane | Categories for the Working Mathematician[END_REF]). One can explicitly compute this end in order to find the right adjoint. Alternatively, and for the convenience of the reader, we give the formula and check that this gives indeed a right adjoint of i -1 y . Let φ ∈ F F (y),k . Then, for (a, b) ∈ Γ we set:

(i y ) ⋆ φ(a, b) := Hom k Hom kΓ (a, b), (a, y) , φ(a) if b y, 0 otherwise.
Since Hom kΓ (a, b), (a, y) is isomorphic to k when b y, this formula can be simplified as

(i y ) ⋆ φ(a, b) ∼ = φ(a) if b y, 0 otherwise.
However, we feel that it is more natural to describe this functor in this way.

h / / f (a, y) iy(α) (c, d) g / / (c, y)
Note that h and α are not unique. However, the different choices are of the form λ × h and λ

-1 × α for λ ∈ k × . Then (i y ) ⋆ (φ)(f ) is the application that sends ρ ∈ Hom k Hom kΓ (a, b), (a, y) , φ(a)
to the k-linear morphism that sends g ∈ Hom kΓ (c, d), (c, y) to φ(α)•ρ(h) ∈ φ(c). Since φ and ρ are k-linear morphisms, we see that the value of (i y ) ⋆ (φ)(f ) does not depend on the choice of α and h. Let η : φ ⇒ ψ be a morphism between two functors of F F (y),k . Then (i y ) ⋆ (η) is the natural transformation defined by (i y ) ⋆ (η) Lemma 4.2. Let y ∈ Y . Then, the functor (i y ) -1 : F Γ,k → F F (y),k is a left adjoint to the functor (i y ) ⋆ : F F (y),k → F Γ,k .

Proof. We give the unit and the co-unit of the adjunction.

Let F ∈ F F (y),k and x ∈ F (y). The unit at F and x, is the k-linear morphism It is clear that i -1 y is an exact functor. For the functor (i y ) * the exactness follows easily from the description of this adjoint. Let Since the functors (i y ) ⋆ and i -1 y are both exact, they can be extended as a pair of adjoint triangulated functors between the derived categories D b F F (y),k and D b F Γ,k .

0 / / F 1 α 1 / / F 2 α 2 / / F 3 / / 0,
Let us remark that, in general, the functor (i y ) ⋆ does not send a projective functor to a projective functor. However, it behaves relatively nicely for these projective functors.

Lemma 4.4. Let y and y ′ ∈ Y . Let x ∈ F (y) and P x be the corresponding projective functor when it is followed by a restriction. Then, andx x ′ 0 otherwise.

i -1 y ′ • (i y ) ⋆ (P x ) ∼ = P x ∈ F F (y ′ ),k if y ′ y and x ∈ F (y ′ ), 0 otherwise. Proof. Let x ′ ∈ F (y ′ ). Then, we have i -1 y ′ • (i y ) ⋆ (P x )(x ′ ) = (i y ) ⋆ (P x )(x ′ , y ′ ) = P x (x ′ ) if y ′ y, 0 otherwise. = k if y ′ y,
Since F (y ′ ) is closed, the condition x x ′ implies that x ∈ F (y ′ ). The result follows.

5 Proofs of Theorem 3.1

First let us recall the famous Morita theorem for derived categories of Rickard.

Theorem 5.1. Let A and B be two rings. Then, the following are equivalent

1. D b (A-Mod) ∼ = D b (B-Mod). 2. B is isomorphic to End D b (A) (T ) op where T is an object of K b (proj(A)) satisfying • Hom D b (A) (T, T [i]) = 0 for i = 0,
• add(T ), the category of direct summands of finite direct sums of copies of T , generates K b (proj(A)) as triangulated category.

Proof. See Theorem 6.4 of [START_REF] Rickard | Morita theory for derived categories[END_REF] or Theorem 6.5.1 of [START_REF] Zimmermann | Representation Theory: A Homological Algebra Point of View[END_REF] for a proof following Keller's approach. Note that the proof of Keller is stronger. It shows that it is possible to realise the derived equivalence as the tensor product with a bounded complex of bimodules. However, it holds for two k-algebras over a commutative ring that are projective over k.

The complex T is called a tilting complex for the ring A. In the present paper, we work with categories of functors. However, it is easy to see that all our functors categories are equivalent to categories of modules over an algebra. Moreover, these algebras are free over the ring k and of finite rank. In particular, in order to build derived equivalences, we can use Rickard's Morita theorem. Since the algebras are free over k, the stronger form of this theorem due to Keller also holds in our context.

Let y ∈ Y and x ∈ Y . We denote by P x the projective functor of F F (y),k that corresponds to the element x.

Proposition 5.2. Let k be a commutative ring. Let X and Y be two finite posets and let F : Y → J (X) be an order preserving map. Then, the complex

T := y∈Y x∈F (y) (i y ) ⋆ (P x ) is a tilting complex for D b F Γ,k .
Proof. Strictly speaking, the complex T is not a tilting complex since its terms are not projective. However, since the category F Γ,k has finite global dimension, we can find a bounded complex of projective objects which is quasi-isomorphic to T.

1. Let y ∈ Y . Let x ∈ F (y) and I x be a finitely injective functor of F F (y),k corresponding to x. It has a finite projective resolution, so there is a bounded complex P • of elements of add( x∈F (y) P x ) and a quasi-isomorphism φ : P • → I. Since the functor (i y ) ⋆ is exact, we have a quasi-isomorphism between (i y ) ⋆ (P • ) and (i y ) ⋆ (I). By Lemma 4.3, we have (i y ) ⋆ (I x ) ∼ = I (x,y) . So for every (x, y) ∈ Γ, the injective functor I (x,y) belongs to the smallest triangulated subcategory of D b (F Γ,k ) that contains add(T). Since every finitely projective functor has a finite injective co-resolution, we conclude that this category is equivalent to K b proj(F Γ,k ) .

2. Let i ∈ Z. Then, using the fact that (i y ′ ) ⋆ is a triangulated functor and the adjunction, we have Since P x and P ′ x are projective objects in F F (y ′ ),k , there are no non-trivial extensions between them. This implies that Hom D b (F Γ,k ) T, T[i] = 0 if i = 0.

Proof of Theorem 3.1. By Proposition 5.2, there is an equivalence between D b (F Γ,k ) and D b (End(T ) op ), where T is the tilting complex of the Proposition. By usual Morita theory, the category F Γ 0 ,k is equivalent to End F Γ 0 ,k (x,y)∈kΓ 0 P (x,y) op where P (x,y) is the representable functor Hom kΓ 0 (x, y), -. Using the Yoneda Lemma, we have Hom F Γ 0 ,k P (x,y) , P (x ′ ,y ′ ) = k if x ′ x, y ′ y and x ∈ F (y ′ ), 0 otherwise.

Since (i y ) ⋆ (P x ) and (i y ′ ) ⋆ (P x ′ ) for x ∈ F (y) and x ∈ F (y ′ ) and y, y ′ ∈ Y , are two functors, we can do the computation of End(T) in the categories of functors instead of the derived category. Then, we have Hom F Γ,k (i y ) ⋆ (P x ), (i y ′ ) ⋆ (P x ′ ) ∼ = Hom F F (y ′ ),k i -1 y ′ • (i y ) ⋆ (P x ), P x ′ ∼ = Hom F F (y ′ ),k (P x , P x ′ ) if y ′ y and x ∈ F (y ′ ) 0 otherwise, ∼ = k if x ′ x, y ′ y and x ∈ F (y ′ ), 0 otherwise. This implies that End(T ) ∼ = End F Γ 0 ,k (x,y)∈kΓ 0 P (x,y) . Taking the 'op' functor, we have the derived equivalence between F Γ,k and F Γ 0 ,k .

Let a and b

  be two co-prime integers. A rational (a, b)-Dyck path is a lattice path in an (a × b)-rectangle that stays above and never crosses the diagonal. We denote by Dyck a,b the set of rational Dyck paths. It is well known that there are 1 a+b a+b b elements in Dyck a,b (see [Biz54] for more details). The usual proof of this formula is to consider the set of all lattice paths in the rectangle a × b, denoted by L a,b . This is a set with a+b b elements. The cyclic group Z/(a + b)Z acts on this set by the so-called cycling relation of a path. The orbits contains a + b elements and exactly one rational Dyck path. The sets L a,b and Dyck a,b can be naturally viewed as posets. A lattice path l 1 is smaller than another l 2 if l 1 lies below l 2 . The formula for the cardinality of Dyck a,b suggests a relation between the poset A a+b × Dyck a,b and the poset L a,b . It is easy to see that these two posets are not isomorphic. Still, we think that they may share the same derived category. Conjecture 3.7. Let a, b be two co-prime integers. Let L a,b be the poset of lattice paths in the rectangle a × b and Dyck a,b be the poset of (a, b)-rational Dyck paths. Then, the poset A a+b × Dyck a,b is derived equivalent to the poset L a,b .

Proposition 3. 8 .

 8 Let k be an algebraically closed field. Let b be an odd integer. Then, there is a derived equivalence over the field k between the posets A b+2 × Dyck 2,b and L 2,b .

  Let 0 = f : (a, b) → (c, d) be a morphism in kΓ such that b d y. Let 0 = g ∈ Hom kΓ (c, d), (c, y) . Then, there exist h ∈ Hom kΓ (a, b), (a, y) and α ∈ Hom kF (y) (a, c) such that the following diagram commutes (a, b)

  (a,b) ρ) = η a • ρ for (a, b) ∈ Γ such that b y and ρ ∈ φ(a, b).

ǫF

  (x) : Hom k Hom kΓ (x, y), (x, y) , F (x) → F (x), that sends α ∈ Hom k Hom kΓ (x, y), (x, y) , F (x) to α(Id (x,y) ) ∈ F (x). Let G ∈ F Γ,k and (a, b) ∈ Γ such that b y. The co-unit of the adjunction at G and (a, b) is the k-linear morphism η G (a, b) : G(a, b) → Hom k Hom kΓ (a, b), (a, y) , G(a, y) that sends γ ∈ G(a, b) to the k-linear morphism that sends α ∈ Hom kΓ (a, b), (a, y) to G(α)(γ). It is now straightforward to check that these two morphisms are the unit and the co-unit of the adjunction.Here, we summarise the main properties of the functors i -1 y and (i y ) ⋆ . Lemma 4.3. Let y ∈ Y . 1. The functor (i y ) ⋆ sends the injective I x ∈ F F (y),k to the injective I (x,y) ∈ F Γ,k .2. The two functors i -1y and (i y ) ⋆ are exact. Proof. Since (i y ) ⋆ is a right-adjoint to an exact functor, it sends I x ∈ F F (y),k to an injective object of F Γ,k . Moreover, one can explicitly compute (i y ) ⋆ (I x ). Let (a, b) ∈ Γ, then we have (i y ) ⋆ (I x )(a, b) = I x (a) if b y 0 otherwise = k if a x and b y 0 otherwise.

  be an exact sequence of functors ofF F (y),k . Let (a, b) ∈ Γ. If b y, then for i = 1, 2, 3 we have (i y ) ⋆ (F i )(a, b) = 0 and (i y ) ⋆ (α i ) (a,b) = 0 for i = 1, 2 so the sequence is exact. If b y, then (i y ) ⋆ (α) (a,b) = Hom k Hom kΓ (a, b), (a, y) , (α i ) a for i = 1, 2. SinceHom kΓ (a, b), (a, y) ∼ = k, the result follows.

Hom

  D b (F Γ,k ) T, T[i] = y,y ′ ∈Y Hom D b (F Γ,k ) (i y ) ⋆ x∈F (y) P x , (i y ′ ) ⋆ x ′ ∈F (y ′ ) P x ′ [i] ∼ = y,y ′ ∈Y Hom D b (F F (y ′ ),k ) i -1 y ′ • (i y ) ⋆ x∈F (y) P x , x ′ ∈F (y ′ ) P x ′ [i] ∼ = y ′ y Hom D b (F F (y ′ ),k ) x∈F (y ′ ) P x ,x ′ ∈F (y ′ )P x ′ [i]

  A is an abelian category, we denote by D b (A) its bounded derived category. We denote by proj(A) the full subcategory of A consisting of the finitely generated projective objects. If B is an additive category, we denote by K b (B) the homotopy category of bounded complexes of B.

	If n ∈ N, we denote by	-→ A n the set {1, • • • , n}. Unless specified otherwise, we see it with
	the total order 1 < 2 < • • • < n.
	2 Two categories of generalized intervals of a poset
	2.1 Categories of intervals of a finite poset
	Let k be a commutative ring with unit. Let (X, ) be a finite poset. For a, b ∈ X, we
	set
		[a, b] := {z ∈ X; a z and z b}.
	As usual, the set [a, b] is called an interval of X. We let Int(X) be the set of intervals of
	X. It has a natural partial order defined by
	[a, b] [c, d] if and only if a c and b d.


Bakhouche Abdelaali
email: bakhouche2006@yahoo.fr

Yamina Tlili-Guiassa

Didier Schwab
email: didier.schwab@imag.fr

Andon Tchechmedjiev
email: andon.tchechmedjiev@imag.fr

Tlili Yamina

Ant Colony Algorithm for Arabic Word Sense Disambiguation through English lexical information

Keywords: Arabic language processing, Word Sense Disambiguation, Ant colony algorithm, Lesk algorithm, Local/Global algorithm, WordNet

The ability to identify the intended meanings of words in context is a central research topic in natural language. Many solutions exist for word sense disambiguation (WSD) in different languages, such as English or French, but research on Arabic WSD remains limited. The main bottleneck is the lack of resources. In this article, we show that it is possible to build a WSD system for the Arabic language thanks to the Arabic WordNet and its connexions to the English Princeton WordNet. Given that the Arabic WordNet does not contain definitions for synsets, we construct a dictionary that maps the Princeton WordNet definitions to the Arabic WordNet. We also create an Arabic evaluation corpus and gold standard. We then exploit this dictionary and evaluation corpus to run and evaluate an adapted Ant Colony algorithm on Arabic text that can use the Lesk similarity measure thanks to definition mapping. The algorithm shows a performance of approximately 80% compared to the random baseline of 78.9 %.

Introduction

Word sense disambiguation (WSD) is the process of disambiguating the sense of an ambiguous word when the word has more than one sense by using the neighbours of the word (context) in a sentence or text [START_REF] Navigli | Word sense disambiguation: A survey[END_REF]Özdemir, 2009). Word sense disambiguation is of interest for several linguistic applications such as automatic translation, multilingual information extraction, semantic indexing, and automatic summarization. Arabic is the fourth most-widely spoken language in the world. It is a highly inflectional language, with a rich morphology and relatively free word order. Ambiguity in Arabic is present at several levels, such as internal word structure ambiguity, syntactic ambiguity, semantic ambiguity, constituent boundary ambiguity and anaphoric ambiguity. This prevalence of ambiguity has led to difficulty with the automatic processing of Arabic [START_REF] Attia | Handling Arabic Morphological and Syntactic Ambiguity within the LFG Framework with a View to Machine Translation[END_REF]. Ant colony optimization (ACO) was first introduced by Marco Dorigo [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF][START_REF] Dorigo | Ant colony optimization theory: A survey[END_REF]. This algorithm is a fairly novel technique for solving computational problems by mimicking the natural behaviour of ants as they generate and select paths to a food source from a colony. The first application of ant colony optimization was to solve the Travelling Salesman Problem and other similar np-hard combinatorial optimization problems (asymmetric traveling salesman problem, the quadratic assignment problem, and the job-shop scheduling problem). In addition, ACO has been successfully applied to transportation planning problems [START_REF] Yang | A Parallel Ant Colony Algorithm for Bus Network Optimization[END_REF][START_REF] Vitins | Optimization of Large Transport Networks Using the Ant Colony Heuristic[END_REF]. To disambiguate words in context, Schwab et al. have proposed a distinction between local and global algorithms: the similarity measure between word senses is the local measure, and the combinatorial optimization algorithm that finds the best sense combination is the global algorithm. They proposed a global ACO algorithm and compared it to Simulated Annealing and Genetic Algorithms. The ACO algorithm obtained better precision, recall and execution time [START_REF] Schwab | A global ant colony algorithm for word sense disambiguation based on semantic relatedness[END_REF][START_REF] Schwab | Ant Colony Algorithm for the Unsupervised Word Sense Disambiguation of Texts: Comparison and Evaluation[END_REF][START_REF] Schwab Didier | GETALP: Propagation of a Lesk Measure through an Ant Colony Algorithm[END_REF]. In this paper, we adapt the approach of [START_REF] Schwab Didier | GETALP: Propagation of a Lesk Measure through an Ant Colony Algorithm[END_REF] to solve the WSD problem in the Arabic language (AWSD henceforth). Firstly, our approach extracts two sets of features, namely the set of words from the Arabic WordNet and the set of meanings from the English WordNet, from which we build the dictionary. Secondly, we present the ACO algorithm used as well as the variant of the Lesk similarity measure applied. The rest of this paper is organized as follows: in section 2, we present the specificity of the Arabic language; in section 3, we briefly discuss some of the related work in the area of Arabic Word Sense Disambiguation; in section 4, we describe the resources and algorithms used; in section 5, we present the proposed method for AWSD; and finally, we present the results of tests of our model.

Specificity of the Arabic language

"Arabic is the official language of hundreds of millions of people in twenty Middle East and northern African countries, and is the religious language of all Muslims of various ethnicities around the world" [START_REF] Elkateb | Arabic WordNet and the challenges of Arabic[END_REF]. Every year, Arabic written content on the web is multiplied by 250; this is the fastest growth of written content for any language on the Internet (Russian is the second fastest at 182x). There are approximately 65 million Arabic speakers on the Internet, which is 18.8% of the global Internet population [START_REF] Menai | Genetic algorithm for Arabic word sense disambiguation[END_REF]. The literary Arabic language is called Modern Standard Arabic MSA [START_REF] Cote | choosing one dialect for the Arabic speaking world: a status planning dilemma[END_REF]. It is currently the only official form of Arabic and is used in most written documents as well as in formal spoken occasions, such as lectures and news broadcasts. It is a difficult language that could hinder the development of tools for the application of natural language processing. The Arabic language has many particularities such as short vowels, the absence of capital letters and complex morphology. The Arabic language is composed of nouns, verbs and particles, wherein these are morphemes and derived from a closed set of approximately 10,000 roots. Arabic is also highly inflectional and derivational, which makes morphological, syntactic and semantic analysis a very complex task [START_REF] Ali | Arabic Natural Language Processing: Challenges and Solutions[END_REF]. There is no capitalization in Arabic, which makes it hard to identify proper names, acronyms, and abbreviations. Furthermore, the Arabic Language is highly ambiguous for several reasons.

 Vowelization is a very interesting characteristic of the Arabic language, which causes ambiguity when it is absent, and this is usually the case.  Polysemy (when a word or phrase has several meanings) is the second problem that causes semantic ambiguity in Arabic.  A rarity of resources such as an Arabic Corpora and pretreatment text tools leads to a lot of time being wasted on the process of collecting and/or modelling and developing these resources. All of these factors collectively will affect the availability of WSD applications for Arabic.

Previous Work

Several approaches that address the problem of Arabic word sense disambiguation have been presented in the past few years. Among the most cited is the work of Mona Diab, who used a supervised learning approach. This approach exploits translational correspondence between words in a parallel Arabic English corpus to annotate Arabic text. It exhibits an absolute precision of 56.9% on the AWSD task [START_REF] Diab | An unsupervised approach for bootstrapping Arabic sense tagging[END_REF]. Menai and Wodjan proposed an approach to solve the Arabic word sense disambiguation problem based on a genetic algorithm. In this algorithm, a text is tokenized, and stop-words are filtered and stemmed. In the pre-processing phase, tokenization splits the text into words. After tokenization, the authors removed stop words to filter out words that were not important in the text, such as prepositions and articles. Subsequently, the authors performed stemming (Khoja's Stemmer) on the remaining tokens. In stemming, the prefixes and suffixes of the word are removed. The senses of each word were then retrieved from the Arabic WordNet (AWN). AWSD (GA) is used to find the most appropriate mapping from words to senses retrieved from the AWN in the context T. The authors have shown that GA performs better than the Naïve Bayes algorithm. They obtained an accuracy of 78.9% [START_REF] Menai | Genetic algorithm for Arabic word sense disambiguation[END_REF]Menai, 2014a;[START_REF] Menai | Word sense disambiguation using evolutionary algorithms -Application to Arabic language[END_REF]. The system presented by Elmougy, Hamza and Noman [START_REF] Elmougy | Naïve Bayes classifier for Arabic word sense disambiguation[END_REF][START_REF] Elmougy | Lexical Disambiguation of Arabic Language: An Experimental Study[END_REF] to solve the ambiguity of nondiacritic words in the Arabic language uses the routing algorithm with a naïve Bayes classifier. It achieved a rate of precision on the order of 76.6%. To disambiguate Arabic words, Zouaghi, Merhben and Zerigui [START_REF] Zouaghi | Word Sense disambiguation for Arabic language using the variant of the Lesk algorithm[END_REF] tested the Naïve Bayes algorithm, the decision lists and the exemplar-based algorithm on tagged samples and a large amount of data in the used corpus. For these tests, the exemplar-based algorithms achieve rates of precision of 48.23%, 43.86% and 52.02%, respectively.

Another method for word sense disambiguation was proposed by Zouaghi, Merhben and Zerigui (Merhben et al., 2009). Their method evaluated the variants of the Lesk algorithm and used the Arabic WordNet to perform word sense disambiguation in Arabic. The modified version of the Lesk algorithm achieved a precision of 67%. The method presented by [START_REF] Nameh | A New Approach to Word Sense Disambiguation Based on Context Similarity[END_REF] is a supervised learning method for word sense disambiguation based on the Inner Product of vectors.

The system extracts two sets of features: the set of words that have occurred frequently in the text and the set of words surrounding the ambiguous word. This approach achieves a precision of 77.1%. [START_REF] Shah | A New Approach to Lexical Disambiguation of Arabic Text[END_REF] proposed an approach for accurate prediction of Arabic text consisting of both lemmas and morphological analyses. The accuracy of their system was reported to be 90%. In spite of the great attention the problem has received in the last years and the important developments achieved, the precision of state-of-the-art algorithms is far from being satisfactory.

Resources and algorithms used in our approach

In this section, we present the characteristics of the resources and algorithms used in our approach.

a. WordNet Database

A WordNet is a machine-readable lexical database that groups words into clusters of synonyms called synsets. Every synset can be thought of as representing a unique word sense (meaning or concept). A WordNet provides general definitions and examples for the synsets and includes semantic relations between them. The semantic relations allow for a WordNet to be interpreted hierarchically as a lexical ontology/taxonomy. WordNet is like a dictionary in that it stores words and meanings. However, it differs from traditional dictionaries in many ways. For instance, words in WordNet are arranged semantically instead of alphabetically. Synonymous words are grouped together to form synonym sets, or synsets. Each such synset therefore represents a single distinct sense or concept [START_REF] Miller | Introduction to WordNet: An on-line lexical database[END_REF]Miller 1995). The Arabic WordNet (AWN) is a lexical database of the Arabic language following the development process of the Princeton English WordNet and the Euro WordNet. It utilizes the Suggested Upper Merged Ontology as an Interlingua to link the Arabic WordNet to previously developed WordNet1 [START_REF] Elkateb | Arabic WordNet and the challenges of Arabic[END_REF]. The Arabic WordNet consists of 9228 synsets (6252 nominal, 2260 verbal, 606 adjectival, and 106 adverbial), containing 18,957 Arabic expressions. This number includes 1155 synsets that correspond to Named Entities, which have been extracted automatically and are being checked by lexicographers [START_REF] Rodriguez | Arabic WordNet: Current state and future extensions[END_REF][START_REF] Elberrichi | Arabic text categorization: a comparative study of different representation modes[END_REF]. These numbers are constantly changing. At the time of writing, the English WordNet consisted of 155287 synsets (117798 nominal, 11529 verbal, 21479 adjectival, and 4481 adverbial).

b. LESK algorithm

The Lesk algorithm is a disambiguation method based on counting the overlaps between the definitions of sense of a target word (supplied by a machine readable dictionary), and the definitions of words in the context [START_REF] Lesk | Automatic sense disambiguation using machine readable dictionaries: how to tell a pine cone from an ice cream cone[END_REF][START_REF] Banerjee | An adapted Lesk algorithm for word sense disambiguation using WordNet[END_REF]. The selected sense for this word corresponds to the definition of the sense containing the maximal number of overlaps with the context. The algorithm begins anew for each word and does not utilize the senses it previously assigned. Formally, given two words w1 and w2, the following score is computed for each pair of word senses: S 1 ∈ Senses (w 1 ) and S 2 ∈ Senses (w 2 ): Score Lesk (S 1 , S 2 ) =| gloss (S 1 ) ∩ gloss (S 2 ) |, where gloss (S i ) is the bag of words in the textual definition of sense S i of w i . The senses that maximize the above formula are assigned to the respective words. However, this requires the calculation of | Senses (w1) | • | Senses (w2) | gloss overlaps. The original Lesk algorithm relies on glosses found in traditional dictionaries such as the Oxford Advanced Learner's Dictionary of Current English, Collins English Dictionary and the Oxford English Dictionary [START_REF] Banerjee | An adapted Lesk algorithm for word sense disambiguation using WordNet[END_REF]. Another version of the Lesk algorithm takes advantage of the highly inter-connected set of relations among synonyms that WordNet offers.

c. Ant colony algorithm (ACO)

Ants are social insects that live in colonies that may include thousands of individuals. When the ants find food, each individual ant does not know where to go. First, ants randomly chose their path. However, their path is chosen depending on the pheromone trails that have been laid on the ground by previous ants. The trail of pheromones on the shortest path is increased faster than the longest path. In the end, all ants choose the shortest path. Three factors that allow the ants to find the shortest path are as follows:

 Ants follow pheromone trails;  Pheromone trails degrade over time;  Short paths take less time to traverse. The idea of the ant colony algorithm is to mimic this behaviour with "simulated ants" walking around the graph representing the problem to be solved.

The first application of ant colony optimization was to solve the Travelling Salesman Problem [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents[END_REF][START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF][START_REF] Dorigo | Ant colony optimization theory: A survey[END_REF]. In this well-known problem, the goal is to find, for finitely many towns whose pairwise distances are known, the shortest path connecting them. Several improvement algorithms have been used with ACO to solve such problems as the asymmetric traveling salesman problem, the quadratic assignment problem, and the job-shop scheduling problem. In addition, ACO has been applied successfully for transportation planning problems [START_REF] Yang | A Parallel Ant Colony Algorithm for Bus Network Optimization[END_REF][START_REF] Vitins | Optimization of Large Transport Networks Using the Ant Colony Heuristic[END_REF].

d. Local/Global algorithm

Several word sense disambiguation systems are based on the notion of local and global algorithms (Ratinov et al., 2011;Schwab et al., 2013b). A local algorithm allows the calculation of the semantic similarity between two lexical objects ( sense, words, constituents, etc.) in the textual segment. Global algorithms propagate local measures at the upper level. In other words, this technique permits a global extension of a local algorithm based on semantic relatedness to an entire text. We use this technique in our approach: the LESK algorithm is the local algorithm, and the ant colony algorithm is the global algorithm.

Generation of an Arabic dictionary

External knowledge is a fundamental component of WSD. In Arabic, there are no available dictionaries in these forms.

However, there has been much work done on bilingual dictionaries based on WordNet architecture [START_REF] Black | Introducing the Arabic WordNet project[END_REF]. Therefore, a bilingual dictionary has been implemented successfully for common communication words using WordNet. This source provides data that are essential to associate English senses with Arabic words (see Fig. 1). However, it has difficulty providing the Arabic equivalent word with certainty to that of an English word.

Disambiguation of ambiguous Arabic words

The proposed work consists of developing a method used to resolve semantic ambiguity for the Arabic language using the Ant colony algorithm (see Fig. 2). In this section, we explain the most important points of this approach.

Construction of the text graph

The environment consists of a graph with ants. It is simply organized according to the elements of the text (text, sentence, word) without external language information to better understand the mechanics of the algorithms. In our graph, we distinguish two types of nodes. Nests produce ants that move on the graph in order to find energy and bring it back to their nest. The more energy brought back by the ants, the more ants the nest can in turn produce.

Types of nodes

Nests and plain nodes are two distinct types of nodes in this graph. Following [START_REF] Schwab | Ant Colony Algorithm for the Unsupervised Word Sense Disambiguation of Texts: Comparison and Evaluation[END_REF], each possible word sense is associated with a nest. From the point of view of an ant, a node can be any of the following:  The ant's nest (anthill), where it was born;  An enemy nest, which corresponds to another sense of the same word;  A friendly nest: all of those nests that are not enemies;  A plain node: any node that is not a nest.

Vector of definition

The odour of a nest is the numerical sense vector and corresponds to the definition of the sense associated with the nest (see Fig. 3). All ants born in the same nest have the same odour vector. 3

Vector of sense's definition 'wash'

Movement of ants

An ant is born (produced by its nest) and goes in search of energy.

It is drawn by nodes that carry a lot of energy and avoids arcs with too much pheromone to enable exploration of more solutions.

Bridge

When an ant arrives on a node adjacent to a potential friend nest (i.e., that corresponds to a sense of a word), it has to decide between taking any of the possible paths or going to that nest node. The only difference is that if the ant chooses to go on the potential friend nest, a bridge between that nest and the ant's home nest is built and the ant follows it to go home. Bridges behave like regular edges, except that if the concentration of pheromone on them reaches a certain level, they collapse and are removed.

Interpretative paths

For all intents and purposes, bridges behave exactly like ordinary paths, however, when the concentration of pheromone on a bridge reaches zero, the bridge "evaporates" and ceases to exist. When many bridges have been created, some will be strengthened (when many ants follow them) and other will disappear. This will lead to a monopolization of energy by the anthills linked by the strongest bridges. From the point of view of linguistics, our bridge construction model corresponds to emergent interpretative paths. At the end of the simulation, for each word node, the anthill with the highest energy level is chosen as the solution.quality of the results.

The choice of an answer

The selected answers correspond to words in the nest node with the highest energy value. The reason for this choice over using the pheromone concentration is that empirically, the energy level correlates better with the actual F1 scores. In turn, the global LESK score of a selected sense combination has an even better correlation with the F1 score. This is why we retain the sense combinations resulting from each iteration of the algorithm (highest energy nests at each iteration) and select the one with the highest global LESK score as the final solution.

Illustrated example

The easiest way to understand how the ant colony works is by means of an example; we illustrate the steps of the algorithm through the path taken by an ant on the phrase: بيتا" الشاعر ""قالpoet said rhyme".

We follow the path of an ant that was born in the anthill /بيت Rhyme -corresponding to the second meaning for the word, .-بيت

Step 1: The ant begins to search for food to take energy to its nest. It begins to explore the graph starting with the name corresponding to the #بيت n node.

Step 2: On the path to this node, it deposits its pheromone, and arriving, it takes energy. It also deposits some of its odour on the node. This odour is marked by the deposition of two components taken at random from its mother nest.

Step 3: The ant then chooses to follow another path where it deposits its pheromone. It will also deposit two vector components of the mother nest at random and take energy. At this stage, the ant has a full quantity of energy, and a pseudo-random decision will make it return to the mother nest node.

Step 4: As an ant cannot go on a node from which it came, unless that is its only chance, our ant has the choice between going on to قال # v-or #الشاعر n.

Step 5: Ants coming from /الشاعر Poet part of their vector on #الشاعر n have more in common with the vector node than our ants, #بيت v-.

Step 6: Our ant therefore is more likely to go to #الشاعر n. It does this while depositing its pheromone along the way. The ant leaves its odour on the destination node but does not take energy, as it is a back node. Now, its only option is to go to /الشاعر Poet -.

Step 7: For the ant, the /الشاعر Poet-friend is a potential node. It therefore has the opportunity to build a bridge to its mother anthill. Therefore, the ant chooses to borrow and deposit its pheromone. It reaches its mother nest and deposits all of its energy. The ant then returns to search mode and resumes its travels to the node where it will die and deposit its transported energy and the energy it took to make it.

Fig. 4 Example of phrase"بيتا الشاعر ""قالpoet said rhyme"

Experimental evaluation

In this section, we present the results of our experiments.

a. Statistics of the Arabic dictionary

The main statistics of the Arabic dictionary that we created are summarized in Table I. The first column of this table gives the parts of speech, while the other columns indicate the number of Arabic parts of speech and the number of English sense definitions. Fig. 5 shows the screen of an English-Arabic dictionary based on WordNet capture. We see that Arabic words do not sufficiently correspond all possible English senses.

Arabic

b. Data pre-processing

The experimental dataset consists of six Arabic texts of various domains (culture, economy, international, local, religion, and sports). These texts are extracted from newspaper articles, which were recorded in the corpus of Elwatan [START_REF] Abbas | Evaluation of Topic Identification Methods on Arabic Corpora[END_REF]. To study the effect of the ACO algorithm, we have conducted six groups of experiments, for each group and for each text category, one-third of the articles were randomly specified and used for testing and the remaining articles were used for training. Table 3 illustrates the domains addressed by these texts and the distribution of words as described in the texts. Pre-processing aims to transform the Arabic text documents into a form that is suitable for the algorithm.

 Each document in the Arabic dataset is processed to remove digits, numbers, hyphens, and punctuation marks.  We have normalized the letters "  All non-Arabic texts were removed.  Arabic function words (stop words) were removed. In these experiments, we utilized the stop word list generated by the website Sourceforge 2 , a list containing 26037 words.

All of the results of the algorithm were obtained using a PC with Intel Core Duo CPU 2.66 and 6.GB RAM of main memory on Windows 7. The application was developed in Java language.

Figure 8 shows the screen of our applications.

c. Evaluation metrics

Evaluation criteria are attempted to indicate how many words the system can disambiguate. The precision is a measurement of how many target words are correctly disambiguated and gives the accuracy of the system.

Precision= ¿correctly disambiguated words ¿ disambiguated words

Recall is defined by the ratio of the number of correctly disambiguated target words to the total number of target words in the dataset.

Recall= ¿correctly disambiguated words ¿tested set words

The F-measure is the harmonic mean of the precision and recall values, as described in the following equation:

F-measure=2. precision. recall precesion+recall

For all of our experiments, we used these three evaluation measures (Recall, Precision, and F-measure) as the bases of our comparisons.

d. Selection of the parameters

The choice of parameters is critical to the performance of the algorithm. The first set of experiments involved the numerical investigation of the ACO parameters and their impact on the performance of AWSD. Table 4 shows the parameters of the ACO. The algorithm does not give the same meanings on each execution; execution of the repeat is required at least twice to get the exact sense. We have noted that after several cycles (approximately 70), the results obtained are similar, as shown in Figure 4, and we can achieve the same results between two executions.

Fig. 5 The F-measure result generated by the algorithm against six Arabic datasets.

In each dataset, we arbitrarily consider 70% of documents for training and 30% for testing.

e. Comparison with other methods

Several approaches that address the problem of Arabic word sense disambiguation have been presented in section 3. The result of these methods cannot be compared directly to our algorithms' results because those methods are for different tasks and their results were generated using different datasets.

For that reason, in this comparison, we apply the same experimental data that we have used before in the experimental study of the Genetic algorithm [START_REF] Menai | Genetic algorithm for Arabic word sense disambiguation[END_REF], Naïve Bayes classifier [START_REF] Elmougy | Naïve Bayes classifier for Arabic word sense disambiguation[END_REF] and Modified version of the Lesk [START_REF] Merhben | Ambiguous Arabic Words Disambiguation: The results[END_REF] Methods Score Ant colony algorithm (our approach) 80 % Genetic algorithm 78.9 % Naïve Bayes classifier 76.6 % Modified version of the Lesk 67% The results obtained with the ant colony algorithm corroborate those obtained in previous studies on ACO for WSD in English [START_REF] Schwab | A global ant colony algorithm for word sense disambiguation based on semantic relatedness[END_REF][START_REF] Schwab | Ant Colony Algorithm for the Unsupervised Word Sense Disambiguation of Texts: Comparison and Evaluation[END_REF][START_REF] Schwab Didier | GETALP: Propagation of a Lesk Measure through an Ant Colony Algorithm[END_REF]) even though they are not comparable.

Our experiments show that our approach exhibits superior results when compared with existing techniques. This is not surprising because our approach attempts to globally optimize the text cohesion, while the methods we used as a baseline optimize it locally. Much better precision and recall were obtained by other Cycles % methods for more specific WSD tasks in Arabic, such as finding the correct sense of query translation terms, and disambiguation of polysmous and homograph Arabic nouns.

We evaluated the performance of different variants of the ACO algorithm on a set of 5000 words extracted from an Arabic corpus.

The results obtained show that ACO is the best performing algorithm.

Conclusion and future work

In this paper, we presented an approach of word sense disambiguation for the Arabic language that tackled several difficulties, in particular the rareness of studies in the field of semantics offering integrated solutions and the lack of lexical resources, in addition to technical problems related to programming imposed by the nature of the Arabic language.

To achieve this, we set our objectives at the beginning and we organized our work into three main steps. First, we conducted a theoretical study on the field. We collected and prepared all of the necessary linguistic data: a body of work and a lexical database. Then, we developed our system. Finally, we concluded with a quantitative and qualitative evaluation of our system.

To the best of our knowledge, there is no published research proposing the Ant colony algorithm-based approach to solve the AWSD problem. The ACO algorithm has the advantage of being easily adapted to a dynamic environment, which is important for the WSD problem because natural languages can evolve quickly.

There is still a lot of work to be done to introduce the Arabic language to the world of NLP, with wider opportunities than is the case with other languages. We believe and hope that this study offers solutions that can be exploited in the developing use of the Arabic language in the world of information technology, communications and electronic management.

Figures, images and tables

Fig. 1

 1 Fig. 1 Arabic Dictionary

Fig.

  Fig.3

Fig. 2

 2 Fig. 2 Diagram of the proposed approach for AWSD

2جملة

  http://sourceforge.net/projects/arabicstopwords/

Fig. 6

 6 Fig. 6 Part of the Arabic Dictionary

Fig

  Fig. 1 Arabic Dictionary

Fig. 2

 2 Fig. 2 Diagram of the proposed approach for AWSD

Fig. 8 .

 8 Fig. 8. The output annotation in the format required for the evaluation script

Table 1 :

 1 Statistics of the Arabic dictionary

		POS	English Sense
	Nouns	9641	14680
	Verbs	2777	6084
	Adjectives	662	762
	collocations	12905	263
	Total	25985	21789

Table 2 :

 2 Table 2 describes the characteristics of the corpus. Statistics of the corpus

	Domains	Number of articles
	Culture	2782

Table 3 :

 3 The six articles in the dataset

Table 4 :

 4 Parameters of the algorithm

	Notation	Description	Value range	Estimation for Text
	GetEnerg	Energy taken by an ant when it arrives on a node	1-30	9.0
	EnergMax	Maximum quantity of energy an ant can carry	1-60	22.142
		Evaporation rate of the
	pheroEvap	pheromone between two	0.0-1.0	0.3577
		cycles
	EnergInit	Initial quantity of energy on each node	5-60	32.0
	AntLife	Ant-life-span	1-30	27.0
	TailleVector	Odour vector length	20-200	135.637
		Percentage of the odour
	depotVector	vector component (words) deposited by an ant when	0-100	0.9775
		it arrives on a node
	NbrCycle	Number of cycles of the simulation	1-100	-

Notation Value Number of Nodes 415 Number of Paths 4096 Number of Ants 1026 Cycle Number 99Table 5 :

 5 Simulation Environment for Text d001

Table 6 :

 6 Comparison with other methods

Table 1 :

 1 Statistics of the Arabic dictionary

	Domains	Number of articles
	Culture	2782
	Economy	3468
	International	2035
	Local	3596
	Religion	3860
	Sports	4550
	Total	20291

Table 2 :

 2 Statistics of the corpus

	Text	Domain	Words	Annotated
	D001	Culture	800	242
	D002	Economy	2130	1133
	D003	International	600	325
	D004	Local	755	432
	D005	Religion	295	125
	D006	Sport	450	298
	TOTAL	-	5030	2555

Table 3 :

 3 The six articles in the dataset

http://www.globalwordnet.org/AWN

Fig. 5 The F-measure result generated by the algorithm against six Arabic datasets.

In each dataset, we arbitrarily consider 70% of documents for training and 30% for testing.

Methods Score Ant colony algorithm (our approach) 80 % Genetic algorithm 78.9 % Naïve Bayes classifier 76.6 % Modified version of the Lesk 67%