VERSION ANGLAISE

Toutes les méthodes d'optimisation ont des paramètres internes qui prennent une part prépondérante dans leurs performances. La difficulté pour leurs utilisateurs est de trouver un bon réglage pour chaque problème. Depuis quelques années une part importante de la recherche en optimisation combinatoire porte sur la conception de méthodes adaptatives. L'objectif de cette démarche est de définir des procédés qui tentent d'adapter dynamiquement le paramétrage des méthodes en fonction du problème. Dans ce contexte, cette thèse porte sur les mécanismes de mémoire et d'adaptation dans le but de mettre au point une méthode de Recherche Locale Adaptative (RLA) combinant des mécanismes d'extension et de restriction du voisinage. L'extension du voisinage est définie par une procédure de détection de blocage de la recherche en étudiant l'historique des choix effectués par la méthode afin d'intervenir sur son comportement. Le mécanisme de restriction quant à lui est basé sur l'utilisation d'une liste Tabou à paramétrage adaptatif pour gérer l'accès aux variables. La méthode ainsi obtenue a été appliquée à deux problèmes : un problème académique, la k-coloration de graphes, et un problème réel, l'affectation de fréquences en réseaux de radiocommunications. Plusieurs variantes de RLA ont été développées et comparées à des résultats publics sur les deux problèmes.