Int J Adv Manuf Technol (2005) 27: 2–6 DOI 10.1007/s00170-004-2162-z

ORIGINAL ARTICLE

Jean-Luc Marcelin

Using genetic algorithms for the optimization of mechanisms

Received: 27 November 2003 / Accepted: 27 February 2004 / Published online: 26 January 2005 © Springer-Verlag London Limited 2005 Abstract This work examines the possibility of using genetic algorithms for the optimization of the loads transmitted in mechanisms. The variables of design are the relative positions of the various connections, considered in a comparative manner. The minimization of the loads transmitted in the connections is achieved by optimizing the respective positions of those lead to less expensive solutions for bearings and sections of beams. The examples show that using this stochastic method is an efficient way to minimize loads in mechanisms. Keywords Genetic algorithms · Mechanisms · Optimization

1 Introduction Stochastic methods of optimization, such as genetic algorithms, are being used more and more for the optimal design of mechanical systems. The principal advantages of genetic algorithms are an assured convergence without use of derivatives and functions with discrete and non-derivable variables. On the other hand, the deterministic methods of optimization, known as methods of gradient, require a reliable calculation of the sensitivities. This is often difficult, or even impossible, for certain problems of mechanical technology with discrete variables. The detractors of the stochastic methods of optimization point out an important volume of calculations, especially in the case of a method of analysis of the finite element type. Nevertheless, in certain cases of application in mechanical technology as the optimization of gears (a problem in which the variables of design are primarily discrete) [1], these methods are effective because the volume of calculations remains reasonable. In this case, the use of a method of gradient would be very difficult because the derivatives of the objective function and the limitations are difficult to calculate. We will show that these J.-L. Marcelin Laboratoire Sols, Solides, Structures, UMR CNRS C5521, BP 53 38041, Grenoble Cedex 9, France E-mail: [email protected]

methods are also very effective for problems of optimization of mechanisms. In the past, the genetic algorithms method was used within the framework of various mechanical problems. These algorithms appeared very effective, and may play an interesting role in a process of integrated design [2, 3]. The potential of these algorithms was also shown in the difficult case of the optimization of the gears [1], and in the optimization of the supports with applications for fastening in machining [4]. In [5], the possibility of using some genetic algorithms and some neural networks to optimize mechanisms in their globality is examined; a detailed example of a gear box shows that using this stochastic method and neural networks is very efficient. We can speak thus of a metamodel for optimization, in a context of integrated design. In [6], a multi-objective optimization of hand prosthesis, four-bar mechanisms is performed with reference to seven positions, with respect to five design criteria. In [7], the prevalent mathematical programming neural network (MPNN) models are surveyed, and MPNN models are developed and applied to the unconstrained optimization of mechanisms. In [8], the optimization of the transient dynamical behavior of mechanisms is addressed. This paper tackles the problem of optimizing the loads transmitted in mechanisms under certain restrictive criteria. These assumptions are as follows: (a) we remain within the framework of fixed topologies and we consider isostatic or slightly hyperstatic mechanisms. In this sense, the principal objective is to minimize the transmitted loads in each connection; (b) the variables of design are the relative positions of the various connections, considered in a comparative manner; and (c) we respect certain technological limitations by excluding certain zones of the plan or space for preset connections. We show through examples that the procedure described in this paper makes it possible to optimize the mechanisms effectively. Indeed, the minimization of the loads transmitted in the connections by optimizing the respective positions of those lead components, compared to less expensive solutions for bearings and sections of beams. The minimization of loads transmitted in the connections thus minimizes the weight of the mechanism, therefore resulting in its optimization.

3

2 Methods 2.1 Genetic algorithms The genetic algorithms seek the optimal solutions of a given problem by simulating the process of evolution and adaptation of living organisms. The problem is translated into terms of maximization of an objective function in a space with N dimensions. The starting point is a randomly chosen population of individuals that are coded by binary numbers, called chromosomes. After this departure, the genetic algorithm randomly generates a new population, formed of individuals increasingly ready to adapt to a well defined environment. The process uses three operators: • Reproduction • Crossing • Mutation The GA (Genetic Algorithms) are now well known, because they are frequently used. Details can be found in [9–11]. 2.2 Optimization of mechanisms Optimization consists of coupling a calculation program of standard mechanisms (called in the continuation analysis program) with the genetic algorithm. Upon request, the analysis program provides the efforts transmitted in each connection, according to the parameters of the problem, which are primarily the relative positions of the various connections.

• Probability of crossing Pcrossing, • Probability of mutation Pmutation. It is clear that the algorithm gives better results when the values chosen for the first two parameters are large (within the limits of capacity of the computer equipment used). In practice, the number of individuals of a population will be about 1 to 5 times the number of the chromosome digits. However, the probabilities of crossing and mutation are more difficult to choose. It has been shown that mutation is a phenomenon much less frequent than crossing; in [9], the following values are advised: Pcrossing = 0.60 Pmutation = 0.03 These advised values are the result of a numerical experimentation on many examples. In any event, the probability of crossing must be higher than the probability of mutation, since mutation is less frequent [9]. For example, if any mutation is removed, the algorithm converges towards an extremum, but there are few chances that it is the absolute extremum. In theory, convergence is obtained when all the values of the costs of a population are stabilized around a maximum value. In practice, convergence is rather slow with tops and bottoms due to the algorithm’s nature. The user can stop the process when the maximum value of the cost of a population does not evolve any more. The user then manually selects the most interesting individuals of the final population in order to compare their merits.

