Adaptation de la dynamique des systemes auto-organises a la resolution du probleme de satisfaisabilite maximale de formules propositionnelles

Abstract FRE

Le problème de satisfaisabilité maximale de formules propositionnelles (Max-SAT) est un problème central en intelligence artificielle, logique mathématique et optimisation combinatoire.

Les algorithmes de résolution utilisent différentes heuristiques pour parcourir l’espace de recherche dont les performances sont liées à leur complexité et au réglage de leurs paramètres.

L’Optimisation Extrémale (EO) est une des méthodes les plus simples à mettre en oeuvre et n’utilise qu’un seul paramètre de contrôle.

Elle est inspirée de la dynamique des systèmes physiques de complexité émergente et de leur capacité à s’auto-organiser pour atteindre un état d’adaptation optimal.

Ce travail est motivé par les progrès récemment réalisés par l’application de cette méthode à des problèmes classiques d’optimisation tels que le partitionnement de graphe.

Dans cet article, nous décrivons un nouvel algorithme de recherche locale stochastique pour la résolution du problème Max-SAT s’articulant autour de la méthode EO et présentons une analyse empirique de ses performances.

Les résultats numériques obtenus améliorent de façon significative ceux produits par les algorithmes de recuit simulé et de recherche taboue.