• View
• Edit
• History
• Print

ENPC2009

Sujet 1: Recherche d'un chemin dans un labyrinthe

L'objectif de ce mini-projet, c'est de définir une méthode permettant de trouver un chemin dans un labyrinthe le plus efficacement possible. Il faut que la méthode soit plus efficace que la méthode de recherche aléatoire. Vous disposerez d'un générateur de labyrinthe (script python) ainsi que d'un document décrivant les méthodes utilisées dans un logiciel de jeux d'échecs pour trouver une stratégie gagnante. Environnement de programmation conseillé: Scilab.

Sujet 2: Optimisation topologique via la programmation linéaire en nombres entier.

L'objectif de ce mini-projet, c'est d'implémenter une méthode décrite dans une thèse. Cette méthode permet de déterminer la forme optimale d'une pièce soumise à des charges et fixée d'une certaine façon. Vous aurez à votre disposition la thèse en question ainsi qu'une boite à outils scilab permettant de faire de la programmation en nombres entiers. Un article est aussi disponible. Environnement de programmation conseillé: Scilab.

Sujet 3: Le problème du voyageur de commerce et le recuit simulé "backbone".

L'objectif de ce mini-projet est d'implémenter une méthode de recuit simulé permettant de trouver le circuit le plus court pour le problème du voyageur de commerce. Vous aurez à implémenter la méthode qui, à partir de plusieurs solutions différentes trouvées par le recuit simulé, générera un problème plus petit et plus simple (les tronçons communs de chaque circuit seront résumés à un point). Vous aurez à votre disposition un article décrivant cette méthode (article 1, article 2, article 3). Environnement de programmation conseillé: Scilab.

Sujet 4: Le problème du voyageur de commerce et le recuit simulé intelligent.

L'objectif de ce mini-projet est d'implémenter un recuit simulé pour résoudre le problème du voyageur de commerce. La méthode à implémenter sera celle définie dans un article d'un concurrent à un challenge Roadef. Cette méthode utilise une grande quantité de voisinages possibles et sélectionne au fur et à mesure de l'optimisation les voisinages les plus intéressants. Vous aurez à votre disposition une présentation décrivant cette méthode. Environnement de programmation conseillé: Scilab.

Sujet 5: Planification d'expériences adaptative.

Le but de ce sujet sera de générer un plan d'expériences adaptatif. Dans un premier temps, on génère un petit plan d'expériences, on génère un modèle de type krigeage. Ensuite, et de façon itérative, on complète ce plan d'expériences en optimisant un critère qui permet de placer un nouveau point. Vous avez à votre disposition un article sur cette approche. Dans le répertoire TestProblems-1.0, vous trouverez des problèmes test pour évaluer cette méthode. Vous aurez à votre disposition un article décrivant cette méthode. Vous aurez à utiliser une boite à outils de Krigeage ainsi que la boite à outils Algorithmes Génétiques (disponible sous scilab-5). Environnement de programmation conseillé: Scilab.

Sujet 6: La méthode de Sherman Woodbury et Morrison.

Le but de ce mini-projet sera d'implémenter une méthode de "Fast Reanalysis" dans un code de calculs de structures de type barres. Cette méthode permet de calculer un gradient d'une structure plus rapidement qu'en utilisant une différence finie classique. Vous aurez à votre disposition une boite à outils permettant de calculer les efforts et déformations dans une structure de type barre. Vous aurez aussi à votre disposition un script Scilab permettant de faire de l'optimisation sur une structure de type barre. Vous aurez à votre disposition un article décrivant cette méthode. Un article wikipedia est aussi disponible. Une méthode similaire est utilisée dans un code éléments finis interne par BMW pour la conception mécanique. Environnement de programmation conseillé: Scilab.

Quelques informations supplémentaires sont disponibles sur cette page.

Sujet 7: L'optimisation Robuste utilisant la méthode des éléments finis stochastiques.

