Marco Luersen Centre Fédéral d’Education Technologique du Paraná

Un algorithme de Nelder-Mead globalisé et borné pour les problèmes de l'ingénieur : GBNM

• Marco Luersen

• - Centre Fédéral d’Education Technologique du Paraná

• CEFET-PR - Brésil

• - Doctorant au Lab. de Mécanique – INSA de Rouen

• Rodolphe Le Riche

• – CNRS URA 1884 et SMS, Ecole des Mines de Saint Etienne

Motivation

• Caractéristiques des problèmes d’optimisation en conception mécanique :

• plusieurs optima locaux

• variables bornées

• calcul de sensibilités souvent laborieux, coûteux où n’existent pas

• temps de calcul limité à quelques milliers d’analyses de la fonction coût

•  optimisation globale souhaitée, mais sa faisabilité est incertaine.

La méthode de Nelder-Mead classique

• Proposée par Nelder & Mead (1965)

• (variables continues)

• Méthode d’ordre zéro : ne requiert pas le calcul du gradient

• Méthode rapide, relativement aux méthodes d’ordre zéro

• Méthode locale

La méthode de Nelder-Mead classique (2)

• Basée sur la comparaison des valeurs de la fonction aux (n+1) sommets d’un simplexe

• Le minimum est cherché en modifiant le simplexe à travers des opérations : réflexion, réflexion/expansion et contractions

La méthode de Nelder-Mead classique (3)

• Inconvénients :

• S’applique à des problèmes sans bornes

• Dégénérescence du simplexe (perte d’une dimension), est un cas d’échec de la méthode

• Méthode locale : s’arrête quand un minimum local est trouvé

Amélioration de la méthode de Nelder-Mead

• Prise en compte des bornes

• Détection des simplexes dégénérés et ré-initialisation

• Test d’optimalité sur les bornes

Prise en compte des bornes

• Prise en compte de bornes par projection :

Dégénérescence (2)

• Critères :

Test d’optimalité sur les bornes

• Ex. : Fonction test de Rosenbrock bidimensionnel

Test d’optimalité sur les bornes (2)

Test d’optimalité sur les bornes (3)

• les conditions de Kuhn et Tucker ne sont pas applicables : fonctions pas dérivables

• conditions de point-col numériquement non vérifiables

• test d’optimalité : une recherche locale, avec un «petit» simplexe initial

• on considère que le simplexe initial est plus petit que le bassin d’attraction

• coût : pour la fonction de Rosenbrock : ~20% (ça marche toujours !)

Globalisation : recherche du minimum global

• Point de vue Ré-initialisation : GBNM Évolutionnaire :

Globalisation par ré-initialisation probabilisée

• chaque fois q’un minimum local est trouvé il est enregistré

• le prochain point initial est choisit de tel sorte à ne pas échantillonner des régions déjà connues : visiter différents bassins d’attraction, sans connaître le nombre de redémarrages à priori

• travail à coût fixé

• redémarrage avec une caractéristique aléatoire-biaisée

Estimation de la probabilité de ne pas avoir échantillonné un point (x)

Estimation de la probabilité de ne pas avoir échantillonné un point (x) (2)

Ré-initialisation probabilisée

• pour le calcul de la probabilité pi , on ne garde comme xi que les points initiaux

• maximisation de  par tirage aléatoire de nb_random_points : parmi nb_random_points aléatoires, trouver celui qui a la plus haute probabilité de n’avoir pas été échantillonné auparavant

Ré-initialisation probabilisée (2)

• si nb_random_points=1 : aléatoire

• si nb_random_points=grand : motif régulier

• (si on connaît le nb. de redémarrages  grille)

• si nb_random_points petit, > 1 (3 à 10) : aléatoire/biaisée

Articulation de :

• Articulation de :

• 3 tests de convergence :

• Small

• Flat

• Degenerated

• 3 formes de ré-initialisation :

• Probabilistic

• Large Test

• Small Test

Caractéristiques des recherches locales : vitesse, précision  Nelder-Mead

• Caractéristiques des recherches locales : vitesse, précision  Nelder-Mead

• Amélioration de la méthode de N-M :

• Prise en compte de bornes par projection
• Détection et traitement des dégénérescences du simplexe pendant la recherche
• Test d’optimalité sur les bornes

• Globalisée par ré-initialisation  stratégie hybride en série : local-global

Applications : Fonctions tests multi-modales bidimensionnelles (3)

Fonctions tests multi-modales bidimensionnelles (4)

•  

Fonction test de Griewank (n = 12) (fonction très multi-modale)

Fonction test de Griewank (n = 12)

Prise en compte des contraintes par pénalisation linéaire adaptative

• f(x) est modifiée par pénalisation :

Prise en compte des contraintes par pénalisation adaptative (2)

Prise en compte des contraintes par pénalisation adaptative (3)

• Interprétation de la pénalisation adaptative linéaire :

• Un Lagrangien généralisé, qui possède un point-col plus souvent que les Lagrangiens ordinaires ;

• Mise à jour des : un gradient à pas fixe pour maximiser la fonction duale, calcul du gradient approché ;

• Convergence possible pour des finis (contrairement aux pénalisations quadratiques).

Applications aux composites

Applications aux composites

• Maximisation du module d’élasticité Ex  min (1 – Ex/Ex_ref)

• plaque composite symétrique et équilibrée à 16 couches

• 4 variables : les orientations des fibres :

• matériau : verre-époxyde

• contraintes :

• utilisation de la théorie classique des stratifiés (CLT)

Maximisation de Ex : plaque composite stratifiée

• Paramètres stabilisés de pénalisation :

Maximisation de Ex : plaque composite stratifiée (2)

Maximisation de la charge critique de flambement

• plaque rectangulaire simplement supportée

• 48 couches,

• symétrique et équilibré,

• chargement de membrane : Nx et Ny

• matériau : carbone-époxyde

Maximisation de la charge critique de flambement (2)

• contraintes :

• - critère de rupture de Hoffman

• - coef. de dilatation thermique :

• théorie classique des stratifiés et flambement linéaire

Maximisation de charge critique de flambement 48 couches : 12 variables

Conclusions

• GBNM : un algorithme pratique pour les problèmes de l’ingénieur :

• travail à coût fixé : nombre d’analyses défini a priori ;

• globalisation par ré-initialisation probabilisées, pour ne pas échantillonner des régions déjà connues, sans connaître le nombre de redémarrages à priori ;

• Nelder-Mead amélioré pour les recherches locales :

• méthode d’ordre zéro, locale et sans bornes  vitesse, précision ;
• détection et ré-initialisation en cas de dégénérescence ;
• prise en compte des bornes par projection et des contraintes par pénalisation adaptative ;
• test d’optimalité, sur les bornes.

Conclusions (2)

• La stratégie la plus robuste de ré-initialisation probabilisée est un compromis entre ré-initialisation aléatoire et ré-initialisation à intervalles réguliers ;

• Pour les problèmes de taille moyenne à bas coût, la méthode GBNM a une plus haute précision que les algorithmes évolutionnaires ;

• La globalisation par ré-initialisation probabilisée n'est pas restrictive à l’algorithme de Nelder-Mead. Elle peut être appliquée à d’autres optimiseurs locaux.