|
ARTICLE VOL 22/RSTI1 - 2003
- pp.281-294
|
Évolution + Adaptation = Résolution
Nous présentons dans cet article les bases d’un nouveau modèle de calcul permettant
de combiner des méthodes complètes et incomplètes pour la résolution de problèmes de
satisfaction de contraintes. Ce schéma algorithmique utilise des techniques de propagation de
contraintes dans un contexte évolutionnaire intégrant également des heuristiques de recherche
locale. L’uniformité des structures utilisées autorise une interaction plus homogène entre les
différentes méthodes mises en oeuvre et permet également de bénéficier au mieux de leurs atouts
respectifs. La grande flexibilité de ce modèle offre également la possibilité d’en envisager diverses
extensions. Nous mettons en avant l’intérêt de notre approche sur quelques exemples par
le biais d’une implémentation.
In this paper, we present a new framework for combining complete and incomplete
methods in order to solve constraint satisfaction problems. This algorithm scheme uses constraint
propagation techniques and local search heuristics embedded in an evolutionary computation
context. The uniformity of the involved structures provides a more harmonious interaction
between the different implemented methods, and also benefits from the respective methods
assets. Furthermore, the great flexibility of this model allows us to foresee various extensions.
We emphasize the interest of our approach on some examples which are solved by means of an
implementation.
Problèmes de Satisfaction de Contraintes - Algorithmes évolutionnistes - Propagation de contraintes - Recherche locale
Constraint Satisfaction Problems - Evolutionary Algorithms - Constraint Propagation - Local Search
Français
|
| PRIX |
• Abonné (hors accès direct) :
12.5 €
• Non abonné :
25.0 €
|
|
| |
--> Tous les articles sont dans un format PDF protégé  |
| |
|
|
ACCÉDER A L'ARTICLE COMPLET
(193 Ko)
--> NÉCESSITE ADOBE DIGITAL EDITIONS :
|
