Abstract FR:

Dans cette thèse, nous abordons la problématique de la difficulté des instances de problèmes vis a vis de la recherche locale stochastique. Notre approche consiste à considérer qu'un processus de recherche locale stochastique est caractérisé par deux entités distinctes: d'une part un algorithme de recherche, d'autre part un paysage spécifique à l'instance de problème à traiter. Nous nous intéressons à une classe de paysages associés au problème de satisfaction d'une formule booléenne. La difficulté de ces paysages est liée à la présence d'extremums locaux. Notre contribution se situe à trois niveaux. En premier lieu, nous développons un outillage dédié à l'étude expérimentale des paysages. Cet outillage comprend un algorithme d'échantillonnage stratifié, permettant notamment d'effectuer des mesures de densité d'extremums locaux dans certaines régions critiques, et deux algorithmes pour le dénombrement approché des extremums globaux. Nous proposons également une méthode originale de production d'instances SAT atypiques en terme de difficulté de résolution, notamment avec l'approche locale stochastique, et en terme de nombre de solutions. Enfin, nous présentons quelques résultats expérimentaux visant à mettre en parallèle, pour un panel d'instances SAT, des données spécifiques aux paysages et des informations relatives au comportement des processus de recherche.