3. Evolutionary algorithm#

3.1. General principles#

Evolutionary algorithms are part of stochastic global optimization methods based on the principles of Darwinian evolution of biological populations, methods commonly known as genetic algorithms. Moreover, we begin by recalling the main phases of a simple genetic algorithm:

    • coding: each parameter to be adjusted is coded in binary base; the population is created;

    • evaluation: each individual in the population is assigned a measure of their adaptation, calculated from the cost to be minimized function;

    • selection: the individuals who will produce the next generation of the population are selected; we naturally select the best in the sense of adaptation;

    • crossing: new individuals are created by the parents designated in the previous phase. In practice, it involves exchanging part of the binary chain between two parents;

    • mutation: random mechanism that disrupts one or more bits of the children’s binary chain in order to maintain a certain level of diversity in the population;

    • replacement: a new population, of the same size, is formed by replacing the parents with the children

Even if, for abuse of language, we often use the term genetic instead of evolutionary, we must remember the few differences that particularize evolutionary algorithms [5]:

  • the individuals in the population are represented by vectors of real numbers and no longer in binary coding;

the selection process is different: while genetic algorithms select :math:`n` parents to create :math:`n` children who completely replace them in the population, evolutionary programs generate*m children from \(n\) parents and then select the new population by keeping the best \(n\) from the set \(n+m\);

  • the probabilities of crossing and mutating may vary over generations.

The advantage of introducing an evolutionary algorithm in*Code_Aster* lies in its ability to multi-directional exploration of the topological space of parameters while avoiding as much as possible the local minima of the functional to be minimized.

The implementation of this algorithm in Code_Aster is the result of the partnership between the AMA department and Politecnico di Milano.

We also note that the most criticized defect of evolutionary algorithms, that of being time intensive CPU, can be easily eliminated by the numerous possible parallelization variants.

3.2. How the algorithm works#

The algorithm is started by choosing METHODE = “GENETIQUE” or “HYBRIDE” in the MACR_RECAL command options. In the second case, the evolutionary algorithm will perform a rough search followed by optimization by the Levenberg-Marquardt algorithm.

Figure 3.2-a Logical diagram of how the evolutionary algorithm works

The overall operation of the algorithm is illustrated on the logic diagram in Figure 3.2-a and the steps are described below:

  1. Initialization: a population of parameter sets is generated and all individuals are initialized with the initial values of the parameters to be adjusted. The size of this population is given by the value of the NB_PARENTS parameter imposed by the user. This value depends on several factors such as uncertainty about the solution: the greater this uncertainty, the greater the population must be. It is therefore recommended to start a calibration study by taking 10 for this value and to refine it according to the results.

  2. Functional evaluation: this is the functional presented in equation 3.1-3. Initially, after the initialization stage, a single evaluation is made because all the individuals in the population are identical. Then, in the realignment loop, we perform as many evaluations of the functional during an iteration as the number of children (NB_FILS) imposed by the user. The larger this parameter that manages the renewal rate of the population, the more time-consuming the algorithm is CPU in this step. By default the number of children is set to 5 (half the size of the population is also imposed by default).

  3. Stop criterion: once the population of \(n\) parents is constituted and each individual has its functional value, we check:

    • the best functional value;

  • the number of iterations already performed by the algorithm

If the best value of the functional is less than the relative residual imposed by the user (1.E-3 by default) or if the maximum number of iterations is reached, the best individuals in the population is provided as a solution.

  1. d)**Selection*: the best individual in the population is selected and it is**the only** (in this implementation) who has the right to reproduce and generate the \(m\) children. This generation is almost random, around the best individual, with a standard deviation imposed by the user (keyword ECART_TYPE). During this step, the algorithm manages the limits imposed on the parameters by the user. Individuals generated in this way are only accepted as children if they are within the limits.

  1. Replacement: after generating the m children, the overall population at this point in the iteration is \(n+m\) (NB_PARENTS + NB_FILS). The replacement operator here realizes a hierarchy of individuals according to the associated values of the functional and replaces the individuals from population PARENTS with the \(n\) best among the \(n+m\).

One of the particularities of this implementation of the evolutionary algorithm in Code_Aster is the absence, for the moment, of mutation and crossing mechanisms.

3.3. Hybrid recalibration technique#

By choosing METHODE =” HYBRIDE “in MACR_RECAL, the user has the possibility to combine the advantages of stochastic algorithms (the evolutionary one here) with those of deterministic algorithms (Levenberg-Marquardt in this case in this case). It is therefore a question of carrying out a first « rough » search in the topological space of the parameters, which will allow the Levenberg-Marquardt algorithm to start the optimization with a starting point closer to the global solution of the functional.

The dosage between stochastic and deterministic is to be set by the user taking into account his expertise. A great deal of uncertainty about the optimal values of the parameters to be adjusted must impose:

  • more iterations of the evolutionary algorithm;

  • a larger standard deviation for the draws;

  • a larger population size.

These are the three levers that the user has at his disposal to perform a quality adjustment with a satisfactory level of performance (time CPU and memory used).