3 Results 2.3 Formulation of the optimization problem 3.1 Test 1 The correct formulation of the optimization problem is essential in achieving effective and technologically valid solutions. This consists in defining an objective function (even multi-objective, which will be the minimization of the transmitted efforts’ components), to choose a set of independent variables of design, and to define the technological limitations in terms of equalities or inequalities on the variables of design. The formulation depends on the problem arising and conditions of the final solution. We will give examples of formulation in the test cases later in the paper.

This first test is very simple, used to validate the strategy Implemented. It acts to optimize the two connections’ position defined on Fig. 1. It is a question of optimizing the relative position of these two connections (linear, annular, and kneecap). The variables of optimization are the quantities a, b and c of Fig. 1. The units are the mm for the lengths, and N for the loads. The constraints of optimization are: 30 < a < 40 , 60 < b < 70 ,

2.4 The particularities in the case of the use of the AG

and: 40 < c < 80 .

There are two difficulties with AG: (a) the first issue is the problem of setting up a solution-coding in the form of chromosomes which is simple and effective; secondly, we must then take into account the technological limitations correctly, which is not immediate in the case of the use of a genetic algorithm. One can take multi-objective functions or carry out a penalization of the objective function by limitations as indicated in [12]. Before each execution, the genetic algorithm requires the user to specify the values of the following parameters:

External efforts are applied to point M, with values (in the reference x, y, z): XM = −1000 N, YM = 10 000 N and ZM = 3000 N. The analytical solution of this isostatic mechanism shows that the variable of design b appears systematically with the denominator of the expressions of the transmitted loads. The analytical solution minimizing these transmitted loads is thus b equal to its maximum value of 70 mm, which we will check thereafter. Now, considering the definition of the problem of optimization, let F be the square root of the sum of squares of the components of the loads transmitted by connections A and B:
1/2 F = YA2 + ZA2 + XB2 + YB2 + ZB2 .

• The number of individuals in a population, • The maximum number of generations, • The chromosomes’ length,

4

The table of coding decoding for c is as follows:

Fig. 1. Test 1

During the process of optimization, a call with a computation software of mechanism will be made to calculate these components for a, b and c. This will be repeated with each analysis. The problem of optimization is raised without difficulty in the following terms: to find the minimum of F, by holding account of the constraints of optimization stated before. For the AG, the problem must be posed in a different term, since the AG seeks the maximum and not the minimum of a function, and requires the coding of a, b and c. Therefore, the problem can be expressed in the following way: to find the maximum of N − F, N is a sufficiently large constant so that expression N − F is always positive. The coding of a, b and c is carried out for each one of these variables with four binary digits, which one arranges end to end for chromosomes in a total of 12 binary digits. The table of coding decoding for a is as follows: 0000 30

0001 30.5

0010 31

0011 31.5

0100 32

0101 32.5

0110 33

0111 34

1000 35

1001 36

1010 37

1011 38

1100 38.5

1101 39

1110 39.5

1111 40

It can be noted that the limitation of optimization for a is included in coding. The table of coding decoding for b is as follows: 0000 60

0001 60.5

0010 61

0011 61.5

0100 62

0101 62.5

0110 63

0111 64

1000 65

1001 66

1010 67

1011 68

1100 68.5

1101 69

1110 69.5

1111 70

It can be noted that the limitation of optimization for b is included in coding.

0000 40

0001 42

0010 44

0011 47

0100 50

0101 53

0110 56

0111 59

1000 62

1001 65

1010 68

1011 71

1100 1101 1110 1111 73 76 78 80 It can be noted that the limitation of optimization for c is included in coding. For example, the chromosome 0000 0101 1101 corresponds to: a = 30, b = 62.5 and c = 76. One obtains the following result for optimization by the genetic algorithm: Probability of crossing: 0.7 Probability of mutation: 0.02 Generation for which one obtains to best individual: 31 Best individual: 0000 1111 1111 Decoding of the chromosome: a = 30, b = 70 and c = 80 The function objective F is 15 274, which corresponds to YA = 14285, ZA = 142, XB = 1000, YB = 4285 and ZB = 3142. It can be noted that the b optimum is the b announced of 70 mm. 3.2 Test 2: optimization of a 3D mechanism We want to optimize the position of the connections of a mechanism of movement transformation whose diagram is given in Fig. 2. It is composed of a beam, three solids and a fixed frame. The units are N for the forces and m for the lengths. The beam of entry is connected to the point M, where there is an applied effort, corresponding to Z, of 100 N. The distance CM is 0.5 m. This beam is connected to a first solid CB by a pivot connection. Solid CB is connected to a second solid AB by a slide connection. Solid AB is connected to a third solid AO by a slide connection. Lastly, solid AO is connected to the fixed frame by a pivot connection of vertical axis. Our objective is to minimize the loads in each connection of the mechanism, with the goal of dimensioning these connections at a lower cost. A standard software of static study of mechanism makes it possible to calculate for a given configuration of the mechanism the loads transmitted in the various connections. For the needs of our test, we will take as function objective minimizing F (as in the preceding example), the square root of the quadratic sum of all the components of loads and moments of all the connections. As for the variables of design which define the relative positions of the various connections compared to the others, one can use four of them that are independent. These variables appear on Fig. 2 and are labelled a, b, c, and α. It should be noted that the angle β is fixed and is worth 20◦ . The limitations on these variables of design are as follows: 0.1 < a < 0.5 0.2 < b < 0.8

