OPTIMISATION SANS GRADIENT ET APPLICATIONS (cours M3, saison 2012/2013)

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éthode de Nelder Mead, recuit simulé, algorithmes génétiques, essaim de particules, ainsi que 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.

Archives : cours 2011/2012

Planning : 

Mardi 02 octobre 2012, 14h00-17h00 (maison de la simulation) : § 1. (M3_2012.ppt)

Mardi 09 octobre 2012, 14h00-17h00 (maison de la simulation) : § 2.1 et 2.2 (NelderMead.sci, MDS.sci)

Mardi 23 octobre 2012, 14h00-17h00 (maison de la simulation) : § 2.3 (RBF.sci, krige.sce)

Mardi 06 novembre 2012, 14h00-17h00 (maison de la simulation) : § 3.1, 3.2 + TP Scilab (SA.sci, GA-binary.sci, GA-real2012.sci, PSO.sci)

Mardi 20 novembre 2012, 14h00-17h00 (maison de la simulation) : § 3.3, 3.4

Mardi 27 novembre 2012, 14h00-17h00 (maison de la simulation) : présentation des projets (cf M3_2012.ppt)

Mardi 4 décembre 2012, 14h00-17h00 (maison de la simulation) : avancée des projets et § 3.4 (fonction coût : projet 1.sci, projet 2.sci)

Mardi 11 décembre 2012, 14h00-17h00 (maison de la simulation) : avancée des projets et § 3.4

Mardi 18 décembre 2012, 14h00-17h00 (maison de la simulation) : soutenance des projets

Projet1 : optimisation d’un réseau de Bragg

Exemple : FBG de longeur 0.01m, filtre de 0.1nm autour de 1550nm (PSO-projet1.sci)

Projet 2 : optimisation d’un parc de panneaux solaires

Exemple : domaine carré de taille 1, 2 parcs, Smax=0.5, dmin=0.1 (SA-projet2.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éthodes directes (Nelder Mead, MDS/Torczon)

2 2 Interpolation (modèles quadratiques et régions de confiance)

2.3 Surfaces de réponse (RBF, krigeage)

3. Méthode sans gradient stochastiques

3.1 Recuit simulé

3.2 Algorithmes génétiques, PSO, stratégies d’évolution

3.3 Résultats de convergence

3.4 Extensions (adaptativité, gestion des contraintes, version multi-objectif)

4. Mise en œuvre sur des cas réels (réseau de Bragg, parc de panneaux solaires)

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
(partie recuit simulé) Modèles aléatoires: J.F. Delmas, 2006
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

    The FBG problem: a talk  'Optimisation of optical communication systems by means of genetic algorithms' by myself
The FBG problem: a PhD dissertation “Synthesis and characterization of fiber Bragg gratings” by J. Skaar  (chapters 2 and 3.1 mainly)
The FBG problem: an article 'Real-coded genetic algorithm for Bragg grating parameter synthesis' by G. Cormier and R. Boudreau
The FBG problem: an article 'Multi-objective and constrained design of fibre Bragg gratings using evolutionary algorithms' by S. Manos and L. Poladian

The solar panel problem : a report  of PhD students