Mémoires de Fin d’Etudes
Etablissement
Université de Tébessa - Larbi Tébessi
Affiliation
Département d’Informatique
Auteur
Laaziz, Safia
Directeur de thèse
Batouche Mohamed Chaouki (Professeur)
Filière
Informatique
Diplôme
Magister
Titre
Résolution des problèmes Max-SAT par des approches inspirées de la nature
Mots clés
Max-SAT, optimisation combinatoire, métaheuristiques, problèmes NP-difficiles, systèmes complexes, intelligence computationnelle.
Résumé
Le problème de satisfiabilité d’une formule booléenne mise sous forme normale conjonctive (SAT) est un problème NP-complet : étnt donné une formule booléenne, la question est de savoir si elle admet un modèle. Une extension de SAT est le problème Max-SAT qui consiste à satisfaire le plus grand nombre de clauses de la formule propositionnelle. Le problème de satisfiabilité maximale de formules propositionnelles (Max-SAT) est un problème central en intelligence artificielle, logique mathématique et optimisation combinatoire. En outre, plusieurs problèmes de Recherche Opérationnelles (RO) ou d’Intelligence Artificielle (IA) peuvent s’exprimer sous forme de problèmes Max-SAT (l’ordonnancement d’actions, la gestion de ressources, la diagnostic des pannes, la recherche d’une clique maximum dans un graphe, …). Max–SAT est problème NP-difficile, la recherche de solutions exactes requière alors des temps exponentiels. De nombreuses méthodes de résolution ont été développées et sont classées sommairement en deux grandes catégories : les méthodes exactes (complètes pour les problèmes de décision) qui garantissent la complétude de la résolution, et les méthodes approchées (resp. incomplètes) qui gagent en efficacité au dé triment de la complétude. L’objet de ce travail est d’une part une synthèse en matière de résolution des problèmes Max-SAT par des méthodes approchées. D’autre part, il s’agit de prposer de nouvelles méthodes pour la résolution des problèmes Max-SAT, ISat et PMSat par des approches inspirées de la nature.
Statut
Validé