Proposition de stage de DEA ou d'ingénieur

2004-2005

Titre : "Programmation génétique et grammaire stochastique"

Résumé 

La programmation génétique (GP) est une variante des algorithmes génétique qui manipule des programmes. Elle a notamment été utilisée pour apprendre des expressions décrivant des structures en réseau (circuits analogiques, réseaux de neurones artificiels).
Pour restreindre intelligemment l'immense espace de recherche, on peut représenter les connaissances du domaine par des grammaires génératives fournies a priori.
Par ailleurs, de récents développements des algorithmes génétiques (les algorithmes à Estimations de Distribution) consistent à rechercher non plus une solution au problème d'optimisation initial, mais une distribution sur l'espace de recherche qui se concentrerait dans les zones intéressantes - contenant les solutions.

Transposés à la programmation génétique, ces algorithmes consistent à apprendre un modèle grammatical génératif stochastique. L'un des objectifs est alors de favoriser l'émergence de modules réutilisables pour rendre plus efficace la recherche d'une bonne solution. Un tel algorithme se décompose dès lors comme suit :

1. générer des individus à partir de la grammaire stochastique,
   
2. évaluer les individus,
   
3. réévaluer les paramètres de la grammaire stochastique en fonction des fitness (performance par rapport au problème) des individus.
   

Les grammaires généralement utilisées dans ce contexte sont des grammaires non-contextuelles paramétrées, où les paramètres ont un lien avec le contexte d'application des règles de production (par exemple, la profondeur dans l'arbre de dérivation). En partant des derniers développements sur ce sujet, l'idée principale de ce stage est d'appliquer des méthodes d'apprentissage pour généraliser sur les paramètres, et pouvoir ainsi maintenir un nombre raisonnable de règles.

Le sujet de ce stage est :

1. d'implémenter avec le framework SFERES un modèle de Programmation Génétique basé sur l'évolution d'un modèle de grammaire non-contextuelle stochastique paramétrée, appliqué classiquement à l'évolution d'une expression,
2. puis d'ajouter au modèle existant des capacités de généralisation permettant d'améliorer et de comparer les performances obtenues au modèle de base,
3. enfin, si les résultats sont satisfaisants, le champ d'application sera étendu à la construction d'une structure en réseau (un automate à états finis, puis un réseau de neurones).