ADAPTATION DE LA DYNAMIQUE DES SYSTEMES AUTO-ORGANISES A LA RESOLUTION DU PROBLEME DE SATISFAISABILITE MAXIMALE DE FORMULES PROPOSITIONNELLES
Mots-clés :
Max-SAT, Heuristique, Optimisation extrémale, Optimisation combinatoire, Recherche locale stochastiqueRésumé
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.Références
- Arora S., Lund C., Motwani R., Sudan M., Szegedy M., "Proof verification and hardness of approximation problems", in Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, (1992), pp. 14-23.
- Asano T., Ono T., Hirata T., "Approximation algorithms for the maximum satisfiability problem", Nordic Journal of Computing, 3, (1996), pp. 388-404.
- Asano T., Williamson D.P., "Improved approximation algorithms for MAX SAT", Journal of Algorithms, 42(1), (2002), pp. 173-202.
- Bak P., Sneppen K., "Punctuated equilibrium and criticality in a simple model of evolution", Physical Review Letters, 71, (1993), pp. 4083-4086.
- Battiti R., Protasi M., "Reactive search, a history-sensitive heuristic for Max-SAT", ACM Journal of Experimental Algorithmics 2, (1997), p.2.
- Boettcher S., Percus A.G., "Nature’s way of optimising", Artificial Intelligence, 119, (2000), pp. 275-286.
- Boettcher S., Percus A.G., "Optimization with extremal dynamics", Physical Review Letters, Vol.86, N°23, (2001), pp. 5211-5214.
- Boettcher S., Percus A.G., "Extremal optimization for graph partitioning", Physical Review E, Vol.64, 026114, (2001), pp. 1-13.
- Cook S.A., "The complexity of theorem proving procedures", in Proceedings of the 3rd Annual ACM Symposium of the Theory of Computation, (1971), pp. 151-158.
- Garey M., Johnson D., "Computers and intractability: A guide to the theory of NP-completeness", W.H. Freeman and Company, New York, (1979).
- Glover F., "Tabu search : Part I", ORSA Journal on Computing, 1 (3), (1989), pp. 190-206.
- Glover F., "Tabu search : Part II", ORSA Journal on Computing, 2 (1), (1989), pp. +32.
- Goemans M., Williamson D.P., "A new -approximation algorithm for the maximum satisfiability problem", SIAM Journal on Discrete Mathematics, 7, (1994), pp. 656-666.
- Goemans M., Williamson D.P., "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM, 42, (1995), pp. 1115-1145.
- Hansen P., Jaumard B., "Algorithms for the maximum satisfiability problems", Computing, 44, (1990), pp. 279-303.
- Jiang Y., Kautz H., Selman B., "Solving problems with hard and soft constraints using a stochastic algorithm for Max-SAT", in Proceedings of the 1st International Joint Workshop on Artificial Intelligence and Operational Research, (1995).
- Johnson D., "Approximation algorithms for combinatorial problems", Journal of Computer and System Sciences, 9, (1974), pp. 256-278.
- Kirkpatrick S., Gelatt C.D., Vecchi P.M., "Optimization by simulated annealing", Science, 220, (1983), pp. 671-680.
- Mazure B., Sais L., Gregoire E., "Tabu search for SAT", in Proceedings of the 14th National Conference on AI, AAAI-1997, (1997), pp. 281-285.
- McAllester D., Selman B., Kautz H., "Evidence for invariants in local search", in Proceedings of the 14th National Conference on AI, AAAI-1997, (1997), pp. 321-326.
- Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller H., Teller E., "Equation of state calculations by fast computing machines", Journal of Chemical Physics, 21, (1953), pp. 1087-1092.
- Selman B., Kautz H., "An empirical study of greedy local search for satisfiability testing", in Proceedings of the 11th National Conference on AI, AAAI-1993, (1993), pp. 46-51.
- Selman B., Kautz H., "Domain independent extensions to GSAT : Solving large structured satisfiability problems", in Proceedings of the IJCAI-93, (1993), pp. 290-295.
- Selman B., Kautz H., Cohen B., "Noise strategies for improving local search", in Proceedings of the 12th National Conference on Artificial Intelligence, AAAI-1994, (1994), pp. 337-343.
- Spears W.M., "Simulated annealing for hard satisfiability problems", in D.S. Johnson and M.A. Trick editors, In Cliques, Coloring and Satisfiability : Second DIMACS Implementation Challenge, (1996), pp. 553-558.
- Yannakakis M., "On the approximation of maximum satisfiability", Journal of Algorithms, 17, (1994), pp. 475-502.
Téléchargements
Publié-e
Comment citer
Numéro
Rubrique
Licence
Les auteurs publiant dans cette revue acceptent les termes suivants :- Les auteurs détiennent le droit d'auteurs et accordent à la revue
le droit de première publication, avec l’ouvrage disponible simultanément [SPÉCIFIER LA PÉRIODE DE TEMPS] après publication, sous la licence Licence d’attribution Creative Commons qui permet à d'autres de partager l'ouvrage en en reconnaissant la paternité et la publication initiale dans cette revue. - Les auteurs peuvent conclure des ententes contractuelles additionnelles et séparées pour la diffusion non exclusive de la version imprimée de l'ouvrage par la revue (par ex., le dépôt institutionnel ou la publication dans un livre), accompagné d'une mention reconnaissant sa publication initiale dans cette revue.
- Les auteurs ont le droit et sont encouragés à publier leur ouvrage en ligne (par ex., dans un dépôt institutionnel ou sur le site Web d'une institution) avant et pendant le processus de soumission, car cela peut mener à des échanges fructueux ainsi qu'à un nombre plus important, plus rapidement, de références à l’ouvrage publié (Consulter The Effect of Open Access).
