Contexte
Le contexte de ce stage est celui des algorithmes d'optimisation évolutionnaires, algorithmes stochastiques d'optimisation inspirés du principe de l'évolution darwinienne des espèces. Dans le cadre de l'optimisation continue, l'algorithme le plus performant à l'heure actuelle est la méthode CMA-ES (Covariance Matrix Adaptation Evolution Strategy) développée par Nikolaus Hansen à la fin des années 90.
Du fait de sa souplesse d'utilisation (ils ne font aucune hypothèse de régularité sur la fonction à optimiser ou les contraintes du problème), cet algorithme connait à l'heure actuelle un succès croissant dans de nombreuses applications industrielles, comme l'optimisation de formes de lentilles, de mécanismes de mélange, pour la détection visuelle d'obstacles, la prédiction du repliement des protéines, la calibration de systèmes de caméras, l'évolution de populations, ...
Cependant, l'algorithme CMA-ES ne s'applique aujourd'hui que sur des problèmes sans contraintes (ou avec des simples contraintes de bornes sur les variables). Or de très nombreux problèmes d'optimisation mettent en jeu des contraintes non-linéaires. Les méthodes de pénalisation sont classiquement utilisées pour ramener un problèmes avec contraintes à un problème sans contraintes : une somme pondérée des violations de contraintes est ajoutée à la fonction objectif (à minimiser). Mais les valeurs des poids de cette pénalisation a une grande influence sur le résultat de l'algorithme. Des méthodes plus spécifiques au domaine des algorithmes évolutionnaires ont également été proposées, tel le rang stochastique : le rang d'une solution possible est modifé de manière stochastique en fonction de la valeur de la violation des contraintes.
Objectifs du stage
Le but du stage est d'étudier la faisabilité ed l'utilisation de méthodes de pénalisation et/ou de rang stochastique dans le contexte d'un algorithme CMA-ES simplifié. L'approche sera essentiellement expérimentale, ce qui signifie l'implantation de plusieurs possibilités de prise en compte des contraintes, et leurs comparaison sur un ensemble de fonctions test qu'il faudra également soigneusement choisir dans la littérature.
Prérequis
Des connaissances en optimisation numériques et en algorithmes évolutionnaires seront appréciées, mais ne sont pas nécessaires. Un goût certain pour la programmation et les calculs numériques est par contre indispensable. Les algorithmes évolutionnaires de base sont disponibles en Matlab, Scilab ou C.
Responsables : Nikolaus Hansen, Laboratoire commun Microsoft-INRIA, Saclay, Anne Auger et Marc Schoenauer, Projet TAO, INRIA Futurs et LRI.
Lieu du stage : LRI
Rémunération: indemnités de stage au tarif syndical suivant ressources (entre 350 et 600 euros par mois)
Le contexte de ce stage est celui des algorithmes d'optimisation évolutionnaires, algorithmes stochastiques d'optimisation inspirés du principe de l'évolution darwinienne des espèces. Dans le cadre de l'optimisation continue, l'algorithme le plus performant à l'heure actuelle est la méthode CMA-ES (Covariance Matrix Adaptation Evolution Strategy) développée par Nikolaus Hansen à la fin des années 90.
Du fait de sa souplesse d'utilisation (ils ne font aucune hypothèse de régularité sur la fonction à optimiser ou les contraintes du problème), cet algorithme connait à l'heure actuelle un succès croissant dans de nombreuses applications industrielles, comme l'optimisation de formes de lentilles, de mécanismes de mélange, pour la détection visuelle d'obstacles, la prédiction du repliement des protéines, la calibration de systèmes de caméras, l'évolution de populations, ...
Cependant, l'algorithme CMA-ES ne s'applique aujourd'hui que sur des problèmes sans contraintes (ou avec des simples contraintes de bornes sur les variables). Or de très nombreux problèmes d'optimisation mettent en jeu des contraintes non-linéaires. Les méthodes de pénalisation sont classiquement utilisées pour ramener un problèmes avec contraintes à un problème sans contraintes : une somme pondérée des violations de contraintes est ajoutée à la fonction objectif (à minimiser). Mais les valeurs des poids de cette pénalisation a une grande influence sur le résultat de l'algorithme. Des méthodes plus spécifiques au domaine des algorithmes évolutionnaires ont également été proposées, tel le rang stochastique : le rang d'une solution possible est modifé de manière stochastique en fonction de la valeur de la violation des contraintes.
Objectifs du stage
Le but du stage est d'étudier la faisabilité ed l'utilisation de méthodes de pénalisation et/ou de rang stochastique dans le contexte d'un algorithme CMA-ES simplifié. L'approche sera essentiellement expérimentale, ce qui signifie l'implantation de plusieurs possibilités de prise en compte des contraintes, et leurs comparaison sur un ensemble de fonctions test qu'il faudra également soigneusement choisir dans la littérature.
Prérequis
Des connaissances en optimisation numériques et en algorithmes évolutionnaires seront appréciées, mais ne sont pas nécessaires. Un goût certain pour la programmation et les calculs numériques est par contre indispensable. Les algorithmes évolutionnaires de base sont disponibles en Matlab, Scilab ou C.
Responsables : Nikolaus Hansen, Laboratoire commun Microsoft-INRIA, Saclay, Anne Auger et Marc Schoenauer, Projet TAO, INRIA Futurs et LRI.
Lieu du stage : LRI
Rémunération: indemnités de stage au tarif syndical suivant ressources (entre 350 et 600 euros par mois)