Méta-heuristiques hybrides pour les problèmes Max-W-Sat difficiles
H. Drias, Dalila Boughaci
كلية المعلوماتية والالكترونيات-جامعة العلوم والتكنولوجيا هواري بومدين - الجزائر · الجزائر
Cette thèse traite un problème réputé difficile qui est la satisfiabilité maximale pondérée (MAX-W-SAT en abrégé). Etant donné un ensemble C de clauses sous forme disjonctive définies sur un ensemble X de variables logiques, à chaque clause Ci un poids Wi est associé. Le problème MAX-W-SAT consiste à trouver une assignation aux variables de X qui maximise la somme des poids des clauses satisfaites. Le problème MAX-W-SAT suscite un intérêt particulier car il possède plusieurs applications notamment en raisonnement automatique et en démonstration de théorèmes. De plus, La résolution de ce problème a une très grande importance dans le domaine de l’intelligence artificielle, en particulier, dans l’élimination de l’incohérence des bases de connaissances dans les systèmes experts. L’accent est mis dans ce travail sur les méta- heuristiques ainsi que les voies qu’ouvrent ces approches dans l’optimisation combinatoire. Il a pour but de clarifier le langage obscurequi entoure les concepts sous-jacents, et d’expliciter l’apport précieux qu’offrent actuellement ces méthodes dans l’intelligence artificielle. Parmi ces méthodes, on trouve la recherche dispersée et la recherche locale guidée, qui bousculent les méthodes classiques et établissent de nouvelles stratégies de recherche. La recherche dispersée appelée en anglais «SCATTER SEARCH» est une méta-heuristique évolutionniste basée population, elle génère de nouvelles solutions en commençant par un ensemble de solutions appelées solutions références. L’approche fonctionne avec un opérateur de combinaison permettant d’obtenir des solutions admissibles. La recherche locale guidée est une approche basée pénalité. Elle permet, en principe, d’éviter l’optimum local. C’est une amélioration de la recherche locale, elle modifie la fonction objective dans le but d’approcher l’optimum global. Dans notre étude, nous avons proposé deux solutions au problème MAX-W-SAT. La première est basée sur la recherche dispersée alors que la seconde est basée sur la recherche locale guidée. De plus, nous essaierons pour notre part d’améliorer les performances de ces derniers algorithmes en présentant quelques orientations générales pour une hybridation pertinente de quelques heuristiques connues dans la littérature informatique basées sur la recherche tabou, et la procédure GSAT.