Keywords: combinatorial optimization -metaheuristic -multiple criteria decision making -mechanics, applied -engineering design optimisation combinatoire -métaheuristiques -décision multicritèremécanique appliquée -conception technique combinatorial optimization -metaheuristic -multiple criteria decision makingmechanics, applied -engineering design optimisation combinatoire -métaheuristiques -décision multicritère -mécanique appliquée -conception technique ICD-LASMIS CNRS FRE 2019

Hybridization of multicriteria metaheuristic optimization methods for mechanical problems

List of Tables

able. Note, the "sliding" of the limits of the intervals to avoid "duplicates": the 3 intervals [0, 1], [START_REF] Abramson | Mesh adaptive direct search algorithms for mixed variable optimization[END_REF]2] and [2,3] become [0, 1] , [2,2] and [3,3]

Introduction

Optimization problems arising from the mechanical and materials engineering field are often difficult to solve. This is due to the characteristics these optimization problems have.

For instance, mechanical optimization problems are usually nonlinear and sometimes strongly nonlinear. They are characterized generally by several conflicting objectives, and by a set of constraints that take the attention (of an optimization algorithm) away from optimization into focusing instead on feasibility.

Another feature that set these problems apart from other optimization problems, is the presence of both continuous and discrete optimization variables. The optimization problem is then called a mixed variables problem. Mixed variable make the solution space disjoint, and thus the optimization problem more difficult to solve. A final difficulty found in mechanical engineering optimization problems is that the physical model is rarely an explicit one and is based usually on numerical models. That makes algorithms like metaheuristics more favorable to solve these problems because they are iterative algorithms and do not require that the optimization problem to be differentiable. Despite its great practicality in real-world optimization problems, little work has been done to analyze and solve multi objective non linear problems with mixed variable. Furthermore, the need to propose new and adequate optimization algorithms to these problems seems more pressing than ever. According to the "No free lunch" theorem [START_REF] Wolpert | No free lunch theorems for optimization[END_REF], it was established that no single metaheuristics is the ultimate best for all kind of optimization problems. Instead, an algorithm can be considered more efficient only for a set of test problems. This realization has driven the hybridization of metaheuristics to a new level. In fact, hybrid metaheuristics has become a very active field, where researchers are more focused nowadays on finding the most adequate hybrid algorithm to the problem at hand. Hybrid metaheuristics are a combination of a metaheuristic with another (or several others) optimization algorithm(s). These optimization algorithms can be stochastic (like metaheuristics) or exact methods.

According to their execution order, they can be carried out in parallel or executed sequentially. They can also be classed according to the hybridization goal. Whether the goal is to obtain faster hybrid algorithms or more accurate ones, hybridization will always try to make the most of its components while minimizing their disadvantages.

Introduction

This thesis is intended first to provide a comprehensive overview of mixed variables handling techniques in mechanical engineering optimization problems. The rare previous reviews on mixed variables optimization problems found in the work of [START_REF] Liao | Population-based heuristic algorithms for continuous and mixed discrete-continuous optimization problems[END_REF] and the work of [START_REF] Socha | Ant colony optimisation for continuous and mixed-variable domains[END_REF] that are described in section 2.1 provided a glimpse from distance on the topic. Our work, however, goes more in detail by breaking down mixed variables handling techniques in metaheuristics into four stages in an up to date, state of the art overview, that does not exist to the best of our knowledge.

Furthermore, a second step in the thesis is to collect numerous hybridization techniques used on some metaheuristics that were able to handle mixed variables problems. Our goal was to set a framework for different hybrid metaheuristics that were never grouped together in a single taxonomy. We tried to cover every alteration that may be considered as hybridization. The taxonomy classed the hybridization according to the nature of the combined optimization algorithms, or according to the execution order and number of objective functions. Even the relatively new concept of coupling a metaheuristic with various constraint handling techniques was treated as a type of hybridization. To conclude the state of the art, a review on some techniques to assess the hybridization was then described.

To test some of the hybridizations, three different optimization problems were introduced; the dimensioning of a plate coupling, the dimensioning of a ball bearing connection and the dimensioning of gear train. The problems shared the same structure, like the existence of variables that can take continuous or discrete values and the existence of multiple (always conflicting) objective functions, under different constraints. They shared also another particularity, which is having a small combinatorial space. This last particularity allows to determine the true, and not approximate, solution (i.e. true Pareto front), and thus to test and compare optimization algorithms based on this knowledge to determine the best hybrid.

The problems were tested using two types of hybridizations. First we used "traditional" metaheuristics while modifying constraint handling technique. The second type was an original type of hybridization between metaheuristics and branch and bound.

The thesis is organized in the following manner:

• Chapter 1, contained the general mathematical formulation for the multi objective non linear constrained optimization problem with mixed variable alongside with the description and equations of the three problems at hand. they were modified to handle mixed variables optimization problems. Finally some exact optimization methods are described in detail.

-In section 2.3, the hybridization of metaheuristics with other metaheuristics or with exact methods is surveyed throughout literature. A special sub-section is dedicated for hybrid multi-objective metaheuristics. Finally, constraint handling techniques were presented as a toolbox for optimization.

-In section 2.4, four ways to evaluate hybrid metaheuristics are discussed thoroughly.

• Chapter 3 was divided as follows:

-In section 3.1, the three optimization problems were solved using "traditional" metaheuristics. The results were presented for two variants of the metaheuristics according to constraint handling technique. Then, an analysis of the results was conducted to determine the best metaheuristic for each problem as well as the best constraint handling technique.

-In section 3.2, a new hybridization between metaheuristics and branch and bound was introduced. In addition, different alterations of the new hybrid were tested on the three test problems using the knowledge from section 3.1 of the best metaheuristic and the best constraint handling technique. Finally the results were analyzed.

• Conclusion and perspectives.

1

Optimization problems

Outline of the current chapter

Formulation of the general optimization problem

In this section, we present the general form of the optimization problem treated in this thesis. The approach is general and can be applied to different problems. The particularity of this optimization problem is the existence of multiple objective functions, under different constraints, with variables that can take continuous or discrete values. This optimization problem is formulated mathematically in the following form:

P MO-MINLP : ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
Minimize f (x, y) = {f 1 (x, y), . . . , f p (x, y)} Under the contraints c j (x, y) ≤ 0 j = 1 . . . m c j (x, y) = 0 j = m + 1 . . . m + l l c ≤ x ≤ u c l e ≤ y ≤ u e with :

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ x, l c , u c ∈ R nc y, l e , u e ∈ Z ne f (x, y) ∈ R p c j (x, y) ∈ R
In this formulation, the problem P MultiObj contains a total of n = n c + n e variables, with n e integer variables and n c continuous variables. These n variables are subject to take values in the domain defined by the lower bounds l c , l e and upper u c , u e . It is assumed here that the functions f 1 (x, y), . . . , f k (x, y), . . . , f p (x, y) and c j (x, y) are 8 CHAPTER 1. Optimization problems continuous real functions, not necessarily convex and often differentiable. This type of problem is referred to as "MO-MINLP" for "Multi-Objective Mixed Integer Non Linear Programming" in the literature.

In the context of optimization in mechanical engineering and more precisely in the context of the design of mechanical systems, possibly including the problems of optimization of mechanical processes, it should be noted that:

• The integer variables y j , j = 1 . . . n e , can refer either to a number of components or to an input number in a data table, allowing manipulation of "catalogs" of mechanical components. So it is impossible to "relax" the integer variables by considering them as continuous.

• These problems generally involve few optimization criteria (often 2 or 3 and rarely more), because these criteria that one seeks to minimize are related to the performances of the system like for example the mass, the rigidity, the cost when that can be realistically estimated. Physical models for expressing, mechanical strength, durability, reliability, etc. are normally used to express the constrained functions of the optimization problem. For some examples and an explanation of how to formulate an optimization problem from an optimization problem, see [START_REF] Papalambros | Principles of optimal design: modeling and computation[END_REF] and [START_REF] Simpson | Multidisciplinary Design Optimization for Complex Engineered Systems: Report From a National Science Foundation Workshop[END_REF].

For more examples about these problems, see [START_REF] Messac | Optimization in practice with MATLAB for engineering students and professionals[END_REF] or [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF].

• Another particularity to this type of optimization problems is that they have small combinatorial space (couple of integer variables accepting less than a hundred values). Therefore, the exact solution can be computed using a simple enumeration procedure, making it possible to test the efficiency of the optimization methods by comparing the obtained solutions to the true Pareto front.

Optimization problem

In this section we present three different optimization problems. The problems are namely:

• The plate coupling problem

• The ball bearing pivot connection problem

• The gear train problem These test problems shared the same structure, like the existence of variables that can take continuous or discrete values and the existence of multiple (always conflicting) objective functions, under different constraints. They shared also another particularity, which is having a small combinatorial space. This last particularity allows to determine the true, and not approximate, solution (i.e. true Pareto front).

To solve these problems, our approach should be specific to the optimization problem at hand and benefit from the following characteristics of this problem:

Optimization problem

• It is a mixed variable problem in which the set of admissible values for the discrete variables admits a reasonable number of elements (i.e hundreds).

• Constrained functions use simple explicit analytic expressions.

First, the optimization problem need to be formulated from the functional conditions. Then the problem is solved using a specific approach guaranteeing the accuracy and completeness of optimal solutions. In fact, the optimal solutions for this kind of problems are necessarily located on the frontier of the domain of solutions (this idea is better explained in section 2.3.4.1). The approach consists in determining all the solutions obtained by intersecting the boundaries defined by the constrained functions. It will then be easy to identify optimal belonging to the front of Pareto.

Plate coupling: dimensioning model

From a simple technical function "transmitting a torque" by adherence via a coupling technique, the elementary mechanism is optimally dimensioned. A torque is to be transmitted between two parallel and perfectly coaxial shafts. The physical principle of force transmission by adhesion is chosen. This principle requires the presence of a normal force between the two surfaces in contact. This force is chosen to be made technologically by threaded elements. Figure 1.1 shows a possible design of this type of mechanism. The goal is to dimension the mechanism in a way that minimizes its cost and its weight. In this problem it will be noted that certain parameters for describing the geometry of the bolts and tools depend on the diameter d of the bolts. The table 1 To translate this dependence, we write ϕ i (d) an arbitrary function linking each parameter to the diameter d. We have:

p = ϕ 1 (d) (1.1) b m = ϕ 2 (d) (1.2)
s m = ϕ 3 (d) (1.
3)

d t = ϕ 4 (d) (1.4)
This problem of dimensioning of this bolted plate coupling can be expressed as a nonlinear multi-objective optimization problem with constrained functions and mixed variables, in the following manner:

Minimize the functions :

F 1 (x, y) = π 2 e p [ ρ J ( 16R b ϕ 2 (d) -N ϕ 4 (d) 2 ) + ρ b N d 2 ] F 2 (x, y) = 0.6d + 5N
Under the contraintes :

C 1 (x, y) = α S M N R b K(d) -1 ≤ 0 C 2 (x, y) = 1 - 2πR b ϕ 3 (d)N ≤ 0 C 3 (x, y) = 1 - (R b -ϕ 2 (d)) R Mini ≤ 0 C 4 (x, y) = (R b + ϕ 2 (d)) R Maxi -1 ≤ 0 C 5 (x, y) = 1 - M M T ≤ 0 C 6 (x, y) = M M Maxi - 1

Expression of the optimization problem for fixed values of d and N

Assuming that d and N are fixed and thus become given:

For the constraint function c 1 (x) :

k 1 M R b -1 ≤ 0 with : k 1 = α S N K(i d )
For constrained functions c 2 (x) and c 3 (x) : Potentially optimal solution points are those which are located in the field of solutions (i.e. which satisfy constrained functions).

M R b R b = k 1 M k 2 k 3 M T M Maxi M 1 M 2 M 3 M 4 M 5 M 6 M 7 M 8 ∇f 1 ∇f 2
Since the nature of the optimization problem is multi-objective, one should to try to determine the set of best compromises thus including the anchor points of the Pareto front. For these anchor points, we try to maximize f 1 and minimize f 2 and vice versa. Given the direction of the gradient of f 1 and f 2 , two situations occur:

• On the boundaries R b = k 2 ,R b = k 3 , M = M T and M = M Maxi the functions f 1
and f 2 are increasing for one and constant for the other and vice versa. In the space of objective functions this will give horizontal or vertical Pareto front portions, without adding any dominant points.

• On the boundary R b = k 1 M , f 1 and f 2 grow at the same time, so this is not part of the Pareto front.

CHAPTER 1. Optimization problems

The coordinates of the points M i are:

M 1 : {M T , k 2 } M 2 : {M Maxi , k 2 } M 3 : {M Maxi , k 3 } M 4 : {M T , k 3 } M 5 : {M T , k 1 M T } M 6 : {k 2 /k 1 , k 2 } M 7 : {k 3 /k 1 , k 3 } M 8 : {M Maxi , k 1 M Maxi } 1.2.

Pareto Front Search

The search algorithm for the Pareto front is as follows:

Algorithm 1 Front of Pareto Coupling for

N = N Mini to N = N Maxi do 3:
Calculate the coordinates of the points M i , i = 1 . . . 8.

4:

Store the M i points that respect ALL constrained functions Calculate the values of the objective functions F 1 and F 2 9: end for 10: Search for the dominant points in the set of F 1 and F 2 values stored. 11: Display the front of Pareto For this problem, it is possible to define certain data with respect to each other to ensure the consistency of the data set.

Starting from the value of the moment to transmit M T , we can define the value ofR Mini from the minimum diameter of the tree to transmit M T for a steel with a shear-elastic limit given by R pg . We then have:

R Mini = 1 2 ( 16M T πR pg ) 1 3
From this it is possible to determine a reasonable value of the radius of the maximal clutter of the coupling R Maxi by taking R Maxi = 3 or 4 × R Mini . Then the maximum number of bolts can be determined with:

c 2 (x) ≤ 0 ⇒ N ≥ k s πR b ϕ 3 (i d )
The bound on N is max for R b = R Maxi , taking k s = 1 one can get :

N Maxi = max i d { πR Maxi ϕ 3 (i d ) } 1.2. Optimization problem 15
The maximum transferable torque M Maxi is given by :

M Maxi = max i d { N Maxi (R Maxi -ϕ 3 (i d )) K(i d ) α S

}

