• Accueil LIP6
  • Page : 'rapport_recherche' inconnue (menus.php)

LIP6 1997/030

  • Thèse
    Apprentissage de Connaissances de Contrôle pour l'Optimisation Combinatoire : Intégration du Raisonnement à Partir de Cas dans la Méthode Tabou
  • S. Grolimund
  • 227 pages - 12/11/1997- document en - http://www.lip6.fr/lip6/reports/1997/lip6.1997.030.ps.gz - 789 Ko
  • Contact : Stephan.Grolimund (at) nulllaforia.ibp.fr
  • Ancien Thème : APA
  • Sous le nom de méthode tabou, on regroupe une famille d'algorithmes qui ont pour but de résoudre des problèmes d'optimisation combinatoire, donc des problèmes NP-difficiles. Basées sur la recherche locale, ces techniques construisent des solutions sous-optimales, mais qui sont en général de bonne qualité. La méthode tabou a fait appel à des techniques d'apprentissage pour améliorer le processus de construction et d'identification de solutions, afin de parvenir aux bonnes solutions de manière plus efficace, et afin de montrer des performances plus robustes. Or, ces techniques d'apprentissage doivent être mises au point de manière spécifique à chaque problème d'optimisation, nécessitant chaque fois une bonne compréhension de la résolution de ce dernier.
    Cette thèse s'inscrit dans la voie de recherche qui étudie la construction, pour la méthode tabou, de techniques d'apprentissage qui sont indépendant du problème d'optimisation auquel elles s'appliquent. Nous proposons une technique d'apprentissage qui est basée sur le raisonnement à partir de cas. Un cas étant relatif à l'application d'une transformation d'une solution, il est composé de : a) le contexte dans lequel la transformation a été appliquée, et b) la récompense qualitative attribuée aux effets de cette transformation. Les futures transformations sont alors examinées de manière approfondie en prenant en considération les récompenses contenues dans les cas antérieurs. L'approche est évaluée sur trois des problèmes classiques d'optimisation combinatoire.
  • Mots clés : Intelligence Artificielle, Optimisation Combinatoire, Raisonnement à Partir de Cas, Méthode Taboue, Apprentissage de Connaissances de Contrôle
  • Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
Mentions légales
Carte du site