Le but de ce mini-projet sera d'implémenter une méthode d'optimisation utilisant la méthode des éléments finis stochastiques. L'optimisation robuste permet de traiter des problèmes d'optimisation ayant des contraintes probabilistes (la probabilité qu'une contrainte soit satisfaite doit être supérieure à une limite donnée). Vous aurez à votre disposition des scripts implémentant des méthodes d'optimisation robustes plus classiques (FORM, Unscented transform). Vous aurez à votre disposition une présentation sur la méthode des éléments finis stochastiques ainsi que divers autres documents (notamment la thèse d'habilitation d'Olivier Le Maitre et une présentation faite cette année. Environnement de programmation conseillé: Scilab.

Sujet 8: L'optimisation de structure via Code Aster

Le but de ce mini-projet sera d'implémenter une méthode d'optimisation de structure efficace utilisant Code Aster et Scilab. Un premier ensemble de scripts a été réalisé. Cette première méthode utilise la méthode de Nelder et Mead pour effectuer une optimisation. Les résultats de ne sont pas satisfaisant. La méthode est relativement lente et ne converge pas toujours. Il faudra donc utiliser une méthode gérant les contraintes, et trouver une façon d'accélérer le calcul (via un calcul de sensibilités par exemple). Vous aurez à votre disposition plusieurs boites à outils permettant de faire une optimisation avec contraintes (Conmin, Ipopt) ainsi qu'une archive contenant une première ébauche de script. Environnement de programmation conseillé: Scilab + Code Aster (+ Python).

Sujet 9: Atelier de peinture 1

On se donne une séquence de voitures que l’on souhaite peindre de deux couleurs différentes, disons rouge et bleu. La séquence est composée de différents modèles, chaque modèle apparaissant exactement deux fois. On cherche la stratégie de peinture qui minimise le nombre de changment de couleurs. Il s’agit du « binary paintshop problem » ou PPW(2,1). Prenons par exemple la séquence suivante, où chaque lettre représente un modèle de voiture :

On pourra par exemple colorier la séquence comme ceci :

soit avec 3 changements de couleurs, ce qui est cependant sous-optimal par rapport à la solution suivante :

L’objectif de ce projet est de proposer un algorithme exact de résolution du PPW(2,1) s’appuyant sur une méthode de « branch and bound ». Les éléves auront à leur disposition une courte bibliographie sur le paint shop problem ainsi qu’un document pédagogique pour les orienter dans leurs recherches. Cette approche est décrite dans cet article. Environnement de programmation conseillé: Scilab

Sujet 10: Atelier de peinture 2

On considère ici une variante du binary paint shop problem, où la séquence de voitures n’est plus composée de modèles apparaissant 2 fois mais n>2 fois, et l’on souhaite en colorier une partie en bleu et le reste en rouge. L’objet de ce projet est dans un premier temps de dévellopper un algoritme de résolution s’appuyant sur une méthode de recuit simulé. On l’essaiera ensuite sur différent cas résolus, et on l’utilisera pour « tester » une conjecture de combinatoire. Les éléves disposeront d’une toolbox scilab pour le recuit simulé. Si l’avancement des deux sujets concernant le paint shop problem le permet, les groupes pourront comparer les performances respectives des algorithmes. L’algorithme exact permettera notamment de juger de la qualité des solutions de l’algorithme approché dans le cas n=2.

Cette approche est décrite dans cet article. Environnement de programmation conseillé : Scilab

Sujet 11: Modélisation du trafic sur un réseau routier

On se donne un réseau de transport avec des flux de voyageurs désirant se rendre d'une origine (O) à une destination (D) et on cherche à répartir ces flux entre les différents chemins reliant O à D de manière à ce que les chemins utilisés est le même temps de parcours et que celui-ci soit inférieur aux temps de parcours des chemins non utilisées. Il s’agit du problème d’affectation du trafic à l’équilibre usager. Ce problème peut s'écrire comme un programme d'optimisation convexe. Le projet consiste à implémenter un algorithme proposé dans un article scientifique, s’appuyant sur une méthode de gradient projetté et de le comparer avec des méthodes existantes. Les éléves disposeront de l’article en question ainsi que d’une toolbox siclab dédiée à l’affectation de trafic, implémentant la plupart des algorithmes usuels d’affcetation, et proposant un outil de visualisation.

Environnement de programmation conseillé : Scilab