Abstract FR:

Le probleme de satisfaction de contraintes (csp pour constraint satisfaction problem) constitue un modele simple et tres general qui permet de representer un grand nombre de problemes combinatoires classiques et d'applications pratiques. Notre etude porte sur la resolution du csp par les metaheuristiques. Elle comporte trois parties. Dans la premiere partie, nous presentons les principales classes de metaheuristiques existantes (recherche locale, algorithmes genetiques et hybrides) et analysons les caracteristiques de ces methodes. La seconde partie propose une approche de resolution generale du csp par la recherche locale. Nous introduisons a) un ensemble de contraintes primitives, b) une fonction d'evaluation des solutions fondee sur une methode de penalisation des contraintes. Les primitives proposees nous permettent de representer un nombre important de problemes comportant des contraintes binaires mais aussi des contraintes n-aires complexes. Nous mettons en oeuvre un ensemble d'algorithmes de recherche locale, notamment un algorithme tabou. Des structures de donnees speciales et des algorithmes incrementaux efficaces sont developpes. Des tests experimentaux sont realises avec des instances aleatoires de csp ainsi que pour la coloration de graphes, l'affectation de frequences et l'affection d'equipages. Les resultats obtenus sont compares avec ceux d'autres approches connues pour ces problemes et s'averent tres competitifs. Dans la troisieme partie, l'approche genetique hybride est appliquee a un csp particulier : la k-coloration de graphe. Pour ce probleme, nous proposons des croisements specialises fondes sur la recombinaison efficace des classes de coloration. Nous developpons ensuite un algorithme hybride qui integre ces croisements et notre algorithme tabou. Les tests effectues montrent que l'algorithme obtient des resultats remarquables et qu'il parvient a ameliorer les meilleurs resultats connus pour plusieurs graphes du challenge dimacs.