OPTIMISATION SANS GRADIENT ET APPLICATIONS (cours M7, saison 2012)

Université Versailles Saint Quentin en Yvelines

Master M2S

Laurent Dumas

Les méthodes d'optimisation sans gradient connaissent un succès croissant dans de nombreux domaines de l'ingénierie ou de la médecine où les fonctions à optimiser sont de type boîte noire, très coûteuses à évaluer, et définies sur des espaces mixtes discret/continus. Ce cours présente les principales méthodes d'optimisation sans gradient développées ces dernières années : méthodes de Nelder Mead, recuit simulé, algorithmes génétiques, essaim de particules, et les modèles approchés permettant de réduire le coût de calcul. Le cours sera illustré par plusieurs applications industrielles ou en sciences du vivant, parmi lesquelles l'optimisation de forme de véhicules, le décodage d’image floues ou la reconstruction d’écoulements artériels.

Planning : 

Jeudi 19 Janvier 2012, 13h30-16h30 : §1 (fichier pdf)

Jeudi 26 Janvier 2012, 13h00-16h30 : §2 à 3.1 (NelderMead.sci, MDS.sci, M7-2012-recuit.sci)

Jeudi 09 Février 2012, 13h00-16h30 (salle TP) : §3.1 à 3.2 (LJ.sci, M7-2012-GAbinary.sci, M7-2012-GA.sci)
Mardi 14 Février 2012, 9h00-12h00 : §3.2 à 3.3 (NSGA.sci, ES-CSA)
Jeudi 16 Février 2012, 13h00-16h30 (salle TP) : §3.3 (énoncé TP, exercice1, exercice2)
Jeudi 01 Mars 2012, 13h00-16h30 : §4 (RBF.sci, AGA.sci)

Examen : énoncé, corrigé : M7exam-SR.sci

Plan du cours : 

1. Quelques problèmes d’optimisation en ingénierie
                                                                                   1.1 Problème du voyageur de commerce
                                                                                   1.2 Configuration d'une molécule d'énergie minimale
                                                                                   1.3 Décodage d'une image de code barre floue et bruitée
                                                                                   1.4 Réduction de consommation d’un véhicule

2. Méthode sans gradient déterministes

2.1 Méthode de Nelder Mead

2 .2 Méthode de Torczon

2 .3 Méthode d’optimisation globale pour les polynômes

3. Méthode sans gradient stochastiques

3.1 Recuit simulé

(principe, algorithme, application au problème LJ)

3.2 Une première méthode évolutionnaire : les algorithmes génétiques

(principe, algorithme binaire et réel, gestion des contraintes, version multi-objectif, application au code barre)

3.3 Stratégies d’évolution

(principe, adaptativité endogène des paramètres)

4. Optimisation par métamodèles

4.1 Modèles RBF

(principe, exemples)

4.2 Krigeage

(principe statistique, exemple de corrélation gaussienne, lien avec RBF)

4.3 Couplage avec les méthodes évolutionnaires

(couplage faible/fort)

References : 

Numercial optimization, theoretical and practical aspects : JF Bonnans, JC Gilbert, C. Lemaréchal, C. Sagastizbal, Springer Verlag 2003.
Genetic Algorithms on search, optimization and machine learning : D. Goldberg, 1989
Multi-Objective Optimization Using Evolutionary Algorithms , K. Deb, 2001

On the web : 

    Documents:

    Un cours en ligne : ' Numerical Optimization ' at Oxford University
    Un cours en ligne : ' Optimization in engineering design ' at  the Georgia Institute of Technology
Présentation du recuit simulé avec application au voyageur de commerce: Interstices
Un tutorial sur les stratégies d’évolution: ‘ES : a comprehensive introduction’, H.G. Beyer, H.P. Schweffel

    Articles:

    Un article sur la (non) convergence de Nelder Mead : SIAM J. Opt.1998
    Un article sur la convergence de MDS: PhD1989
   Un article sur la convergence d’un ES (1,1) : EA2007
Un article sur les metamodèles RBF/krigeage: Meta2009

Applications:

The LJ problem: article 1 article 2 , article 3 , article 4 thesis

The barcode problem: article 1