The following data are considered in Table 1.2 With these values, the following Pareto solutions are obtained : We note that the Pareto front is discrete (i.e consisting of "points" for each optimal integer value of N ) and discontinuous in the sense that for 2 consecutive values of diameter (example between d=5 mm and d= 6 mm or between d=6 mm and d=8 mm, there is a "jump".

M T = 4 × 10 6 N mm e p = 10 mm f 1 = 0.15 N Mini = 8 f m = 0.15 R Mini = 30 mm α S = 1.5 R Maxi = 120 mm ρ J = 2.7 × 10 -6 kg/mm 2 N Maxi = 49 ρ b = 7.8 × 10 -6 kg/mm 2 M Maxi = 9.085 × 10 7 N mm R e = 627 MPa
d [mm] N [] R b [mm] M [N mm] f 1 relative weight f 2 relative cost c 1 [] c 2 [] c 3 [] c 4 []
Calculating this Pareto Front requires exploring all combinations of 15 diameters values and 59 -8 + 1 = 52 values of the number of bolts, or 780 combinations. For each of its combinations, it is possible to scan the space of the continuous variables in the range of the boundaries and thus obtain the image of the domain of the boundaries, solutions that can be realized in the space of objective functions. We then obtain the following figure.

Ball bearing pivot connection: dimensioning model

A simple technical function, known as a "pivot connection", makes it possible to guide in rotation a shaft transmitting a given mechanical power. Here, we assume a pivot connection made by two bearings with a row of balls. The assembly studied is that of an isostatic mounting (figure 1.6) where one of the bearings is assimilated to a ball joint (R1) and the other (R2) to an annular linear connection. The goal of the optimization is to optimize the relative mass of the system, and relative cost of bearings.

The forces applied to the shaft are modeled by a torsor expressed at the point O the center of the link and the origin of the reference to define the positions x 1 and x 2 of the bearings. We will note i r1 and i r2 the number of bearings (R1) and (R2). To translate the dependency between the i r number of the bearing and its various parameters, we denote by ϕ i (i r ) an arbitrary function linking each parameter to the bearing number i r . We have: Minimise the fonctions :

x 1 x 2 x 1Max x 1Min x 2Max x 2Min O R1 R2 z ! 𝑥 ⃗ 𝑦 ⃗ A B (1) (0) (0)
C = ϕ 1 (i r ) (1.5) C 0 = ϕ 2 (i r ) (1.6) d = ϕ 3 (i r ) (1.7) D = ϕ 4 (i r ) (1.8) B = ϕ 5 (i r ) (1.9) d a = ϕ 6 (i r ) (1.10) m = ϕ 7 (i r ) (1.11) no. C [N] C 0 [N] d [mm] D [mm] B [mm] da [mm] m [g]
F (x, y) = πρ a 4 [ ϕ 3 (i r1 ) 2 ϕ 5 (i r1 ) + ϕ 3 (i r2 ) 2 ϕ 5 (i r2 ) + . . . . . . ( x 1 + x 2 - ϕ 5 (i r1 ) + ϕ 5 (i r2 ) 2 ) max{ϕ 6 (i r2 ), ϕ 6 (i r2 )} 2 ] + . . . . . . ϕ 7 (i r1 ) + ϕ 7 (i r2 ) F (x, y) = ϕ 1 (i r1 ) + ϕ 1 (i r2 )
Under the constraints :

C (x, y) = (XF r1 (x 1 , x 2 ) + Y F a1 ) ( 60L v ω 10 6 ) 1 3 -ϕ 1 (i r1 ) ≤ 0 C (x, y) = F r2 (x 1 , x 2 ) ( 60L v ω 10 6 ) 1 3 -ϕ 1 (i r2 ) ≤ 0 C (x, y) = ( x 1Min + ϕ 5 (i r1 ) 2 ) -x 1 ≤ 0 C (x, y) = x 1 - ( x 1Max - ϕ 5 (i r1 ) 2 ) ≤ 0 C (x, y) = ( x 2Min + ϕ 5 (i r2 ) 2 ) -x 2 ≤ 0 C (x, y) = x 2 - ( x 2Max - ϕ 5 (i r2 ) 2 ) ≤ 0 C (x, y) = d 1Min -ϕ 3 (i r1 ) ≤ 0 C (x, y) = d 2Min -ϕ 3 (i r2 ) ≤ 0 C (x, y) = max {ϕ 4 (i r1 ), ϕ 4 (i r2 )} -D Max ≤ 0 C (x, y) = ϕ 4 (i r1 ) -ϕ 4 (i r2 ) ≤ 0 Or : C (x, y) = ϕ 4 (i r2 ) -ϕ 4 (i r1 ) ≤ 0 With : x = {x 1 , x 2 } T y = {i r1 , i r2 } T i r1 , i r2 ∈ {1, . . . , 61} × {1, . . . , 61}
Given : By considering the maximum mass of the shaft and that of the bearings, one can normalize the objective function F 1 , similarly for F 2 by considering the maximal "cost" as: 2 max{ϕ 1 (i r1,2 )}.

{x 1,2Min , x 1,2Max , d 1,2Min , D Max , . . . . . . ρ a , ω, L v , X O , Y O , Z O , M O ,

Expression of the optimization problem for a fixed pair of bearings

Assuming that i r1 and i r2 are fixed and thus become given data : For the constraint function C 1,2 (i r1 , i r2 , x 1 , x 2 ) :

F r1 (x 1 , x 2 ) ≤ k 1 with : k 1 = 1 X ⎡ ⎣ ( 10 6 60L v ω ) 3 ϕ 1 (i r1 ) -Y F a1 ⎤ ⎦ F r2 (x 1 , x 2 ) ≤ k 2 with : k 2 = ( 10 6 60L v ω ) 3 ϕ 1 (i r2 ) 1.2

. Optimization problem

The constrained functions C 3,4,5,6 (i r1 , i r2 , x 1 , x 2 ) defines lower and upper bounds of variables x 1 and x 2 ,These bounds are functions of the parameters B 1,2 = ϕ 5 (i r1,2 ) of the bearing pair.

x 1 ≥x 1Inf with :

x 1Inf = x 1Min + ϕ 5 (i r1 ) 2
x 1 ≤x 1Sup with :

x 1Sup = x 1Max - ϕ 5 (i r1 ) 2
x 2 ≥x 2Inf with :

x 2Inf = x 1Min + ϕ 5 (i r2 ) 2
x 2 ≤x 2Sup with :

x 2Sup = x 1Max - ϕ 5 (i r2 ) 2
The boundaries of the domain of solutions in the domain of the variables x 1 and x 2 is therefore defined by the bounds on x 1 and x 2 and the constrained functions C 1 and C 2 .

The following figure is obtained: These 6 constrained functions define 6 boundaries whose intersections 2 to 2 make it possible to define:

• 4 points at the 4 corners of the terminals on the variables x 1 and x 2 .

• 4 points of intersection between C 1 and C 3,4,5,6 .

• 4 points of intersection between C 2 and C 3,4,5,6 .

That is 12 points in total.

The coordinates of the 12 points M i are:

M 1 : {x 1Inf , x 2Inf } M 5 : x 1 such as C 1 (i r1 , i r2 , x 1 , x 2Inf ) = 0 and x 2 = x 2Inf M 2 : {x 1Inf , x 2Sup } M 6 : x 1 such as C 1 (i r1 , i r2 , x 1 , x 2Sup ) = 0 and x 2 = x 2Sup M 3 : {x 1Sup , x 2Inf } M 7 : x 2 such as C 1 (i r1 , i r2 , x 1Inf , x 2 ) = 0 and x 1 = x 2Inf M 4 : {x 1Sup , x 2Sup } M 8 : x 2 such as C 1 (i r1 , i r2 , x 1Sup , x 2 ) = 0 and x 1 = x 2Sup M 9 : x 1 such as C 2 (i r1 , i r2 , x 1 , x 2Inf ) = 0 and x 2 = x 2Inf M 10 : x 1 such as C 2 (i r1 , i r2 , x 1 , x 2Sup ) = 0 and x 2 = x 2Sup M 11 : x 2 such as C 2 (i r1 , i r2 , x 1Inf , x 2 ) = 0 and x 1 = x 2Inf M 12 : x 2 such as C 2 (i r1 , i r2 , x 1Sup , x 2 ) = 0 and x 1 = x 2Sup

Search for Pareto Front

The search algorithm for the Pareto front is as follows: The following data are considered :

Algorithm 2 Front of Pareto Coupling

1: for all i r1 ∈ {1, . . . , 61} do

2:

for all i r2 ∈ {1, . . . , 61} do

3:

Calculate the coordinates of the points M i , i = 1 . . . 12.

4:

Store the M i points that respect ALL constrained functions Calculates the values of the objective functions F 1 and F 2 9: end for 10: Search for the dominant points in the set of F 1 and F 2 values stored. 11: Display the front of Pareto Table 1.

L v = 1800 h ω = 970 tr/ min X O = 4000 N Y O = -4200 N Z O = 11 600 N M O = 0 N m M O = 0 N m ρ a =

-bearing pivot connection data

With the table data 1.5, the algorithm 2 explores exhaustively a set of: 61 2 ×12 = 44652 intersection points of all boundaries 2 to 2. In the end there are only 442 feasible solutions if the constraints are strictly negative or null, or 542 feasible solutions if the the constraints are less than 10 -6 . In the following we will present the results for the two cases.

For the case of 442 feasible solutions

The following results are obtained: Of the 542 eligible solutions we finally get the following 5 Pareto solutions:

0 ir2 [] x1 [mm] x2 [mm] F1 [g] F2 [N] C1 [] C2 [] C3 [] C4 [] C5 [] 11 C6 [] C7 [] C8 [] C9 [] 27
ir1 ir2 x1 [mm] x2 [mm] F1 [ ] F2 [ ] C1 C2 C3 C4 C5 C6 C7 C8 C9 C10

Multi objective optimization of a gear train

The dimensioning problem of the gear train can be formulated as a problem of multi objective optimization. A gear transmits a mechanical power between two shafts while ensuring homo-kinetic transmission of the rotational movement with a certain reduction ratio between the input and output shafts.

In fact, gears are widely used in many mechanical systems because:

• The transmission of the rotational movement is perfectly homokinetic for well dimensioned and correctly machined gears.

• Transmission efficiency is considered good, very close to the unit: 0.98 to 0.99.

• The reliability and power transmission per unit volume is very important with high quality steels.

• The conception and the dimensioning models are well mastered for "classical" designs, and up until today there are no competitive solutions.

The "standard" method of sizing the gears is standardized. Two standards co-exist, one American said to be proposed by the AGMA and accredited by the ANSI and the other international: ISO 6336. The model used here is that of the international standard CHAPTER 1. Optimization problems ISO 6336. This study concerns cylindrical gears with parallel, straight or helical axes, see figure 1.13. Here it would be too long and complex to detail all the parameters involved in the model and the set of necessary relationships.

One can distinguish 4 groups of parameters:

1. Parameters that completely define the geometry of the toothing:

• Including parameters that can be modified because they are directly related to the toothing:

z 1 , z 2 , m n , b, β, x 1 and x 2 .
• Including tool-specific parameters, parameters generally considered fixed in a design study: α n , m n , ρ a the tool radius, h a addendum coefficient, h f dedendum coefficient, s pr the over-thickness of machining.

2. Parameters related to the material of the teeth, taken from a list of 38 shades of steel and cast iron for gears.

3. The parameters defining the lubrication conditions and the ISO quality of the machining of the teeth.

4. The parameters defining the load: Power to transmit P t , gear rotation speed N 1 and the desired life in hours.

To this are added the parameters related to the dimensioning context: power transmitted, desired distance between centers, maximum overcrowding. In all the possible cases, at least 6 constraints functions are essential to ensure a satisfactory optimal dimensioning: 1. Transmissible resistance to tooth foot is sufficient.

2. The power transferable to the surface pressure is sufficient.

4.

No interference during meshing: two conditions one gear and the other on the wheel.

5.

The tooth thickness at the top of the tooth is sufficient.

By choosing to impose:

• The geometry of the cutting tool as a given data of the optimization problem.

• A pair of materials not necessarily identical for the gears.

• Manufacturing quality and lubrication conditions.

By limiting the study to a straight gear case, the variables of this optimization problem are:

x = {i m , x 1 , x 2 , b} T y = {z 1 , z 2 } T
The objective is to minimize both the volume of material and the relative sliding between the pinion and the wheel. The objective functions are:

f 1 (x, y) = d ′2 1 b d 2
1sup b sup and :

f 2 (x, y) = |g SB1 -g SA2 | |g SB1 | + |g SA2 | with :
g SB1 : Maximum slippage at tooth base for pinion.

g SB1 = z 1 + z 2 z 2 ⎛ ⎝ 2 √ d 2 a2 -d 2 b2 2 √ d 2 a2 -d 2 b2 -z 1 m ′ n sin α ′ n ⎞ ⎠ (1.12)
g SA2 : Maximum slippage at tooth base for wheel.

g SA1 = z 1 + z 2 z 2 ⎛ ⎝ 2 √ d 2 a1 -d 2 b1 2 √ d 2 a1 -d 2 b1 -z 2 m ′ n sin α ′ n ⎞ ⎠ (1.13) CHAPTER 1.

Optimization problems

The 6 constraints functions can be written as follows:

c 1 (x, y) = 1 - P uF P t ≤ 0 (1.14) c 2 (x, y) = 1 - P uH P t ≤ 0 (1.15) c 3 (x, y) = 1 - ε α 1.3 ≤ 0 (1.16) c 4 (x, y) = √ d 2 a1 -d 2 b1 -z 1 m ′ n sin α ′ n ≤ 0 (1.17) c 5 (x, y) = √ d 2 a2 -d 2 b2 -z 2 m ′ n sin α ′ n ≤ 0 (1.18) c 6 (x, y) = 1 - 4 m n min 1,2 {s a } ≤ 0 (1.19)
In general, conditions are imposed on the transmission ratio (u > 1) of the gear. It should be noted that the numbers of teeth z 1 and z 2 are not independent since u is fixed, we have: u = z 2 z 1 . z 1 and z 2 being integer, the transmission ratio u can not be exactly satisfied, but with a certain tolerance δu, we will then verify that:

u -δu ≤ z 2 z 1 ≤ u + δu
We can therefore identify the integers z 1 and z 2 which satisfy this relation with a tolerance δu and we have:

⃓ ⃓ ⃓ ⃓ ( z 2 z 1 ) i -u ⃓ ⃓ ⃓ ⃓ ≤ δu i = 1 . . . n z
Where n z is the number of teeth ratio that respects the transmission ratio.

The optimization variable vector can be simplified and reduced to 5 variables, of which 2 are continuous and 5 are continuous:

x = {i z , i m , x 1 , x 2 , b} T
where i z = 1 . . . n z is the index of the integer ratios (z 2 /z 1 ) iz which satisfy the transmission ratio u to about ±δu.

On the basis of this formulation, two design situations can be considered:

• Design with spacing a fixed with a tolerance of ±δa :

In this case, it is possible to determine the minimum and maxi moduli which satisfies the conditions on the minimum spacing a -δa and maximum a + δa,given the tooth number ratios (z 2 /z 1 ) iz :

m n Min = a -δa max iz {z 1 + z 2 }
(1.20)

m n Max = a + δa min iz {z 1 + z 2 }
(1.21)

One thus can limit the combinatorial space of the problem, and in the case of the processed example we get: 497 ratios and an interval of 9 module values 4473 possible combinations for the 2 integer variables i z and i m .

• Free entraxe a design:

In this case all standardized module values are a priori usable and the combinatorial space is vast with: 547 ratios and an interval of 41 module values, thus 547 × 41 = 22427 possible combinations for the 2 whole variables i z and i m .

In order to simplify the identification of the front of Pareto we will study only the first possibility.

Application example

Consider the case of application, taken from a cement mill reducer.

⃓ ⃓ ⃓ ⃓ ( z 2 z 1 ) i -u ⃓ ⃓ ⃓ ⃓ ≤ δu i = 1 . . .

}

Taking into account the imposed spacing and the usable modules, only the last 4971 ratios and the modules between 20 mm (i m = 33) and 50 mm (i m = 41) sont convenables.

This preliminary analysis reduces the combinatorial space of the problem and simplifies the formulation of the problem by avoiding a constraint function on the transmission ratio u of the gear.

We then have the following formulation:

Minimise the functions :

f 1 (x) = d ′2 1 b d 2 1sup b sup f 2 (x) = |g SB1 -g SA2 | |g SB1 | + |g SA2 | Under the constraints : c 1 (x) = 1 - P uF P t ≤ 0 c 2 (x) = 1 - P uH P t ≤ 0 c 3 (x) = 1 - ε α 1.3 ≤ 0 c 4 (x) = √ d 2 a1 -d 2 b1 -z 1 m ′ n sin α ′ n ≤ 0 c 5 (x) = √ d 2 a2 -d 2 b2 -z 2 m ′ n sin α ′ n ≤ 0 c 6 (x) = 1 - 4 m n min 1,2 {s a } ≤ 0 c 7 (x) = | m ′ n (z 1 + z 2 ) -a 2δa | ≤ 0 With : x = {i z , i m , x 1 , x 2 , b} T i z ∈ {1 . . . 497} i m ∈ {33 . . . 41} x 1,2 ∈ [-1, 1] b ∈ [b inf , b sup ]

Search for Pareto Front

In order to determine the Pareto front in acceptable computation times it is still possible to reduce the combinatorial space this problem. One can search among the 497 × 9 = 4497 combinations of ratios of number of teeth and modules, those which respect the imposed spacing with a sum of the coefficients of offsets such as

-2 ≤ x 1 + x 2 ≤ 2.
For each configuration it is also verified that the power transmitted for the sum of the maximum allowances x 1 + x 2 authorized by the center distance and the maximum width b = b sup is sufficient. We finally get 174 acceptable combinations. We denote by i c the index of these 174 combinations and so each i c corresponds to a value of i z and i m of the variable vector of the optimization problem. To simplify the search for the Pareto front, we can, first of all, eliminate among the 174 those that will not give a "dominant" Pareto front.

The anchor points of each of the Pareto fronts can be calculated from 174 combinations.

We assume here that we are able to calculate the global optimum of the optimization problem in continuous variables x c = {x 1 , x 2 , b} T for each combination {i z , i m }. The figure 1.14 shows an example of the anchor points for the combinations {66, 68, 117} 2 . It can be seen that, under the hyothesis, the anchor points are correctly identified, the pareto front of the 68 combination is dominated by those of the 66 and 117 combinations, while the 66 and 117 combinations give two "dominant" front, which if not dominated will be the final Pareto front. Finally, on 174 combinations, so 174 pair of anchors, one can identify only 14 combinations giving 14 Pareto fronts. To define the final Pareto front, it will be necessary to completely determine these 14 Pareto fronts, and then select the "pieces" of dominant fronts according to the algorithm 3.

The search algorithm for the Pareto front is as follows: Solve the problem in continuous variables: x c = {x 1 , x 2 , b} T with an NBI algorithm or εconstraints.

Algorithm

3:

Store the points of the "continuous" Pareto front. 4: end for 5: for all 14 Pareto fronts stored do 6:

Select the dominant Pareto front "fragments". 7: end for 8: Display the final Pareto front.

For the anchor points as well as for the complete exploration of a Pareto front, the calculations were done with the "MultiStart" option of the fmincon algorithm of MultiStart MatLab TM , which greatly limits the risk of obtaining local minima. The calculation of an entire Pareto front is done using the NBI algorithm (see [START_REF] Das | Normal-Boundary Intersection: An Alternate Method for Generating Pareto Optimal Points in Multicriteria Optimization Problems[END_REF] and [START_REF] Siddiqui | On improving normal boundary intersection method for generation of Pareto frontier[END_REF]).

Finally we get the final Pareto front of the figure 1.15, defined by 8 combinations. This front is discontinuous, each combination corresponding to a continuous "piece" of the front. The points that seem isolated, are in fact a dominant anchor of a piece of front, for which the precision of calculation of the front is not big enough to describe exactly the piece of front. For example the 59 configuration gives a "red" dot that looks isolated and this point is not dominated by the "cyan" dots of the 58 configuration. To judge more clearly, it would be necessary to refine the definition of the 58 configuration front. CHAPTER 1. Optimization problems The final Pareto front of the figure 1.15 consists of the 23 points "solutions listed in the table 1.9.

All of these calculations required:

• 781 102 evaluations of objective functions and constraints.

• 5170 s calculations on a 2-core processor with 2.6 GHz. Based on experiences, the hybridization should not be based on random combinations, but rather on solid bases, with innovative and insightful ideas, and scientific testing.

Mixed variables

Many engineering optimization problems can be modeled using combinations of continuous and discrete variables. This type of engineering problems often originates from the mechanical engineering field [START_REF] Liao | Population-based heuristic algorithms for continuous and mixed discrete-continuous optimization problems[END_REF]. Discrete variables are used for several reasons; such as choosing between different design options or representing a set of standard size components. For example, the number of teeth of a gear should be chosen as an integer.

The engineering problem that contains integer, discrete, zero-one and continuous variables is often called a mixed-variable optimization problem.

Mixed-variable optimization problems are in fact, a combination of combinatorial and continuous optimization problems [START_REF] Socha | Ant colony optimisation for continuous and mixed-variable domains[END_REF]. Combinatorial optimization involves looking for optimal combinations or permutations of available components and this requires the problem to be partitioned into a finite set of components [START_REF] Bernardo | Implementation of an ant colony optimization algorithm with constraint handling for continuous and mixed variable domains[END_REF]. While continuous optimization requires finding values for variables with a continuous domain. Mixed-variable optimization problems are particularly difficult to tackle, because they combine two type of difficulties. The first is that of combinatorial problems, where it is necessary to check all the solutions to be certain that the optimal one has been found. While the second difficulty is that of continuous problems where the search space is infinite and may be unbounded.

It is also useful to distinguish between ordinal discrete values and categorical discrete values. Ordinal variables exhibit a natural ordering relation, while categorical variables take their values from a finite set of categories [START_REF] Abramson | Mesh adaptive direct search algorithms for mixed variable optimization[END_REF]. They are often a set of non-numeric elements (e.g., shapes, colors or types of material...).

Compared to a problem with continuous variables only, a problem with mixed variables has a smaller solution space, due to discretization. It may then seem easier to solve. However, this is not the case. Problems with mixed variables require robust optimization methods and a large number of evaluations. Indeed, because of the presence of discrete variables, the solution space often becomes disjoint and non-convex [START_REF] Moreau | Optimisation des systèmes mécaniques: couplage de méthodes déterministes et évolutionnaires pour les problèmes en variables mixtes[END_REF]. Several local or global minima are likely to exist in this solution space.

One of the simplest methods to find an optimum for problems with mixed variables is to solve this problem by relaxing the restrictions due to the discrete variables and an optimum is then obtained for continuous variables only. Finally, the solution is defined for mixed variables as the closest discrete variable. A major flaw for this method is that, the discrete optimum can be far from the optimum for continuous variables. In Figure 2.1, an objective function is represented in both continuous and discrete variable cases. In the case of continuous decision variable, the optimum is clearly at a decision variable value of 4.5. However, the optimum in the discrete case is obtained at a decision variable value of -3 which is far from the rounding of 4.5. Another way to solve mixed variable optimization problems is the enumerative approach, where all possibilities of the discrete variables are finitely enumerated. Then, subproblems resulting from the enumeration are iteratively solved in the continuous space. However, due to the "combinatorial explosion" with the increase of the problem size, only the smallest instances could be solved by such an approach.

Despite its great practical importance, mixed variable optimization is not as much popular as continuous variable optimization and therefore, few algorithms have dealt with these problems. One of the rarest attempts to analyze mixed variable optimization techniques was the work of [START_REF] Liao | Population-based heuristic algorithms for continuous and mixed discrete-continuous optimization problems[END_REF]. In their work, the authors have divided algorithms that can handle mixed-variable optimization problems into three groups; 1. The first group is based on a two-partition approach, in which the variables are divided into continuous variables and discrete variables. The variables of one partition are optimized independently for fixed values of the variables of the other partition. This way of thinking usually leads to a large number of objective function evaluations. Moreover, since the dependency between the variables that belongs to different partitions is not explicitly treated, the algorithms using this approach are inclined to find some locally optimal solutions. An example for this type of approaches is the work in [START_REF] Sambo | MORE: Mixed Optimization for Reverse Engineering&# x2014; An Application to Modeling Biological Networks Response via Sparse Systems of Nonlinear Differential Equations[END_REF], where a mixed discrete and continuous optimization algorithm is introduced for the problem of fitting a sparse system of nonlinear differential equations to biological time series. The authors used a Local Search component, which searches in the discrete space of network structures, and a CHAPTER 2. Hybrid Metaheuristics For Mixed Variables Optimization Covariance Matrix Adaptation-Evolution Strategy component for the optimization of continuous system parameters. The authors argued that keeping separate the two tasks of searching in the space of network structures and of optimizing continuous parameters allowed to easily handle the optimization of the system matrix as a whole, rather than decomposing the problem and solving it for each variable.

2. The second group used a continuous relaxation procedure. For this group, all variables are considered continuous. The ordinal variables are first relaxed into continuous variables and later repaired during the evaluation of the objective function. The goal of the repair mechanism is to obtain a discrete value at each iteration. The simplest repair mechanisms are rounding and truncation (check Figure 2.1). Also it is possible to process the categorical variables using continuous relaxations. In general, the performance of algorithms based on the continuous relaxation approach depends on the repair mechanism and the continuous solvers. An example for this type of approaches is the work in [START_REF] Guo | Swarm intelligence for mixed-variable design optimization[END_REF].

3. The third group adopts a categorical optimization approach that directly manages discrete variables without continuous relaxation. Therefore, all possible ordering relations that may exist between discrete variables are disregarded and thus all discrete, ordinal, and categorical variables are treated as categorical variables. For this group, the continuous variables are processed by a continuous optimization method. An example for this type of approaches is the work in [START_REF] Audet | Pattern search algorithms for mixed variable programming[END_REF].

Another attempt to analyze mixed variable optimization was found in [START_REF] Socha | Ant colony optimisation for continuous and mixed-variable domains[END_REF], where the author divided techniques to cope with mixed variables into two categories:

• Hybrid and Relaxation-based Methods the relaxation-based methods are identical to classification 2 of [START_REF] Liao | Population-based heuristic algorithms for continuous and mixed discrete-continuous optimization problems[END_REF] where mixed variables optimization problems are relaxed to become continuous optimization problems. But another possible procedure that belongs in this category is to couple two methods specific to respectively continuous and combinatorial optimization. Then, one method may be used as a form of local search for the other. The basic downside of this approach comes from the different philosophy represented by combinatorial and continuous optimization methods.

• Native Mixed-Variable Optimization Algorithms that are able to naturally handle mixed-variable optimization problems. The authors mentioned only few methods including Genetic Adaptive Search and [START_REF] Deb | A flexible optimization procedure for mechanical component design based on genetic adaptive search[END_REF], where, in order to enable simultaneous handling of both discrete and continuous variables, a particular crossover and mutation operators were used.

To the best of our knowledge, no review has ever analyzed the techniques to handle mixed variables in an optimization problem from the point of view of "metaheuristic operators". Throughout the scope of this this work, we will monitor in section 2.2.2 the occasions where metaheuristics are used to solve a mixed-variable optimization problem. We focus in particular on how a metaheuristic operator (such as crossover and mutation for evolutionary algorithms or movement for swarm algorithms) is modified to adapt to mixed variables.

Optimization algorithms

The first "era" of optimizing constrained, mixed variables, multi-objective problems commenced with using "stand-alone" optimization algorithms, where the notion of hybridization was not as much popular as it is nowadays. Throughout this section, we present two types of optimization algorithms. The first type of algorithms were metaheuristics, which are described briefly with examples on both trajectory and population based metaheuristics. Afterwards, we discuss how the transition was made in literature from mono-objective metaheuristics (almost all metaheuristics are introduced to solve mono-objective optimization problems) to multi-objective metaheuristics. Finally, we monitor the occasions where metaheuristics were modified to handle mixed variables problems. The second type of algorithms were exact algorithms, where some suitable algorithms for mixed variable optimization problems were described in detail.

Metaheuristics

Metaheuristics were basically developed to overcome the shortcomings of exact optimization techniques which failed to solve nonlinear, complex optimization problems. They are implemented through an iterative generation process that is able to locate good quality solutions in a relatively short time. Metaheuristics are famous and wide spreading optimization techniques. The majority of them are inspired by natural phenomena like natural selection or the behavior of animals or even by music and immune systems among other inspirations. Metaheuristics are often divided in literature into two major groups: trajectory-based and population-based metaheuristics. Most of these algorithms were initially introduced for continuous optimization. In this section, we describe some "traditional" metaheuristics from both groups. We emphasis on metaheuristics that were modified so that they were able to handle mixed variable multi-objective optimization problems.

Transition from mono to multi-objective metaheuristics

Many "real-world" optimization problems are multi-objective ones with two or more objectives to deal with. These objectives are often conflicting, wherein an improvement for one objective can lead to the deterioration for the other. In this kind of problems, there is no single solution, but rather a set of solutions that represent a certain performance trade-off between different criterias. Almost all metaheuristics were initially introduced to handle mono-objective optimization problems. The main methodologies mentioned in [START_REF] Giagkiozis | An overview of populationbased algorithms for multi-objective optimisation[END_REF], and used to extend mono-objective to multi-objective metaheuristics are enumerated below.

• Pareto-based methods: These methods employ Pareto-dominance relations to evaluate the quality of the population. They are still used to this day; however, it would appear that their ability to handle problems with more than three objectives (many-objective problems) is somewhat limited. Some examples among many of this type of category are NSGA-II [START_REF] Deb | A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II[END_REF] and MOPSO [START_REF] Reyes-Sierra | Multi-Objective Particle Swarm Optimizers: A Survey of the State-of-the-Art[END_REF] (Reference that contains a review on the many variations of MOPSO)

• Decomposition-based methods: Decomposition methods employ a scalarising function and a set of weighting vectors to decompose an multi-objective problem into a set of single-objective sub-problems. Upon solution of this set of sub-problems, it is hoped that a good approximation of the Pareto front is obtained. There is evidence to suggest that this way of dealing with multi-objective problems is much more scalable for many-objective problems. However, there are still difficulties to be resolved for this type of methods. For example, the distribution of solutions on the Pareto front is controlled by the selection of weighting vectors. An example of this type of category is [START_REF] Zhang | MOEA/D: A multiobjective evolutionary algorithm based on decomposition[END_REF].

• Indicator-based methods:This type of methods for multi-objective problems is also promising. They are based on metrics developed to measure the quality of the solution set obtained from a metaheuristic. Examples for this category are [START_REF] Beume | SMS-EMOA: Multiobjective selection based on dominated hypervolume[END_REF] and [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF]. The most prevalent of these indicators has been the hypervolume indicator which will be discussed in section 2.4.1.

Trajectory-based metaheuristics

A trajectory-based technique starts with a single initial solution and, at each step of the search, the current solution is replaced by another (often the best) solution found in its neighborhood [3]. Trajectory-based metaheuristics are called exploitation-oriented methods, because they promote intensification in the search space. Their approach is to explore the problem space via transition from one feasible solution to another. Some well known trajectory-based metaheuristics are tabu search [START_REF] Glover | Tabu search-part I[END_REF], simulated annealing [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] and variable neighborhood search [START_REF] Mladenović | Variable neighborhood search[END_REF].

• Simulated annealing is inspired by metallurgy, where a technique called annealing consists on heating then controllably cooling a material to reduce its defects. By analogy, in simulated annealing, cooling is represented as a slow decrease in the probability of accepting worse solutions as the search explores the solution space. Algorithm 4 demonstrates the steps of a simple simulated annealing routine.

• Tabu search is basically a local search that explores the neighborhood of each solution as the search progresses. In order to not become stuck in poor-scoring areas, the local search make use of memory structures called tabu list. Tabu list is a set of prohibited solutions used to filter which solutions will be admitted to the neighborhood. Algorithm 5 gives a simple overview on a Tabu search routine.

Algorithm 4 Simulated annealing.

1: Input:

2:

x represents a vector solution in the solution space

3:
Objective functionsf 1 (x), ..., f k (x)

4:
Initial temperature's value T max 5:

lowest temperature T min 6:

Maximum number of iterations M axGeneration at a given temperature 7: Set the current solution x current to the initial solution's value x 0 : x current = x 0 . 8: Set the current temperature T to T max : T = T max . 9: while T ⩾ T min do 10:

for i = 1 to M axGeneration do 11:
Generate randomly a neighboring solution to x current : x ′ .

12:

Compute the change in the objective function

E = f (x ′ ) -f (x current ).
13:

if E ⩽ 0 then 14:

Set

x current = x ′ .
15:

else 16:
Generate q=random(0,1)

17:

if q ⩽ e -E/T then 18:

Set

x current = x ′ .
19:

end if 20:
end if

21:

end for

22:

Generate α=random(0,1)

23:

T = α × T 24: end while

CHAPTER 2. Hybrid Metaheuristics For Mixed Variables Optimization

Algorithm 5 Tabu Search.

1: Input:

2:

x represents a vector solution in the solution space

3:
Objective functionsf 1 (x), ..., f k (x)

4:
maximum length of the tabu list:

Leng(L) = z 5:
Maximum number of iterations M axGeneration 6: Set the current solution x current to the initial solution's value x 0 . 7: initialize the tabu list: L = {}. 8: for i = 1 to Maximum Generations do 9:

Generate randomly a neighboring solution to x current : x ′ .

10:

if x ′ ̸ ∈ L then 11: if Leng(L) > z then 12:
Remove the oldest solution from the list L.

13:

Set x ′ ∈ L. Trajectory-based techniques are particularly recommended when there is limited time for search, for example for real-time systems. They offer relatively good convergence time, but they lack the ability to cover the search space in a sufficient manner.

Population-based metaheuristics

Population-based algorithms work on a population of solutions. The initial population is usually randomly generated, and then enhanced through an iterative process. At each generation of the process, the entire population (or a part of it) is replaced by newly generated individuals (often the best ones). These techniques are called explorationoriented methods, since their main ability resides in the diversification in the search space [3]. Some well known population-based metaheuristics are evolutionary algorithms, particle swarm optimization, ant colony optimization, firefly algorithm, cuckoo search and bat algorithm among many others.

• Evolutionary algorithms are genetic inspired metaheuristics. An evolutionary

Optimization algorithms 49

Algorithm 6 VNS 1: Input:

2:

x represents a vector solution in the solution space

3:
Objective functionsf 1 (x), ..., f k (x)

4:
maximum length of the tabu list:

Leng(L) = z 5: lowest temperature T min 6: k = 1 7: while (k ≤ k max ) & (Max number of iterations is not reached) do 8:
Shaking: generate a point x ′ at random from the k th neighborhood of x 9:

Local search: apply a local search method with x ′ as initial solution;

10:

Denote with x ′′ the so obtained local optimum

11:
if (x ′′ is better than x) then 12:

x = x

k = k + 1 16:
end if 17: end while algorithm uses natural selection-like mechanisms, such as selection, recombination, and mutation. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators. Among evolutionary algorithms, the best known is Genetic algorithm [START_REF] Holland | Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence[END_REF]. Genetic algorithm seeks the solution of a problem in the form of a string of numbers and always uses recombination in addition to selection and mutation operations. The best example for genetic algorithms in multi-objective optimization is the non dominated sorting version (NSGA-II) [START_REF] Deb | A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II[END_REF] represented in algorithm 7.

With solutions in the form of computer programs, Genetic programming [START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF] determines the fitness of solution by the ability to solve a computational problem. With a fixed structure of the program, Evolutionary programming evolves numerical parameters [START_REF] Liu | A unified framework for population-based metaheuristics[END_REF].

• Particle swarm optimization (PSO) [START_REF] Eberhart | A new optimizer using particle swarm theory[END_REF] imitates animal flocking behavior. It solves a problem by having a population of candidate solutions called particles, and moving these particles around in the search-space according to a mathematical formula over the particle's position and velocity. Each particle's movement is not only affected by its local best known position, but is also guided towards the best known positions in the search-space, which are updated when better positions are found by other particles. This approach is expected to move the swarm toward the best solutions [START_REF] Kleindorfer | The network challenge: strategy, profit, and risk in an interlinked world[END_REF]. The adaptation of PSO to multi-objective optimization can be 50 CHAPTER 2. Hybrid Metaheuristics For Mixed Variables Optimization Algorithm 7 NSGA-II algorithm 1: Input:

2:

x represents a vector solution in the solution space

3:
Objective functionsf 1 (x), ..., f k (x)

4:

Population size N 5:

Maximum number of iterations M axGeneration Select points on the lower front with higher crowding distance • Ant colony optimization imitates the behavior of ants seeking a path between their colony and a source of food. During their search for food, ants wander randomly, and return to their colony when they find food, while laying down pheromone trails. If some other ants find the same path, they are likely to follow this path, returning and reinforcing it if they eventually find food. However, the pheromone trail starts to evaporate over time, thus reducing its attractive strength. Because short path gets marched over more frequently, the pheromone density becomes higher on shorter paths than longer ones [START_REF] Shan | Emergency Response Decision Support System[END_REF]. This behavior was first imitated in a PhD thesis [START_REF] Dorigo | Optimization, learning and natural algorithms[END_REF]. The goal of the first algorithm was to search an optimal path in a graph. Since then, the original idea has been modified in different ways to solve a wider class of optimization problems.

• Bat algorithm (BA) was first introduced in [START_REF] Yang | Bat algorithm for multi-objective optimisation[END_REF]. It is a meta heuristic that imitates the bat's echolocation system. It can be summarized as follows: Each virtual bat flies randomly with a velocity v i at position (solution) x i with a varying frequency or wavelength φ ∈ [φ min ,φ max ] and loudness A i and where β ∈ [0, 1] is a random vector drawn from a uniform distribution and x * is the current global best location (solution) which is located after comparing all the solutions among all the n bats at each iteration t. As a bat searches and finds its prey, it updated its position and velocity and changes frequency, loudness and pulse emission rate r. Search is intensified by a local random walk. Selection of the best continues until a stop criteria is met. One can find a standard BA routine for multi-objective optimization in algorithm 9.

• cuckoo search is an optimization algorithm first developed by [START_REF] Yang | Cuckoo search via Lévy flights[END_REF]. The algorithm was inspired by some cuckoo species that lay their eggs in the nests of other host birds. Some host birds can find the intruding cuckoos and engage direct conflict with them. The analogy of the algorithm is that each egg in a nest represents a solution, and a cuckoo egg represents a new solution. The goal is to use the new and potentially better solutions (cuckoos) to replace a so called not-so-good solution in the nests. A representation of cuckoo search algorithm for multi-objective optimization can be found in algorithm10.

• Firefly algorithm was introduced in [START_REF] Yang | Nature-inspired metaheuristic algorithms[END_REF]. It is inspired by the flashing behaviour of fireflies. Fireflies are insects that produce rhythmic flashes. The main goal of the flashing light is to attract partners.The intensity of light is the factor that guides other fireflies to move toward the source of the light. The light intensity is varied according to the distance. Firefly algorithm assume three rules [START_REF] Yang | Nature-inspired metaheuristic algorithms[END_REF]:

1. Fireflies are attracted toward each others regardless of gender.

2. The attractiveness of the fireflies is correlative with the brightness of the fireflies, thus the less attractive firefly will move forward to the more attractive

CHAPTER 2. Hybrid Metaheuristics For Mixed Variables Optimization

Algorithm 8 MOPSO algorithm 1: Input:

2:

x represents a vector solution in the solution space

3:
Objective functionsf 1 (x), ..., f k (x)

4:
number of particles n 5:

Maximum number of iterations M axGeneration 6:

Repository Size nRep 7:

Inertia Weight w 8:

Personal Learning Coefficient c1 9:

Global Learning Coefficient c2 for j = 1 to N do 20:

Select the leader particle

21:

Update particle position taking into account w, the personal learning experience of each particle (c1), and the global learning experience of the swarm (c2)

22:

Evaluate particle's fitness value

23:

Apply mutation with a µ rate and update particle position

24:

Update the best personal memory Find repository member

28:

Combine new repository member with repository member

29:

Update repository member using the dominance sorting algorithm x represents a vector solution in the solution space

3:
Objective functionsf 1 (x), ..., f k (x) Maximum number of iterations M axGeneration 7:

Loudness A 8:

pulse emission rate r 9:

frequency or wavelength φ 10: Initialize the bat population x i (i = 1, 2, . . . , n)and v i the velocity 11: for j = 1 → N (points on Pareto fronts) do

12:

Generate K weights w k ≥ 0 so that

∑ K k=1 w k = 1 13: Form a single objective f = ∑ K k=1 w k f k 14:
while t < MaxGeneration do 15:

φ i = φ min + (φ max -φ min )β 16: v t+1 i = v t i + (x t i -x * )φ i 17: x t+1 i = x t i + v t i 18:
if rand > r i then

19:

Random walk around a selected best solution 20:

end if

21:

Generate a new solution by flying randomly

22: if (rand < A i ) & (f (x i ) < f (x * )) then 23:
Accept the new solutions 24:

increase r i and reduce A i 25:

end if

26:

Rank the bats and find the current best x *

27:

end while x represents a vector solution in the solution space

3: Objective functionsf 1 (x), ..., f k (x) 4:
number of nests of solutions n Get a cuckoo randomly (say, i) and replace its solution by performing Lévy flights;

12:

Evaluate its quality/fitness F i

13:

Choose a nest among n (say, j) randomly;

14: if F i > F j then 15:
Replace j by the new solution; A fraction of the worse nests are abandoned with a probability pa and new ones are built;

18:

Keep the best solutions/nests;

19:

Rank the solutions/nests and find the current best;

The brightness of fireflies is depend on the objective function

Algorithm 11 illustrated a version of firefly algorithm for multi-objective optimization.

Algorithm 11 Multi objevtive Firefly algorithm

1: Input:

2:

x represents a vector solution in the solution space

3: Objective functionsf 1 (x), ..., f k (x) 4:
number of fireflies n 5:

Number of points on the Pareto front N 6:

Maximum number of iterations M axGeneration 7:

Absorption coefficient γ 8: Generate an initial population of fireflies

x i (i = 1, 2, . . . , n) 9: for i = 1 → N do 10:
Formulate light intensity I so that it is associated with f ( x) for j = 1 → n(all n fireflies) do 13:

for l = 1 → i(n fireflies) do 14: if I j > I i then 15:
Vary attractiveness with distance r via exp(γr) Rank fireflies and find the current best;

22:

end while 23: end for In [START_REF] Beheshti | A review of population-based metaheuristic algorithms[END_REF], the authors gave a review on some population-based metaheuristics including the three types mentioned above. They all have in common a slow convergence rate. In fact , population-based approaches often converge relatively slowly towards optimal solutions. But they are known to be more able to cover the search space better than trajectory-based metaheuristics.

Metaheuristics for mixed variables problems

While continuous variables can take on any value between two numbers, discrete variables do not afford such spreading and smoothness. They can only have a value from a set of predefined values. In their most wide form, these predefined values can be integers, zero-one numbers, graphs, objects, colors, etc... As we mentioned in section 2.1, the literature is very scarce on the topic of mixed variable optimization, despite its importance for real-world applications. As a matter of fact, the authors in [START_REF] Giagkiozis | An overview of populationbased algorithms for multi-objective optimisation[END_REF] reviewed in their recent work, the ability of seven metaheuristics to handle mixed variables problems. A scale ranging from 1 to 5 was given to to measure the relative strengths and weaknesses of algorithm families for multi-objective problems with mixed variables. A value of 5 translates that this particular family of algorithms is very well suited for this type of problem, while a value of 1 means that the algorithm is poorly suited for this type of problems. The comparison showed that while six algorithms out of seven were able to handle mixed variables optimization, all of these six algorithms scored 1 in their suitability test.

In the following, we will review the modifications introduced on some metaheuristic components in order to handle these discrete variables. The main components that we will discuss are:

• Initialization

• Distance measure between individuals (solutions)

• Solution update • Creating neighborhoods

Initialization

The simplest and most common way for solution initialization in mixed-variables optimization problems is to treat each type of variables separately; where different adequate initialization procedures are developed according to the type of variable at hand. This way of initialization is manifested in its best form in [START_REF] Cao | An evolutionary programming approach to mixedvariable optimization problems[END_REF], where the authors presented a mixed-variable evolutionary programming (MVEP) technique for solving nonlinear optimization problems which contain integer, discrete, zero-one and continuous variables.

Regarding the initialization part, their technique consisted on generating each part (continuous variables, zero-one variables, integer variables and discrete) of the initial parent vector separately.

Distance between individuals

The distance metric between solutions is often used in metaheuristics where solutions are represented as population of individuals. It serves as way to promote diversity or to update the current solution. In general, the normalized Euclidean metric distance is the most used technique. It can handle both continuous and integer variables. Another famous technique is the hamming distance, which is used mainly for binary variables. The hamming distance of two vectors x i and x j is given by d = |H| where H is number of entries, k, for which x i (k) ̸ = x j (k).

A genetic algorithm named "Struggle Genetic Algorithm (StrGA)" was introduced in [START_REF] Dimopoulos | Mixed-variable engineering optimization based on evolutionary and social metaphors[END_REF]. Since the algorithm was designed to handle mixed variable problems, appropriate distance metrics were used for real, integer and binary variables accordingly. For real and integer variables, the normalized Euclidean metric distance was used, while for the binary variables the Hamming metric distance was used. The total distance metric between two individuals, both consisting of real, integer and binary variables, was chosen as the sum of the respective distance metrics.

The hamming distance was also used to measure the distance between fireflies in Firefly algorithm [START_REF] Yang | Nature-inspired metaheuristic algorithms[END_REF]. The algorithm was modified in order to handel problems with non-continuous variables [START_REF] Poursalehi | Multi-objective loading pattern enhancement of PWR based on the discrete firefly algorithm[END_REF], [START_REF] Durkota | Implementation of a discrete firefly algorithm for the QAP problem within the sage framework[END_REF], [START_REF] Mamaghani | Software modularization using the modified firefly algorithm[END_REF].

Solution update

The update of a current solution in metaheuristics is executed in different ways. It can be done either by a move in some trajectory based metaheuristics like simulated annealing, or by crossover and mutation operators in evolutionary algorithms, or by a walk in swarm metaheuristics like Ant Colony Optimization... According to the type of variable, the way of adapting a metaheuristic operator to mixed variables problems may change. Rounding is the most encountered technique to handle non-continuous variables while updating a solution.

A technique that can handle any type of discrete variables is to work, in conjunction

with rounding, on variable indices. It consists of treating variables as objects, regardless of their nature, and to choose randomly according to its index the next updated solution.

For example, in [START_REF] Cao | An evolutionary programming approach to mixedvariable optimization problems[END_REF], the mutation operator was adapted to handle discrete and continuous variables. A parent vector x i is mutated to create an offspring vector x i+N . In the case of discrete variables, a mutation is done by changing variables from a pre-specified discrete value to another one, that is:

x d i+N,j = d l+IN T [(2r 3 -1).DST j ] if x d i = d l Where j = 1, 2, ..., n d , and r 3 ∼ U (0, 1).
DST j is a step size (an integer) of discrete variable for a mutation, d l is the lth element of the discrete variable subset X d and INT[x] denotes the greatest integer less than the real value x.

The same technique is also used for simulated annealing which was modified to handle mixed variables in [START_REF] Huang | Optimal design with discrete variables: some numerical experiments[END_REF] and [START_REF] Deb | A flexible optimization procedure for mechanical component design based on genetic adaptive search[END_REF] in the following manner:

(a) For continuous variables:

x (k+1) i = min(x iU , x (k) i + α(x iU -x iL )) if z ≤ 5 x (k+1) i = max(x iL , x (k) i + α(x iU -x iL )) if z > 5
where z is a random number uniformly distributed between 0 and 1. x (k+1) i and x (k) i denote, respectively, the new and the current values for the ith variable, k is the trial number within the same iteration (same temperature level), x iL and x iU are the lower and upper bound for the ith variable respectively, and α is the step size calculated as follows: α = max(0.01, 0.2(0.9) K-1 ), where K is the iteration number.

(b) For discrete variables: If the current design point has the mth discrete value for the ith variable (i.e., x

(k) i = d im )
, then the new value for the ith variable becomes x

(k+1) i = d ij , where j = min(q i , m+J), if z ≤ 5 or j = max(1, m-J), if z > 0.5. The integer J is calculated as J = max(1, IN T (0.2(0.9) K-1 q i )),
where INT(x) denotes the integer part of x, and q i is the number of discrete values for the ith variable.

Another occurrence where this technique was also used is for Particle Swarm Optimization PSO, where the authors of [START_REF] Sun | A modified particle swarm optimization with feasibility-based rules for mixed-variable optimization problems[END_REF] and [START_REF] Sun | An improved particle swarm optimization with feasibility-based rules for mixed-variable optimization problems[END_REF] introduced the modifications presented in Algorithm 12

Algorithm 12

The processing of discrete variables in PSO.

1: Begin 2: if the variable is discrete then

3: Suppose x id (t) = d[j] 4:
if v id (t + 1) ≥ 0 then 5:

x id (t + 1) = d[j + 1]

6: else 7:

x id (t + 1) = d[j -1] 8:
end if 9: end if Where x id (t) and x id (t + 1) denote, respectively, the new and the current values for the id variable. v id (t + 1) represent the new velocity and d[j] is the jth value from a set of predefined values. Finally, we mention as last example the work of [START_REF] Liao | Ant colony optimization for mixed-variable optimization problems[END_REF], where the authors have introduced ACO M V , an algorithm for optimizing ant colonies to solve the mixed variable optimization problems. ACO M V integrates a continuous optimization solver (ACO R ), a continuous relaxation approach (ACO M V -o ) and a categorical optimization approach (ACO M V -c ) to solve continuous and mixed-variable optimization problems.

Optimization algorithms

59

(ACO R ) processes continuous variables, while (ACO M V -o ) and (ACO M V -c ) treat ordinal and categorical variables respectively .

• Construction of probabilistic solutions for ordinal variables: The continuous relaxation approach, ACO M V -o , is used if the proposed optimization problem includes ordinal variables. ACO M V -o does not work on the actual values of the ordinal variables but rather on their indices in an array. The values of the indices for the new solutions are produced in the form of real numbers, as is the case for continuous variables. However, before the evaluation of the objective function, the continuous values are rounded to the nearest valid index and the value of this index is then used for the evaluation of the objective function.

• Probabilistic solution construction for categorical variables While ordinal variables are "relaxed" and processed by the original ACO R , categorical variables are treated differently by ACO M V -c because this type of variables has no predefined order. At each stage of ACO M V -c , an ant assigns a value to a variable at a time. For each categorical variable, an ant probabilistically chooses one of the available values.

2. In the particular case were variables are integers, a simple rounding is enough to update the solution.

For example, a crossover operator is defined in StrGA [START_REF] Dimopoulos | Mixed-variable engineering optimization based on evolutionary and social metaphors[END_REF], where each variable is treated separately, according to its type (i.e. real, integer, binary). For real variables arithmetic crossover is used and offspring individuals are then produced.

While for the integer variables, a rounding operator denoted as IN T () is applied to these variables.

Another example is the work in [START_REF] Cao | An evolutionary programming approach to mixedvariable optimization problems[END_REF], where the mutation operator is adapted to handle integer, discrete, zero-one and continuous variables . A parent vector x i is mutated to create an offspring vector x i+N , based on the following rule:

(a) For continuous variables: A mutation is carried out by adding to each component of x c i,j a Gaussian variable with zero mean and a standard deviation proportional to the normalized objective value of the parent trial solution, (b) For integer variables: A mutation is achieved by changing a variable from one integer value to another one with a random step size.

A last example is the work in [START_REF] Sun | A modified particle swarm optimization with feasibility-based rules for mixed-variable optimization problems[END_REF] and [START_REF] Sun | An improved particle swarm optimization with feasibility-based rules for mixed-variable optimization problems[END_REF], where PSO is updated to handle integer variables as shown in Algorithm 13.

Where x id (t) and x id (t + 1) denote, respectively, the new and the current values for the id variable. v id (t + 1) represent the new velocity and int() denotes a rounding operator.

CHAPTER 2. Hybrid Metaheuristics For Mixed Variables Optimization

Algorithm [START_REF] Bożejko | Parallel tabu search algorithm for the hybrid flow shop problem[END_REF] The processing of integer variables in PSO. if v id (t + 1) ≥ 0 then 4:

x id (t + 1) = int(x id (t) + v id (t + 1)) + 1 x id (t + 1) = int(x id (t) + v id (t + 1)) -1

7:
end if 8: end if 9: if the variable is continuous then 10:

x id (t + 1) = x id (t) + v id (t + 1) 11: end if 2.

Creating neighborhoods

Some trajectory-based metaheuristics that are based on neighborhood concept were changed to cope with mixed-variable optimization.

• The authors in [START_REF] Dhingra | Discrete and continuous variable structural optimization using tabu search[END_REF] demonstrated the applicability and robustness of tabu search through an application to single and multiobjective structural optimization problems with discrete and continuous variables.

Given the number of search moves (K) for variable x, the step lengths used to define K neighborhoods around x were:

in the case of continuous variables:

h j = (x max -x min )/z j j = 1, ..., K with H = [h 1 , ..., h K ].
Here x max and x min denote the upper and lower bounds on variable x and Z is a constant.

-If variable x is allowed to assume only discrete values over set R, the neighborhood moves h j , j = I, ..., K are defined as follows:

The elements of R are indexed from I to |R|. Assuming the current value of x corresponds to index value i, I ≤ i ≤ R, the search neighborhoods around x(or i) are defined as i ± j where j is a randomly chosen integer such that j ≤ δx.

Here δx denotes the largest deviation permitted in the indexing variable. Using this definition of neighborhoods, K = δx. It may be noted that the feasibility of neighborhood steps is ensured by requiring i ± j ∈ [l, ..., R].

• Variable neighborhood search was used separately for:

-continuous optimization The authors in [START_REF] Mladenović | General variable neighborhood search for the continuous optimization[END_REF], for example, showed that the neighborhood N k (x) denotes the set of solutions in the kth neighborhood of x, and using the metric p k , where the metric are defined in an usual way, i.e., as distance. It is defined as:

N k (x) = {y ∈ S|p k (x, y) ≤ r k }
where r k is the radius (size) of N k (x) monotonically non decreasing with k. Here the neighborhood contains an infinite number of points.

-discrete optimization The authors in [START_REF] Brimberg | Variable Neighborhood Descent for the Capacitated Clustering Problem[END_REF], for example, defined each neighborhood by a move that relocates a certain number of elements from their current groups to another. In particular, the following three neighborhoods are distinguished. Insertion neighborhood, Swap neighborhood, Two Out/One In neighborhood

Exact methods

In contrast to metaheuristics, exact methods are algorithms that solve an optimization problem to optimality, and not only to near optimal solutions. Therefore, they are the number one choice for any optimization problem if they can provide a solution with acceptable computational effort. Exact optimization methods were used numerous times for combinatorial optimization. It is this combinatorial aspect that make them suitable for mixed variable optimization problems. In this paragraph, we present two exact methods that were coupled many times with metaheuristics to solve various optimization problems.

• Branch and bound [START_REF] Land | An automatic method of solving discrete programming problems[END_REF] Branch and bound algorithms are a fairly old algorithmic principle (1958)(1959)(1960) originally developed by [START_REF] Laurence | Linear Programming with Pattern Constraints[END_REF], [START_REF] Markowitz | On the Solution of Discrete Programming Problems[END_REF] and [START_REF] Land | An Automatic Method of Solving Discrete Programming Problems[END_REF] to solve linear economic programming problems with integer variables. The branch and bound algorithm is based on an enumeration of candidate solutions by means of state space search: the set of candidate solutions is viewed as a rooted tree [START_REF] Murphy | Machine learning: a probabilistic perspective[END_REF].

The enumeration part is referred to as branching while bounding refers to the fathoming of possible solutions by comparison to a known lower or upper bound on the solution value [START_REF] Socha | Ant colony optimisation for continuous and mixed-variable domains[END_REF]. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against lower and upper estimated bounds on the optimal solution, and is rejected if it cannot produce a better solution than the best one found so far by the algorithm [START_REF] Murphy | Machine learning: a probabilistic perspective[END_REF].

The literature concerning branch and bound algorithms applied to multi objective mixed variable optimization problems is rather scarce. For example, a search in "SCOPUS" with the words "branch and bound", "multi-objective" and "non-linear" returns only 25 references, of which only 1 [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF], includes mixed variables. If we consider the work related to linear multi-objective problems in mixed variables, we can also mention the recent review of [START_REF] Przybylski | Multi-objective branch and bound[END_REF] which gives a fairly complete overview of the work published on this subject with the field of application of operational research problems.

• Branch and cut [START_REF] Padberg | A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems[END_REF] Branch and cut is a combinatorial optimization method for solving integer linear optimization problems. This method involves running a branch and bound algorithm and using cutting planes technique to tighten the linear programming relaxations. The principle is to solve the linear program without the integer constraint using the regular simplex algorithm. When an optimal solution is found, and one of its variables that is supposed to be integer has a non integer value, a cutting plane algorithm is used to find a linear constraint satisfied by all integer values of the solution but violated by the fractional value [START_REF] Mitchell | Branch-and-cut algorithms for combinatorial optimization problems[END_REF]. If such a constraint is found, then it is added to the linear program so that the resolution of that program gives a solution with fewer non integer values. This procedure is repeated until an entire solution is found, which is then optimal, or until no cutting plane can be found. At this point, the branch and bound part of the algorithm begins. The problem is divided into two sub-problems, one by adding the constraint that the variable is greater than or equal to the integer part by excess of the intermediate solution and the other by adding the constraint that the variable is less or equal To its usual integer part (by default). These two new linear programs are solved with the simplex algorithm and the procedure described above is iterated.

Hybridization

After trying independent optimization algorithms to solve constrained, mixed variables, multi-objective optimization problems, the next step was to combine or modify these algorithms in the hope to obtain better results. Nowadays, the hybridization of pure metaheuristics has become a common strategy to solve optimization problems. The huge number of efficient hybrid metaheuristics proves that hybrid metaheuristics represent actually the most efficient algorithms for many classical and real-life difficult problems [START_REF] Talbi | Combining metaheuristics with mathematical programming, constraint programming and machine learning[END_REF].

In the section we describe different types of hybridization. First the combination of metaheuristics and exact methods is discussed thoroughly. Then various types of combinations for metaheuristics are enumerated. Furthermore, a special attention is given for hybrid multi-objective optimization. Finally, the relatively new concept of altering a metaheuristic by coupling it with various constraint handling techniques is considered as a type of hybridization and is discussed in detail.

Coupling metaheuristics with exact methods

The first approach for hybridization was to consider the cooperation between metaheuristics and other metaheuristics. At first, it seemed like the only straightforward approach, and others ways to hybridize metaheuristics were neglected. It was not until researchers realized the complementary aspect between some exact methods and metaheuristics that this type of hybridization emerged. In fact, exact methods are often used for combinatorial optimization problems with small instances. They are known for their capability to solve these small instances problems and asses their optimality. However, they are not used to solve large NP-hard problems because they are computationally expensive.

Combinations that are able to exploit simultaneously the advantages of exact methods (e.g. enumerative criteria for Branch and Bound algorithm) and the capabiltiy of metaheuristics to deal with large instances optimization problems, are often a good trade, when solving mixed variables optimization problems. Since this realization, different attempts to classify this type of hybridzation were made. The authors in [START_REF] Dumitrescu | Combinations of local search and exact algorithms[END_REF], treated the hybridization between exact methods and local search.

In [START_REF] Puchinger | Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification[END_REF], the authors presented a state of the art on the combination of metaheuristics and exact algorithms in combinatorial optimization. They classed these hybrids in two main categories; The first category was called "Collaborative Combinations", in which the algorithms exchange information, but are not part of each other. This category was subdivided in two subcategories:

• Sequential execution.

• Parallel and intertwined execution.

The second category was called "Integrative Combinations"; in which one technique is a subordinate embedded component of another technique. It was also subdivided in two subcategories:

• Incorporating exact algorithms in metaheuristics.

• Incorporating metaheuristics in exact algorithms. Some examples from the literature were given by the authors to clarify each subcategory. A more elaborate taxonomy (that was originally introduced in [START_REF] Talbi | A taxonomy of hybrid metaheuristics[END_REF]) was recalled in [START_REF] Jourdan | Hybridizing exact methods and metaheuristics: A taxonomy[END_REF] to illustrate the different types of cooperation between exact methods and metaheuristics. According to this taxonomy, the design of metaheuristics can be classified in two types of design classification:

• Low-level/High-level -Low-level: A given function of a metaheuristic is replaced by another method.

-High-level: The different algorithms are self-contained.

• Relay/Teamwork -Relay: A set of methods is applied one after another, each using the output of the previous as its inputs, acting in a pipeline fashion.

-Teamwork: It represents cooperative optimization models.

Four classes were derived from this hierarchical taxonomy.

• Low-level Relay Hybrid In this type of cooperation, a given method is embedded into another method, and the two (or possibly more) methods used lose their identity to produce a new algorithm. The embedded method has to be executed sequentially. An example of this type of cooperation can be found in [START_REF] Augerat | Separating capacity constraints in the CVRP using tabu search[END_REF], where a branch and cut algorithm is proposed to solve a capacitated vehicle routing problem (CVRP).

• Low-level Teamwork Hybrid In this class, an element of a given method is replaced by another method. It consist in an embedded method which can be executed in parallel with the global method. Two examples for this class of hybrids are when:

-The exact approach build partial solutions, which are used to define a search space for the heuristic approach. Then, the results obtained by the heuristic are analyzed in order to refine bounds, or column to generate in a branch and cut algorithm.

-The heuristic search works like memetic algorithms [START_REF] Moscato | On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms[END_REF], but in this case, the genetic operator is replaced by an exact search within a subspace of the global search space.

• High-level Relay Hybrid In this class, the different methods are self-contained and are executed in sequence. In general, the most natural approach is to design a sequential execution of a metaheuristic which is launched before an exact approach. An example for this type of hybridization is that of [START_REF] Talbi | Hybridation des algorithmes génétiques avec la recherche tabou[END_REF] • High-level Teamwork Hybrid This class contains algorithms where self-contained methods are performing a search in a parallel and cooperative manner. This involves principally island parallel models, with two different types of islands, those which are dedicated to exact search, and those dedicated to heuristic search. During the execution, the different algorithms exchange information, which is dependent of the type of the island. The major difficulty is to set parameters (when and how the exchange is realized for example). An example for this type of hybridization is that of [START_REF] Belding | The distributed genetic algorithm revisited[END_REF]

Coupling metaheuristics with other metaheuristics

The combination of different metaheuristics is the most common type of hybridization found in the literature. According to its execution order, a hybrid metaheuristic that falls in this category can be parallel or sequential.

Parallel hybrids

Despite the fact that they are now regarded as an independent class of metaheuristics, parallel metaheuristics are intrinsically a kind of hybrid metaheuristics.

In metaheuristics, parallelization is mainly used for the following reasons [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]: speed-up the search, improve the quality of the obtained solutions and improve the robustness and to solve large scale problems.

According to the authors in [3], the parallelization techniques of a "standard" metaheuristic vary depending on whether it is a trajectory-based (single solution) or a population-based metaheuristic.

For trajectory-based metaheuristics, three types of parallelization are often found in the literature:

• Parallel moves model: A master-slave approach is conducted here. Where at the beginning of each iteration, the master duplicates the current solution between distributed nodes. Each solution separately manages their own solution/candidate and the results are then returned to the master. This technique of parallelization does not alter the behavior of the metaheuristic. A relatively recent example of this hybridization genre is [START_REF] Bożejko | Parallel tabu search algorithm for the hybrid flow shop problem[END_REF].

• Parallel multistart model: This approach of parallelization involves simultaneously launching several trajectory-based methods for computing better and robust solutions. They may be homogeneous or heterogeneous, cooperative or independent, start from the same or different solution(s), and configured with the same or different parameters. An example of this category is [START_REF] Hijaze | An investigation of topologies and migration schemes for asynchronous distributed evolutionary algorithms[END_REF].

• Move acceleration model: Techniques that fit in this category evaluate the quality of each move in a parallel centralized way. This model becomes attractive when the evaluation function can be parallelized as its computationally expensive.

In that case, the function can be regarded as an aggregation of a certain number of partial functions that can be run in parallel. The interested readers are reffered to the work of [START_REF] Chang | A parallel simulated annealing approach to band selection for high-dimensional remote sensing images[END_REF].

Also for population-based metaheuristics, three strategies can transform a "standard" metaheuristic into a parallel one:

• Master-slave model: In this approach, a central processor performs the selection operations while the associated slave processors (workers) run the variation operator and the evaluation of the fitness function. An example is the work of [START_REF] Bullnheimer | Parallelization strategies for the ant system[END_REF].

• Island model: Island (or distributed) model is when the population is partitioned in a small set of subpopulations (islands) in which isolated serial algorithms are executed. Sparse individual exchanges are performed among these islands with the goal of introducing some diversity into the subpopulations. An example of this genre is the work of [2]. In order to design a distributed metaheuristic, one must take several decisions:

topology or logical links between the islands.

migration rate or number of individuals that undergo migration in every exchange.

migration period or number of performed steps in every subpopulation between two successive exchanges.

selection/replacement of the migrants

• Cellular model: In this case, the concept of "neighborhood" is introduced, so that an individual may only interact with its nearby neighbors in the breeding loop.

An example of the concept can be found in [START_REF] Alba | Parallelism and evolutionary algorithms[END_REF].

Admitting that parallel metaheuristics are hybrid by nature, several modifications have been introduced to improve this class of metaheuristics. In [START_REF] Luque | Parallel Hybrid Trajectory Based Metaheuristics for Real-World Problems[END_REF], the authors introduced a new hybrid algorithm combining path relinking with a set of cooperating trajectory based parallel algorithms to yield a new metaheuristic of enhanced search features. In their model, the algorithm do not have to choose between the two solutions, (which is the case in a standard trajectory based algorithm) but generates a new solution with the main features of both solutions. With this aim, they ran path relinking technique to generate some paths using the current solution and the incoming solution as initial points. The generated path provides the parallel technique of a set of candidate solutions to continue the search, and therefore, a selection scheme is needed to chose one. The utilization of this last technique allow to generate a wide set of candidate solutions to continue the search. This set is composed by solutions which include information from the current solution of the subalgorithm and also information from the incoming solution.

The authors have studied different design alternatives such as the several cooperation schema between subalgorithms or different mechanism to select the next solution from the set of solutions generated by path relinking. The results show that their proposed method is more accurate and efficient than the existing one.

In [START_REF] Luque | An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization[END_REF], hybrid models have been proposed in which a two-level approach of parallelization is undertaken. In general, the higher level for parallelization is a coarse-grain implementation (i.e., a set of islands) and each island performs other parallel model such as cellular, master-slave method, or even another distributed method.

Sequential hybrids

With regards to the hybridization purpose, non parallel hybrid algorithms can loosely be divided into two categories [START_REF] Ting | Hybrid metaheuristic algorithms: past, present, and future[END_REF]: Collaborative Hybrids Under this category, all sub-algorithms collaborate to solve the same problem directly; and different sub-algorithms are used in different search stages. The contribution weight of each participating algorithm can be regarded as half and half in the simplest case. A challenging issue in hybrids is to know when to switch to the second algorithm. Some examples on collaborative Hybrids are [START_REF] Ciornei | Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization[END_REF] and [START_REF] Shelokar | Particle swarm and ant colony algorithms hybridized for improved continuous optimization[END_REF].

Integrative Hybrids In this type of hybrids, one primary algorithm is utilized to solve the problem, while another sub-algorithm is applied to tune the parameters for the primary algorithm. In this aspect, one algorithm is regarded as a subordinate, embedded in a master metaheuristic. For this category, the contributing weight of the secondary algorithm is approximately 10 to 20%. This involves incorporation of a manipulating operator from a secondary algorithm into a primary algorithm. For example, many algorithms utilized the mutation operator from GA into PSO, resulted in so called Genetic PSO or Mutated PSO.

Two types of manipulation can be identified for integrative hybrids:

• Full manipulation. The entire population is manipulated at every iteration. Such operation can be integrated inline with the existing source code, usually as a subroutine/subfunction.

• Partial manipulation. In this manipulation, only a portion of the entire population is accelerated using local search methods such as gradient methods. Choosing the right portion and the right candidate to be accelerated pose a great challenge in assuring the success of this hybrid structure Some examples on collaborative Hybrids are [START_REF] Li | A hybrid memetic algorithm for global optimization[END_REF] and [START_REF] Yan | Hybrid Differential Evolution with Convex Mutation[END_REF].

hyper heuristics A hyper-heuristic is an automated methodology for selecting or generating heuristics to solve hard computational search problems [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF]. In hyper-heuristic methods, parameters are selected by a subalgorithm or via a learning mechanism [START_REF] Ting | Hybrid metaheuristic algorithms: past, present, and future[END_REF].

There is an ongoing debate about the nature of hyper-heuristic and whether it can be considered as a kind of hybrid methods. While some scholars adopt this point of view [START_REF] Ting | Hybrid metaheuristic algorithms: past, present, and future[END_REF] and consider it as a collaborative hybrid, others consider that the main difference between metaheuristics and hyper-heuristics is that the search space for metaheuristics is that of the problem solutions, whereas hyper-heuristics always search within a search space of heuristics. Thus, it cannot be as a kind of hybrid metaheuristics . For the sake of completeness we will provide a brief review about hyper-heuristics and we refer the interested readers to the following references [START_REF] Burke | Hyperheuristic approaches for multiobjective optimisation[END_REF], [START_REF] Ryser-Welch | A review of hyper-heuristic frameworks[END_REF], [START_REF] Burke | Hyper-heuristics: A survey of the state of the art[END_REF], [START_REF] Özcan | A comprehensive analysis of hyperheuristics[END_REF], [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF]. One of the key motivations for hyper heuristics, is to raise the level of generality at which optimisation systems can operate. Hyper-heuristics are broadly concerned with intelligently choosing the right heuristic or algorithm in a given situation. According to [START_REF] Burke | A classification of hyper-heuristic approaches[END_REF], a hyper-heuristic can be classified with respect to the nature of the heuristic search space, or with respect to the source of feedback during learning. These two dimensions yields the following classification:

• With respect to the nature of the heuristics search space:

• heuristic selection methodologies for choosing or selecting existing heuristics.

• heuristic generation methodologies for generating new heuristics from the components of existing ones.

According to the source of the feedback during learning, one can distinguish between online and offline learning. In online learning hyper-heuristics, the learning takes place while the algorithm is solving an instance of a problem, whereas in offline learning hyper-heuristics, the idea is to gather knowledge in the form of rules or programs, from a set of training instances, that will hopefully generalize to solving unseen instances.

• The different sources of feedback information:

-Online learning hyper-heuristics Learn whilst solving a given instance of a problem.

-Offline learning hyper-heuristics Learn, from a set of training instances, a method that would generalize to unseen instances -No-learning hyper-heuristics Do not use feedback from the search process

Hybrid multi-objective optimization

While the previous paragraphs may contain some mono-objective optimization hybrids, this section is dedicated to focus on the hybridization in multi-objective optimization.

An "obvious" preliminary observation is that a lot of hybrid metaheuristics in this field were based on the cooperation between trajectory-based (or single solution based) metaheuristics and population based metaheuristics. The cooperation between these two different approaches for multi-objective optimization is justified by the fact that these two approaches are complementary to each other. Trajectory-based metaheuristics are well known for their capacity to intensify the search; they are able to converge aggressively towards good solutions, but they need to be guided be guided along the non-dominated frontier. On the other hand, population-based approaches are good explorers of the search space; they are very well suited to maintain a diversified population of solutions along the non-dominated frontier, but often converge too slowly to the non-dominated frontier.

Naturally, methods that try to take advantage of these features by combining components from both approaches, represent often a good trade.

A review on hybrid metaheuristics for multi-objective combinatorial optimization was presented in [START_REF] Ehrgott | Hybrid metaheuristics for multi-objective combinatorial optimization[END_REF]. The authors talked about four types of hybridization here:

• Hybridization to make a method more aggressive.

• Hybridization to drive a method.

• Hybridization for exploring complementary strengths.

• Hybridization with other techniques.

They also provided examples for each class of hybridization.

In [START_REF] Purshouse | A review of hybrid evolutionary multiple criteria decision making methods[END_REF], the authors reviewed techniques which have combined evolutionary multiobjective optimization and multiple criteria decision making. Three classes of hybrid techniques were presented: a posteriori, a priori, and interactive. They also included methods used to model the decision-makers preferences and example algorithms for each category. At the end, the authors identified eight key challenges for hybrid approaches and argued that these challenges should be priority research themes for new work blending evolutionary multi-objective optimization and multiple criteria decision making methods.

The authors in [START_REF] Mashwani | Hybrid Multiobjective Evolutionary Algorithms: A Survey of the State of-the-art[END_REF], gave a survey on hybrid multi-objective evolutionary algorithms. In their work, they talked about four hybridization approaches. First, they treated the subject of hybridization between multi-objective evolutionary algorithms and local search. Than, they provided some hybrid versions of well known multi-objective evolutionary algorithms based on Pareto Dominance. They dedicated a whole section to talk about the enhanced versions of multiobjective evolutionary algorithm based on decomposition paradigm. Finally, they presented multi-method search approaches.

An interesting recent work is that of [START_REF] Talbi | Hybrid Metaheuristics for Multi-objective Optimization[END_REF], where the author tackled three different types of combinations to solve multi-objective optimization problems, namely:

• Combining metaheuristics with (complementary) metaheuristics.

• Combining metaheuristics with exact methods from mathematical programming approaches.

• Combining metaheuristics with machine learning and data mining techniques.

In order to illustrate each type of these combinations, the same taxonomy mentioned in paragraph 2.3.1 and that was introduced [START_REF] Talbi | A taxonomy of hybrid metaheuristics[END_REF], was recalled. The goal of the taxonomy was to provide a mechanism to allow comparison of hybrid algorithms in a qualitative way. That approach resulted in four classes of hybrid metaheuristics for each type of the combinations above. Hereunder, we enumerate these classes with some examples for each one.

Combining metaheuristics with (complementary) metaheuristics

• Low-level relay hybrids This rare class of hybrids represents multi-objective hybrid metaheuristics in which a given metaheuristic is embedded into a single solution based metaheuristic. One example cited by the author is that of [START_REF] Burke | Hyperheuristic approaches for multiobjective optimisation[END_REF] where a multi-objective tabu search hyperheuristic may be used to optimize the use of different solution based metaheuristics.

• Low-level teamwork hybrids This class of hybridization represents an active and very successful type of hybridization. It is inspired by the "obvious" observation we made reference to earlier in this paragragh. It consists of population based metaheuristics integrating single-solution based metaheuristics. An examples for this type of hybrids is the work in [START_REF] Iqbal | Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees[END_REF], where the authors solved the multi-objective Vehicle Routing Problem with Soft Time Windows (VRPSTW). The total traveling distance, number of window violations and number of required vehicles were minimized while capacity and time window constraints were met. The metaheuristic used to solve the problem was a hybrid multi-objective Artificial Bee Colony algorithm. Where the authors have extended the exploitation performed by employed and onlooker bees for neighborhood candidate selection into two steps: a random swapping followed by a random permutation.

• High-level relay hybrids In This class of hybrids, self-contained multiobjective metaheuristics are executed in a sequence. A classical example is the application of an intensification strategy like a solution based metaheuristic on the approximation of the Pareto set obtained by a population based metaheuristic [START_REF] Deb | A hybrid multi-objective evolutionary approach to engineering shape design[END_REF].

• High-level teamwork hybrid It involves several self-contained multi-objective metaheuristics performing a search in parallel and cooperating to find a Pareto set approximation. One example is the work in [START_REF] Delisle | Parallel implementation of an ant colony optimization metaheuristic with OpenMP[END_REF], where the authors presented a shared memory parallel implementation of an Ant Colony Optimization metaheuristic that is applied to an industrial scheduling problem, and showed the main issues that had to be adressed during the parallelization process.

Combining Metaheuristics with Exact Methods

• Combining branch and bound with multi-objective metaheuristics -Metaheuristic to generate an upper bound: At first the multi objective metaheuristic is executed to get a Pareto set approximation. This approximation is considered as a good upper bound approximation for the multi-objective exact algorithm. Hence, many nodes of the search tree can be pruned by the branch and bound algorithm. -Exact algorithm to explore very large neighborhoods: The main idea is to reduce the search space explored by the exact algorithm by pruning nodes when the solution in construction is too far from the initial Pareto solution (obtained using a multi objective metaheuristic). -Exact algorithm to solve subproblems: In this hybrid heuristic approach, the exact multi-objective algorithm solve subproblems which are generated by the multi-objective metaheuristic. A given region of the decision space is explored by the exact algorithm.

• Combining branch and cut with multi-objective metaheuristics For this class, the authors gave an example that combines a mono-objective branch and cut algorithm and a multiobjective metaheuristic to solve the bi-objective covering tour problem. In the hybrid approach, the multi-objective metaheuristic generates a Pareto set approximation, which is used to build subproblems; these subproblems are then solved using the branch and cut algorithm. The branch and cut algorithm first relaxes the integrality conditions on the variables and the connectivity constraints of the integer linear programming model. Integrality is then gradually restored by means of a branch and bound mechanism.

Combining Metaheuristics with Data Mining

In this section, the author talked about combinations of metaheuristics with machine learning and data mining techniques (e.g. feature selection, classification, clustering, association rules) and classified this class of hybrids according to:

• Search operators: This class of hybrids consists of integrating knowledge into search operators. An example can be found in [START_REF] Jourdan | Preliminary investigation of the 'learnable evolution model'for faster/better multiobjective water systems design[END_REF], where a set of rules that describes why some individuals dominate others (positive rules) and why some individuals are dominated by others (negative rules) are extracted using the C4.5 classifier. Offsprings that match the positive rules and do not match the negative rules are generated. The obtained results indicate that those learnable evolution models allow to speedup the search and improve the quality of solutions.

• Parameter setting: This type of hybridization deals with robustness of the algorithm. An operator may give different results while used in a metaheuristic. This motivates the use of adaptive operator probabilities to automate the selection of efficient operators. The adaptation can be done by exploiting information gained, implicitly or explicitly, regarding the current ability of each operator to produce solutions of better quality [START_REF] Tuson | Adapting operator settings in genetic algorithms[END_REF].

• Clustering archives in multi-objective metaheuristics: a classical approach using data mining approaches in the population management of multiobjective metaheuristics is the application of clustering algorithms on the archive. The objective is to produce a set of well diversified representatives Pareto solutions in a bounded archive. An archive is often used to store Pareto solutions and the clustering is then performed to avoid a bias towards a certain region of the search space and to reduce the number of Pareto solutions.

Constraint handling as toolbox for hybridization

The presence of constraints in an optimization problem has been pointed out as one of the sources of difficulties found in real world optimization problems [START_REF] Michalewicz | How to solve it: modern heuristics[END_REF] alongside other problems like huge search spaces, the noise in the objective function(s) and the complexity of the modeling process. Constraints can distract the attention of the search and narrow it down just to the search for a valid or achievable solution. On the other hand, in their original versions, metaheuristics were designed for unconstrained search spaces [START_REF] Back | Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms[END_REF], [START_REF] Engelbrecht | Fundamentals of computational swarm intelligence[END_REF]. This was the main motivation for adding constraint handling techniques to metaheuristics in order to guide the search towards regions with feasible solutions.

In this section we present seven constraint handling techniques that were commonly coupled with metaheuristics. These constraint handling techniques are independent of the metaheuristic at hand. They can be used to solve continuous and mixed variable optimization problems. The purpose of this section is serve these techniques as a toolbox for hybridization. As a matter of fact, various constraint handling methods can be effective during different stages of the search process, depending on several factors such. These factors can be the case where metaheuristics used for optimization were evolutionary algorithms. Furthermore, the work in [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF] presented a review of the literature on techniques for adapting nature inspired algorithms (including evolutionary algorithms among others) to optimization problems with constraints. It addresses this problem by dividing these techniques into: old, current, and futuristic. For older techniques, the authors tried to combine the classifications of approaches that have been introduced in previous surveys on this subject, especially [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] and [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF], in an up-to-date and relatively brief taxonomy.

Then the most representative current techniques for handling constraints were briefly discussed and analyzed. According to the authors, the focus is shifted now towards modifications on the elements of the nature inspired algorithms adopted, and not on the constraint-handling technique itself. At the end, the authors listed and described several research topics that have attracted little attention from researchers and which, according to their point of view, may constitute promising fields for future research.

A recent review is that of [START_REF] Yousefi | A Practical Review on the Application of Constraint Handling Strategies in Evolutionary Computation from an Engineering Point of View[END_REF] which dealt with constraint handling techniques for evolutionary algorithms from the engineering point of view. His approach was to update the techniques of previous reviews without structurally changing their old taxonomies.

In the following, we describe the main techniques of constraint handling for metaheuristics that are found in the literature.

Penalty Functions

The penalty functions were proposed by [START_REF] Courant | Variational methods for the solution of problems of equilibrium and vibrations[END_REF] and later extended by [START_REF] Carroll | The created response surface technique for optimizing nonlinear, restrained systems[END_REF] and [START_REF] Fiacco | Extensions of SUMT for nonlinear programming: equality constraints and extrapolation[END_REF]. In this type of approaches, the optimization problem with constraints is transformed into a problem without constraint by adding penalty terms to the objective functions. In general, the penalty term is determined from the amount of constraint violation of the solution. It can expressed using Equation 2.1.

p(x) = Σ m i=1 r i .max(0, g i (x)) 2 + Σ p j=1 c i .|h j (x)| 2 (2.1)
where p(x) is the penalty term, g i (x) and h i (x) are the inequality and equality constraints functions respectively, r i and c j are positive constants called "penalty factors".

As can be seen from Equation 2.1, the objective is to diminish the fitness of non feasible solutions, in favor of the selection of feasible ones.

Even if their implementation is fairly simple, the penalty functions require careful tuning of the penalty factors to determine the severity of the penalty to be applied. Besides, a good penalty factor value is highly dependent of the problem at hand.

Unlike mathematical programming approaches, where the internal and external penalty functions are employed, metaheuristics are usually focused on external penalty function approaches, because of the assumption that the first generation of a metaheuristic can only contain non feasible solutions.

We present four of the most prominent penalty functions in this paragraph. They can be classified according to their control strategy:

Mapped space Feasible region

Code/Decode • If the penalty coefficients remain constant throughout the search process, the penalty function is called static [START_REF] Morales | A universal eclectic genetic algorithm for constrained optimization[END_REF], [START_REF] Hoffmeister | Problem-independent handling of constraints by use of metric penalty functions[END_REF], [START_REF] Homaifar | Constrained optimization via genetic algorithms[END_REF].

• If the penalty coefficients change with the iteration number, the penalty function is called dynamic [START_REF] Michalewicz | Evolutionary optimization of constrained problems[END_REF], [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF], [START_REF] Joines | On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA's[END_REF].

• In the adaptive penalty functions, informations coming as the search progresses, are added to control the penalty [START_REF] Jadaan | ADAPTIVE PENALTY FUNCTION FOR SOLVING CONSTRAINED EVOLUTIONARY OPTIMIZATION[END_REF], [START_REF] Nanakorn | An adaptive penalty function in genetic algorithms for structural design optimization[END_REF], [START_REF] Crossley | A study of adaptive penalty functions for constrained genetic algorithm-based optimization[END_REF]. An interesting aspect of this approach is that it attempts to avoid getting a population that is entirely feasible or entirely unfeasible.

• For death penalty functions, non feasible individuals are rejected. This method has the disadvantage of not extracting the information from non feasible individuals [START_REF] Coit | Penalty guided genetic search for reliability design optimization[END_REF].

The main problem with penalty functions is that the "ideal" penalty factor to be adopted cannot be known a priori for any problem. If the penalty is adopted too high or too low, problems will occur during the search; Let us take, for example, the case where the optimum is at the limit of the feasible region (which is often the case in engineering problems). If the penalty is too high, metaheuristics will be pushed within the region, very quickly, and will not be able to move towards the boundary of the feasible region. On the other hand, if the penalty is too low, much of the research time will be devoted for exploring the non feasible region because the penalty will be negligible with respect to the objective function.

Despite their well-documented shortcomings, the penalty functions are still widely used and improved in the literature. According to [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF] the most common penalty functions to find in the literature are the adaptive penalty functions used alongside with genetic algorithms as optimization metaheuristics.

Decoding

The decoding strategy usually refers to techniques that create a correspondence (or mapping) from the feasible region of an optimization problem, to a more easy to handle space, where the metaheuristic is known to perform better in the new space Figure 2.2.

An appropriate mapping strategy should have the following characteristics:

• It should be guaranteed that every feasible solution in the original search space is incorporated in the mapped space. Vice versa, every solution in the mapped space should correspond to a unique solution in the original search space.

• The mapping process should be quick.

• Small modifications in the mapped space should lead to small modifications in the original space.

Decoding approaches are theoretically attractive for researchers. But they are rarely used, because their implementation involves a high computational cost. Some good examples on decoding strategy can be found in [START_REF] Kim | Mapping based constraint handling for evolutionary search; thurston's circle packing and grid generation[END_REF], [START_REF] Kim | Riemann mapping constraint handling method for genetic algorithms[END_REF], [START_REF] Koziel | A decoder-based evolutionary algorithm for constrained parameter optimization problems[END_REF], [START_REF] Koziel | Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization[END_REF].

Localization of feasible region boundaries

In real world engineering problems, it is likely that some constraints are active around the optimal points [START_REF] Schoenauer | Evolutionary computation at the edge of feasibility[END_REF], i.e. some optimal points are on the edge of feasibility. The reason for this is that constraints in real-world problems often represent resource limitations. From an optimization point of view, the exploitation of resources, as far as possible, is an asset. Thus, active constraints at good quality solutions are highly probable.

Despite the evidence of this remark, few researchers have focused on the importance of searching within the boundaries of the feasible region. This technique lies within the "Methods based on the preservation of the feasibility of the solutions" class of [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] and the class "Special representations and operators" of [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF]. GENOCOP (Genetic Algorithm for Numerical Optimization for Constrained Optimization) [START_REF] Michalewicz | Genetic algorithms data structures evolution programs[END_REF] was probably the first variant of the genetic algorithm that applies search operators at borders to handle constraints. GENOCOP had three mutations and three crossover operators. One of the mutation operators was a boundary mutation that could generate a random point on the boundary of the feasible area. The experiments showed that the presence of this operator caused a significant improvement for GENOCOP, and enabled it to find an optimum for problems whose optimal solution lies on the edge of the feasible region.

The authors in [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] presented two test cases where the idea was to search only the boundaries of feasible space using an ad hoc initialization procedure and some specific operators were (geometrical crossover for test case 1, and sphere crossover for test case 2). The authors argued that this technique allowed the search to reach the optimum solution in less computational time in comparison to ordinary techniques.

A variant of the evolutionary algorithm for the optimization of a water distribution system has been proposed in [START_REF] Wu | A self-adaptive boundary search genetic algorithm and its application to water distribution systems[END_REF]. The main argument was that the method should be able to use information on the boundaries between the unfeasible and feasible area to be effective in solving the problem of the water distribution system. The proposed approach was based on the change of the penalty factor in order to orient the search towards the boundaries of the feasible search space. The penalty factor was modified as a function of the percentage of feasibility of individuals in the population in such a way that there are always unfeasible solutions in the population. In this case, the crossover can make use of these unfeasible and feasible individuals to generate solutions on the limit of the feasible region.

A recent and interesting technique is found in [START_REF] Bonyadi | On the edge of feasibility: a case study of the particle swarm optimizer[END_REF], which consists of restricting the feasible zone of an optimization problem to its boundary. In the proposed method the thickness of the narrowed boundary is adjustable by a parameter following the routine:

if ((max(ctr) ≤ delta active ))
Generate initial solution end

Where "ctr" is the constraint function and "delta active " is a value the can be increased or decreased based on the desired closeness to the boundaries . The method is extended in a way that is capable of limiting the feasible zones at the boundaries in the case where at least one of the constraints in a given subset of the set of constraints is active while other constraints may or may not be. Another extension deals with the case where all constraints in a given subset are active and the rest can be active or not. The particle swarm optimization algorithm is used as a framework to compare the proposed methods. The results showed that the proposed methods can limit the search at the boundary requested by the user. Thus, they help to effectively locate the optimal solutions on the boundaries of the feasible zone.

Feasibility rules Feasibility rules are the most used techniques to manage the constraints of an optimization problem for a metaheuristic [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF]. They do not impose additional parameters or calculation load. They are simple and flexible which makes them very suitable to be coupled easily with any type of selection mechanism. The basic idea was proposed by Deb [START_REF] Deb | An efficient constraint handling method for genetic algorithms[END_REF]. In his approach, three feasibility criteria were added to a binary tournament selection in a genetic algorithm in the following manner:

1. When comparing two feasible solutions, the one with the best objective function is chosen.

2. When comparing a feasible and an unfeasible solution, the feasible solution is chosen.

3. When we compare two unfeasible solutions, the one with the lowest amount of constraint violation is chosen.

The sum of constraint violation can be expressed in several ways. One of the ways is showed in Equation 2.2.

φ(x) = Σ m i=1 max(0, g i (x)) 2 + Σ p j=1 |h j (x)| 2 (2.2)
where φ(x) is the sum of constraint violation , g i (x) and h i (x) are the inequality and equality constraints functions respectively. The main disadvantage is that, feasibility rules are likely to cause premature convergence. That is mainly due to the fact that this kind of mechanism strongly favors the possible solutions. Thus, if no other mechanism is adopted to preserve diversity (especially paying attention to the need to maintain unfeaisable solutions in the population), this approach will greatly increase the selection pressure [START_REF] Mezura-Montes | A simple multimembered evolution strategy to solve constrained optimization problems[END_REF]. Different constraint handling techniques were inspired by Deb's feasibility rules. For example, a recent study [START_REF] Chehouri | A Constraint-Handling Technique for Genetic Algorithms using a Violation Factor[END_REF] proposed a similar technique were the same feasibility rules were kept, but the comparison was done based on another indicator, called number of violations (NV).

Stochastic ranking Stochastic ranking was initially proposed in [START_REF] Runarsson | Stochastic ranking for constrained evolutionary optimization[END_REF]and [START_REF] Runarsson | Search biases in constrained evolutionary optimization[END_REF]. This technique has been designed to deal with the inherent shortcomings of penalty functions.

In the stochastic ranking, instead of the definition of a penalty factor, a parameter P f defined by the user controls the criterion used for the comparison of unfeasible solutions, either:

• As a function of their sum of constraint violation (Equation 2.2).

• Or based only on their objective function value.

That is, if two adjacent individuals are feasible, the comparison is determined by the objective function; otherwise, the probability of comparing them according to the objective function is P f . Stochastic ranking is a state of the art constraint handling technique [START_REF] Coello Coello | Constraint-handling techniques used with evolutionary algorithms[END_REF]. It uses a bubble-like sorting process to classify the solutions in the population as shown in Algorithm 14. After ranking, m best individuals are chosen as parents for the next generation according to a truncation rate set of ≃ 1/7 [START_REF] Runarsson | Stochastic ranking for constrained evolutionary optimization[END_REF].

Algorithm 14 Stochastic ranking using a bubble-sort-like procedure where λ is the number of individuals in a population, N is the number of sweeps going through the whole population, and φ denotes the constraint violation function.

1: I j = j ∀j ∈ 1, ..., λ 2: for i = 1 to N do 3:

for j = 1 to λ -1 do 4:

u = random(0,1)

5: if (φ(I j ) = φ(I j+1 ) = 0) or (u < P f ) then 6: if f (I j ) > f (I j+1 ) then 7:
Swap((I j ), (I j+1 )) end if 18: end for ε-constraint method The ε-constraint method (not to be confused with ε-constraint [START_REF] Haimes | On a bicriterion formulation of the problems of integrated system identification and system optimization[END_REF] for multi objective optimization method) proposed in [START_REF] Takahama | Constrained optimization by the ε constrained hybrid algorithm of particle swarm optimization and genetic algorithm[END_REF] is one of the most recent constraint handling techniques reported in the literature. This technique transforms a constrained optimization problem into an unconstrained one, by introducing two new operators; firstly < ε according to the Equation 2.3 , then the second operator ≤ ε defined in an equivalent manner.

(f (x 1 ), φ(x 1 )) < ε (f (x 2 ), φ(x 2 )) ⇔ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ f (x 1 ) < f (x 2 ) if φ(x 1 ), φ(x 2 ) ≤ ε f (x 1 ) < f (x 2 ) if φ(x 1 ) = φ(x 2 ) φ(x 1 ) < φ(x 2 ) otherwise (2.3)
Where ε > 0, determines the level of comparison between a pair of solutions x 1 and x 2 with objective function values f (x 1 ) and f (x 2 ) and the sums of constraint violation φ(x 1 ) and φ(x 2 ) defined in Equation 2.2.

As can be seen, if the two solutions compared are feasible, slightly unfeasible (as determined by the ε value), or even if they have the same amount of constraint violation, they are compared with the values of the objective function. Otherwise, they are compared according to their sum of constraint violation.

Therefore, if ε = ∞, the ε comparison works using only the values of the objective function as a comparison criterion. On the other hand, if ε = 0, then the ϕ(x 1 ) and ϕ(x 2 ) comparisons are equivalent to a lexicographic order in which the minimization of constraint violation sums ϕ(x) precedes the minimization of the objective function f (x), in a manner equivalent to the feasibility rules.

The ε-constraint method is an improvement on the previous work of [START_REF] Takahama | Constrained optimization by α constrained genetic algorithm (αGA)[END_REF], where an approach called the α-constraint method was proposed. Comparisons were made then according to α level a similar way to ε-constraint method. However, unlike the value of ε which represents a tolerance related to the constraint violation sum, the value of α is related to the satisfaction level of the constraints of for a given solution.

multi-objective optimization techniques

The use of multi-objective optimization concepts to solve constrained optimization problems is reviewed in [START_REF] Mezura-Montes | Constrained optimization via multiobjective evolutionary algorithms[END_REF]. The basic idea behind such techniques is to handle objective functions and constraints separately. These approaches can be divided to the following groups:

• Techniques which transform a constrained optimization problem into a bi-objective problem. The two objective functions in this case are the original objective function and the sum of constraint violation as indicated in Equation 2.2.

• Techniques which transform a constrained optimization problem into a multiobjective optimization problem, with the original objective function as first function and each constraint as a single objective function.

This kind of approaches is proven to generate an important diversity loss. However, this has not prevented the use of these techniques which are among the most popular constraint-handling techniques [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF]. Both transformations (into a bi or multi-objective problem), have been popular in the literature. However, the use of transformation of a constrained optimization problem into a bi-objective optimization problem has been preferred, with respect to considering each constraint as an independent objective [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF].

Evaluation of hybrids

The evaluation of hybrids, also known as performance assessment of hybrid metaheuristics, is a necessary task that should not be dealt with lightly. If it is conducted properly, the evaluation should give an honest feedback regarding the hybridization choices. However, it is not a trivial task and must be done on a fair basis. A good evaluation is deeply related to the goals defined when designing the hybrid metaheuristic. Indeed, the evaluation might measure the contribution of an hybrid in terms of search time, quality of solutions, robustness of the instances, diversification, intensification, easiness of implementation, innovation using new nature-inspired paradigms, automatic tuning of parameters, and so on.

In this section we present four ways to evaluate a hybrid metaheuristic; namely mertics, computational effort, statistical assessment and robustness.

Metrics

Metrics are a sort of performance indicators that try to asses the quality of solutions in terms of precision. They usually tend to compare the solutions obtained using an hybrid metaheuristic to optimal solutions in case these were known. In the more frequent case, where optimal solutions for a problem are not known a priori, metrics might compare the performance of an hybrid metaheuristic to that of another hybrid, or to a state-of-the-art metaheuristic.

They differ also between single and multi objective optimization. In the case of a hybrid metaheuristic used for single objective optimization, metrics are simply a measure of the distance or the percent deviation of the obtained solution to one of the following solutions [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]:

• Global optimal solution found by an exact algorithm.

• Lower/upper bound solution: For optimization problems where the global optimal solution is not available, tight lower bounds for minimization problems(or upper bounds for maximization problems) may be considered as an alternative to global optimal solutions.

• Best solution found so far in case the global optimal solution is not available.

For multi-objective optimization hybrids, there is no single solution to asses. But rather a set of non dominated solutions called "Pareto Frontier". The number of metrics introduced in this case is much larger than in the case of single objective optimization. Several classifications of metrics for multi-objective optimization can be found in the litterature. Whether it is the classification found in [START_REF] Coello | Advances in multi-objective nature inspired computing[END_REF]:

• Convergence-based metrics: Where a metric is sensed to provide the closeness of the obtained approximation with respect to the true Pareto front.

Examples of this sort of metric are: contribution [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF], generational distance [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithms: classifications, analyses, and new innovations[END_REF], [START_REF] Van Veldhuizen | On measuring multiobjective evolutionary algorithm performance[END_REF].

• Diversity-Based Indicators: Where a metric will provide information about the uniformity of the distribution of the obtained solutions along the Pareto front

Examples of this sort of metric are: spacing [START_REF] Schott | Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization[END_REF], spread [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF] and entropy [START_REF] Farhang-Mehr | Diversity assessment of Pareto optimal solution sets: an entropy approach[END_REF].

• Hybrid Indicators: Where a metric attempts to combine, in a single value, the performance on both, convergence and diversity

Examples of this class of metric are: hypervolume [START_REF] Zitzler | Evolutionary algorithms for multiobjective optimization: Methods and applications[END_REF], and the R-metrics [START_REF] Hansen | Metaheuristics for multiple objective combinatorial optimization[END_REF], [START_REF] Knowles | On metrics for comparing nondominated sets[END_REF].

Or the classification found in [START_REF] Cheng | On the performance metrics of multiobjective optimization[END_REF]:

• Set Based Metrics: Where to comparison between two sets of solutions (the first for example is that of the hybrid metaheuristic, and the second is that of the true Pareto frontier) is done among the solutions, in term of non domination.

Examples of this sort of metric are: outperformance relations [START_REF] Hansen | Evaluating the quality of approximations to the non-dominated set[END_REF], C Measure [START_REF] Zitzler | Evolutionary algorithms for multiobjective optimization: Methods and applications[END_REF].

• Reference Point Based Metrics: Where a reference point is needed to find this metric. In this type of metrics the "goodness" of solutions is measured by a single scalar. These metrics are easy in concept and efficient in calculation, however, these metrics are sensitive to the choice of the reference point.

Examples of this sort of metric are: S Measure [START_REF] Zitzler | Evolutionary algorithms for multiobjective optimization: Methods and applications[END_REF], D Measure [START_REF] Zitzler | Evolutionary algorithms for multiobjective optimization: Methods and applications[END_REF] • True Pareto Front/Set Based Metrics: Where these metrics compare the distribution of Pareto front found by the hybrid search algorithm and the true Pareto front. This kind of metrics is only utilized on benchmark problems, because the true Pareto front is unknown for real-world problems.

Examples of this sort of metric are: Inverted generational distance (IGD) [START_REF] Li | Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II[END_REF] or the Hypervolume difference metric [START_REF] Zhou | Approximating the set of Pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm[END_REF].

Another classification is that of [START_REF] Okabe | A critical survey of performance indices for multi-objective optimisation[END_REF], where the authors distinguished between cardinality-based metrics, accuracy metrics, distribution and spread metrics. They then divided the accuracy metrics into distance-based and volume-based metrics. Obviously, the number of metrics and their classifications are far more exhaustive to be discussed in our review. The interested readers are referred to [START_REF] Knowles | On metrics for comparing nondominated sets[END_REF], [START_REF] Hansen | Metaheuristics for multiple objective combinatorial optimization[END_REF], [START_REF] Zitzler | Performance assessment of multiobjective optimizers: an analysis and review[END_REF] and [START_REF] Riquelme | Performance metrics in multiobjective optimization[END_REF] for more details. A a matter of fact, we are going to restrict the discussions in this paragraph to some state-of-the-art metrics that can be used to evaluate hybrid metaheuristics.

In a recent study [START_REF] Riquelme | Performance metrics in multiobjective optimization[END_REF], an extensive review on the performance metrics multi-objective evolutionary algorithms was presented, based on the research articles published in a specialized event: Evolutionary Multi-criterion Optimization conference (EMO). The authors revealed all the performance metrics used by the EMO community during 8 years, from 2005 to 2013. The study included 54 metrics. They found some interesting results:

• the hypervolume (HV) is the preferred metric among the research community.

In fact, hypervolume was the most used metric beyond the classification method chosen.

• Generational distance (GD) and inverted generational distance (IGD) are the most used metrics, with regard to convergence metrics. IGD is clearly getting more acceptance, while GD is decreasing in usage.

• The spread (∆) was the most accepted diversity metric, with regard to diversity metrics. However, in the last years, the research community has not shown interest in measuring only the diversity of solutions anymore, decreasing the relevance of this metric.

• HV and IGD are the metrics that show a tendency to be used more in the future with respect to other metrics. Additionally, the regression line for IGD indicates that this metric is experimenting a significant growth in usage.

• In the following years, hypervolume may tend to stop its growth in citations given the rise of many-objective problems where HV is not suitable because of its exponential computational complexity.

For the rest of this paragraph, we will provide a brief review on the hypervolume metric(HV), the generational distance (GD), the inverted generational distance (IGD) metrics and the spread (∆) metric.

Hypervolume Based on the conclusions of [START_REF] Riquelme | Performance metrics in multiobjective optimization[END_REF], the hypervolume metric [START_REF] Zitzler | Evolutionary algorithms for multiobjective optimization: Methods and applications[END_REF] is preferred by the research community. This might be due to the fact that it captures in a single scalar both the closeness of the solutions to the optimal set and, to some extent, the spread of the solutions across objective space. The hypervolume may be classed as a volume based metric and a reference point based metric. The hypervolume is a measure of how much the objective space is weakly dominated by a given nondominated set. i.e., it measures the size of the portion of objective space that is dominated by these solutions collectively [START_REF] Cheng | On the performance metrics of multiobjective optimization[END_REF]. By definition it represents the volume in objective function space covered by the nondominated set of solutions Figure 2.3. In other words, HV is the union of the hypercuboids (bounded by the reference point and the non dominated set) Also, it is defined relative to an "anti-optimal" reference point R , which can be the worst possible point in objective function space. This point is usually not known and has to be chosen carefully [START_REF] Knowles | On metrics for comparing nondominated sets[END_REF], as it's choice might affect the ordering of the nondominated sets. The larger the hypervolume is, the wider is the range of Pareto optimal solutions. Therefore, hypervolume has to be maximized. Also, it has been proved that hypervolume is maximized if and only if the set of solutions contains only Pareto optima [START_REF] Fleischer | The measure of Pareto optima applications to multi-objective metaheuristics[END_REF]. Some disadvantages for HV are:

• It is higly dependent of the choice of reference point.

• Hypervolume is expensive to calculate, an approach needs to be designed to approximate it within a reasonable error [START_REF] While | A faster algorithm for calculating hypervolume[END_REF].

• Extreme points play an important role than points in the middle of the Pareto front [START_REF] Cheng | On the performance metrics of multiobjective optimization[END_REF].

generational distance Generational distance (GD) [START_REF] Van Veldhuizen | Multiobjective evolutionary algorithm research: A history and analysis[END_REF] requires prior knowledge of the true optimal Pareto front. It computes the average distance from the approximation (obtained by a hybrid metaheuristic) to the true Pareto front of the problem. Assume that F is the set of non dominated solutions found using a hybrid metaheuristic, and F * is the true Pareto front. In the case of a double objective optimization problem, GD is defined as follows: Where n is the number of solutions in F and d is the euclidean distance in objective function space between solution of F and the nearest member of F * Due to the non-negativity of norms, GD is also non-negative, GD ≥ 0 for all finite sets F and F * . However a value of GD = 0 indicates that all the generated elements are in the Pareto front.

GD = √ ∑ n i=1 d 2
Another variant for the GD is the inverted generational distance (IGD), that is, for a double objective optimization problem, defined as follows:

IGD = √ ∑ n * i=1 d 2 i n *
Where n * is the number of solutions in F * . Some non ideal points for these metrics is that they do not provide informations regarding the diversity of solutions, also the number of solutions in the sets should be large enough to obtain an accurate result, and the non dominated frontier should be known a priori.

Spread

The spread ∆ was introduced by [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF].It includes information about both uniformity and spread. The formulation of this metric for a bi-objective optimization problem is:

∆ = d f + d l + Σ n-1 i=1 |d i -d| d f + d l + (n -1) d
where d f and d l are the Euclidian distances between the extreme solutions in the non dominated set obtained using a hybrid metaheuristic and the Pareto front, n is the number of solutions in the non dominated, d is the average of all distance d i , where i ∈ [1, n -1]. The drawback ∆ is that it works only for 2 objective problems and do not provide informations regarding the convergence.

Computational effort

The quantification of computational effort used by a hybrid metaheuristic to get to optimality, is a good way to asses the effectiveness of hybridization.

In order to do so, the meaning of the computation time must be clearly specified: CPU time or wall clock time, with or without input/output and preprocessing/post processing time [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]. Also the computer characteristics (e.g, operating systems, processor, memory) should be indicated for each trial, since they have a big impact on the efficiency of hybrid metaheuristic.

On the other hand, not all computational effort indicators have to be dependant of computer systems. Another way to asses computational effort is the number of objective function evaluations or number of iterations. This approach is used for time-intensive and constant objective functionsm, but it may be problematic for problems where the evaluation cost is low compared to the rest of the metaheuristics or is not time constant [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]. However, one should pay attention that hybrids usually use a higher number of iterations (especially sequential hybrids) than original metaheuristics. This observation should be taken into account in order to make a fair comparison. In the case of two sequential metaheuristics, one possible solution for this dilemma is to consider the hybrid algorithm as a combination of two cycles instead of one in the convergence graph [START_REF] Ting | Hybrid metaheuristic algorithms: past, present, and future[END_REF].

Statistical assessment

Once the experimental results for the new hybrid metaheuristic are obtained for different indicators, statistical tests can performed to estimate the confidence of the results to be scientifically valid (i.e., determining whether an obtained conclusion is due to a sampling error) [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]. In order to perform a statistical assessment of the results, the first step is to collect revealing statistics on each performance measure adopted, such as the mean, the variance and the median. A usuall way to present these descriptive statistics is to use a box-plot and to present side-by-side box-plots of the different algorithms to be compared [START_REF] Coello | Advances in multi-objective nature inspired computing[END_REF]. Then, different statistical tests may be carried out to analyze and compare the hybrid metaheuristics. In many occasions, Wilcoxon test has been carried out to test the hybridization of a metaheuristic. The Wilcoxon test (also called the Wilcoxon signed rank sum test) is a non-parametric test, statistical hypothesis test used when comparing two related, non-normally distributed samples, or repeated measurements on a single sample to assess whether their population mean ranks differ (i.e. it calculates the difference between each set of pairs and analyzes these differences) For example, a study of the synergy relationships provided by some hybrid approaches was presented in [START_REF] Rodriguez | Hybrid metaheuristics based on evolutionary algorithms and simulated annealing: taxonomy, comparison, and synergy test[END_REF]. It applied the Wilcoxon test with p -value = 0.05, and analyzed the data from repeated-measures with two conditions R + and R -,where the values of R + are associated to the hybrid metaheuristic and those of R -are associated to the non hybrid metaheuristic. Wilcoxon test was also used to evaluate hybrid metaheuristics in [START_REF] Chen | A hybrid metaheuristic approach for the capacitated arc routing problem[END_REF], [START_REF] Wu | A hybrid metaheuristic method for the maximum diversity problem[END_REF], [START_REF] Rodriguez | Hybrid metaheuristics based on evolutionary algorithms and simulated annealing: taxonomy, comparison, and synergy test[END_REF] among other references.

Evaluation of hybrids 85

While Wilcoxon test is used for non-normally distributed samples, the most widely used test, under normality conditions, is the paired t-test [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF]. Kolmogorov-Smirnov test can be performed to check whether the obtained results follow a normal (Gaussian) distribution.

Moreover, the authors in [START_REF] Coello | Advances in multi-objective nature inspired computing[END_REF], make the difference between two categories of statistical tests, depending on their goal:

• Comparison of Dominance Ranks.

• Comparison of Indicators: This can be done in two possible ways:

-By using a single indicator.

-By using a set of indicators.

Robustness

A metaheuristic is generally characterized by several runs, with random operators and different initial which may cause the fluctuation of solution results. Thus, enhancing the stability of a hybrid metaheuristic becomes quite important. In general, there is no single common definition for robustness. One acceptable definition found in [START_REF] Montgomery | Design and analysis of experiments[END_REF] states that the lower the variability of the obtained solutions the better the robustness. For a hybrid metaheuristic, robustness should also measure the performance of the algorithms according to different types of input instances and/or problems. The metaheuristic should be able to perform well on a large variety of instances and/or problems using the same parameters. It may also be related to the average/deviation behavior of the algorithm over different runs of the algorithm on the same instance. [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF].

Proposition for hybrid algorithms

Outline of the current chapter In this chapter, we apply the principles of hybridization and evaluation of hybrids found in chapter 2 to the three dimensioning optimization problems (plate coupling, bearing and gear train) described in chapter 1.

The first approach was to alter five "traditional" meta heuristics in order to tackle these three mixed variables optimization problems along with their constraints. Then, based on the knowledge gained from the first approach, a new hybridization between metaheuristics and branch and bound was introduced and tested on the three optimization problems.

The results of the two approaches were analyzed and compared.

Adapting meta heuristics to handle constraints

"Traditional" metaheuristics are not able, by nature, to handle mixed variables constrained problems. Alterations that were described in paragraph 2.2.2 were applied to handle the mixed variable nature of the problem, while alterations in paragraph 2.3.4 were applied 88 CHAPTER 3. Proposition for hybrid algorithms to handle the constraints. For the mixed variables, a rounding routine was conducted after the initialization of solutions and after each solution update. The update here is referred to whatever modification or "perturbation" made on the current solutions in the hope to find better ones. A perturbation can be the crossover and mutation in genetic algorithms or the walk in other algorithms for example. As for the constraints, they were handled using two constraint handling techniques:

1. The penalty function: Where the objective functions are changed by adding penalties using equation 2.1.

2. The use of penalty function along with the localization of feasible region boundaries method (described in paragraph 2.3.4.1). The localization of feasible region boundaries was used in the following manner; During the initialization, only solutions close to the boundaries are allowed.

The five traditional algorithms were NSGA2 (algorithm 7), MOPSO (algorithm 8) Cucko search(algorithm 10), Bat algorithm(algorithm 9) and firefly algorithm (algorithm11). These well known metaheuristics to the combinatorial optimization scientific society, were conducted five times for each problem using the first constraint handling technique, then another five times using the second one. Then from each five times is extracted the best, average and worst attempt for each algorithm (to compensate the stochastic aspect of metaheuristics). The input parameters used for each metaheuristic are illustrated in table 3.1. They are the exact same parameters for the three optimization problems. The parameters that were unique for each type of problems were the penalty factor p in equation2.1 (p = 0.001 for the plate coupling problem, p = 0.0001 for the bearing problem, p = 0.1 for the gear train problem). The delta active parameter described in 2.3.4.1 and used in the second constraint handling approach also differs according to the problem at hand ((delta active = 0.2 for the plate coupling problem, delta active = 0.25 for the bearing problem, delta active = 0.4 for the gear train problem)).

To evaluate the efficiency of the hybridization and rank the attempts, four evaluation criteria were adopted, taking in consideration that the true Pareto front is known in our case (for the three problems):

1. The generational distance GD (section 2.4.1), that compares the average distance between the true Pareto front and the hybrid one. Therefore the lower the value of GD, the better the quality of the solution is.

2. The spread ∆ (section 2.4.1), that evaluates the distribution across the Pareto front. Therefore the higher the value of ∆, the better the quality of the solution is.

3. The percentage of intersection between the true Pareto front and the hybrid one.

It is calculated as the percentage solutions in the hybrid front that are overlapping other solutions on the true front (with a precision 3 digits after the decimal point).

3.1. Adapting meta heuristics to handle constraints 89 4. The time until convergence, which represent the time consumed by the algorithm until the convergence.

To determine the best solution, one has to consider these four criteria into account (and not separately). For example, a small percentage of intersection does not mean a bad solution, as the hybrid front can be close but not overlapping the true front. Instead, in addition the percentage, both GD and ∆ should be considered to get a clear insight on the quality of the solution. The convergence time is considered a second degree criterion that reflects the effectiveness of algorithm's execution and not it's results. This criteria will come handy in section3.2.

Our approach was to consider GD the essential criterion in case of a significant superiority of a Pareto front, i.e. if the values of GD are relatively different, the front with the smallest GD is considered to be better. While if the values of GD are relatively close, the iteration with the greatest ∆ is considered to be better. The percentage of intersection between the true front and the experimental one is a verification criteria that helped us check if GD and ∆ are well representing the effectiveness of an algorithm.

NSGAII

Results analysis

By comparing all the graphs, one can safely assume that the traditional metaheuristics were unable to solve the three optimization problem. Even in the case of best iteration, not all Pareto solutions were found by the metaheuristics. In the following, we conduct a comparison to determine the best solution for each optimization problem. Then another comparison will determine the best constraint handling technique for each problem.

Comparison between different metaheuristics

To analyze the results and determine the best metaheuristic for each optimization problem, we compared the best metaheuristics for each problem according to GD and ∆. We did that for both constraint handling techniques and on three levels (best best, best average, best worst). The results were gathered in table 3 • NSGAII is the overall best metaheuristic for the second problem (5 occurrences).

• NSGAII is the overall best metaheuristic for the third problem (5 occurrences).

Comparison between constraint handling techniques

To determine the best constraint handling techniques for each optimization problem, a comparison between the results in section 3.1.1 and the results in section 3.1.2 is conducted for each optimization problem according the three criterion; namely GD, ∆ and the time until convergence. The results are found in table 3.11 for the first problem, table 3.12 for the second problem and table three for the third 3.13 one. For each problem, the overall best constraint handling technique is the one with most occurrences in the corresponding table. From that we get:

• The second constraint handling techniques, nicknamed "boundary" is the overall best technique for the first problem (26 occurrences).

• "Boundary" technique is the overall best technique for the first problem (26 occurrences).

• "Boundary" technique is the overall best technique for the first problem (23 occurrences).

The need for hybridization

Even with use of the best metaheuristics for the three optimization problems (see subsection 3.1.3.1) and the best constraint handling technique for these problems (see subsection 3.1.3.2),the calculated Pareto front is still far from being a good solution. The low percentage of intersection of solutions between the true front and the calculated one for the three problems can prove this assumption. Thus, came into view the need for a better approach to solve the problems. In the next section we present an approach based on the hybridization between the best metaheuristic for the problems and an exact method (Banch & bound).

Hybridizing meta heuristics and branch & bound

The problems of optimization with mixed variables introduce a combinatorial aspect insofar as one can bring them back to the resolution of a finite number of problem of optimization in continuous variables. In this case, an efficient technique allowing to enumerate this set of optimization problem in continuous variables, is of interest to the extent that this enumeration can be realized in a reasonable time (that depends on the complexity of the algorithm).

Based on the review of [START_REF] Przybylski | Multi-objective branch and bound[END_REF] mentioned in II, Branch and bound algorithms whose principle could be summed up as "divide and conquer", are synthesized around the following 4 basic elements:

1. A separation procedure that makes it possible to split all the solutions into subsets, while ensuring that the union of the subsets remains equal to the complete set of solutions.

2. The definition and update of an approximation of one or more solutions solutions.

3. An evaluation procedure for a subset that allows to calculate a lower bound for this subset.

4.

A procedure for choosing the next subset to separate.

The authors of this review also report that the definition of an approximation of the optimal solution and the evaluation procedure can be deduced from the nature of the problem to be treated. On the other hand, the choice of a separation technique and of the next subsets to be separated does not belong to any general approach and must be established empirically by experimenting several separation techniques on benchmarks of standard problems.

Our proposal is bascially inspired by [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] with two with some distinctions that will be discussed in the following.

Hybrid's explanation throughout a literature test problem

A literature test problem (P 1 ) is introduced to illustrate the principles of the algorithm "Branch and Bound". The problem is taken from [START_REF] Mela | Algorithm for generating the Pareto optimal set of multiobjective nonlinear mixed-integer optimization problems[END_REF]:

Initial formulation: This problem of bi-objective optimization in mixed variable proposed by [START_REF] Mela | Algorithm for generating the Pareto optimal set of multiobjective nonlinear mixed-integer optimization problems[END_REF] makes it 110 CHAPTER 3. Proposition for hybrid algorithms possible to illustrate the principles of sub-problems.

P Mela : ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Minimize f (x, y) = [f 1 (x, y), f 2 (x, y)] With : f 1 (x, y) = 1 2 [x y] ⊤ G [ x y ] + c 1⊤ [ x y ] f 2 (x, y) = c 2⊤ [ x y ]
With :

⎧ ⎪ ⎨ ⎪ ⎩ x ∈ R 2 × [-1, 1] 2 y ∈ Z 8 × [0, 1] 8 f (x, y) ∈ R 2
(3.1) This is a problem with no constraint function, with 2 continuous variables x = [x 1 , x 2 ], each belonging to the interval [-1, 1] and 8 integer variables with binary values y = [y 1 , . . . , y 8 ] with y j = {0, 1}, j = 0, . . . , 8. We proposed to modify this problem in order to have a wider integer value range for each integer variable, to illustrate the principles of separations. So the following variables were changed:

z l = y j + 2 y j+1 with : j = 2l
So that for y j = {0, 1}, j = 0, . . . , 8 we have z l = {0, 1, 2, 3}, l = 0, . . . , 3, so just convert 4 the integer values of z l = {0, 1, 2, 3} into binary to get the values of y j = {0, 1}, j = 0, . . . , 8. The figure 3.7 shows the domain of the solutions in the space of the objective functions. For this problem we can determine the 7 configurations of the integer variables z l which contains the Pareto front: z * = {1, 2, 0, 2} , {2, 0, 0, 0} , {2, 0, 0, 2} , {2, 2, 0, 2} , . . . {3, 0, 0, 0} , {3, 0, 0, 2} , {3, 2, 0, 2} .

(3.2)

Sub-problems

The P MO-MINLP problem is a complex and expensive problem to solve, the general principle is to solve several simpler problems instead. The proposed division is that of [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF], it consists in considering two different "sub-problems":

1. A single objective optimization problem with mixed variables, where each of the objective functions of the problem P MO-MINLP will be independently minimized.

2. A multi-objective problem with continuous variables considering that integer variables have fixed values.

Sub-problem with single objective in mixed variables

From P MO-MINLP this problem will be written as follows;

P MINLP ( le , ūe ) :

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Minimize f k (x, y), k ∈ [1, . . . , p] Under the contraints c j (x, y) ≤ 0 j = 1 . . . m c j (x, y) = 0 j = m + 1 . . . m + l l c ≤ x ≤ u c le ≤ y ≤ ūe with : ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ x, l c , u c ∈ R nc y, le , ūe ∈ Z ne f (x, y) ∈ R p c j (x, y) ∈ R
Note that this single-objective problem is defined for a particular value of the lower bounds le and upper bounds ūe integer variables. To "evaluate" the problem P MO-MINLP ( le , ūe ) we will determine the p minimums (

x * k , y * k ) of functions f k (x, y) for k ∈ [1, . . . , p].
Some reminders of classic definitions, to unify the notations, in the multi-objective problems [START_REF] Miettinen | Nonlinear Multiobjective Optimization[END_REF]:

• The p anchor points of the Pareto front, denoted P * k ∈ R p , corresponding to the Pareto front extremums, such as:

P * 1 = { f 1 (x * 1 , y * 1 ) , . . . , f k (x * 1 , y * 1 ), . . . , f k (x * 1 , y * 1 )
} . . .

P * k = { f 1 (x * k , y * k ), . . . , f k (x * k , y * k ) , . . . , f p (x * k , y * k ) } . . . P * p = { f 1 (x * p , y * p ), . . . , f k (x * p , y * p ), . . . , f p (x * p , y * p ) }
• The point called "Ideal", P * I ∈ R p corresponding to the minimum of each of the optimization criteria such as:

P * I = { min k {f 1 (x * k , y * k )} , . . . , min k {f p (x * k , y * k )} } •
The "Nadir" point, P * N , corresponding to the maximums of each of the optimization criteria such as:

P * N = { max k {f 1 (x * k , y * k )} , . . . , max k {f p (x * k , y * k )} }
Here we minimize each objective function f k (x), k = {1, . . . , p} independently of the others, under the original constraints of the problem P MO-MINLP . The problem P MINLP ( le , ūe ) is a priori easier to solve than the original problem P MO-MINLP and there are several algorithms for it. Among them are Note here that the optimization problem P MINLP ( le , ūe ) must be able to be solved whatever the value of the bounds le ≥ l e et ūe ≤ u e .

For example, for the problem example P Mela , if we successively minimize f 1 (x, z) and then f 2 (x, z) with the original bounds on integer variables z l , l = 0, . . . , 3 l e = {0, 0, 0, 0} and u e = {3, 3, 3, 3} we get the situation of the figure 3.8, and thus the anchor points of the Pareto Front of the original problem P Mela . We also obtain the point "Ideal" and the point of "Nadir" of this problem.

Multi-objective problems with continuous variables

This multi-objective problem in continuous variables is obtained from the general problem P MO-MINLP by setting the n e integer variables assuming thaty = ȳ, we'll note P MO-NLP (ȳ) 114 CHAPTER 3. Proposition for hybrid algorithms that can be written:

P MO-NLP (ȳ) : ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Minimize f (x, ȳ) = [f 1 (x, ȳ), . . . , f p (x, ȳ)] Under the constraints c j (x, ȳ) ≤ 0 j = 1 . . . m c j (x, bmȳ) = 0 j = m + 1 . . . m + l l c ≤ x ≤ u c ȳ ∈ [l e , u e ] × Z ne with : ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ x, l c , u c ∈ R nc ȳ, l e , u e ∈ Z ne f (x, ȳ) ∈ R p c j (x, ȳ) ∈ R
There is therefore a finite number of sub-problems of the type P MO-NLP (ȳ) from the problem P MO-MINLP . This number depends on the number of possible combinations of all admissible values of integer variables. For example, with n e integer variables, each admitting 10 values, there would be 10 ne combinations so n Conf = 10 ne "configurations" of the problem P MO-NLP . In general, with n e integer variables and n vu allowable values for each integer variables we have:

n Conf = u=ne ∏ u=1 n vu
This problem P MO-NLP (ȳ) is easier to solve than the original problem P MO-MINLP . There are many algorithms recognized as effective in the literature such as: evolutionary meta-heuristics, gradient-based deterministic algorithms like NBI, or "ε constrained" and to the extent that the problem P MO-NLP is convex the aggregation techniques to bring P MO-NLP to a non-objective problem [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF].

For example, in the case of the P Mela problem, with integer variable vectors z1 = {1, 2, 2, 1} and z2 = {3, 2, 2, 2}, we get the two configurations of the figure 3.10. Of course, with ȳ running in the space of n conf = 4 4 = 256 configurations, all combinations would be explored, and one could identify the final Pareto front, keeping only the dominant solutions.

Branching and subsets

To solve P MO-MINLP a trivial method would be to enumerate all possible configurations of P MO-NLP , to solve each of these sub-problems and finally retain only Pareto's solutions. This technique is applicable when the number of configurations is relatively small so for spaces of integer variables rather small, on the other hand the computation time increases prohibitively when the combinatorial space of the integer variables is large, the growth being exponential with respect to numbers of integer variables.

The separation principle must therefore allow us to share the full space of n conf combinations in smaller sub-spaces. As suggested in [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] the sub-space splitting will be done by acting on the lower bounds l e and higher u e integer variables. We will thus have two types of sub-spaces of combinations:

• Those for which le = ūe , which will be associated with a problem of the type P MO-NLP (ȳ) with ȳ = le = ūe .

• Those for which le < ūe ,which will be associated with a problem of the type P MINLP ( le , ūe ).

At the risk of not exploring the entire space of combinations (and therefore solutions), the principle of branching or separation must respect the following rule:

The union of all subspaces must be equal to the complete space ofn conf combinations of the problem P MO-MINLP . In the following, to represent the progression of these separations during the iterations of the algorithm we associate with each subspecies of combinations a node of a tree (example of tree in the figure 3.11). The top of the tree, the root node, representing the complete space of n conf combinations, the leaves of the tree, the terminal nodes, representing the subspaces of cardinality combinations 1. These nodes will be associated with problems of the type P MO-NLP (ȳ). We propose to implement two principles of separation by modifying the lower and upper bounds l e et u e of the integer variables. 1. A principle, which we will call "Branching by integers", which consists in choosing an integer variable, such that the values of its lower and higher bounds are different.

We then create as many intervals [(l e ) s , (u e ) s , ] as values integers between the lower and upper bounds of the variable to be separated. This principle is illustrated by the figure 3.12. The complete exploration of the tree would then create n nodes nodes in this tree with:

n nodes = 1 + in=ne ∑ in=1 ( u=in ∏ u=1 n vu ) (3.3)
Note that n nodes depends on the order of the separations of the n e integer variables, and that n nodes is maximal when the order of separation corresponds to that of the decreasing order of the number of integer values allowed by integer variables (i.e. we first branch the integer variable which admits the largest number n vu of integer values and second the next one, etc.).

l e u e 0 3 1 2 2 3 2 3 (l e ) 1 (u e ) 2 0 0 1 2 2 3 2 3 (l e ) 2 (u e ) 3 1 1 1 2 2 3 2 3 (l e ) 3 (u e ) 3 2 2 1 2 2 3 2 3 (l e ) 4 (u e ) 4 3 3 1 2 2 3 2 3
Figure 3.12 -Illustration on the problem P Mela Branching by integer on the 1st integer variable.

2.

A principle, which we will call "Branching by anchor points", which consists in using the information provided by the evaluation of the current node using the anchor points of the Pareto front calculated via the minimization of the functions objectives f k (x, y) , k = {1, . . . , p}. With p objective functions we thus obtain at most p anchor points from the Pareto Front. By choosing a variable for which the lower and upper bounds are different, we can create p + 1 intervals [(l e ) s , (u e ) s ].

We can estimate the total number of nodes n nodes with this separation principle, assuming we create at most p + 1 "child" nodes from a "father" node ", until the number of" child "nodes is equal to the number of" leaves "of the tree. We deduce that

n nodes = 1 + in=nsep ∑ in=1 (p + 1) in avec n sep = ⌈ 1 ln(p + 1) ln ( u=ne ∏ u=1 n vu )⌉ (3.4
)

l e P 1 P 2 u e 1 2 3 3 0 1 2 3 0 1 3 3 0 0 3 3 (l e ) 1 . . (u e ) 1 1 . . 3 0 . . 1 0 . . 3 0 . . 3 (l e ) 2 . . (u e ) 2 1 . . 3 2 . . 2 0 . . 3 0 . . 3 (l e ) 3 . . (u e ) 3 1 . . 3 3 . . 3 0 . . 3 0 . . 3
Figure 3.13 -Illustration for the problem P Mela Branching by anchor on the second variable. Note, the "sliding" of the limits of the intervals to avoid "duplicates": the 3 intervals [0, 1], [START_REF] Abramson | Mesh adaptive direct search algorithms for mixed variable optimization[END_REF]2] and [2,3] become [0, 1] , [2,2] and [3,3].

Subset evaluation

In branch and bound algorithms applied to single-objective problems, the evaluation consists in determining a lower bound of the optimum of the subset that is evaluated. The closer this lower bound is to the optimum, the better the evaluation. The assessment is qualified "exact" when it is equal to the optimum. To deal with problems in mixed or integer variables, the common practice in the literature is to relax restrictions due to integer variables and to solve an optimization problem in continuous variables to evaluate the subset. In this case, we obtain a solution necessarily less than or equal to the solution of the problem in mixed or integer variables, easier to calculate, which is also a minor of the optimum. In our context, that of the P MO-MINLP problems we must take into account the following particularities:

• There are two types of subsets to evaluate: problemes of type P MO-NLP (ȳ) associated with leaf nodes and problems of type P MINLP ( le , ūe ) associated with other nodes of the tree.

• The fact that the restrictions on integer variables can not be relaxedfor the evaluation of subsets associated with problems of type P MINLP ( le , ūe ).

Noting s the index of the node obtained after the separation number s, the evaluation of the node s will give us:

• If the node s is a leaf, then associated with a problem P MO-NLP (ȳ s ), we get a Pareto front (thus a discrete set of Pareto solutions whose density and distribution depend on the algorithm used) that we will write (F * P ) s such that :

(F * P ) s = {(f * 0 ) s , . . . , (f * i ) s } ∈ R p .
and (X * P ) s for the corresponding solutions in the variable space such as:

(X * P ) s = {(x * 0 , ȳs ), . . . , (x * i , ȳs )} ∈ R nc × Z ne with (f * i ) s = f (x * i , ȳs
). The figure 3.10 gives an illustration of this evaluation for two different values of ȳs ,for the problem P Mela . Note: The "Ideal" point can be determined for this type of node in the same way as with the anchor points, which we will write (P * I ) s .

• If the node s is not a leaf, then associated with a problem P MINLP ( le , ūe ), we obtain at most the p anchor points of the Pareto front that we will note: (P * k ) s , k = {1, . . . , p} and the point "Ideal" that we will write (P * I ) s . Here we determine in a way the hypervolume encompassing the Pareto front associated with this problem. This evaluation will be qualified exact under the assumption that the global minimum of the problem P MINLP ( le , ūe ) is reached for each objective function f k (x, y) since these minimums are obtained by holding restrictions on integer variables (see illustration examples on P Mela in figures 3.8 and 3.9).

Hybridizing meta heuristics and branch & bound 119

This evaluation obviously depends on the bounds on the integer variables le and ūe . Then the property1 for this evaluation:

The "Ideal" point (P * I ) s from the problem evaluation P MINLP (( le ) s , (ū e ) s ) is necessarily dominated by the "Ideal" point (P * I ) s ′ from P MINLP (( le ) s ′ , (ū e ) s ′ ) if :

( le ) s ′ ≥ ( le ) s et (ū e ) s ′ ) ≤ (ū e ) s )

