ADAPTATION DE LA DYNAMIQUE DES SYSTEMES AUTO-ORGANISES A LA RESOLUTION DU PROBLEME DE SATISFAISABILITE MAXIMALE DE FORMULES PROPOSITIONNELLES

M. EL BACHIR MENAÏ, M BATOUCHE

Ré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.

Mots-clés


Max-SAT ; Heuristique ; Optimisation extrémale ; Optimisation combinatoire ; Recherche locale stochastique

Texte intégral :

PDF

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.


Renvois

  • Il n'y a présentement aucun renvoi.




Direction des Publications et de l'animation scientifique

Université des Frères Mentouri Constantine 1. Route Ain El-Bey. 25000. Algérie.