5

The table of coding/decoding for c is as follows: 0000 0.10

0001 0.15

0010 0.17

0011 0.20

0100 0.22

0101 0.25

0110 0.27

0111 0.30

1000 0.32

1001 0.35

1010 0.37

1011 0.40

1100 1101 1110 1111 0.42 0.45 0.47 0.50 The table of coding/decoding for α is as follows: 0000 20

0001 22

0010 24

0011 25

0100 26

0101 27

0110 28

0111 29

1000 30

1001 31

1010 32

1011 33

1100 1101 1110 1111 34 36 38 40 It is seen that the limitations of the problem, in particular those on the variables of design, are integrated in coding. Thus, it is not necessary to penalize the objective function which will be of the type N − F (N constant very large). For a population of 30 individuals, of 50 generations, of a 0.8 probability of crossing, and a 0.1 probability of mutation, the AG leads quickly to the following solution: a = 0.35, b = 0.5, c = 0.2, α = 36◦ which corresponds to chromosome 1001011100111101 and for which F = 1752.

Fig. 2. Test 2

0.1 < c < 0.5 20◦ < α < 40◦ We voluntarily limit the coding of the four variables of design to a binary chromosome of 16 digits on the whole, with four digits per variable according to the tables of coding and decoding. The table of coding/decoding for a is as follows: 0000 0.10

0001 0.15

0010 0.17

0011 0.20

0100 0.22

0101 0.25

0110 0.27

0111 0.30

1000 0.32

1001 0.35

1010 0.37

1011 0.40

1100 1101 1110 1111 0.42 0.45 0.47 0.50 The table of coding/decoding for b is as follows: 0000 0.20

0001 0.22

0010 0.25

0011 0.30

0100 0.35

0101 0.40

0110 0.45

0111 0.50

1000 0.52

1001 0.55

1010 0.60

1011 0.65

1100 0.70

1101 0.75

1110 0.77

1111 0.80

4 Conclusion This study showed the effectiveness and simple application genetic algorithms to address the problem of optimizing mechanisms, as compared to the deterministic methods. This basic study provides a first consideration of feasibility and will be supplemented in the near future with examples dealing with more complex problems. Indeed, the test of a topological optimization of mechanism seems completely achievable because stochastic techniques are well adapted to these primarily discrete problems. Furthermore, calculations of mechanism are relatively efficient in terms of computing times, compared to structural analyses by finite elements.

References 1. Marcelin JL (2001) Genetic optimization of gears. Int J Adv Manuf Technol 17(12):910–915 2. Marcelin JL (1999) Evolutionary optimization of mechanical Structures. Eng Optim 31:571–588 3. Marcelin JL (1999) Evolutionary optimization of mechanical structures: towards an integrated optimization. Eng Comput 15:326–333

6 4. Marcelin JL (2001) Genetic search applied to selecting support positions in machining of mechanical parts. Int J Adv Manuf Technol 17(5):344–347 5. Marcelin JL (2004) A metamodel using neural networks and genetic algorithms for integrated optimal design of mechanisms. Int J Adv Manuf Technol 24(9–10):708–714 6. Haulin EN, Vinet R (2003) Multiobjective optimization of hand prosthesis mechanisms. Mech Mach Theory 38(1):3–26 7. Li J, Gupta KC (1998) Mechanism design with MP-neural networks. J Mech Des 120(4):527–532

8. Schulz M, Brauchli H (1998) Optimization of mechanisms and the effect of collisions. Mech Struct Mach 26(4):401–421 9. Goldberg DE (1989) Genetic algorithm in search, optimization and machine learning. Addison-Wesley, Boston 10. Koza JR (1992) Genetic programming: on the programming of computers by means of natural evolution. MIT Press, Cambridge, MA 11. Michalewicz Z (1996) Genetic algorithms + data stuctures = evolution Programs, 3rd ed. Springer, Berlin Heidelberg New York 12. Marcelin JL, Trompette P, Dornberger R (1995) Optimisation of composite beam structures using a genetic algorithm. Struct Optim 9:236–244