Lower bounds

In branch and bound algorithms, the quality of the evaluation and the ability to obtain as quickly as possible a lower bound as close as possible to the desired optimum (in the case of single-objective problems) conditions the performance of the algorithm. In the case of multi-objective problems, this concept has been declined by [START_REF] Ehrgott | Bounds and Bound Sets for Biobjective Combinatorial Optimization Problems[END_REF] in the form of a lower bounding set, that is, a "dominant" approximation of the desired Pareto front. This concept is also used in [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] works, which we rely on. In practice, in the branch and bound algorithms this lower bound or this lower bounding set is set days with the successive evaluations of the subsets obtained by separation. This bet is made when an evaluation is better, ie less than the limit in the single-objective case, or when an evaluation is not dominated by the lower bounding set in the multi-purpose case. objective.

In our case, the evaluation being exact, the lower bounding set will thus contain the current approximation of the Pareto front. We therefore define:

• F * P = {f * 0 , . . . , f * i } ∈ R p
the lower bounding set containing only non dominated solutions of the problem solutions P MINLP ( le , ūe ) et P MO-NLP (ȳ).

• X * P = {(x * 0 , y * 0 ), . . . , (x * i , y * i )} ∈ R nc × Z ne the
corresponding solutions in the variable space.

In our case the evaluation of the subsets gives us either the hypervolume encompassing the Pareto front via the anchor points for the problems of the type P MINLP ( le , ūe ), which is the Pareto front associated with the problem P MO-NLP (ȳ).

