Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Grenoble INP ENSE3, 11 septembre 2014 Problèmes et algorithmes d’optimisation

1 Grenoble INP ENSE3, 11 septembre 2014 Problèmes et algorithmes d’optimisation (6 heures) _______ 1. Objectif de ce Bureau d'Études L’objectif de ce Bureau d’Etudes est d’étudier les comportements et les spécificités de quelques algorithmes d’optimisation sur des problèmes d’optimisation académiques. La mise en œuvre de ces algorithmes sur un problème plus réaliste fera l’objet d’un autre BE. Pour réaliser cette étude nous utiliserons GOT-It, un logiciel co-développé par la société CEDRAT et le G2Elab (Laboratoire de Génie Electrique de Grenoble). Le texte de ce sujet débute par 2 sections introductives : - la définition des 3 problèmes d’optimisation qui serviront de support aux études, - une présentation rapide du logiciel d’optimisation qui sera utilisé, Il se poursuit par 4 sections explicitant les études à réaliser : - une expérimentation sur le problème unimodal de Rosenbrock, - une expérimentation sur le problème multimodal de Belledonne, - une expérimentation sur le problème multiobjectif BiSphère, - une étude de robustesse des solutions sur le problème de Belledonne. 2. Les problèmes d’optimisation étudiés Un problème d’optimisation de dimension n peut être écrit de façon générale sous la forme : – minimiser ) ,..., , ( ) ( 2 1 n x x x f x f = avec { } n n x x x x ℜ ∈ = ,..., , 2 1 – en respectant ( ) ( ) n j x x x m m i x G m i x G j j j e i e i ,..., 1 ,..., 1 0 ,..., 1 0 max min = ≤ ≤ + = ≤ = = où – La quantité f(x) est un critère à minimiser, appelé aussi fonction objectif. Il peut y avoir plusieurs critères. – Le vecteur x est constitué de n variables xj qui représentent les paramètres du problème. – Les fonctions Gi(x) représentent les contraintes d’égalité et d’inégalité. – Les valeurs min j x et max j x désignent les contraintes de domaine. 2 Grenoble INP ENSE3, 11 septembre 2014 Exemple 1 : Le problème de Rosenbrock Minimiser 2 1 2 2 1 2 2 1 1 ) 1 ( ) ( 100 ) , ( − + − = x x x x x f avec 2 2 2 2 2 1 + ≤ ≤ − + ≤ ≤ − x x Ce problème possède un seul optimum 0 ) 1 , 1 ( 1 = f . Exemple 2 : Le problème multimodal de Belledonne Minimiser ) 0.3 + 4 )cos( - (12 + ) 5 )cos( - (1 ) , ( 2 2 2 1 2 1 2 1 2 y y y y y y f = avec 2 0 2 0 2 1 ≤ ≤ ≤ ≤ y y Ce problème possède 1 minimum global 73956 . 2 1 - ) 01548 . 0 , 36864 . 1 ( 2 = f et 3 minima locaux 64671 . 2 1 - ) 01548 . 0 , 56434 . 0 ( 2 = f , 92323 . 11 - ) 86648 . 0 , 36864 . 1 ( 2 = f et 83038 . 11 - ) 86648 . 0 , 56434 . 0 ( 2 = f . Exemple 3 : Le problème multiobjectif BiSphere Minimiser simultanément 2 2 2 1 2 1 31 ) 1 ( ) , ( z z z z f + − = et 2 2 2 1 2 1 32 ) 1 ( ) , ( − + = z z z z f avec 5 5 5 5 2 1 + ≤ ≤ − + ≤ ≤ − z z Les deux solutions partielles 0 ) 0 , 1 ( 31 = f et 0 ) 1 , 0 ( 32 = f ne peuvent pas être atteintes simultanément. Il faut nécessairement envisager un compromis entre les deux objectifs. Il y a une infinité de compromis possibles. 3. Présentation rapide du logiciel d’optimisation GOT-It. GOT-It donne la possibilité de décrire un problème d’optimisation, de sélectionner un algorithme d’optimisation, de lancer une optimisation et d’analyser les solutions. Sur le réseau de l’ENSE3, la version 2 du logiciel est disponible, cependant nous allons utiliser une version 2-beta, plus récente, accessible comme suit - Connecter un lecteur "O:" sur \\FSRV1\Pedagogie\Dist-JLC - Ouvrir une fenêtre sur "O:" - Lancer le plus récent got_dist\gotit_exec_GOT_Vyyyy-mm-dd.bat (double clic) - Si le logiciel communique en anglais, basculer en français (tools -> Prefererences … -> FRENCH puis quitter et relancer le logiciel) - Créer un nouveau projet (Projet > Créer nouveau projet…). Remarque : Une version allégée de ce logiciel, nommée FGot, est téléchargeable librement à http://forge- mage.g2elab.grenoble-inp.fr/project/got. Les fonctionnalités de FGot sont suffisantes pour ce TP. Attention, les fichiers *.fgot sont lisibles par GOT-It, mais la réciproque n’est pas vrai. Description d’un problème d’optimisation : - La commande Paramètre permet de décrire pour chaque paramètre (x1,x2,...) son nom, sa valeur (utilisée comme valeur initiale par certains algorithmes 3 Grenoble INP ENSE3, 11 septembre 2014 d’optimisation), ses valeurs minimale et maximale, sa grille d’arrondi et son unité. Il est possible de fixer un paramètre ou d’indiquer s’il est incertain. - La commande Fonction permet de décrire des fonctions auxiliaires. - La commande Fonction d’optimisation permet de décrire les noms et expressions des buts à atteindre (f1, f2, …) et des contraintes (g1, g2, …). - La commande Problème d’optimisation permet de décrire pour chaque problème d’optimisation son ou ses objectifs et ses contraintes. Sélection d’un optimiseur : - La commande Algorithme d’optimisation permet de sélectionner un optimiseur en mesure de résoudre un problème d’optimisation. Remarque : Un optimiseur est le plus efficace en précision et coût (nombre d’évaluations) lorsqu’il est employé pour résoudre le type de problème d’optimisation pour lequel il a été conçu (monoobjectif / multiobjectif, non contraint / contraint). Optimisation : - La commande Optimisation permet de lancer l’optimisation d’un problème d’optimisation à l’aide d’un optimiseur. Analyse : - La commande Outil d’analyse permet d’analyser la ou les solutions et permet aussi de visualiser graphiquement les fonctions. 4. Expérimentation sur le problème de Rosenbrock Dans cette première expérimentation, nous allons utiliser le problème de Rosenbrock (rechercher sur internet) pour mettre en évidence le fonctionnement des algorithmes d’optimisation mis à notre disposition. - Créer un nouveau projet (lui associer par exemple le nouveau fichier Rosenbrock.gotit). - Décrire les paramètres continus x1 et x2 (prendre 1/10000 comme taille de grille pour x1 x2, ne pas définir d’unité) et la fonction de Rosenbrock f1 (la nommer F1) (l’opérateur « élévation à la puissance » est **, par exemple 2 1 ) 1 ( − x se code (x1-1)**2 ). - Visualiser la fonction F1 (essayer "Traceur courbes", "Evaluateur", "Traceur isovaleurs", "Traceur surface" disponibles dans Outil d’analyse). - Passer du contexte Paramétrique au contexte Optimisation. - Dans le menu « Réglage », cocher la case « Vider le cache ». - Dans Fonction d’optimisation créer OF1, le But de minimisation, avec F1 pour fonction et 5E-5 pour cible (le but à atteindre est F1 inférieur ou égal à 5E-5). - Décrire le Problème d’optimisation (le nommer Rosenbrock) dont le but unique est OF1. 4 Grenoble INP ENSE3, 11 septembre 2014 - Sélectionner un algorithme d’optimisation SQP (le nommer SQP). - Créer et exécuter l’Optimisation du problème Rosenbrock avec SQP (faire plusieurs essais avec pour x1 x2 les valeurs initiales [2, 2], [0, 0], [2, -2], [-2, - 2], [-2, 2]). Si nécessaire, augmenter le nombre maximal d’itérations. Relever les nombres d’itérations de l’algorithme et d’évaluations de la fonction. Expliquer la différence entre itérations et évaluations ? Astuce 1 : Dans l’arbre de données, un clic droit sur une optimisation puis Analyser renseigne sur les résultats obtenus. Astuce 2 : Une optimisation déjà réalisée peut être re-exécutée en tenant compte des modifications (entre autres) des paramètres. Pour cela, dans l’arbre de données, faire un clic droit sur l’optimisation puis Exécuter. Astuce 3 : Le déroulement de l’optimisation peut être re-visualisé. Pour cela, dans sa fenêtre graphique, sélectionner le panneau [x2](x1), clic droit sur la figure puis Rejouer. Astuce 4 : Dans la fenêtre graphique, il est possible d’ajouter ou d’enlever des panneaux de déroulement d’optimisation (clic droit sur le fond de panneau ou sur n’importe quel onglet, par exemple sur [x2](x1) ). Astuce 5 : La sélection dans l’arbre de données de plusieurs objets (exemple : les paramètres, l’algorithme d’optimisation, l’optimisation, …) suivie de Editer, débute une édition simultanée dans une table. Le bouton Exécuter, permet de re-exécuter (après Valider, si un objet a été modifié) sans quitter l’édition simultanée. Remarque sur la cible d’une fonction d’optimisation : La cible d’une fonction d’optimisation permet d’indiquer à l’algorithme d’optimisation une valeur à atteindre. Si aucune cible n’est définie, l’algorithme cherche la plus petite valeur possible dans le cas d’une minimisation ou la plus grande valeur possible dans le cas d’une maximisation. Dans les situations où la fonction d’optimisation est coûteuse, il est usuel de définir une cible à atteindre relativement modeste afin de limiter le coût de uploads/Management/ algo-optim.pdf