ETAT DE L’ART DES ALGORITHMES D’OPTIMISATION

ETAT DE L’ART DES ALGORITHMES D’OPTIMISATION

L’optimisation de forme a fait l’objet de nombreux travaux [Kusiak et al. 1989], [Balan 1996], [Vieilledent 1999], [Castro el al. 2000], [Antonio al. 2002], etc. Grâce à ces études, la performance et l’efficacité des algorithmes d’optimisation ont beaucoup évoluées. Il est nécessaire de faire une présentation de ces algorithmes avant de présenter la nouvelle approche d’hybridation. Ce chapitre a cet objectif. Un problème d’optimisation de forme peut généralement être présenté comme suit:  µMinimiser 10 10 (1.1) Φ(µ) représente la fonction coût, qui peut être une combinaison de plusieurs critères ; ( ) (µhµc ) ii et désignent les contraintes d’inégalité et d’égalité auxquelles est soumis le vecteur des paramètres à optimiser µ. Selon les circonstances (résultats expérimentaux, disponibilité du gradient de Φ(µ), etc.) ainsi que les ressources disponibles (nombre possible d’évaluations, capacité des ordinateurs, etc.), le problème d’optimisation (1.1) pourra être résolu par différents algorithmes. Citons certains d’entre eux comme l’algorithme de gradient conjugué, les algorithmes de Newton, les algorithmes génétiques, les stratégies d’évolution, les méthodes de surface de réponse, etc. Nous pouvons classifier ces algorithmes d’optimisation en 3 catégories comme suit : – Algorithmes à direction de descente (algorithmes à base de gradient) – Algorithmes d’ordre 0 et algorithmes évolutionnaires – Algorithmes hybrides Nous allons maintenant présenter ces trois classes d’algorithmes d’optimisation. 

METHODES A DIRECTION DE DESCENTE

Dans cette section, nous introduisons une classe importante d’algorithmes de résolution des problèmes d’optimisation : les algorithmes à direction de descente. Ce sont des algorithmes qui ont obligatoirement besoin de l’information du gradient des fonctions coût pour chercher Do Tien Tho   l’optimum du problème. Leur utilisation nécessite que la fonction coût soit au moins une fois différentiable par rapport aux paramètres à optimiser. Nous en décrirons, dans la première partie de cette section, les principes généraux. 

Principes généraux

Pour utiliser avec cette catégorie d’algorithmes, supposons que la fonction Φ est continue et différentiable dans tout l’espace de recherche. Nous notons ∇Φ(µ) et respectivement le vecteur gradient et la matrice hessienne de la fonction coût Φ(µ) en µ. La condition nécessaire d’optimalité du problème d’optimisation (1.1) s’écrit : ∇ Φ(µ) 2 ∇Φ(µ) = 0 (1.2) Lorsque la fonction coût Φ(µ) est deux fois différentiable, on peut écrire une condition suffisante d’optimalité :  définie positive 0 2 µ µ (1.3) Les méthodes à direction de descente ont pour objectif de calculer un vecteur µ satisfaisant la condition nécessaire d’optimalité (1.2). Pour une fonction coût donnée Φ(µ), on dit que d est une direction de descente de Φ(µ) en si la relation suivante est vérifiée : n µ∈ℜ d.∇Φ(µ) < 0 (1.4) Géométriquement cela veux dire que d fait avec l’opposé du gradient − ∇Φ(µ) un angle θ strictement plus petit que 2 π . Si d est une direction de descente, pour tout λ > 0 suffisamment petit, en utilisant un développement de Taylor d’ordre 1 nous avons : Φ(µ + λd ) < Φ(µ) (1.5) Nous voyons que Φ(µ) décroît dans la direction d. Les directions de descentes sont intéressantes car, pour faire diminuer Φ (µ), il suffit de faire un déplacement de µ le long de d. L’algorithme général construit une suite d’itérés µ k approchant une solution µ* du problème (1.1) par la récurrence : (1.6) est appelé le pas de descente, une direction de descente de Φ en .  Le pas de descente doit être déterminé de telle sorte que la valeur de la fonction décroisse le plus possible. En général, un algorithme de recherche linéaire est utilisé pour trouver un pas « optimal » à chaque itération. L’algorithme général de cette classe de méthodes d’optimisation pour résoudre un problème sans contrainte s’écrit : Choix d’un itéré initial , et d’un paramètre d’arrêt ε n µ ∈ℜ 0 Pour k ≥ 0 1. tant que ∇Φ( ) > ε k µ , continue ; 2. recherche d’une direction de descente ; k d 3. recherche linéaire : déterminer un pas >0 minimisant k λ ( ) k k Φ µ + λ d 4. actualisation pour l’itération suivante : ; k = k+ 1 k k k k µ = µ + λ d +1 5. aller à l’étape 1. Le test d’arrêt apporté à l’étape 1 porte sur la condition nécessaire d’optimalité d’ordre 1 : ∇Φ( ) ≈ 0 k µ . Pour définir une méthode de direction de descente, il faut donc préciser deux ingrédients principaux qui sont : – la manière de choisir la direction de descente, qui donne le nom de l’algorithme – la méthode de recherche linéaire pour déterminer le pas de descente λ optimal à chaque itération Quelques méthodes correspondant à des choix particuliers ces deux ingrédients sont décrits dans les paragraphes qui suivent. 

Choix de la direction de descente 