Given the non-linearity of these problems, so the Pareto front (both the one in F * P , and (F * P ) s that is obtained by solving P MO-NLP (ȳ s )), we can obtain either anchor points or dominant Pareto front pieces when the point "Ideal"(P * I ) s is not dominated by F * P . The figures 3.14a and 3.14b illustrate an update situation of F * P for a leaf node, and the figures 3.15a and 3.15b for a node that is not a leaf. 2 ) s , is not dominated and will be added to F * P .

Figure 3.15 -Update of F * P in the case of a node that is not a leaf. Successive separations of the s node will explore the hypervolume defined by the anchor points.

Fathoming

The fathoming of a subset consists in not exploring (probing, separating, branching ..) a subset because this one and therefore all the subsets included in it, will not contain an optimal solution ( for the mono-objective case) or Pareto front elements, therefore elements of the set F * P in the multi-objective case. For that, it suffices to compare the evaluation of this subset with the lower bound (in the mono-objective case) or the lower bounding set (in the multi-objective case). If this evaluation is better (lower for the mono-objective case or dominant for the multi-objective case), then this subset may explore again or it will not be: it is fathomed. So the more we fathom subsets at the beginning of the exploration, the more we limit it and focus on subsets that may contain elements of solutions. This fathoming is an essential factor in the performance of a branch and bound algorithm and is largely based on two elements:

