Abstract FR:

Sous le nom de methode tabou, on regroupe une famille d'algorithmes qui ont pour but de resoudre des problemes d'optimisation combinatoire, donc des problemes np-durs. Basees sur la recherche locale, ces techniques construisent des solutions sous-optimales, mais qui sont en general de bonne qualite. La methode tabou a fait appel a des techniques d'apprentissage pour ameliorer le processus de construction et d'identification de solutions, afin de parvenir aux bonnes solutions de maniere plus efficace, et afin de montrer des performances plus robustes. Or, ces techniques d'apprentissage doivent etre mises au point de maniere specifique a chaque probleme d'optimisation, necessitant chaque fois une bonne comprehension de la resolution de ce dernier. Cette these s'inscrit dans la voie de recherche qui etudie la construction, pour la methode tabou, de techniques d'apprentissage qui sont independant du probleme d'optimisation auquel elles s'appliquent. Nous proposons une technique d'apprentissage qui est basee sur le raisonnement a partir de cas. Un cas etant relatif a l'application d'une transformation d'une solution, il est compose de : a) le contexte dans lequel la transformation a ete appliquee, et b) la recompense qualitative attribuee aux effets de cette transformation. Les futurs transformations sont alors examines de maniere approfondie en prenons en consideration les recompenses contenues dans les cas anterieurs. L'approche est evaluee sur trois des problemes classiques d'optimisation combinatoire.