Méthode de la plus forte pente Il s’agit de la méthode à direction de descente d’ordre 1 la plus simple. L’inverse du gradient est évidemment une direction de descente si n’est pas un point stationnaire. La direction normalisée d de plus forte décroissance de Φ au voisinage d’un point µ est donnée par : k µ ( ) ( ) µ µ d ∇Φ ∇Φ = − (1.7) Do Tien Tho Page 5 CEMEF – Ecole des Mines de Paris Thèse de doctorat Optimisation de forme en forgeage 3D Chapitre I La méthode du gradient est facile à mettre en œuvre. Cependant, sa convergence peut être très lente. Loin de la solution, cette direction est une bonne direction de descente. En revanche, dans le voisinage d’une solution optimale µ* du problème, là où les termes du second ordre de Φ(µ) en µ* jouent un rôle plus important, on observe une diminution très lente de Φ. Cela est son défaut majeur. Il existe des techniques d’accélération permettant de palier à cet inconvénient [Minoux 1983]. Néanmoins, elles sont fort coûteuses et peu utilisées. Dans le domaine de mise en forme, Jensen et al. [Jensen et al. 1998] se sont servis cette méthode pour la minimisation de l’usure en emboutissage. I.2.2.2. Méthode du gradient conjugué L’algorithme du gradient conjugué [Morris 1982] peut être vu comme une légère modification de l’algorithme de la plus forte pente, pour lequel on garde en mémoire la direction de descente de l’itération précédente. La direction de descente est donnée par :  Le scalaire peut prendre différentes valeurs, ce qui donne à l’algorithme des propriétés différentes. Nous présentons ici les deux méthodes qui sont très fréquemment citées dans la littérature. Elles calculent par les formules suivantes : k β k β – Méthode de Fletcher-Reeves [Fletcher et al. 1964] : ( ) ( ) 2 1 2 − ∇Φ ∇Φ = k k k µ µ β (1.9) – Méthode de Polak-Ribière [Polak et al. 1969] : Cet algorithmes est proposé à l’origine pour la minimisation de fonctions quadratiques, puis il est étendu à des fonctions quelconques dans [Fletcher et al. 1964]. Néanmoins, il cumule les erreurs d’arrondi, la convergence n’est alors assurée que si l’on procède à des réinitialisations périodiques. Certaines techniques de redémarrage ont été proposées (méthode de Beales [Powell 1975] par exemple). Zabaras et al. [Zabaras et al. 1995] ont utilisé cette méthode pour l’optimisation du flux de chaleur en solidification. I

Méthode de Newton

L’algorithme général de Newton est une méthode de résolution de systèmes d’équations non linéaires. Dans le cadre de l’optimisation, il est utilisé comme un algorithme de direction de descente sur la condition nécessaire d’optimalité (1.2). Do Tien Tho Page 6 CEMEF – Ecole des Mines de Paris Thèse de doctorat Optimisation de forme en forgeage 3D Chapitre I Pour décrire cet algorithme, nous considérons l’approximation quadratique Q(µ) de Φ(µ) au voisinage d’un point à l’itération k:On choisit alors qui minimise . Il est définit par la condition d’optimalité (1.2) ce qui conduit au système linéaire suivant pour déterminer la direction de descente : ) Cette méthode est reconnue comme une des plus efficaces dans la famille des algorithmes à direction de descente. Sa principale difficulté réside dans le calcul des dérivées secondes de Φ qui s’avère le plus souvent coûteux et difficile à réaliser. Plusieurs algorithmes proposent de lever cette difficulté en utilisant une approximation de la matrice hessienne. On peut mentionner le cas particulier où Φ peut s’écrire sous forme de moindres carrés. On obtient alors une approximation du hessien en ne considérant que les produits des gradients. Cette approximation, qui est à la base des algorithmes de GaussNewton ou Levenberg-Marquardt [Minkowycz 1988], est largement utilisée en identification de paramètres rhéologiques [Gavrus 1996] [Ghouati 1998]. 

Méthodes quasi-Newton

L’idée des méthodes de quasi-Newton est de remplacer la matrice hessienne (ou son inverse) par une approximation mise à jour itérativement. La direction de descente s’écrit : ( k ∇ Φ µ 2 ) [ ] ( ) k k k H . µ ~ d = − ∇Φ −1 (1.13) où la matrice k H ~ doit converger vers la matrice hessienne lorsqu’on s’approche de l’optimum. Pour tout k, la matrice k H ~ doit vérifier plusieurs conditions. D’une part, elle doit être symétrique et définie positive. D’autre part, on impose à la matrice k+1 H ~ de vérifier la relation de quasi-Newton suivante :   Plusieurs méthodes pour construire la suite k H ~ ont été proposées. Les deux méthodes les plus connues sont de rang 2, celle DFP de Davidon-Fletcher-Powell [Fletcher et al. 1963] et celle BFGS [Broyden et al. 1970]. Pour un problème d’extrusion, Kusiak et al. [Kusiak et al. 1989] ont montré l’efficacité des méthodes de quasi-Newton en comparant une méthode DFP, un algorithme de plus forte pente et une méthode d’ordre 0 le simplex. Avec de nombreuses utilisations comme dans [Noiret et al. 1996], [Zhao et al. 1997], [Bourdin et al. 1998], [Vieilledent et al. 1998], la méthode BFGS semble la plus adaptée aux problèmes d’optimisation en mise en forme.