• The quality of the evaluation: in our case this one is exact, so there is no better one, but it is expensive because it is necessary to solve p problems of minimization mono-objective in mixed variables.

• The ability to locate as early as possible a lower bounding set of quality, as close as possible to the desired Pareto front.

In our context, the rules for "fathoming" a tree node during iterations are inspired by [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF]. These rules are:

1. The "Ideal" point (P * I ) s of the s node is dominated by the current approximation of the Pareto front, F * P . As all nodes s ′ coming from a separation of this one will have bounds like ( le ) s ′ ≥ ( le ) s and (ū e ) s ′ ) ≤ (ū e ) s ), their "Ideal" point (P * I ) s ′ will necessarily be dominated by (P * I ) s and therefore by F * P .

2. This one is empty in the sense that solving optimization problems P MINLP (( le ) s , (ū e ) s ) or P MO-NLP (ȳ s ) do not give solutions.

3. This is a "leaf" node, because in this case the values of the integer variables are fixed, so there is no need to separate this node again, including the non-dominated parts of the Pareto f ront(F * P ) s will be used to define the final Pareto front.

Tree progression

There are typically two progression strategies in the tree by choosing the next node to separate in order to:

• Progress to "Breadth first", the next node is created for the next separation of the same variable as the previous separation, until the last possible separation.

We then choose as the next node, the node created for the first separation of this variable (see figure 3.16a)

• Progress to "Deep first", the next node is created by separating the next variable (in the predefined order of separating variables), and so on until reaching the last variable. We then continue with the first separable node using the next separation of the variable of this node (see figure 3.16b) In almost all the "branch and bound" algorithms proposed in the literature, the progression choice is static, it is defined at the beginning and is no longer modified during the successive separations [START_REF] Przybylski | Multi-objective branch and bound[END_REF].

Enhanced Initialization

The first node of the tree, the root node, is associated with the problem P MINLP (l e , u e ) with the original values of the bounds on the integer variables. This problem is fixed and F * P is initialized with the obtained anchor points.

In order to improve the initialization of F * P , we are inspired by an idea of [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] which consists of enriching F * P with the solutions obtained by a "ε constraints" method or the vectorε ∈ R p is chosen to scan the interval of the optima of p functions to minimize. These optima are known since the anchor points were computed to initialize the root node.

For this we define the problem P MINLP (ε) such that:

P MINLP (ε) : ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Minimize f k (x, y) k ∈ [1, . . . , p] Under the constr. c j (x, y) ≤ 0 j = 1 . . . m c j (x, y) = 0 j = m + 1 . . . m + l f k(x, y) ≤ ε k k ∈ [1, . . . , k -1, k + 1, . . . , p] l c ≤ x ≤ u c l e ≤ y ≤ u e with : ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ x, l c , u c ∈ R nc y, l e , u e ∈ Z ne f (x, y), ε ∈ R p c j (x, y) ∈ R
In this variant we minimize f k (x), k ∈ [1, . . . , p] under the original constraints of the problem P MO-MINLP , adding the constraints:

f k(x, y) ≤ ε k, k ∈ [1, . . . , k -1, k + 1, . . . , p]
defined by the vector ε k of p -1 values.

Note that if we knew the proper value of the ε vector we could by solving the P MINLP (ε) problems for each appropriate ε value, get the solution (i.e. the Pareto front) of P MO-MINLP .

Hybridizing meta heuristics and branch & bound 123

Proposal of a Branch and Bound algorithm

The algorithm we propose allows to:

• Choose the separation principle: "by integer" or "by anchor points".

• Define the order of separating variables.

• The type of progression: "breadth first" or "deep first".

• Activate or not the enhanced initialization.

• Activate or not the fathoming of nodes, so as to test the ability of the algorithm to explore all combinations.

This algorithm is synthetically presented in below: This algorithm is synthetically presented below, manages a list of "nodes" that stores in memory for a node the information needed to solve the optimization problems of the type P MINLP (( le ) s ′ , (ū e ) s ′ ) or P MO-NLP (ȳ s ′ ).

Remarques :

• The list of N nodes contains the nodes that are not dominated. These nodes are either leaves (lower and upper bounds on identical integer variables) or separable nodes (hence for which the bounds on integer variables are different). The number of items in this list varies during iterations. The cleaning then consists of removing the leaf nodes, which are non-separable nodes by definition.

• The Pareto filtering is to eliminate in F * P all the solutions which are not of rank 1, so which are dominated.

• The choice of the node to be separated in the list N is done according to the method of progression chosen: the first separable of the list N for the progression in "Breadth first", or the last separable from N for progression in "Deep first" mode.

• The creation of a node is done according to the method of separation chosen: by integer or by points of anchor.

Algorithm test using problem "P Mela "

To test the proposed algorithm we will use "exact solvers" for problems of the type P MINLP (( le ) s ′ , (ū e ) s ′ ) or P MO-NLP (ȳ s ′ ) of the problem P Mela (3.1). We take advantage of the fact that for this problem, the number of integer variables n e = 4 and the number of integer values allowed per integer variable n vu = 4, u = {1, . . . , 4} are small. So we have n Conf = 4×4×4×4 = 256 problems of type P MO-NLP (ȳ s ′ ), with ȳs ′ browsing all 256 combinations of integer variables.

For each of these 256 multi-objective problems of 2 continuous variables, it is possible to calculate a very good approximation of the Pareto front by a sufficiently fine sampling of the domain defined by the bounds on the integer variables. For example, with 50 Algorithm 15 Main loop of the Branch and Bound algorithm 1: Initialization :

• F * P ← {∅}, X * P ← {∅}, N ← {∅}.

• Resolution of P MINLP (l e , u e ).

• N ← N + {N 0 }. Choosing a node, N s , in the list N .

4:

Create a node N s ′ from N s by branching.

5:

Node evaluation N s ′ , solving P MINLP (( le ) s ′ , (ū e ) s ′ ).

6:

if N s ′ ̸ = ∅ then Cleaning the list N : clear the "leaf" nodes. 19: end while values per continuous variable, we have to calculate 50 × 50 × 256 = 640000 values. We can thus determine for each of the 256 values of ȳs ′ a good approximation of the Pareto front of this problem and whatever the value of ( le ) s ′ and (ū e ) s ′ the corresponding anchor points (figure 3.17). Note that this is an upper bound of the number of nodes, so separations. This terminal is used to secure the algorithm and to stop calculations if the list of separable nodes is not empty.

By disabling the fathoming of the nodes and cleaning the list of N nodes, we obtain the results of figure 3.18 which show the evolution of the number of nodes at the separations. The 4 configurations of the algorithm can be seen by combining the 2 types of separations and the 2 progression modes as:

• the algorithm produces the 256 leaf nodes, as many as combinations of integer variables.

