Apprentissage de Connaissances de Contrôle pour l'Optimisation Combinatoire : Intégration du Raisonnement à Partir de Cas dans la Méthode Tabou

S. Grolimund

LIP6 1997/030: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
227 pages - Novembre/November 1997 - French document.

PostScript : 771 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Apprentissage et Acquisition de Connaissances

Titre français : Apprentissage de Connaissances de Contrôle pour l'Optimisation Combinatoire : Intégration du Raisonnement à Partir de Cas dans la Méthode Tabou
Titre anglais : Learning of control knowledge for combinatorial optimisation: An integration of case-based reasoning to tabu search

Résumé : 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.

Abstract : Tabu search is a meta-heuristic that is able to solve various NP-hard combinatorial optimisation problems. A variant of classical local search, tabu search constructs high quality, near to optimal solutions. In order to speed up the solution generation process, as well as to make its results more robust, tabu search employs particular learning techniques whilst optimisation is in progress. However, these learning schemes have to be specially adapted to each optimisation problem at hand.
This thesis studies the construction of a learning technique for tabu search which is problem independent. We introduce an algorithm that uses case-based reasoning. A case is constructed from the application of a transformation to a solution state. It has two parts, a description of the context in which the transformation applies, and a qualitative reward credited to it with regard to the results of the transformations application. Using this information available in the cases, the ongoing transformations are more deeply analysed with respect to available reward. The fully implemented system is evaluated on three classical combinatorial optimisation problems.

Mots-clés : Intelligence Artificielle, Optimisation Combinatoire, Raisonnement à Partir de Cas, Méthode Taboue, Apprentissage de Connaissances de Contrôle

Key-words : Artificial Intelligence, Combinatorial Optimisation, Case-Based Reasoning, Tabu Search, Learning of Control Knowledge

Publications internes LIP6 1997 / LIP6 research reports 1997

Responsable Éditorial / Editor
webmaster@lip6.fr