Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Thèse

Approches Hybrides pour les problèmes de Satisfiabilité (SAT et MAX-SAT)

Résumé : Cette thèse est centrée sur la résolution des problèmes de satisfiabilité SAT et MAX-SAT. Les contributions apportées sont de trois types. Tout d’abord nous avons développé l’algorithme mémétique GASAT pour les problèmes SAT et MAX-SAT hybridant un algorithme tabou et un algorithme génétique. Des outils spécifiques aux problèmes de satisfiabilité y ont été intégrés tels que des mécanismes d’intensification, de diversification et un nouvel opérateur de croisement. Ensuite, nous avons proposé un nouveau cadre de résolution permettant aux méthodes exactes et aux méthodes approchées de manipuler la même représentation de l’espace de recherche. Pour cela, nous avons ajouté une troisième valeur de vérité indéterminé . Les résultats obtenus par les algorithmes hybrides trivalués montrent l’intérêt de ce cadre de résolution. Enfin, nous nous sommes penchés sur les heuristiques de branchement des algorithmes de Branch and Bound pour le problème MAX-SAT. L’étude que nous présentons montre que ces heuristiques réagissent très différemment en fonction des paramètres initiaux, de la structure de l’instance étudiée et des mécanismes d’amélioration du Branch and Bound. Elle permet d’envisager la création de nouvelles heuristiques spécifiquement dédiées au problème MAX-SAT.
Type de document :
Thèse
Liste complète des métadonnées

https://hal.univ-angers.fr/tel-03379662
Contributeur : Frédéric lardeux Connectez-vous pour contacter le contributeur
Soumis le : vendredi 15 octobre 2021 - 09:56:39
Dernière modification le : lundi 14 novembre 2022 - 02:42:07

Identifiants

  • HAL Id : tel-03379662, version 1

Citation

Frédéric Lardeux. Approches Hybrides pour les problèmes de Satisfiabilité (SAT et MAX-SAT). Intelligence artificielle [cs.AI]. Université d'Angers, 2005. Français. ⟨NNT : ⟩. ⟨tel-03379662⟩

Partager

Métriques

Consultations de la notice

8