• for the integer separation (figures (figures 3.18c and 3.18a), the algorithm explores all the tree by producing the set of 341 nodes.

• for separation by anchor points (figures 3.18d and 3.18b), the algorithm produces fewer nodes than the theoretical maximum (1093). This is because for each separate node, the maximum number of 3 separation intervals is not always obtained. Indeed for this problem we have 2 objective functions, so a priori 2 anchor points so at most 3 separation intervals, unless for a given variable, these intervals are of zero length. This occurs when the anchor points are merged (i.e. the Pareto front is reduced to a point), or if the anchor points are merged with one of the two bounds on the integer variables.

We will also note the influence of the progression mode which results in:

• a difference in the progression of the number of solutions of the final Pareto front.

• a difference in the progression of the number of leaf nodes in the case of integer separation.

For these 4 configurations, the algorithm produces the same solution of the final Pareto front, identical to the exact solution, as shown in Figure 3 We observe that :

• For integer separation, the separation order has no influence on this problem. This is because the 4 integer variables all have the same values. Note that the product algorithm always explores the entire tree (341 total nodes) and produces the correct number of leaf nodes (256).

• For anchor separation, there are differences in the progression of the number of leaf nodes during separations, and also a variation in the total number of nodes explored, which is still well under 1093, the bound higher. As before this is due to the fact that there is not systematically 3 intervals at each separation. The table 3.14 shows that of the 24 executions corresponding to the 24order of separations, the total number of separations (hence of one plus one) varies from 516 to 548. For each case we specify the number of cases at 1, 2 and 3 intervals.

Convergence test with fathoming and node list cleanup

By activating the fathoming, and incidentally cleaning the list of nodes, for the 4 possible configurations of the algorithm combined with the 24 separation orders, ie 96 executions of the algorithm we obtain the results of the figure 3.21. We observe that :

• The number of separations required is significantly reduced: 88 separations needed against 340 with equivalent configurations (see figures 3.20c and 3.20a).

• The 96 executions each produce a Pareto front that is exactly the same as the exact Pareto front (same results as those in Figure 3. [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF]).

• The number of sheets produced by the algorithm is much lower which reflects a partial exploration of the tree. At least 24 leaves (figure 3.21d) are produced, and these 24 leaves contain the 7 leaves defining the final Pareto front (see (3.2)).

• The separation order influences the algorithm's behavior for 4 configurations, resulting in a significant change in the number of separations needed to converge: from 88 to 195 separations.

• On the 96 executions, these are the configurations:

-Integer Breadth First [4 3 6 5] and Integer Deep First [4 5 6 3] that give the fastest convergence with 88 separations.

and Anchor Deep First [5 6 3 4], the slowest with 194 separations.

These results are difficult to generalize because they depend on the structure of the problem to be solved. In conclusion :

• Tests on the problem P Mela with deactivated fathoming validate the algorithm: it all explores the tree and produces all the leaf nodes of the problem. Note here that in the problem P Mela , there are no constraints, so all nodes can be evaluated because there are no problems of "empty" nodes because associated with a problem of optimization without solution because of the functions constraints.

• the fathoming plays its role by limiting the exploration of the tree. 3.15) using an exact (and not a metaheuristic) solver (this approach was not applied to the gear train problem because of it's big combinatorial space). The idea behind this was to not let the quality of the metaheuristic interfere with the results. The second step after that is to test our hybrid algorithm (Branch and bound + metaheuristic) using the best configuration.

Optimization results for the three optimization problems using the new hybrid

For each configuration, the algorithm was able to find the true Pareto front. For example, figure 3.24 shows the Pareto front for the plate coupling problem using the hybrid algorithm with an exact solver, while figure 3.25 shows the Pareto front for the bearing problem using the hybrid algorithm with an exact solver.

Because the true front was found each time, the criterion to determine the best configuration was the number of seperations before convergence. Figure 3.22 and table 3.16 gives a comparison between configurations for the plate coupling problem according to the number of separations before convergence, while figure 3.23 and table 3.17 gives the same comparison between configurations for the bearing problem. From these comparisons, one can conclude that the best configuration for these two problems is when the separation type is set to anchor, the order of separation is set to [1 2] (the separation will start with the first variable, then continue with the second). The progress of the separation (Deep or Breadth), showed no effect on the rapidness of convergence.

Results of the three problems

.

Based on the observations from sections 3.1.3 and 3.2.3.1, the new hybrid is applied to our three optimization problems using NSGAII as a solver, with the "boundary" technique as a constraint handling method, and the best algorithm configurations; config1(type:anchor -order:[1,2] -progress:deep) and config2(type:anchor -order:[1,2]progress:Breadth). The corresponding results are shown in figures 3.26, 3.27, 3.28, 3.29, 3.30, 3.31 Judging by these figures, the new hybrid was able to surpass traditional metaheuristics, as it finds the true Pareto front in the case of the plate coupling and the bearing problems. In the case of the gear train problem, it was more close to the true front (compared to (a) Integer separation, progression "deep first". (a) Integer separation, progression "deep first". 3.18 -Time until convergence using the new hybrid traditional metaheuristics) while being evenly distributed. The only drawback was that it takes longer to converge. Table 3.18 shows the significance increase in the time that the algorithms takes until convergence. Nevertheless, a further study needs to be done to determine the time saved by new hybrid by comparison to a full enumerative algorithm.

Conclusions and perspectives

In this thesis, a new hybrid metaheuristic to address mixed variables optimization problems was provided. These problems, usually found in real-world mechanical engineering problems, are not sufficiently studied in literature. Three real-world mechanical engineering test problems were presented at first. They were namely; the plate coupling problem, the bearing problem and the gear train problem. An extensive state of the art study was conducted; First various alterations introduced on metaheuristics to enable it to handle mixed variables problems were gathered and classed in four classes according to whether the alteration is made during the initialization part, on the distance between individuals, during the solution update part, or when creating neighborhoods in neighborhood-based metaheuristics. This new perspective on how to handle mixed variables optimization was addressed in the hope to provide a better understanding for interested researchers.

In a second step, different hybridization techniques for metaheuristics were identified and classed using a new and global framework. The hybrid metaheuristic, able to handle mixed variables optimization problems, can be either a combination of a metaheuristic with an exact metaheuristic or a metaheuristic with another metaheuristic. It can be executed sequentially or in parallel, work collaboratively or be integrated one another. A special attention was given to hybridization for multi-objective optimization problems.

Finally the emerging idea of coupling metaheuristics with various constraint handling techniques was also considered as a type of hybridization, and seven constraint handling techniques were presented. The new framework for hybridization will definitely help researchers identify and exploit the most prominent hybridization techniques nowadays. A third step was to present four ways to evaluate the effectiveness of the hybridization. These evaluation techniques were the metrics as measuring indicators, the computational effort, the statistical assessment and the robustness of the hybrid at hand.

Then came the experimental part, were five traditional metaheuristics were tested on the three optimization problems. The evaluation criterion were the generational distance, the spread, the time until convergence and the percentage of overlapped points between the obtained front an the true Pareto front. The tests were done using two constraint handling variants; namely the penalty function and the "boundary" technique. NSGA II turned to be the best metaheuristics for the three problems, while "boundary" technique was the best technique for the three problems as well.

139

Introduction

La plupart des problèmes de conception mécanique sont des problèmes d'optimisation. Ces problèmes d'optimisation possèdent trois caractéristiques qui les rendent difficiles à résoudre. Ces caractéristiques sont la nature mixte des variables (continues et discrètes), l'existence de contraintes non linéaires et la présence de plusieurs critères non linéaires à minimiser pour guider les décisions de conception. Les critères que l'on cherche à minimiser sont liés aux performances du système comme par exemple la masse, la rigidité... Ce type de problème est dénommé : « Problème en variables mixtes non linéaire multiobjectif » ou « MO-MINLP » pour « Multi-Objective Mixed Integer Non Linear Programming » dans la littérature. Dans cette écriture le problème P MO-MINLP comporte au total n = n c + n e variables, avec n e variables entières et n c variables continues. Ces n variables sont assujetties à prendre des valeurs dans le domaine définit par les bornes inférieures l c , l e et supérieures u c , u e . Le problème P MO-MINLP comporte aussi p fonctions f l (x, y), . . . , f k (x, y), . . . , f p (x, y) objectifs qui sont des fonctions réelles continues, pas nécessairement convexes ni différentiables. Il est soumis à des fonctions contraintes c j (x, y) qui sont de la même nature que les fonctions objectifs.

Variables Mixtes

De nombreux problèmes d'optimisation d'ingénierie peuvent être modélisés en utilisant des combinaisons de variables continues et discrètes. Ce type de problèmes d'ingénierie provient souvent du domaine de la mécanique. Les variables discrètes sont utilisées pour plusieurs motifs ; comme le choix entre différentes options de conception ou la représentation d'un ensemble de composants de taille standard. Par exemple, le nombre de dents d'un engrenage doit être choisi comme un nombre entier. Le problème d'ingénierie qui contient des variables entières, discrètes, zéro-un et continues est souvent appelé un problème d'optimisation en variables mixtes. Le fait que les variables entières, peuvent faire référence à un nombre de composants ou à un numéro d'entrée dans une table de données, permettant de manipuler des « catalogues » de composants mécaniques, rend impossible la "relaxation" des variables entières en les considérant comme continues. En effet ces variables entières font par exemple référence à un nombre de composants ou à un index permettant d'utiliser des valeurs dans une table (typiquement un catalogue de composants). Les variables entières rendent un problème d'optimisation non convexe, et donc beaucoup plus difficile à résoudre. La mémoire et le temps de la solution peuvent augmenter exponentiellement en ajoutant plusieurs variables entières. Même avec des algorithmes hautement sophistiqués et des supercalculateurs modernes, il existe des modèles avec seulement quelques variables entières qui n'ont jamais été résolues jusqu'à l'optimalité. Cela est dû au fait que de nombreuses combinaisons de valeurs entières spécifiques pour les variables doivent être testées, et chaque combinaison nécessite la solution d'un problème d'optimisation linéaire ou non linéaire "normal". Le nombre de combinaisons peut augmenter exponentiellement avec la taille du problème. La littérature est très rare sur le sujet de l'optimisation des variables mixtes, malgré son Techniques de manipulation des variables mixtes 145 importance pour les applications du monde réel. Dans la section suivante, on présente une partie de l'état de l'art sur comment manipuler les variables mixtes dans un algorithme d'optimisation.

Techniques de manipulation des variables mixtes

Alors que les variables continues peuvent prendre n'importe quelle valeur entre deux nombres, les variables discrètes n'offrent pas un tel étalement et une telle douceur. Comme nous avons mentionné dans II, elles ne peuvent avoir qu'une valeur à partir d'un ensemble de valeurs prédéfinies. Dans leur forme la plus large, ces valeurs prédéfinies peuvent être des entiers, des nombres zéro-un, des graphiques, des objets, des couleurs, etc ... Malgré sa grande importance pratique, l'optimisation à variables mixtes ne bénéficie pas, d'une popularité aussi grande que l'optimisation à variables continues et donc, peu d'algorithmes pour traiter ces problèmes sont disponibles dans la littérature. Parmi les tentatives les plus importantes pour analyser les techniques d'optimisation des variables mixtes on trouve le travail de Liao et al. [START_REF] Liao | Population-based heuristic algorithms for continuous and mixed discrete-continuous optimization problems[END_REF] et le travail de [START_REF] Giagkiozis | An overview of populationbased algorithms for multi-objective optimisation[END_REF]. Dans la référence [START_REF] Giagkiozis | An overview of populationbased algorithms for multi-objective optimisation[END_REF], les auteurs ont passé en revue dans leurs travaux récents la capacité de sept métaheuristiques à gérer des problèmes de variables mixtes. Une échelle allant de 1 à 5 a été donnée à mesurer les forces et les faiblesses relatives des familles d'algorithmes pour des problèmes multi-objectifs avec des variables mixtes. Une valeur de 5 traduit que cette famille particulière d'algorithmes est très bien adaptée à ce type de problème, tandis qu'une valeur de 1 signifie que l'algorithme est mal adapté à ce type de problèmes. La comparaison a montré que si six algorithmes sur sept étaient capables de gérer l'optimisation des variables mixtes, tous ces six algorithmes avaient obtenu une note de 1 dans leur test d'adéquation. Dans notre travail, nous avons passé en revue les modifications introduites sur certains composants métaheuristiques afin de gérer ces variables discrètes. Nous avons également classé ces modifications en quatre classes qui sont :

Techniques pour manipuler les contraintes

La présence de contraintes dans un problème d'optimisation a été souligné comme l'une des sources de difficulté trouvés dans les problèmes d'optimisation du monde réel [START_REF] Michalewicz | How to solve it: modern heuristics[END_REF] à côté d'autres problèmes comme les énormes espaces de recherche, le bruit dans la(es) fonction(s) objectif(ves) et de la complexité de la processus de modélisation. Les contraintes peuvent éloigner l'attention de la recherche sur optimisation et se restreindre juste à la recherche d'une solution valable ou réalisable. D'autre part, dans leur version originale, les méta-heuristiques ont été conçues pour des espaces de recherche sans contrainte [START_REF] Back | Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms[END_REF] , [START_REF] Engelbrecht | Fundamentals of computational swarm intelligence[END_REF]. Ce fut la principale motivation pour ajouter des techniques de manipulation des contraintes aux méta-heuristiques dans le but de guider la recherche vers des régions avec des solutions faisables. Plusieurs revues de la littérature ont traité le problème des techniques de manipulation des contraintes pour les méta-heuristiques : Dans Pour les techniques anciennes, Mezura et al. ont essayé de combiner les classifications des approches qui ont été introduit dans les enquêtes précédentes sur ce sujet, notamment ceux de [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF] et [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF], dans une taxonomie mise à jour et relativement brève. Ensuite les techniques actuelles les plus représentatives de la manipulation des contraintes ont été brièvement discutées et analysées. Contrairement aux techniques présentées pour les techniques anciennes, la nombre d'approches examinées dans ce cas est plus faible. Cela est dû du fait que les différences entre les approches sont, dans ce cas, plus axé sur les modifications apportées aux éléments de algorithme d'optimisation adopté, et non pas sur la technique de contrainte de manipulation elle-même. Enfin les auteurs ont listé et décrit plusieurs sujets de recherche qui ont attiré peu d'attention des chercheurs, et qui peuvent constituer ,selon leur point de vue, des pistes prometteuses pour la recherche future. Un revue récent est celui de Yousefi et al. [START_REF] Yousefi | A Practical Review on the Application of Constraint Handling Strategies in Evolutionary Computation from an Engineering Point of View[END_REF] qui traitait les techniques de manipulation des contraintes pour les algorithmes évolutionnaires du point de vue de l'ingénierie. Son approche était de mettre à jour les techniques des revues précédentes sans changer structurellement les taxonomies anciennes. Dans notre travail, on décrit les principaux techniques de manipulation des contraintes pour les méta-heuristiques qui se trouve dans la littérature. On parle de sept classe de méthodes.

• Fonctions de pénalité

Hybridation

La motivation derrière de telles hybridations de différents concepts algorithmiques est habituellement d'obtenir des systèmes plus performants qui exploitent et unissent les avantages des stratégies pures individuelles, c'est-à-dire que ces hybrides sont censés bénéficier d'une synergie. Le nombre grandement croissant d'applications rapportées de métaheuristiques hybrides documentent la popularité, le succès et l'importance de cette ligne de recherche spécifique. En fait, il semble aujourd'hui que le choix d'une approche hybride adéquate est déterminant pour atteindre les meilleures performances dans la résolution des problèmes les plus difficiles. En fait, l'idée d'hybrider des métaheuristiques n'est pas nouvelle, mais remonte aux origines mêmes des métaheuristiques. Au cours des dernières années, un nombre assez impressionnant d'algorithmes ont été signalés qui ne suivent pas purement le paradigme d'une métaheuristique traditionnelle unique. Au contraire, ils combinent divers composants algorithmiques, souvent issus d'algorithmes d'autres domaines de recherche sur l'optimisation. Ces approches sont communément appelées métaheuristiques hybrides. L'absence de définition précise de ce terme a parfois fait l'objet de critiques. Notons cependant que le caractère relativement ouvert de cette expression peut être utile, car les frontières strictes entre les domaines de recherche connexes sont souvent un obstacle à la pensée créatrice et à l'exploration de nouvelles orientations de recherche. La principale motivation de l'hybridation des différents algorithmes est d'exploiter le caractère complémentaire des différentes stratégies d'optimisation, c'est-à-dire que les hybrides sont censés bénéficier de la synergie. En fait, le choix d'une combinaison adéquate de concepts algorithmiques complémentaires peut être la clé pour atteindre les meilleures performances dans la résolution de nombreux problèmes d'optimisation. Malheureusement, développer une approche hybride efficace est en général une tâche difficile qui nécessite une expertise de différents domaines d'optimisation. En outre, la littérature montre qu'il est non trivial de généraliser, c'est-à-dire qu'un certain hybride pourrait bien fonctionner pour des problèmes spécifiques, mais il pourrait avoir un mauvais rendement pour d'autres. Néanmoins, il existe des types d'hybridation qui se sont révélés efficaces pour de nombreuses applications. Ils peuvent servir de guide pour les nouveaux développements. Pour l'extraction de directives utiles pour le développement de métaheuristiques hybrides, il sera nécessaire d'améliorer la méthodologie de recherche qui est aujourd'hui couramment utilisée dans le domaine de la métaheuristique. Malheureusement, la méthodologie de recherche utilisée est souvent caractérisée par une approche plutôt ad hoc qui consiste à mélanger différents composants algorithmiques sans tentatives sérieuses d'identifier la contribution de différents composants à la performance des algorithmes. À notre avis, la communauté de la recherche devrait s'efforcer de se diriger vers une méthodologie scientifique solide, composée de modèles théoriques pour décrire les propriétés des métaheuristiques hybrides et en utilisant une méthodologie expérimentale comme en sciences naturelles. Nous sommes convaincus que la recherche sur les métaheuristiques hybrides est encore à ses débuts. Dans les années à venir, la plupart des publications sur les applications métaheuristiques porteront sur les hybrides. Nous espérons que ce travail contribuera à donner plus de structure et d'orientation à cette intéressante ligne de recherche. Dans [START_REF] Raidl | A unified view on hybrid metaheuristics[END_REF], l'auteur a collecté certains éléments clés métaheuristiques dans une "boîte à outils". Le but était d'utiliser cette boîte à outils afin de construire de nouvelles métaheuristiques hybrides efficaces. Selon lui, cette façon de penser semble être supérieure pour construire une métaheuristiques hybride par rapport à l'autre point de vue, qui se penche trop fortement sur les philosophies historiques et naturelles derrière les différents paradis méta-heuristiques. Son idée était simple ; toutes les métaheuristiques existants partagent certaines idées et diffèrent entre eux par certains composants clés caractéristiques. Le fait de rendre ces composants clés explicites et de les collecter dans une boîte à outils de composants, nous permet de choisir à partir de ces composants ceux qui semblent être les plus appropriés pour le problème cible à portée de main dans la conception d'un algorithme d'optimisation. On peut classer les hybrides selon différents critères :

Types des algorithmes hybrides

Ordre d'execution

Une autre propriété par laquelle nous pouvons distinguer les métaheuristiques hybrides est l'ordre d'exécution. Dans ce modèle, un algorithme est exécuté strictement après l'autre, et l'information est passée seulement dans une di-rection. Un prétraitement intelligent des données d'entrée ou un post-traitement des résultats d'un autre algorithme entrerait dans cette catégorie. Un autre exemple sont les problèmes multi-niveaux qui sont résolus en considérant un niveau après l'autre par des algorithmes d'optimisation dédiés. Au contraire, nous avons les modèles entrelacés et parallèles, dans lesquels les algorithmes peuvent interagir de manière plus sophistiquée. Les métaheuristiques parallèles constitue un champ de recherche important.

Stratégie de contrôle Nous pouvons distinguer davantage les métaheuristiques hybrides selon leur stratégie de contrôle. Il existe des combinaisons intégratives et collaboratives. Dans les approches intégratives, un algorithme est considéré comme subordonné, composant d'un autre algorithme. Dans des combinaisons collaboratives, les algorithmes échangent des informations, mais ne font pas partie de l'autre. On trouve une présentation d'exemples et de courtes synthèses de la littérature concernant cinq catégories importantes de métaheuristiques hybrides. Plus précisément, les auteurs ont concentré sur l'hybridation des métaheuristiques avec les (méta) heuristiques, la programmation des contraintes, les méthodes Branch & bound, la relaxation des problèmes et la programmation dynamique. Pour chaque sujet, deux exemples sont présentés, puis une courte synthèse de la littérature. À la fin, les auteurs ont recommandé qu'avant de commencer à développer une métaheuristique hybride, les chercheurs examinent soigneusement si une technique métaheuristique hybride est la méthode de solveur appropriée pour le problème à portée de main. Les questions suivantes doivent être posées :

• Quel est l'objectif d'optimisation ? Ai-je besoin d'une solution raisonnablement bonne très rapidement, ou puis-je me permettre de dépenser la mise en oeuvre et le temps de calcul afin d'obtenir de très bonnes solutions. Si la puissance humaine et le temps de calcul sont critiques, les métaheuristiques hybrides ne sont généralement pas recommandées. Ce n'est que lorsque de très bonnes solutions sont nécessaires qui ne peuvent être obtenues par une méthode complète dans un délai réalisable, le développement d'une métaheuristique hybride est conseillé.

• Existe-t-il encore de la place pour améliorer les résultats des approches métaheuristiques existantes et / ou des techniques complètes ? Dans certains cas, les stratégies purement métaheuristiques existantes pourraient déjà très bien fonctionner pour les instances problématiques à résoudre. Ou, alternativement, les instances de problème à l'étude pourraient être résolubles par des techniques complètes dans une quantité raisonnable de temps de calcul. Dans ces cas, il n'a pas de sens de consacrer du temps et des efforts dans le développement d'une métaheuristique hybride.

• Quel type de metaheuristic hybride pourrait bien fonctionner pour mon problème ? Malheureusement, l'état actuel de la recherche ne fournit pas de réponses concluantes à cette question. Il est difficile de trouver des directives générales. Le processus de conception et de mise en oeuvre de métaheuristiques hybrides efficaces peut être assez compliqué et implique la connaissance d'un large spectre de techniques algo-rithmiques, de programmation et de structures de données, ainsi que de l'ingénierie algorithmique et des statistiques.

Pour le développement d'algorithmes performants, les auteurs ne peuvent que recommander (1) une recherche documentaire approfondie dans le but d'identifier les approches d'optimisation les plus réussies pour le problème en cours ou pour des problèmes similaires, et (2) l'étude de différentes manières de combiner les caractéristiques les plus prometteuses des approches identifiées.

Evaluation des hybrides

L'évaluation des hybrides, également appelée évaluation des métaheuristiques hybrides, est une tâche nécessaire qui ne devrait pas être traitée à la légère. Si elle est menée correctement, l'évaluation devrait donner une rétroaction honnête concernant les choix d'hybridation. Cependant, ce n'est pas une tâche insignifiante et doit être faite sur une base équitable. Une bonne évaluation est fortement liée aux objectifs définis lors de la conception de la métaheuristique hybride. En effet, l'évaluation de la robustesse du cas, la robustesse des instances, la diversification, l'intensification, la facilité de mise en oeuvre, l'innovation à l'aide de nouveaux paradigmes, le réglage automatique des paramètres, etc. Dans notre travail, nous présentons quatre façons d'évaluer une métaheuristique hybride ; à savoir mértiques, effort de calcul, évaluation statistique et robustesse.

Métaheuristiques

Les métaheuristiques ont été développées pour surmonter les insuffisances des techniques d'optimisation exactes qui n'ont pas permis de résoudre les problèmes d'optimisation complexes et non linéaires. Ils sont mis en oeuvre grâce à un processus de génération itérative qui permet de trouver des solutions de bonne qualité dans un délai relativement court. Les métaheuristiques sont des techniques d'optimisation célèbres et largement répandues. La majorité d'entre eux sont inspirés par des phénomènes naturels comme la sélection naturelle ou le comportement des animaux ou même par la musique et les systèmes immunitaires parmi d'autres inspirations. Les métaheuristiques sont souvent divisées en deux groupes principaux : les métaheuristiques basées sur la trajectoire et la population. La plupart de ces algorithmes ont été initialement introduits pour une optimisation continue. Dans notre travail, nous décrivons quelques métaheuristiques "traditionnelles" des deux groupes. Nous mettons l'accent sur les métaheuristiques qui ont été modifiées afin de pouvoir gérer des problèmes d'optimisation multi-objectifs variables mixtes.

Méthodes exactes

Contrairement aux métaheuristiques, les méthodes exactes sont des algorithmes qui résolvent un problème d'optimisation à l'optimalité, et pas seulement à des solutions quasi optimales. Par conséquent, ils sont le choix numéro un pour tout problème d'optimisation s'ils peuvent fournir une solution avec un effort de calcul acceptable. Les méthodes d'optimisation exactes ont été utilisées plusieurs fois pour l'optimisation combinatoire. C'est cet aspect combinatoire qui les rend appropriés pour des problèmes d'optimisation de variables mixtes. Dans ce qui suit, nous parlons d'une méthode exacte qui a été couplé plusieurs fois avec des métaheuristiques pour résoudre divers problèmes d'optimisation.

Problème d'un train d'engrenage

Présentation du problème

On peut formuler un problème d'optimisation à partir du modèle de dimensionnement ISO 6336. Ici il serait trop long et complexe de détailler l'ensemble des paramètres intervenant dans le modèle et l'ensemble des relations nécessaires. Globalement, on peut distinguer 4 groupes de paramètres :

1. Les paramètres définissant complètement la géométrie de la denture :

• Dont des paramètres modifiables car liés à la denture directement : z 1 , z 2 , m n , b, β, x 1 et x 2 .

• Dont des paramètres spécifiques à l'outillage, paramètres généralement considérés comme fixes dans une étude de conception : α n , ρ a le rayon d'outil, h a le coefficient de saillie, h f le coefficient de creux, s pr la sur-épaisseur d'usinage.

1. La puissance transmissible en résistance au pied de dent est suffisante.

2. La puissance transmissible à la pression superficielle est suffisante.

3. Le facteur de conduite est supérieur à 1.3.

4. Pas d'interférence de fonctionnement lors de l'engrènement : deux conditions l'une le pignon l'autre sur la roue.

5. L'épaisseur de dent au sommet de celle-ci est suffisante.

En choisissant d'imposer :

• La géométrie de l'outil de taillage comme un donnée du problème d'optimisation.

• Une paire de matériaux pas forcément identique pour la roue et le pignon.

• Des conditions de qualité de fabrication et de lubrification.

En limitant l'étude à un cas d'engrenage droit, les variables de ce problème d'optimisation sont :

x = {z 1 , z 2 , i m , x 1 , x 2 , b} T On choisit de minimiser à la fois le volume de matériau et le glissement relatif entre la pignon et la roue.

BnB hybride

Puis, suite à l'incapacité de ces métaheuristiques «traditionnelles» modifiées de répondre à certaines métriques d'évaluation, un nouvel algorithme hybride couplant métaheuristiques et l'algorithme de séparation et évaluation a été introduit. L'algorithme hybride combine les avantages des métaheuristiques (efficacité pour les problèmes multi-objectifs non linéaires) et l'exploration systématique avec des variables mixtes des algorithmes de séparation et évaluation. Ce nouvel algorithme hybride comprenant des techniques de séparation spécifique est bien adapté pour résoudre des problèmes mixtes multi-objectifs non-linéaires. Il donne de meilleurs résultats sur ces problèmes tests que les métaheuristiques «traditionnelles» et ouvre de nombreuses perspectives d'améliorations.

Sous-problèmes

Le problème P MO-MINLP est un problème complexe et couteux à résoudre, le principe général consiste à résoudre à la place plusieurs problèmes plus simples. Le découpage proposé est celui de [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF], il consiste à considérer deux "sous problèmes" différents :

Séparation en sous ensembles

Le principe de séparation doit nous permettre de partager l'espace complet des n conf combinaisons en sous-espace plus petits. Comme suggéré dans [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] le découpage en sous-espace se fera en agissant sur les bornes inférieures l e et supérieures u e des variables entières. On aura donc deux types de sous-espaces de combinaisons :

• Ceux pour lesquels le = ūe , que l'associera à un problème du type P MO-NLP (ȳ) avec ȳ = le = ūe .

• Ceux pour lesquels le < ūe , que l'associera à un problème du type P MINLP ( le , ūe ).

Au risque de ne pas explorer la totalité de l'espace des combinaisons (donc des solutions), le principe de séparation doit respecter la règle suivante : L'union de tous les sous-espaces doit être égale à l'espace complet des n conf combinaisons du problème P MO-MINLP .

On propose de mettre en oeuvre deux principes de séparation par modification des bornes inférieures et supérieures l e et u e des variables entières.

1. Un principe, que nous nommerons "séparation par les entiers", qui consiste à choisir une variable entière, telle que les valeurs de ses bornes inférieures et supérieures sont différentes. On crée ensuite autant d'intervalles [(l e ) s , (u e ) s , ] que de valeurs entières comprises entre les bornes inférieure et supérieure de la variable à séparer.

Évaluation des sous-ensembles

On rappelle que dans les algorithmes branch and bound appliqué à des problèmes monoobjectif, l'évaluation consiste à déterminer un minorant de l'optimum du sous-ensemble que l'on évalue. En notant s l'indice du noeud obtenu après la séparation numéro s, l'évaluation du noeud s nous donnera :

• Si le noeud s est une feuille, donc associé à un problème P MO-NLP (ȳ s ), on obtient un front Pareto (donc une ensemble discret de solutions de Pareto dont la densité et la répartition dépendent de l'algorithme utilisé).

• Si le noeud s n'est pas une feuille, donc associé à un problème P MINLP ( le , ūe ), on obtient au maximum les p points d'ancrage du front de Pareto.

Bornes inférieures

Dans les algorithmes branch and bound la borne inférieure ou cet ensemble bornant inférieur est mis jours avec les évaluations successives des sous-ensembles obtenus par séparation. Cette mise s'effectue dès lors qu'une évaluation est meilleure, c'est à dire inférieure à la borne dans le cas mono-objectif, ou lorsque une évaluation n'est pas dominée par l'ensemble bornant inférieur dans le cas multi-objectif.

Stérilisation

La stérilisation d'un sous-ensemble consiste à ne pas explorer (sonder, séparer,..) un sous-ensemble car celui-ci et donc que tous les sous-ensembles inclus dans celui-ci, ne contiendrons pas de solution optimale (pour le cas mono-objectif) ou d'éléments de front Pareto, donc d'éléments de l'ensemble F * P dans le cas multi-objectif. Pour cela il suffit de comparer l'évaluation de ce sous-ensemble avec la borne inférieure (dans le cas mono-objectif) ou l'ensemble bornant inférieur (dans le cas multi-objectif). Si cette évaluation est meilleure (inférieure pour le cas mono-objectif ou dominante pour le cas multi-objectif), alors ce sous-ensemble peut-être explorer à nouveau sinon il ne le sera pas : il est stérilisé 2 .

Progression dans l'arborescence

Il existe classiquement deux stratégies de progression dans l'arborescence en choisissant le prochain noeud à séparer de façon à :

• Progresser en "Largeur d'abord", le prochain noeud est crée pour la prochaine séparation de la même variable que la précédente séparation, jusqu'à la dernière séparation possible. On choisit ensuite comme prochain noeud, le noeud crée pour la première séparation de cette variable (voir figure 3.16a)

• Progresser en "Profondeur d'abord", le prochain noeud est crée par séparation de la variable suivante (dans l'ordre prédéfini de séparation des variables), et ainsi de suite jusqu'à atteindre la dernière variable. On continue ensuite avec le premier noeud séparable en utilisant la prochaine séparation de la variable de ce noeud.(voir figure 3.16b)

Initialisation améliorée

Le premier noeud de l'arborescence, le noeud racine, est associé au problème P MINLP (l e , u e ) avec les valeurs originales des bornes sur les variables entières. Ce problème est résolu et F * P est initialisé avec les points d'ancrages obtenus. Afin d'améliorer l'initialisation de F * P , on s'inspire d'une idée de [START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] qui consiste a enrichir F * P avec les solutions obtenues par une méthode de "ε contraintes" ou le vecteur ε ∈ R p est choisi pour balayer l'intervalle des extrémuns des p fonctions à minimiser. Ces extrémuns sont connus puisque les points d'ancrage ont été calculés pour initialiser le noeud racine.

Proposition d'un algorithme "Branch and Bound"

L'algorithme que nous proposons permet de :

• Choisir le principe de séparation : "par entier" ou "par points d'ancrage".

• Définir l'ordre de séparation des variables.

• Le type de progression : "largeur d'abord" ou "profondeur d'abord".

• D'activer ou pas l'initialisation améliorée.

• D'activer ou pas la stérilisation des noeuds, de façon à tester la capacité de l'algorithme à explorer toutes les combinaisons.

Cet algorithme est synthétiquement présenté en pseuo-langage ci-dessous :

French Summary Algorithm 16 Boucle principale de l'algorithme "Branch and Bound" 1: Initialisation :

• F * P ← {∅}, X * P ← {∅}, N ← {∅}.

• Résolution de P MINLP (l e , u e ).

• F * P ← F * P + { (P * 1 ) 0 , . . . , (P * k ) 0 , . . . , (P * p ) 0 } .

• N ← N + {N 0 }.

• s ← 0 2: while N ̸ = {∅} do 3:

Choix d'un noeud, N s , dans la liste N .

4:

Création d'un noeud N s ′ à partir de N s par séparation.

5:

Évaluation du noeud N s ′ , résolution de P MINLP (( le ) s ′ , (ū e ) s ′ ).

6:

if N s ′ ̸ = ∅ then Nettoyage de la liste N : efface les noeuds "feuilles". 19: end while

Test de l'algorithme sur le problème "fil rouge"

Pour tester l'algorithme proposé on utilisera des "solveurs exacts" pour les problèmes du type P MINLP (( le ) s ′ , (ū e ) s ′ ) ou P MO-NLP (ȳ s ′ ) du problème P Mela (3.1). On profite ici du fait que pour ce problème, le nombre de variables entières n e = 4 et le nombre de valeurs entières admissibles par variable entière n vu = 4, u = {1, . . . , 4} sont faibles. On a donc n Conf = 4 × 4 × 4 × 4 = 256 problèmes du type P MO-NLP (ȳ s ′ ), avec ȳs ′ parcourant l'ensemble des 256 combinaisons de variables entières.

Pour chacun de ces 256 problèmes multi-objectifs de 2 variables continues, il est possible de calculer une très bonne approximation du front de Pareto par un échantillonnage suffisamment fin du domaine définit par les bornes sur les variables entières. Avec par exemple 50 valeurs par variables continues, on a à calculer 50 × 50 × 256 = 640000 valeurs.

On peut ainsi déterminer pour chacune des 256 valeurs de ȳs ′ une bonne approximation du front de Pareto de ce problème et quelque soit la valeur de ( le ) s ′ et (ū e ) s ′ les points d'ancrage correspondant (figure 3.17).

On constate pour les 4 configurations de l'algorithme en combinant les 2 types de séparations et les 2 modes de progression que :

• l'algorithme produit les 256 noeuds feuilles, soit autant que de combinaisons de variables entières.

• pour la séparation par entier (figures 3.18c et 3.18a), l'algorithme explore bien toutes l'arborescence en produisant l'ensembles des 341 noeuds.

• pour la séparation par points d'ancrage (figures 3.18d et 3.18b), l'algorithme produit moins de noeuds que le maximum théorique (1093). Cela s'explique par le fait que pour chaque noeud séparé, on obtient pas toujours le nombre maximal de 3 intervalles de séparations. En effet pour ce problème on a 2 fonctions objectifs, donc à priori 2 points d'ancrage donc au maximum 3 intervalles de séparation, sauf si pour une variable donnée, ces intervalles sont de longueur nulle. Cela se produit lorsque les points d'ancrages sont confondus (i.e. le front de Pareto se réduit à un point), ou si les points d'ancrages sont confondus avec l'une des deux bornes sur les variables entières.

On notera également l'influence du mode de progression qui se traduit par :

• une différence dans la progression du nombre de solutions du front de Pareto final.

• une différence dans la progression du nombre de noeeuds feuilles dans le cas de la séparation par entiers.

Pour ces 4 configurations, l'algorithme produit la même solution du front de Pareto final, identique à la solution exacte, comme le montre la figure 3.19.

On test après l'influence de l'ordre de séparation pour les 4 configurations (2 type de séparations, 2 mode de progression). Avec 4 variables entières il y a 4! = 24 ordres différents.

On constate que :

• Pour la séparation par entier, l'ordre de séparation n'a aucune influence pour ce problème. Cela est dû a fait que les 4 variables entières admettent toutes les mêmes valeurs. On notera que l'algorithme produit explore toujours toutes l'arborescence (341 noeuds au total) et produit le bon nombre de nooeuds feuilles (256).

• Pour la séparation par points d'ancrage, on remarque des différences dans la progression du nombre de noeuds feuilles au cours des séparations, et également une variation du nombre total de noeuds explorés, qui est toujours largement inférieur à 1093, la borne supérieure. Comme précédemment cela est dû au fait qu'il y pas systématiquement 3 intervalles à chaque séparation. Le tableau 3.14 montrent que sur les 24 exécutions correspondant au 24 ordres de séparations, le nombre total de séparations (donc de noeuds plus un) varient de 516 à 548. Pour chaque cas on précise le nombre de cas à 1,2 et 3 intervalles.

Meilleure configuration pour le problème de l'accouplement à plateaux et le problème du roulement

Maintenant que le nouvel algorithme hybride est expliqué en détail, l'étape suivante consiste à le tester sur les trois problèmes d'optimisation. Afin de tester l'efficacité de notre algorithme et de choisir la meilleure configuration pour les deux premiers problèmes, nous avons choisi de tester toutes les configurations possibles de 8 (voir le tableau 3.15) en utilisant un solveur exact (et non métaheuristique) (cette approche n'a pas été appliquée au problème du train d'engrenages à cause de son grand espace combinatoire). L'idée derrière cela était de ne pas laisser la qualité du métaheuristique interférer avec les résultats. La deuxième étape consiste à tester notre algorithme hybride (Branch et bound + metaheuristic) en utilisant la meilleure configuration. Pour chaque configuration, l'algorithme était capable de trouver le véritable front de Pareto. Par exemple, la figure 3.24 montre le front de Pareto pour le problème de l'accouplement à plateaux en utilisant l'algorithme hybride avec un solveur exact, tandis que la figure 3.25 montre le front de Pareto pour le problème de roulement.

Puisque le vrai front ayant été trouvé à chaque fois, le critère de détermination de la meilleure configuration était le nombre de séparations avant convergence. La figure 3.22 et la table 3.16 comparent les configurations du problème de l'accouplement à plateaux en fonction du nombre de séparations avant convergence, alors que la figure 3.23 et la table 3.17 donne la même comparaison entre les configurations pour le problème de roulement. À partir de ces comparaisons, on peut conclure que la meilleure configuration pour ces deux problèmes est lorsque le type de séparation est défini par les points d'ancrages, l'ordre de séparation est défini comme [1 2] (la séparation commencera par la première variable, puis se poursuivra par la seconde). La progression de la séparation (Profondeur ou Largeur) n'a pas eu d'effet sur la rapidité de la convergence.

Résultats des trois problèmes

Basé sur les observations des sections 3.1.3 et 3.2.3.1, le nouvel hybride est appliqué à nos trois problèmes d'optimisation en utilisant NSGAII comme solveur, avec la technique "boundary" comme méthode de traitement des contraintes et les meilleurs configuratiosn de algorithme (type : ancre -ordre : [1,2] -progression : profond) et (type : ancre -ordre : [1,2] -progression : largeur). Les résultats correspondants sont indiqués dans les figures 3.26, 3.27, 3.28, 3.29, 3.30, 3.31.

À en juger par ces chiffres, le nouvel hybride est capable de surpasser les métaheuristiques traditionnelles, car il trouve le véritable front de Pareto dans le cas de l'accouplement à plateaux et du problème de roulements. Dans le cas du problème du train d'engrenage, il était plus proche du vrai front (comparé aux métaheuristiques traditionnelles) tout en étant distribué de manière uniforme. Le seul inconvénient est que la convergence prend plus de temps. La table 3.18 montre l'augmentation du temps que prend l'algorithme jusqu'à la convergence. Néanmoins, une étude supplémentaire peut Conclusion et perspectives 161 être effectuée pour déterminer le temps économisé par un nouvel hybride par comparaison avec un algorithme énumératif complet.

Conclusion et perspectives

Dans cette thèse, un nouveau métaheuristique hybride pour résoudre les problèmes d'optimisation des variables mixtes a été fourni. Ces problèmes, généralement rencontrés dans les problèmes réels de génie mécanique, ne sont pas suffisamment étudiés dans la littérature. Trois problèmes test d'ingénierie mécanique ont été présentés dans un premier temps : le problème de couplage de la plaque, le problème de roulement et le problème du train d'engrenage. Une étude approfondie de l'état de l'art a été menée ; Les différentes modifications introduites sur les métaheuristiques pour traiter les problèmes de variables mixtes ont été regroupées et classées en quatre classes selon que l'altération est effectuée lors de la partie initialisation, de la distance entre les individus, lors de la métaheuristiques basées sur le voisinage. pour les trois problèmes a été effectuée en utilisant un algorithme exact au lieu d'un métaheuristique. L'idée derrière cela était de ne pas laisser la qualité du métaheuristique interférer avec les résultats. Une fois la meilleure configuration déterminée, elle a été associée au meilleur métaheuristique (NSGAII) et à la meilleure technique de traitement des contraintes ("boundary") et testée sur les trois problèmes. Le nouvel hybride a été capable de surpasser les métaheuristiques traditionnelles, car il trouve le vrai front de Pareto dans la plupart des cas. Dans d'autres cas, il était plus proche du vrai front (comparé aux métaheuristiques traditionnelles) tout en étant distribué de manière homogène. Le seul inconvénient est que la convergence prend plus de temps. Malgré notre approche systématique de l'hybridation, il est toujours inévitable de tenir compte des caractéristiques particulières du problème que l'on essaie de résoudre. Peutêtre faudrait-il mener une étude supplémentaire pour déterminer le temps économisé par un nouvel hybride par comparaison avec un algorithme énumératif complet. L'idée intuitive (décrite dans 2.3.4.1), à savoir que la solution des problèmes d'optimisation de l'ingénierie est susceptible de se trouver dans les limites de la région faisable, est loin d'être pleinement exploitée. À long terme, des efforts supplémentaires doivent être déployés pour exploiter la nature combinatoire des métaheurisitques et les guider dans la recherche de solutions à proximité des limites des régions faisables. Jusqu'à ce jour, on peut considérer l'idée d'un paramètre delta active dynamique ; c'est-à-dire que le nombre d'itérations change en fonction de la difficulté à générer une solution dans la limite des solution faisables.

1. 1

 1 Standardized values of parameters depending on diameter d of bolts . . . 1.2 coupling data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The 25 Pareto solutions of the bolted coupling. . . . . . . . . . . . . . . . 1.4 Data for single-rowed ball bearings (SKF) . . . . . . . . . . . . . . . . . . 1.5 bearing pivot connection data . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Pareto solutions for pivot connection with ball bearings. . . . . . . . . . . 1.7 Pareto solutions for pivot connection with ball bearings. . . . . . . . . . . 1.8 Gear data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9 The 23 Pareto solutions of the gear. . . . . . . . . . . . . . . . . . . . . . 3.1 Algorithms Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Metrics for the plate coupling problem using penalty technique . . . . . . 3.3 Metrics for the bearing problem using penalty technique . . . . . . . . . . 3.4 Metrics for the gear train problem using penalty technique . . . . . . . . . 3.5 Metrics for the plate coupling problem using boundary technique . . . . . 3.6 Metrics for the bearing problem using boundary technique . . . . . . . . . 3.7 Metrics for the gear train problem using boundary technique . . . . . . . 3.8 Results comparaison for the plate coupling problem . . . . . . . . . . . . . 3.9 Results comparaison for the bearing problem . . . . . . . . . . . . . . . . 3.10 Results comparaison for the gear train problem . . . . . . . . . . . . . . . 3.11 Comparison between penalty and boundary techniques for the plate coupling problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Comparison between penalty and boundary techniques for the bearing problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 Comparison between penalty and boundary techniques for the gear train problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Separation by anchor points: variation of the number of intervals in the separations of the problem P Mela . . . . . . . . . . . . . . . . . . . . . . . 3.15 Eight possible configurations for algorithm . . . . . . . . . . . . . . . . . . 3.16 Comparison between configurations for the plate coupling problem . . . . 3.17 Comparison between configurations for the bearing problem . . . . . . . . xiii xiv List of Tables 3.18 Time until convergence using the new hybrid . . . . . . . . . . . . . . . . 137 List of Figures 1.1 Plate coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Domain solutions for d and N fixed. . . . . . . . . . . . . . . . . . . . . . 1.3 The 428 solutions and those on the Pareto front in the variable space. . . 1.4 The 428 solutions and those on the Pareto front in the objective space. . . 1.5 The 25 Pareto solutions of the bolted coupling. . . . . . . . . . . . . . . . 1.6 Pivot connection with 2 single row bearings: isotatic mounting ball joint (R1) and linear annular (R2). . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Domain of solutions in the plane x 1 , x 2 for a given bearing pair (here i r1 = i r2 = 27, for the data of the table . . . . . . . . . . . . . . . . . . . . 1.8 The 442 feasible solutions with Pareto solutions in the space of x 1 and x 2 positions of (R1) and (R2) . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.9 The 442 feasible solutions with Pareto solutions in the F 1 and F 2 criteria space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10 Pareto front of the pivot bearing connection . . . . . . . . . . . . . . . . . 1.11 The 442 feasible solutions with Pareto solutions in the F 1 and F 2 criteria space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.12 Pareto front of the pivot bearing connection . . . . . . . . . . . . . . . . . 1.13 Example of a helical toothing and direction of stress on the toothing . . . 1.14 Pareto front dominance selection example with anchor points. . . . . . . . 1.15 Set of dominant Pareto fronts. . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Optimization in both discrete and continuous domain . . . . . . . . . . . 2.2 Decoding Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Hypervolume for two objective functions with R as reference point . . . . 3.1 Pareto fronts for the plate coupling problem using penalty technique . . . 3.2 Pareto fronts for the bearing problem using penalty technique . . . . . . . 3.3 Pareto fronts for the gear train problem using penalty technique . . . . . 3.4 Pareto fronts for the plate coupling problem using boundary technique . . 3.5 Pareto fronts for the bearing problem using boundary technique . . . . . . 3.6 Pareto fronts for the gear train problem using boundary technique . . . . xv xvi List of Figures 3.7 Solutions area and Pareto front of the problem P Mela . . . . . . . . . . . . 3.8 Anchor points for P Mela with l e = {0, 0, 0, 0} and u e = {3, 3, 3, 3} . . . . . 3.9 Anchor points for P Mela with l e = {1, 2, 2, 1} and u e = {2, 2, 2, 2} . . . . . 3.10 2 configurations of the P Mela problem in continuous variables for the integer variable vector z1 = {1, 2, 2, 1} et z2 = {3, 2, 2, 2} . . . . . . . . . . . . . . 3.11 Representative example of a branching tree into subspaces of combinations of the problem P MO-MINLP . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Illustration on the problem P Mela Branching by integer on the 1st integer variable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 Illustration for the problem P Mela Branching by anchor on the second vari-

  The 256 Pareto fronts of each combination and the final Pareto front of the P Mela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.19 Comparison of Pareto fronts; exact and obtained by the algorithm for P Mela 3.18 P Mela : Evolution of the number of nodes during separations for the default separation order : [3, 4, 5, 6] . . . . . . . . . . . . . . . . . . . . . . . . . . 3.20 P Mela : Evolution of the number of nodes during separations for all possible separation orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.21 P Mela : Evolution of the number of nodes during separations for all possible separation orders, fathoming and cleaning of the list N activated. . . . . . 3.22 Plate coupling problem: evolution of the number of nodes during separations for all possible separation orders, fathoming and cleaning of the list activated. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.23 Bearing problem: evolution of the number of nodes during separations for all possible separation orders, fathoming and cleaning of the list activated. 3.24 Pareto front for the plate coupling problem using exact solver and type:anchor -order:[1,2] -progress:breadth . . . . . . . . . . . . . . . . . . . . . . . . . 3.25 Pareto front for the bearing problem using exact solver and type:integerorder:[2,1] -progress:deep . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.26 Pareto front for the plate coupling problem using using best configuration with progress type set to deep . . . . . . . . . . . . . . . . . . . . . . . . . 3.27 Pareto front for the plate coupling problem using using best configuration with progress type set to breadth . . . . . . . . . . . . . . . . . . . . . . . 3.28 Pareto front for the bearing problem using best configuration with progress type set to deep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.29 Pareto front for the bearing problem using best configuration with progress type set to breadth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 -

 11 Figure 1.1 -Plate coupling

4 √

 4 {R b , M } T y = {i d , N } T d ∈ {6, 8, 10, 12, 14, 16, 20, 24}N ∈ [N Mini , N Maxi ] × N M ∈ [M T , M Maxi ]And:K(d) = 0.9R e f m π(d -0.93815ϕ 1 (d)) 2 16ϕ 1 (d)+0.583(d-0.6495ϕ 1 (d))f 1 ) d-0.93815ϕ 1 (d))Given :{N Mini , N Maxi , R Mini , R Maxi , e p , M T , . . . . . . M Maxi , α S , f 1 , f m , R e ,ρ J , ρ b } with: d: Nominal thread diameter [mm]. p: bolt thread pitch [mm].

f 1 :

 1 Coefficient of friction thread [].α S : Dispersion coefficient of the tightening tool > 1 []. R e : Elastic limit of the bolt depending on its quality class [MPa]. M : Torque transmitted by coupling [N m]. N : Number of bolts []. R b : Position radius of N bolts [mm]. f m : Coefficient of friction between the plates of the coupling []. s m : Circumference of the clamping tool, depending on b m and the installation radius of the N bolt[mm]. b m : Diameter of the holes in the rims, depending on the nominal diameter of the bolt d [mm]. e p : Thickness of the coupling rims [mm]. ρ J : Density of the rim material [kg/mm 3 ]. ρ b : Density of the bolt material [kg/mm 3 ]. d Maxi : Diameter of the largest bolts [mm]. N Mini : Minimum number of bolts []. N Maxi : Maximum number of bolts []. M T : Minimum torque that can be transmitted by adhesion [N m]. M Maxi : Maximum torque that can be transmitted by adhesion [N m]. R Mini : Minimal position radius of the bolts [mm]. R Maxi : Maximal position radius of the bolts [mm].

R b ≥ k 2

 2 with : k 2 = max { R Mini + ϕ 3 (i d ), ϕ 3 (i d )N k s π } For the constraint function c 4 (x) : R b ≤ k 3 with : k 3 = R Maxi -ϕ 3 (i d )The boundaries for the domain of the solutions are defined by the three inequalities above and by the boundaries M T and M Maxi on M . The values of the constants k1, k2 and k3 depend on d, N and the data of the optimization problem and give the position relative of the 4 boundaries of the domain. The domain of the solutions can then be easily represented in the plane of the variables R b and M . The following figure 1.7 is obtained: The points M i , i = 1 . . . 8 are determined by all the possible intersections of 2

Figure 1 . 2 -

 12 Figure 1.2 -Domain solutions for d and N fixed.

Figure 1 . 4 -

 14 Figure 1.4 -The 428 solutions and those on the Pareto front in the objective space.

Figure 1 . 5 -

 15 Figure 1.5 -The 25 Pareto solutions of the bolted coupling.

Figure 1 . 6 -

 16 Figure 1.6 -Pivot connection with 2 single row bearings: isotatic mounting ball joint (R1) and linear annular (R2).

:F a1, 2 :F r1, 2 :B 1 , 2 :D 1 , 2 : 1 , 2 :

 22121212 Lifespan expressed in hours []. ω : Speed of rotation of the tree expressed in [tr \min]. C : Dynamic load bearing capacity, intrinsic to rolling bearing [N]. P eq : Radial equivalent load [N]. Axial load for (R1) and (R2) [N]. Radial load for (R1) and (R2) [N]. X,Y : A dimensionless coefficient that depends on the bearing type and on the ratio Fa C 0 . C 0 : Static load bearing capacity, intrinsic to the rolling bearing [N]. Bearing width for (R1) and (R2) [mm]. Outside diameter of bearings for (R1) and (R2) [mm]. d 1,2 : Bearing inner diameter for (R1) and (R2) [mm]. d 1,2Min : Minimum bearing inner diameter for (R1) and (R2) [mm]. x 1,2Min : Minimum limit of bearings positions for (R1) and (R2) [mm]. x 1,2Max : Maximum limit of bearing positions for (R1) and (R2) [mm]. D Max : Maximum bearing mounting diameter [mm]. m Mass of bearings for (R1) and (R2) [g]. d a1,2 : Diameter of the necessary shoulders on the shaft for bearings for (R1) and (R2) [mm].ρ a : Shaft density [g/mm 3 ].

Figure 1 . 7 -

 17 Figure 1.7 -Domain of solutions in the plane x 1 , x 2 for a given bearing pair (here i r1 = i r2 = 27, for the data of the table

7 . 8 ×

 78 10 -3 g/mm 3 x 1Min = -200 mm x 1Max = -20 mm x 2Min = 20 mm x 2Max = 200 mm d 1Min = 10 mm d 2Min = 10 mm D Max = 200 mm .

Figure 1 . 8 - 1 F 1 :

 1811 Figure 1.8 -The 442 feasible solutions with Pareto solutions in the space of x 1 and x 2 positions of (R1) and (R2)

F 2 :

 2 Relative cost of bearings.

Figure 1 . 9 -

 19 Figure 1.9 -The 442 feasible solutions with Pareto solutions in the F 1 and F 2 criteria space

F 2 :

 2 Relative cost of bearings.

Figure 1 . 10 - 1 . 2 . 2 . 4 1 F 1 :

 110122411 Figure 1.10 -Pareto front of the pivot bearing connection

F 2 :

 2 Relative cost of bearings.

Figure 1 . 11 -

 111 Figure 1.11 -The 442 feasible solutions with Pareto solutions in the F 1 and F 2 criteria space

F 2 :

 2 Relative cost of bearings.

Figure 1 . 12 -

 112 Figure 1.12 -Pareto front of the pivot bearing connection

Figure 1 . 13 -

 113 Figure 1.13 -Example of a helical toothing and direction of stress on the toothing

3 .

 3 The driving factor is greater than 1.3 .

Figure 1 . 14 -

 114 Figure 1.14 -Pareto front dominance selection example with anchor points.

Figure 1 . 15 -

 115 Figure 1.15 -Set of dominant Pareto fronts.

Figure 2 . 1 -

 21 Figure 2.1 -Optimization in both discrete and continuous domain

6 :Crossover Percentage p crossover 7 : 17 : 18 : 19 :

 67171819 Mutation Percentage p mutation 8: Initialize the population 9: Generate N random solution and insert into Population 10: Evaluate objective values 11: Assign rank based on a Pareto sort 12: Generate Child Population of size N 13: Binary tournament selection 14: Crossover and Mutation according to p Crossover and p M utation 15: for i = 1 to Maximum Generations do 16: for each Parent and each Child in Population do Assign rank based on a Pareto sort Generate sets of non dominated solutions Determine the Crowding distance 20: Loop (inside) by adding solutions to next generations starting from the first front until N individuals 21:

4 :of bats n 5 :

 45 number Number of points on the Pareto front N 6:

5 : 6 : 7 :

 567 Number of points on the Pareto front N Maximum number of iterations M axGeneration or stop criterion Discovery rate of alien eggs/solutions pa 8: Generate an initial population of n host nestsx i (i = 1, 2, . . . , n) 9: for j = 1 → N (points on Pareto fronts) do 10: while (t <MaxGeneration) or (stop criterion) do 11:

20 :

 20 Pass the current best solutions to the next generation;

Figure 2 . 2 -

 22 Figure 2.2 -Decoding Process

Figure 2 . 3 -

 23 Figure 2.3 -Hypervolume for two objective functions with R as reference point

Figure 3 . 5 - 108 CHAPTER 3 .Figure 3 . 6 -

 35108336 Figure 3.5 -Pareto fronts for the bearing problem using boundary technique

Figure 3 . 7 -

 37 Figure 3.7 -Solutions area and Pareto front of the problem P Mela .

Figure 3 . 8 -

 38 Figure 3.8 -Anchor points for P Mela with l e = {0, 0, 0, 0} and u e = {3, 3, 3, 3}

Figure 3 . 9 -

 39 Figure 3.9 -Anchor points for P Mela with l e = {1, 2, 2, 1} and u e = {2, 2, 2, 2}

Figure 3 .

 3 Figure 3.10 -2 configurations of the P Mela problem in continuous variables for the integer variable vector z1 = {1, 2, 2, 1} et z2 = {3, 2, 2, 2}

PFigure 3 . 11 -

 311 Figure 3.11 -Representative example of a branching tree into subspaces of combinations of the problem P MO-MINLP .

120 CHAPTER 3 .

 1203 Proposition for hybrid algorithms f1(x, y) The "Ideal" point (P * I ) s of the node s is not dominated by the current Pareto edge F * P and the Pareto edge computed for the node s, (F * P ) s is partially dominated by F * P . The "Ideal" point (P * I ) s of the node s is not dominated by the current Pareto edge F * P and the Pareto edge computed for the node s, (F * P ) s is completely dominated by F * P .

Figure 3 . 14 -

 314 Figure 3.14 -Update of F * P in the case of a leaf node

Figure 3 .

 3 Figure 3.16 -llustration of different types of progression. The nodes are numbered in the order of creation.

Figure 3 . 17 -

 317 Figure 3.17 -The 256 Pareto fronts of each combination and the final Pareto front of the P Mela

  .19.

Figure 3 . 19 -

 319 Figure 3.19 -Comparison of Pareto fronts; exact and obtained by the algorithm for P Mela

Figure 3 .

 3 Figure 3.18 -P Mela : Evolution of the number of nodes during separations for the default separation order : [3, 4, 5, 6]

Figure 3 .

 3 Figure 3.20 -P Mela : Evolution of the number of nodes during separations for all possible separation orders

  (a) Integer separation, progression "deep first". (b) Anchor separation, progression "deep first". (c) Integer separation, progression "breadth first". (d) Anchor separation, progression "breadth first".

Figure 3 .

 3 Figure 3.21 -P Mela : Evolution of the number of nodes during separations for all possible separation orders, fathoming and cleaning of the list N activated.

  Number of leaf nodes Number of Pareto Sol. (b) Anchor separation, progression "deep first".

  (c) Integer separation, progression "breadth first".

  (d) Anchor separation, progression "breadth first".

Figure 3 . 22 -

 322 Figure 3.22 -Plate coupling problem: evolution of the number of nodes during separations for all possible separation orders, fathoming and cleaning of the list activated.

  Number of leaf nodes Number of Pareto Sol. (b) Anchor separation, progression "deep first".

  (c) Integer separation, progression "breadth first".

  (d) Anchor separation, progression "breadth first".

Figure 3 . 23 -

 323 Figure 3.23 -Bearing problem: evolution of the number of nodes during separations for all possible separation orders, fathoming and cleaning of the list activated.

••

  Initialisation Distance entre les individus • Solution mise à jour • Création des quartiers

  [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF], Michalewicz et al. ont proposé de classer ces techniques en 4 classes :[START_REF] Abramson | Mesh adaptive direct search algorithms for mixed variable optimization[END_REF] méthodes basées sur la préservation de la faisabilité des solutions, (2) les méthodes basées sur les fonctions de pénalité, (3) les méthodes basées sur la recherche de solutions faisables (4) autres méthodes hybrides. Dans[START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF], Coello introduisait une classification différente où ces techniques sont classes en 5 classes : (1) Fonctions de pénalité (2) représentations spéciales et les opérateurs, (3) algorithmes de réparation, (4) Séparation des objectifs et des contraintes, (5) Méthodes hybrides. Les deux références précédentes traitaient les techniques pour manipuler les contraintes dans le cas unique où les méta-heuristiques d'optimisation sont les algorithmes évolutionnaires. De leur part, Mezura et al.[START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF] ont présenté une revue de la littérature des techniques pour adapter les algorithmes inspirés de la nature (algorithmes évolutionnaires y inclus parmi d'autres) aux problèmes d'optimisation avec contraintes. Ils ont abordé ce problème en divisant ces techniques en : anciennes, actuelles et futuristes.

•• 147 •

 147 Décodage Localisation des limites des régions faisables Hybridation Règles de faisabilité • Classement stochastique • ε-constraint, méthode • Techniques d'optimisation multi-objectifs

  Nous pouvons combiner (a) différentes stratégies métaheuristiques, (b) des métaheuristiques avec certains algorithmes spécifiques au problème que nous considérons, tels que des simulations spéciales, ou (c) des métaheuristiques avec d'autres techniques plus générales provenant de domaines tels que la recherche opérationnelle (OR) et Intelligence artificielle (AI). Des exemples marquants des méthodes d'optimisation d'autres domaines qui ont été combinés avec succès avec les métaheuristiques sont des approches exactes telles que la programmation dynamique, Branch & Bound, et diverses techniques de integer linear programming d'un côté et des techniques de calcul soft telles que les réseaux neuronaux et la logique floue de l'autre côté . Niveau d'hybridation Distinguer le niveau auquel les différents algorithmes sont combinés : Les combinaisons de haut niveau conservent en principe les identités individuelles des algorithmes originaux et coopèrent sur une interface relativement bien définie ; Il n'y a pas de relation directe, forte du fonctionnement interne des algorithmes. Au contraire, les algorithmes dans les combinaisons de bas niveau dépendent fortement les uns des autres et les composants individuels sont échangés.

Figure 3 . 33 -

 333 Figure 3.33 -Liaison pivot avec 2 roulements à une rangée de billes : montage isotatique rotule (R1) et linéaire annulaire (R2).

2 .

 2 Un principe, que nous nommerons "séparation par les points d'ancrages", qui consiste à utiliser l'information fournie par l'évaluation du noeud courant en se servant les points d'ancrages du front Pareto calculé via la minimisation des fonctions objectifs f k (x, y) , k = {1, . . . , p}. Avec p fonctions objectifs on obtient donc au maximum p points d'ancrages du Front de Pareto.

  problèmes de conception mécanique sont des problèmes d'optimisation. Ces problèmes d'optimisation possèdent trois caractéristiques qui les rendent difficiles à résoudre. Ces caractéristiques sont la nature mixte des variables (continues et discrètes), l'existence de contraintes non linéaires et la présence de plusieurs critères non linéaires à minimiser pour guider les décisions de conception. Pour aborder ces problèmes, notre approche consiste d'abord à définir des problèmes tests représentatifs de ces difficultés, pour lesquels nous pouvons calculer le front théorique de Pareto. Les performances de cinq méthodes métaheuristiques « traditionnelles » d'optimisation intégrant une amélioration spécifique pour gérer les particularités des problèmes de référence ont été testées. Puis, suite à l'incapacité de ces métaheuristiques « traditionnelles » modifiées de répondre à certaines métriques d'évaluation, un nouvel algorithme hybride couplant métaheuristiques et l'algorithme Branch & bound a été introduit. L'algorithme hybride combine les avantages des métaheuristiques (efficacité pour les problèmes multi-objectifs non linéaires) et l'exploration systématique avec des variables mixtes des algorithmes Branch & bound. Ce nouvel algorithme hybride comprenant des techniques de branchement spécifique est bien adapté pour résoudre des problèmes mixtes multiobjectifs non-linéaires. Il donne de meilleurs résultats sur ces problèmes tests que les métaheuristiques « traditionnelles » et ouvre de nombreuses perspectives d'améliorations Mots clés : optimisation combinatoire -métaheuristiques -décision multicritère -mécanique appliquée -conception technique. design problems are optimization problems. These optimization problems hold three characteristics that make them difficult to solve. These characteristics are the mixed nature of the variables (continuous and discrete), the existence of non-linear constraints and the presence of multiple non-linear criteria or objectives that needs to be minimized to guide the decision making. To tackle such problems, our approach consisted on defining a benchmark of representative test problems that capture the essence of these difficulties, for which we can calculate the theoretical Pareto front. The performance of five ''traditional'' metaheuristics algorithms that integrates specific enhancement to handle particularities of the benchmark problems was tested. Then, in light of the shortcomings of these ''traditional'' modified metaheuristics to meet certain evaluation metrics, a new hybrid algorithm that couples metaheuristics and branch & bound was introduced. The hybrid algorithm combines the advantages of metaheuristics like its efficiency for non-linear multi-objective problems alongside with systematic exploration of mixed variables that branch & bound algorithms have. This new hybrid algorithm including specific branching techniques is well suited for solving nonlinear multi-objective mixed problems. It gives better results than "traditional" metaheuristics on the test problems and opens up many prospects for improvement. Keywords: combinatorial optimization -metaheuristic -multiple criteria decision making -mechanics, applied -engineering design.

  . . . . . . 3.14 Update of F * P in the case of a leaf node . . . . . . . . . . . . . . . . . . . 3.15 Update of F * P in the case of a node that is not a leaf. Successive separations of the s node will explore the hypervolume defined by the anchor points. . 3.16 llustration of different types of progression. The nodes are numbered in the order of creation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.17

1.1 Formulation of the general optimization problem 7 1.2 Optimization problem 8

  1.2.1 Plate coupling: dimensioning model . . . . . . . . . . . . . 9 1.2.2 Ball bearing pivot connection: dimensioning model . . . . . 18 1.2.3 Multi objective optimization of a gear train . . . . . . . . . 29

Table 1 .

 1 1 -Standardized values of parameters depending on diameter d of bolts

	.1 specifies the

Table 1 .

 1 2 -coupling dataThe value of R Mini is determined by R pg = 100 MPa.

		110								d=5
										d=6
										d=8
		100								d=10
										d=12
										d=14
		90								d=16
	Rb [mm]	80								d=20 d=24 d=27 d=30
		70
		60
		0.4	0.6	0.8	1	1.2	1.4	1.6	1.8	2
						M [N mm]			•10 7
	Figure 1.3 -The 428 solutions and those on the Pareto front in the variable space.

Table 1 .

 1 3 -The 25 Pareto solutions of the bolted coupling.

	5 40 111.80 4.000 • 10 6	0.119	0.29	0.000 -0.208 -2.042 -0.013
	5 41 109.10 4.000 • 10 6	0.117	0.30	0.000 -0.168 -1.968 -0.037
	5 42 106.50 4.000 • 10 6	0.115	0.30	0.000 -0.127 -1.898 -0.060
	5 43 104.00 4.000 • 10 6	0.113	0.31	0.000 -0.085 -1.830 -0.082
	5 44 101.60 4.000 • 10 6	0.111	0.31	0.000 -0.041 -1.766 -0.103
	5 45	99.64 4.000 • 10 6	0.109	0.32 -0.003	0.000 -1.711 -0.120
	6 33 109.20 4.000 • 10 6	0.138	0.26	0.000 -0.207 -1.873 -0.025
	6 34 106.00 4.000 • 10 6	0.135	0.26	0.000 -0.158 -1.789 -0.054
	6 35 102.90 4.000 • 10 6	0.132	0.27	0.000 -0.108 -1.709 -0.081
	6 36 100.10 4.000 • 10 6	0.130	0.28	0.000 -0.056 -1.634 -0.106
	6 37	97.37 4.000 • 10 6	0.127	0.28	0.000 -0.003 -1.562 -0.131
	8 19 104.10 4.000 • 10 6	0.165	0.19	0.000 -0.387 -1.587 -0.051
	8 21	94.22 4.000 • 10 6	0.153	0.21	0.000 -0.251 -1.341 -0.142
	8 22	89.93 4.000 • 10 6	0.147	0.21	0.000 -0.178 -1.234 -0.181
	8 23	86.02 4.000 • 10 6	0.143	0.22	0.000 -0.101 -1.137 -0.216
	8 24	82.44 4.000 • 10 6	0.139	0.22	0.000 -0.021 -1.048 -0.249
	10 12 104.00 4.000 • 10 6	0.205	0.17	0.000 -0.508 -1.419 -0.028
	10 13	96.03 4.000 • 10 6	0.192	0.18	0.000 -0.423 -1.233 -0.103
	10 14	89.17 4.000 • 10 6	0.181	0.18	0.000 -0.330 -1.074 -0.167
	10 15	83.22 4.000 • 10 6	0.172	0.19	0.000 -0.231 -0.936 -0.222
	10 16	78.02 4.000 • 10 6	0.164	0.19	0.000 -0.126 -0.815 -0.271
	12 10	85.88 4.000 • 10 6	0.190	0.18	0.000 -0.456 -0.941 -0.188
	12 11	78.07 4.000 • 10 6	0.176	0.18	0.000 -0.341 -0.764 -0.262
	12 12	71.57 4.000 • 10 6	0.165	0.19	0.000 -0.216 -0.617 -0.323
	12 13	66.06 4.000 • 10 6	0.157	0.19	0.000 -0.080 -0.493 -0.375

1 : relative weight

Table 1 .

 1

	rr [mm]	Code

Table 1 .

 1 -31.50 31.54 1.56 • 10 -1 3.53 • 10 -1 -2.45 • 10 -9 -4.40 • 10 2 -157.00 0.00 -2.54 -159.5 -30.00 -50.00 -105.00 -5.00 6 -Pareto solutions for pivot connection with ball bearings.

	00 0.00	0.00 -157 -20.00 -20.00 -110.00	0.00

27 -31.50 31.50 1.16 • 10 -1 4.36 • 10 -1 -2.63 • 10 3 -1.45 • 10 4 -157.1 : Relative weight of the shaft.

Table 1 .

 1 -31.50 30.60 0.1477 0.1762 -2.47 • 10 2 3.64 • 10 -12 -157.00 0.00 -1.60 -160.40 -30.00 -50.00 -105.00 -5.00 7 -Pareto solutions for pivot connection with ball bearings.

	00 0.00	0.00 -157.00 -20.00 -20.00 -110.00	0.00

27 27 -31.50 31.50 0.111 0.2180 -2.63 • 10 3 -1.45 • 10 4 -157.1 : Relative weight of the shaft.

  n z

	An excerpt of these ratios gives:
	{ 83 11	,	84 11	,	85 11	, . . . ,	300 38	,	300 39	,	300 40

Table 1 .

 1 9 -The 23 Pareto solutions of the gear.

	1.2. Optimization problem

Hybrid Metaheuristics For Mixed Variables Optimization Outline of the current chapter 2.1 Mixed variables 42 2.2 Optimization algorithms 45 2

  .2.1 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2.2 Metaheuristics for mixed variables problems . . . . . . . . . 55 2.2.3 Exact methods . . . . . . . . . . . . . . . . . . . . . . . . .

	fairly mature. And the time has come to put its framework.
		61
	2.3 Hybridization	62
	2.3.1 Coupling metaheuristics with exact methods . . . . . . . . .	62
	2.3.2 Coupling metaheuristics with other metaheuristics . . . . .	64
	2.3.3 Hybrid multi-objective optimization . . . . . . . . . . . . .	68
	2.3.4 Constraint handling as toolbox for hybridization . . . . . .	71
	2.4 Evaluation of hybrids	79
	2.4.1 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	80
	2.4.2 Computational effort . . . . . . . . . . . . . . . . . . . . . .	84
	2.4.3 Statistical assessment . . . . . . . . . . . . . . . . . . . . . .	84
	2.4.4 Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . .	85
	Hybrid metaheuristics are not new techniques. As a matter of fact, the notion of hybrid
	metaheuristics started with the invention of metaheuristics themselves. The huge number
	of publications on hybrid metaheuristics proves that these techniques are quite famous
	and effective.
	Usually hybrid metaheuristics are hard to implement, because they are very dependent
	of the problem at hand. Most hybridization attempts are ad-hoc approaches. There is
	almost no systematic way to choose, implement or test hybrids. Perhaps that allowed
	creativity at first when hybrid metaheuristics was still a new and emerging field. But
	nowadays, with the enormous number of publications each year, this field is considered

10 :

 10 Mutation rate µ 11: Generate initial particles 12: Evaluate fitness values of initial particles 13: Create the best personal memory 14: Create the best global memory 15: Create grid index for solution dimension 16: Find repository member 17: Find grid for repository members

18:

for i = 1 to M axGeneration do

19:

  Results analysis . . . . . . . . . . . . . . . . . . . . . . . . . 99

	3.1 Adapting meta heuristics to handle constraints	87
	3.1.1 Using the first constraint handling technique (penalty) . . .	91
	3.1.2 Using the second constraint handling technique (boundary)	97
	3.1.3 3.2 Hybridizing meta heuristics and branch & bound	109
	3.2.1 Hybrid's explanation throughout a literature test problem .	109
	3.2.2 Proposal of a Branch and Bound algorithm . . . . . . . . .	123
	3.2.3 Optimization results for the three optimization problems using
	the new hybrid .

. . . . . . . . . . . . . . . . . . . . . . . . 130

.1 Using the first constraint handling technique (penalty) 3.1.1.1 Plate coupling problem

	3.1. Adapting meta heuristics to handle constraints 92 CHAPTER 3. Proposition for hybrid algorithms 91 3.1. Adapting meta heuristics to handle constraints 93 94 CHAPTER 3. Proposition for hybrid algorithms 3.1. Adapting meta heuristics to handle constraints 95 96 CHAPTER 3. Proposition for hybrid algorithms 3.1. Adapting meta heuristics to handle constraints 97
	Maximum Number of Iterations 100 Maximum Number of Iterations 100 Personal Learning Coefficient 1 Maximum Number of Iterations 200 Frequency minimum (a) NSGA II Table 3.2 -Metrics for the plate coupling problem using penalty technique Population Size Crossover Percentage Mutation Percentage 100 0.7 0.4 MOPSO Population Size Repository Size Inertia Weight 100 100 0.5 Global Learning Coefficient Mutation Rate -2 0.1 -Population Size Loudness Pulse rate 30 0.25 0.5 Frequency maximum Number of Pareto points -Plate pb=70 (b) MOPSO True front Best front Average front Worst front Relative cost 0.22 0.24 0.26 0.28 0.4 0.45 0.5 Table 3.3 -Metrics for the bearing problem using penalty technique Relative friction 0.3 0.4 0.5 0.6 Table 3.4 -Metrics for the gear train problem using penalty technique Relative cost of bearings 0.7 0.3 0.32 0.34 True front Best front Average front Worst front Best 68 8.569 • 10 -4 1.105 602.42 cuckoo Average 28 5.369 • 10 -4 1.400 577.37 Worst 32 9.145 • 10 -4 0.643 594.37 (a) NSGA II (b) MOPSO True front Best front Average front Worst front 0.55 True front Average front Worst front Worst 0 0.149 0.441 573.20 Average front Worst front 0.8 Average front Worst front Worst 0 1.262 • 10 -2 0.868 3,769.08 Best front cuckoo Average 0 8.230 • 10 -2 0.593 602.25 True front Best front 0.9 True front Best front cuckoo Average 0 5.459 • 10 -3 0.664 3,487.62 0.6 Best 0 3.970 • 10 -2 0.409 588.62 (a) NSGA II (b) MOPSO 1 Best 4.35 3,587.90 4.338 • 10 -3 0.710 MOBA 0.12 0.14 0.16 0.18 0.2 0.22 0.24 True front Best front Average front Worst front Relative weight 0.1 0.12 0.14 0.16 0.18 0.2 0.22 0.24 Relative cost 0.16 0.18 0.2 0.22 0.24 0.26 0.28 0.3 0.32 0.34 True front Best front Average front Worst front solutions convergence [s] Best 0 1.200 • 10 -3 0.320 255.52 MOPSO Average 48 1.800 • 10 -3 1.064 236.95 Worst 36 1.800 • 10 -3 0.855 212.57 Best 40 7.684 • 10 -4 1.107 362.54 NSGA Average 40 1.600 • 10 -3 0.788 303.39 Worst 44 2.200 • 10 -3 0.881 294.25 Best 40 7.419 • 10 -4 1.193 413.61 MOBA Average 24 7.560 • 10 -4 1.034 385.53 Worst 20 5.057 • 10 -4 0.467 426.87 Best 48 3.085 • 10 -4 0.679 542.47 firefly Average 8 8.757 • 10 -4 0.669 477.31 Worst 0 1.200 • 10 -3 0.320 542.47 Relative weight of the shaft 0.2 0.3 0.4 0.5 0.6 True front Best front Average front Worst front Relative weight of the shaft 0.1 0.2 0.3 0.4 0.5 0.6 Relative cost of bearings 0.3 0.35 0.4 0.45 0.5 0.55 0.6 True front Best front Average front Worst front solutions convergence [s] Best 0 5.020 • 10 -2 0.711 472.40 MOPSO Average 0 6.010 • 10 -2 0.843 474.59 Worst 0 7.370 • 10 -2 0.434 486.83 Best 25 2.844 • 10 -5 0.667 447.80 NSGA Average 0 5.710 • 10 -2 0.709 294.86 Worst 25 3.600 • 10 -3 1.188 476.31 Best 0 2.020 • 10 -2 0.684 439.41 MOBA Average 0 6.070 • 10 -2 0.568 413.32 Worst 0 8.510 • 10 -2 0.585 406.86 Best 25 1.900 • 10 -3 1.009 250.34 firefly Average 0 2.400 • 10 -3 0.678 463.26 Worst 0 7.490 • 10 -2 0.429 352.72 Relative volume 0.35 0.4 0.45 0.5 True front Best front Average front Worst front Relative volume 0.3 0.35 0.4 0.45 0.5 Relative friction 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 True front Best front Average front Worst front solutions convergence [s] Best 26.09 3.600 • 10 -3 0.827 3,205.80 MOPSO Average 21.74 3.800 • 10 -3 0.811 2,427.00 Worst 0 4.800 • 10 -3 0.670 3,213.40 Best 43.48 3.500 • 10 -3 0.755 2,267.00 NSGA Average 0 7.500 • 10 -3 0.603 2,400.90 Worst 0 2.800 • 10 -3 0.520 2,599.70 Best 0 4.100 • 10 -3 0.725 2,856.80 MOBA Average 0 3.600 • 10 -3 0.679 2,642.10 Worst 0 3.400 • 10 -3 0.392 2,707.30 Best 4.35 4.100 • 10 -3 0.633 3,305.50 firefly Average 0 1.400 • 10 -3 0.244 3,322.20 Worst 0 4.300 • 10 -3 0.271 3,041.70 3.1Relative weight Relative cost 0.22 0.24 0.26 0.28 0.3 0.32 0.34 Relative cost of bearings 0.4 0.45 0.5 Relative friction 0.3 0.4 0.5 0.6 0.7 0.55 0.6 0.8 0.9 1 0.1 Relative cost 0.16 0.18 0.2 0.22 0.24 0.26 0.28 0.3 0.32 0.34 0.1 Relative cost of bearings 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.3 Relative friction 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Algo. Iter % of GD ∆ Time until 3.1.1.2 Bearing Algo. Iter % of GD ∆ Time until 3.1.1.3 Gear train Algo. Iter % of GD ∆ Time until 3.1.
	0.2 0.2	0					0	0.2 0.2		Bearing pb=10	-
	0.35 0.18 0.1							0.35 0.18 0.1		Gear pb=100
	0.1 0.16 0.1 0.3 0 0.3	Maximum Number of Iterations Relative weight 0.12 0.14 0.16 0.18 Relative weight of the shaft 0.2 0.3 0.4 0.35 0.4 Relative volume (c) Firefly (c) Firefly (c) Firefly 200 0.3 0.32 0.6 1 0.34 0.55 0.9 0.8	0.2 0.45	Firefly Population Size 0.22 0.24 0.1 0.12 0.16 0.5 0.6 0.1 0.2 0 0.3 0.5 0.3 0.35 0.14 Absorption coefficient 0.16 0.18 Relative weight of the shaft 0.3 0.4 0.4 Relative volume Relative weight (d) Cuckoo (d) Cuckoo (d) Cuckoo 50 1 True front Best front Average front Worst front True front True front Best front Best front Average front Average front Worst front Worst front	0.2 0.45	0.22 0.5 Pareto points 0.24 0.5 0.6 Number of Plate pb=70 Bearing pb=10
		Maximum Number of Iterations Relative cost 0.22 0.24 0.26 0.28 0.4 0.45 0.5 Relative friction 0.3 0.4 0.5 0.6 Relative cost of bearings 0.7			Cuckoo Population Size Discovery rate of alien eggs	Gear pb=100 Number of Pareto points
			0.2 0.2
			0.35 0.18 0.1							Plate pb=70
		150	0.1 0.16 0.1 0.3 0.3 0	0.12	0.14 0.35 0.2	40 Relative weight Relative weight of the shaft Relative volume 0.16 0.18 0.3 0.4 0.4	0.2 0.45	0.22 0.5	0.25 0.24 0.6 0.5	Bearing pb=10 Gear pb=100
						(e) MOBA (e) MOBA (e) MOBA
				Table 3.1 -Algorithms Parameters
	Figure 3.1 -Pareto fronts for the plate coupling problem using penalty technique Figure 3.2 -Pareto fronts for the bearing problem using penalty technique Figure 3.3 -Pareto fronts for the gear train problem using penalty technique

2 Using the second constraint handling technique (boundary)

	3.1.2.2 Bearing 3.1.2.3 Gear train
	Algo.	Iter	% of		GD		∆	Time until
			solutions					convergence [s]
		Best	0	4.500 • 10 -3 0.647	2,316.20
	MOPSO Average	0	4.800 • 10 -3 0.626	2,048.80
		Worst	0	5.100 • 10 -3 0.632	2,139.20
	Best 3.1.2.1 Plate coupling NSGA Average	21.74 0	2.438 • 10 -3 0.852 8.200 • 10 -3 0.900	2,880.93 2,371.51
		Worst	0	5.794 • 10 -3 0.618	2,251.97
		Best	0	4.174 • 10 -3 0.649	2,575.61
	MOBA Average	0	4.278 • 10 -3 0.603	2,437.65
		Worst	0	6.795 • 10 -3 0.653	2,551.84
		Best	0	6.301 • 10 -3 0.402	2,606.34
	firefly	Average	0	1.638 • 10 -2 0.890	2,728.47
		Worst	0	4.963 • 10 -3 0.640	2,713.37
		Best	0	4.958 • 10 -3 0.605	2,264.06
	cuckoo Average	0	5.259 • 10 -3 0.586	2,937.93
		Worst	0	4.054 • 10 -3 0.567	2,872.59
	Algo.	Iter Algo.	% of Iter	% of	GD	GD	∆	Time until ∆ Time until
			solutions solutions			convergence [s] convergence [s]
		Best	72 Best	8.810 • 10 -4 1.335 25 2.433 • 10 -5 0.734 177.33	382.11
	MOPSO Average MOPSO Average 20	4.369 • 10 -4 0.450 0 8.220 • 10 -2 0.594 173.41	98.83
		Worst	12 Worst	9.640 • 10 -4 0.690 0 0.131	132.44 0.555	295.93
		Best	44 Best	8.787 • 10 -4 1.429 25 6.946 • 10 -4 0.646 125.76	125.76
	NSGA	Average NSGA Average 40	1.700 • 10 -3 0.832 25 1.109 • 10 -4 0.866 98.83	315.31
		Worst	44 Worst	2.700 • 10 -3 0.826 0 7.780 • 10 -2 0.476 140.17	140.17
		Best	36 Best	8.580 • 10 -4 1.421 25 1.282 • 10 -5 0.385 264.11	293.44
	MOBA Average MOBA Average 12	9.640 • 10 -4 0.690 0 6.340 • 10 -2 0.451 298.97	298.97
		Worst	8 Worst	2.100 • 10 -3 0.457 0 0.108	293.44 0.569	222.16
		Best	24 Best	7.163 • 10 -4 0.769 0 5.130 • 10 -2 0.499 288.84	237.97
	firefly	Average firefly Average 28	4.270 • 10 -4 0.503 0 0.163	385.23 0.414	379.58
		Worst	32 Worst	1.700 • 10 -3 1.223 0 0.152	237.97 0.615	288.84
		Best	24 Best	7.943 • 10 -4 0.724 25 5.569 • 10 -5 0.704 363.54	363.54
	cuckoo Average cuckoo Average 12	8.284 • 10 -4 0.599 0 9.900 • 10 -3 0.483 336.71	375.53
		Worst	44 Worst	1.200 • 10 -3 1.405 0 7.120 • 10 -2 0.539 343.96	303.29
	Table 3.5 -Metrics for the plate coupling problem using boundary technique Table 3.6 -Metrics for the bearing problem using boundary technique

Table 3 .

 3

7 -Metrics for the gear train problem using boundary technique

Table 3 .

 3 .8 for the first problem, table3.9 for the second problem and table 3.10 for the third one. For each problem, the overall best metaheuristic is the one with most occurrences in the corresponding table. From that we get:

	• Cuckoo, NSGAII and Firefly are the overall best metaheuristics for the first problem
	(3 occurrences).

8 -Results comparaison for the plate coupling problem

  Upper bound of separation number: s Max ← n nodes -1

	• F * P ← F * P +	{ (P * 1 ) 0 , . . . , (P * k ) 0 , . . . , (P * p ) 0	} .
	• In the case of improved initialization add solutions in F * P .
	• s ← 0
	•

2: while N ̸ = {∅} AND s ≤ s Max do 3:

  Solving P MO-NLP (ȳ s ′ ) with ȳs ′ ← ( le ) s ′ .

	7: 8:	if (P * I ) s ′ dominates F * P then F * P ← F * P + { (P * 1 ) s ′ , . . . , (P * k ) s ′ , . . . , (P * p ) s ′	}
	9:	if ( le ) s ′ = (ū e ) s ′ then
	10:
	11:	F * P ← F * P + (F * P ) s ′
	12:	end if
	13:	Pareto filtering of F * P .
	14:	N ← N + {N s ′ }
	15:	end if
	16:	end if
	17:	s ← s + 1
	18:

Table 3 .

 3 [START_REF] Brimberg | Variable Neighborhood Descent for the Capacitated Clustering Problem[END_REF] -Separation by anchor points: variation of the number of intervals in the separations of the problem P Mela

	Number of separations 516 525 548 548
	Nb. sep. for 1 intervalle 76	92	80	91
	Nb. sep. for 2 intervalles 115 101 133 149
	Nb. sep. for 3 intervalles 70	77	61	53

3.2.3.1 Best configuration for plate coupling and bearing problems

  Now that the new hybrid algorithm is fully explained, the next step is to test it on the three optimization problems. In order to test effectiveness of our algorithm and choose the best configuration for the two first problems, we chose to test all the 8 possible

	Seperation type Seperation order Progress
	Anchor	[1 2]	Breadth
	Anchor	[1 2]	Deep
	Anchor	[2 1]	Breadth
	Anchor	[2 1]	Deep
	Integer	[1 2]	Breadth
	Integer	[1 2]	Deep
	Integer	[2 1]	Breadth
	Integer	[2 1]	Deep
	Table 3.15 -Eight possible configurations for algorithm
	configurations (see table

Configuration Seperation type Seperation order Progress Separations

			1
								True front
			0.95					Optimal front
			0.9
			0.85
		Relative cost	0.7 0.75 0.8
			0.65
			0.6
			0.55
			0.5
			0.5	0.6	0.7	0.8	0.9	1
						Relative weight
	Figure 3.24 -Pareto front for the plate coupling problem using exact solver and
		type:anchor -order:[1,2] -progress:breadth
			0.24
								True front
			0.23					Optimal front
			0.22
		Relative cost of bearings	0.19 0.2 0.21
			0.18
			0.17
			0.16
			0.1	0.11	0.12	0.13	0.14	0.15	0.16
					Relative weight of the shaft
	Figure 3.25 -Pareto front for the bearing problem using exact solver and type:integer -
		order:[2,1] -progress:deep
	1	Anchor			[1 2]	Breadth	125
	2	Anchor			[1 2]	Deep	125
	3	Anchor			[2 1]	Breadth	126
	4	Anchor			[2 1]	Deep	126
	5	Integer			[1 2]	Breadth	358
	6	Integer			[1 2]	Deep	358
	7	Integer			[2 1]	Breadth	409
	8	Integer			[2 1]	Deep	409

Table 3 .

 3 16 -Comparison between configurations for the plate coupling problem

	Configuration Seperation type Seperation order Progress separations
	1	Anchor	[1 2]	Breadth	798
	2	Anchor	[1 2]	Deep	798
	3	Anchor	[2 1]	Breadth	858
	4	Anchor	[2 1]	Deep	858
	5	Integer	[1 2]	Breadth	1159
	6	Integer	[1 2]	Deep	1159
	7	Integer	[2 1]	Breadth	854
	8	Integer	[2 1]	Deep	915

Table 3 .

 3 17 -Comparison between configurations for the bearing problem

		1
							True front
		0.95					Optimal front
		0.9
		0.85
	Relative cost	0.7 0.75 0.8
		0.65
		0.6
		0.55
		0.5
		0.5	0.6	0.7	0.8	0.9	1
				Relative weight
	Figure 3.26 -Pareto front for the plate coupling problem using using best configuration
	with progress type set to deep
		1
							True front
		0.95					Optimal front
		0.9
		0.85
	Relative cost	0.75 0.8
		0.7
		0.65
		0.6
		0.55
		0.5
		0.5	0.6	0.7	0.8	0.9	1
				Relative weight
	Figure 3.27 -Pareto front for the plate coupling problem using using best configuration
	with progress type set to breadth

•

  Branch & bound[START_REF] Land | An automatic method of solving discrete programming problems[END_REF] Les algorithmes Branch & bound sont un principe algorithmique assez ancien(1958)(1959)(1960) développé à l'origine par[START_REF] Laurence | Linear Programming with Pattern Constraints[END_REF],[START_REF] Markowitz | On the Solution of Discrete Programming Problems[END_REF] et[START_REF] Land | An Automatic Method of Solving Discrete Programming Problems[END_REF] pour résoudre des problèmes de programmation économique linéaire avec des variables entières. L'algorithme Branch & bound est basé sur une énumération de solutions candidates au moyen d'une recherche d'espace d'état : l'ensemble des solutions candidates est considéré comme un arbre enraciné[START_REF] Murphy | Machine learning: a probabilistic perspective[END_REF]. La partie d'énumération est appelée branchement tandis que la limite fait référence à l'analyse de solutions possibles par comparaison à une limite inférieure ou supérieure connue sur la valeur de la solution[START_REF] Socha | Ant colony optimisation for continuous and mixed-variable domains[END_REF]. L'algorithme explore les branches de cet arbre, qui représentent des sous-ensembles de l'ensemble de solutions. Avant d'énumérer les solutions candidates d'une branche, la branche est vérifiée par rapport aux bornes estimées inférieure et supérieure de la solution optimale, et rejetée si elle ne peut pas

	Problèmes d'optimisation
	Pour aborder les difficultés mentionnées dans II, notre approche consiste d'abord à définir
	des problèmes tests représentatifs de ces difficultés, pour lesquels nous pouvons calculer
	le front théorique de Pareto. Les performances de cinq algorithmes métaheuristiques
	«traditionnelles» d'optimisation intégrant une amélioration spécifique pour gérer les
	particularités des problèmes de référence ont été testées.

Accouplement à plateaux : modèle de dimensionnement Présentation du problème

	French Summary
	Figure 3.32 -Accouplement à plateaux boulonnés
	On considère une fonction technique simple "transmettre un couple" entre 2 arbres
	parallèle et parfaitement co-axiaux. On choisit d'utiliser le principe physique d'une
	transmission d'effort par adhérence. Ce principe nécessite la présence d'un effort normal
	entre les 2 surfaces en contact, effort normal ou "presseur" que l'on choisit de réaliser
	technologiquement par des éléments filetés. La figure 3.32 montre une conception possible
	de ce type de mécanisme. On souhaite dimensionner ce mécanisme pour minimiser son
	coût et sa masse.

Liaison pivot par roulement à billes : modèle de dimensionnement Présentation du problème

  On considère une fonction technique simple "liaison pivot" permettant de guider en rotation un arbre transmettant une puissance mécanique donnée. On se place ici dans l'hypothèse d'une liaison pivot réalisée par deux roulements à une rangée de billes. Le montage étudié est celui d'un montage isostatique (figure3.33) où l'un des roulements est assimilé à une liaison rotule (R1) et l'autre (R2) à une liaison linéaire annulaire.On souhaite dimensionner ce mécanisme pour minimiser son coût et sa masse. Les efforts appliqués sur l'arbre sont modélisés par un torseur exprimé au point O le centre de la liaison et l'origine du repère pour définir les positions x 1 et x 2 des roulements.

	Problèmes d'optimisation	153
	x 1	x 2
	x 1Max
	x 1Min	x 2Max

  1. Un problème d'optimisation mono objectif en variables mixtes, où l'on minimisera indépendamment chacune des fonctions objectifs du problème P MO-MINLP . Ici on minimise chaque fonction objectif f k (x), k = {1, . . . , p} indépendamment des autres, BnB hybride 155 sous les contraintes originales du problème P MO-MINLP . Le problème P MINLP ( le , ūe ) est donc à priori plus facile à résoudre que le problème original P MO-MINLP et il existe plusieurs algorithmes pour cela. On peut citer comme précédemment les métaheuristiques évolutionnaires, les techniques branch & bound, ... 2. Un problème multi-objectif en variables continues en considérant que les variables entières ont des valeurs fixées. Il existe donc un nombre fini de sous-problèmes du type P MO-NLP (ȳ) issus du problème P MO-MINLP . Ce nombre dépend du nombre de combinaisons possibles de toutes les valeurs admissibles des variables entières. Par exemple avec n e variables entières, admettant chacune 10 valeurs, il existerait 10 ne combinaisons donc n Conf = 10 ne "configurations" du problème P MO-NLP . Ce problème P MO-NLP (ȳ) est plus facile à résoudre que le problème original P MO-MINLP . Il existe de nombreux algorithmes reconnus comme efficace dans la littérature comme : les méta-heuristiques évolutionnaires, les algorithmes déterministes à base gradient comme NBI, ou "ε contraints" et dans la mesure où le problème P MO-NLP est convexe les techniques d'agrégations permettant de ramener P MO-NLP à un problème nono-objectif [93].

  Filtrage de Pareto de F * P .

	7:	if (P * I ) s ′ domine F * P then
	8:	F * P ← F * P +
	11:	F * P ← F * P + (F * P ) s ′
	12:	end if
	13:
	14:	N ← N + {N s ′ }
	15:	end if
	16:	end if
	17:	s ← s + 1
	18:

{ (P * 1 ) s ′ , . . . , (P * k ) s ′ , . . . , (P * p ) s ′ } 9:

if ( le ) s ′ = (ū e ) s ′ then 10:

Résolution de P MO-NLP (ȳ s ′ ) avec ȳs ′ ← ( le ) s ′ .

For the first 50 ratio, the sum z1 + z2 is too small for a spacing a + δa = 3400mm and this leads to modules larger than 50 mm

Property that should be formally shown based on references[START_REF] Cacchiani | A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs[END_REF] and[START_REF] Przybylski | Multi-objective branch and bound[END_REF]

Les paramètres liés au matériau des dentures, pris dans une liste de 38 nuances d'acier et de fonte pour les engrenages.

Les paramètres définissant les conditions de lubrification et la qualité ISO de l'usinage de la dentures.

Les paramètres définissant le chargement : Puissance à transmettre P t , la vitesse de rotation du pignon N 1 , la durée de vie souhaitée en heures.A cela s'ajoute des paramètres liés au contexte de dimensionnement : puissance transmise, entraxe souhaité, encombrement maximal.Dans tous les cas de figure envisageable, au minimum 6 fonctions contraintes sont indispensable pour assurer un dimensionnement optimal satisfaisant :

ICD-LASMIS CNRS FRE 2019 -

Remerciements

Dans un deuxième temps, différentes techniques d'hybridation des métaheuristiques ont été identifiées et classées à l'aide d'un nouveau cadre global. Le métaheuristique hybride, capable de traiter des problèmes d'optimisation de variables mixtes, peut être une combinaison d'un métaheuristique avec un métaheuristique exact ou d'un métaheuristique avec un autre métaheuristique. Il peut être exécuté séquentiellement ou en parallèle, travailler en collaboration ou être intégré l'un à l'autre. Une attention particulière a été accordée à l'hybridation pour des problèmes d'optimisation multi-objectifs. Enfin, l'idée émergente de coupler les métaheuristiques avec diverses techniques de manipulation des contraintes a également été considérée comme un type d'hybridation, et sept techniques de manipulation des contraintes ont été présentées. Le nouveau cadre d'hybridation aidera certainement les chercheurs à identifier et à exploiter les techniques d'hybridation les plus en vue de nos jours. Une troisième étape consistait à présenter quatre façons d'évaluer l'efficacité de l'hybridation. Ces techniques d'évaluation étaient mértiques, l'effort de calcul, l'évaluation statistique et la robustesse. Vient ensuite la partie expérimentale où cinq métaheuristiques traditionnelles ont été testées sur les trois problèmes d'optimisation. Le critère d'évaluation était la distance générationnelle, l'étalement, le temps jusqu'à la convergence et le pourcentage de points superposés entre le front obtenu et le vrai front de Pareto. Les tests ont été effectués en utilisant deux variantes de manipulation de contraintes ; à savoir la fonction de pénalité et la technique "boundary". NSGA II s'est avéré être la meilleure métaheuristique pour les trois problèmes, alors que la technique des "boundary" était également la meilleure technique pour les trois problèmes. Gardant cette connaissance à l'esprit, nous avons ensuite présenté le nouvel hybride. Un problème de test a été utilisé pour expliquer les composants de l'algorithme, comme l'initialisation améliorée, la progression de l'arborescence, l'expérimentation, etc. Ensuite, le nouvel hybride (metaheuristic + branch & bound) a été testé sur les trois problèmes d'optimisation. Mais d'abord, une étape pour déterminer la meilleure configuration

CHAPTER 2. Hybrid Metaheuristics For Mixed Variables Optimization ratio between feasible search space and the whole search space, multi-modality of the problem, nature of equality/inequality constraints, the chosen metaheuristic [START_REF] Mallipeddi | Ensemble of Constraint Handling Techniques for Single Objective Constrained Optimization[END_REF]. Because of the interactions between these diverse factors and the stochastic nature of metaheuristics, it is not straightforward to determine which constraint handling method is the best during a particular stage of the evolution to solve a given problem [START_REF] Mallipeddi | Ensemble of constraint handling techniques[END_REF]. Thus the idea of hybridizing a certain metaheuristic by mixing it with different constraint handling methods is starting to appear more frequently in the domain of metaheuristics. Such an idea can be found in for example in [START_REF] Tasgetiren | An ensemble of differential evolution algorithms for constrained function optimization[END_REF], where the authors combined three metaheuristics with three constraint handling techniques. The approach was tested on eighteen test scalable test problems. Another example was presented in [START_REF] Elsayed | Integrated strategies differential evolution algorithm with a local search for constrained optimization[END_REF], where the authors combined several metaheuristics with two constraint-handling techniques and generated sixteen variants which were assigned to each individual in a single-population algorithm. The amount of usage of each hybrid variant was decided based on its ability to improve solutions. The approach showed a very competitive performance, with a main drawback that is the number of parameters to be tuned by the user. But perhaps the most prominent example on hybridization of metaheuristics using different constraint handling techniques is a technique called ensemble of constrained handling techniques (ECHT) introduced in [START_REF] Mallipeddi | Ensemble of constraint handling techniques[END_REF], where the authors proposed an ensemble of four constraint techniques in a four sub-population scheme to solve a constrained optimization problem. Each constraint handling technique has its own population and parameters, and was used to evolve an specific sub-population. The parent population corresponding to a particular constraint handling method not only competes with its own offspring population but also with offspring population of the other constraint handling methods. Due to this, an offspring disregarded by its subpopulation may survive in another population. The authors found out that the ECHT works better together than when each constraint-handling techniques are tried separately. The approach was tested on 37 test problems. The results supported the claim that ECHT is highly competitive. However, the main drawback of the approach is the calibration required (from the user) for each of the constraint-handling techniques adopted.

Constraint handling techniques

The development of constraint-handling techniques for multi-objective optimization problems has received relatively little attention in the specialized literature. This may be due to the fact that most researchers assume that any constraint-handling technique developed for single-objective optimization can be easily coupled to a multi-objective algorithm [START_REF] Mezura-Montes | Constraint-handling in nature-inspired numerical optimization: past, present and future[END_REF]. In contrast, several reviews of the literature have addressed the problem of constraint handling techniques for metaheuristics. The authors in [START_REF] Michalewicz | Evolutionary algorithms for constrained parameter optimization problems[END_REF], proposed to class these techniques in four different classes.While in [START_REF] Coello | Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art[END_REF], Coello introduced a different classification where these techniques are classified into five classes.

The two previous references treated techniques for constraints handling in the unique

Conclusions and perspectives

Keeping this knowledge in mind, we then moved to present the new hybrid. A test problem was used to explain the components of the algorithm like the enhanced initialization, the tree progression, fathoming and more... Then the new hybrid (metaheuristic + branch & bound) was tested on the three optimization problems. But first, a step to determine the best configuration for the three problems was conducted using an exact algorithm instead of a metaheuristic. The idea behind this was to not let the quality of the metaheuristic interfere with the results. After the best configuration was determined, it was coupled with the best metaheuristic (NSGAII) and the best constraint handling technique ("boundary") and tested on the three problems.

The new hybrid was able to surpass traditional metaheuristics, as it finds the true Pareto front in most cases. In other cases, it was more close to the true front (compared to traditional metaheuristics) while being evenly distributed. The only drawback was that it takes longer to converge. Despite our systematic approach on hybridization, it is still inevitable to consider the special characteristics of the problem one is trying to solve. Perhaps, a further study needs to be done to determine the time saved by new hybrid by comparison to a full enumerative algorithm. The intuitive idea, (described in 2.3.4.1), that the solution of engineering optimization problems is likely to be found in the boundaries of the feasible region is far from being fully exploited. On the long term, further work needs to be done to harness the combinatorial nature of metaheurisitcs and guide them to produce solutions near the boundary regions. Until that day, one can consider the idea of a dynamic delta active parameter; i.e,that changes with the iteration number, with respect to how difficult a solution near to the boundary solution can be generated.

Part II

French version

French Summary

Outline of the current chapter

Conclusion et perspectives 161

Contents

Abstract vii

Remerciements ix

Contents xi

List of Tables xiii

List of Figures xv

I English version

Contents

Hybridization of multicriteria metaheuristic optimization methods for mechanical problems

Abstract

Most mechanical engineering design problem are optimization problems. These optimization problems hold three characteristics that make them difficult to solve. These characteristics are the mixed nature of the variables (continuous and discrete), the existence of non linear constraints and the presence of multiple non linear criteria or objectives that needs to be minimized to guide the decision making. To tackle such problems, our approach consisted on defining a benchmark of representative test problems that capture the essence of these difficulties, for which we can calculate the theoretical Pareto front. The performance of five "traditional" metaheuristics algorithms that integrates specific enhancement to handle particularities of the benchmark problems was tested. Then, in light of the shortcomings of these "traditional" modified metaheuristics to meet certain evaluation metrics, a new hybrid algorithm that couples metaheuristics and branch & bound was introduced. The hybrid algorithm combines the advantages of metaheuristics like its efficiency for non-linear multi-objective problems alongside with systematic exploration of mixed variables that branch & bound algorithms have. This new hybrid algorithm including specific branching techniques is well suited for solving nonlinear multi-objective mixed problems. It gives better results than "traditional" metaheuristics on the test problems and opens up many prospects for improvement.

Keywords