ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 16/3 - 2002  - pp.367-382  - doi:10.3166/ria.16.367-382
TITLE
A Distributed Guided Genetic Algorithm for Max-CSPs

RÉSUMÉ
Ce papier traite les problèmes de satisfaction maximale des contraintes (Max-CSP) connus pour leur aspect NP-Complet, et ce, par une approche Multiagent (MA) des algorithmes génétiques (AGs) qui sont qualifiés de coûteux en termes de temps. L'objectif est donc double : d'une part, tirer profit de l'efficacité des AGs pour donner une bonne qualité aux Max-CSPs et, d'autre part, bénéficier des fondements MA afin de réduire la complexité temporelle des AGs. Les agents, crées dynamiquement, coopèrent pour satisfaire le maximum de contraintes. Chaque agent s'occupe d'une sous-population de chromosomes violant le même nombre de contraintes, et ce, à l'aide d'un AG guidé par le concept de "template" et l'heuristique de minimisation de conflits. Pour montrer l'avantage de cette approche des comparaisons expérimentales avec une version centralisée sont présentées.


ABSTRACT
This paper addresses Maximal Constraint Satisfaction Problems (Max-CSP), known to be NP-complete, by a multi-agent approach of Genetic Algorithms (GAs) which are known to be "expensive" in time. The objective is then double: on the one hand, take advantage of GA efficiency to provide good quality for Max-CSP and on the other hand, benefit from multi-agent principles to reduce GA temporal complexity. The approach consists of agents dynamically created and cooperating in order to satisfy the maximal number of constraints. Each agent performs its own GA, guided by both the template concept and the Min-conflict-heuristic, on a sub-population composed of chromosomes violating the same number of constraints. To show the advantage of this approach, experimental comparisons with a centralized implementation are given.


AUTEUR(S)
Khaled GHÉDIRA, Boutheina JLIFI

MOTS-CLÉS
problèmes de satisfaction maximale de contraintes, systèmes multiagents, algorithmes génétiques, heuristique de minimisation de conflits.

KEYWORDS
Maximal constraint satisfaction problems, multi-agent systems, genetic algorithms, min-conflict-heuristic.

LANGUE DE L'ARTICLE
Anglais

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (207 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier