Please use this identifier to cite or link to this item: http://univ-bejaia.dz/dspace/123456789/13838
Full metadata record
DC FieldValueLanguage
dc.contributor.authorTaguelmimt, Redha-
dc.contributor.authorBoukredera, Djamila ; promotrice-
dc.date.accessioned2021-01-19T08:23:14Z-
dc.date.available2021-01-19T08:23:14Z-
dc.date.issued2020-
dc.identifier.urihttp://hdl.handle.net/123456789/13838-
dc.descriptionOption : Intelligence Artificielleen_US
dc.description.abstractLa génération de structures de coalitions est une problématique de recherche importante dans les systèmes multi-agents (SMA). Elle consiste à diviser l’ensemble des agents en sous-ensembles disjoints appelés coalitions, de manière à maximiser le gain. Trouver la structure de coalitions optimale est un problème NP-complet qui est donc difficile à résoudre, même avec des hypothèses assez restrictives. Cela a motivé les chercheurs à développer divers algorithmes déterministes et ap- proches heuristiques pour résoudre efficacement le problème. Dans ce mémoire, nous avons d’abord proposé une nouvelle représentation de l’espace de recherche basée sur le graphe des partitions. Ensuite, nous avons développé une approche heuristique innovante et efficace pour rechercher ef- ficacement l’espace des structures de coalitions afin de trouver une solution proche de l’optimum dans un temps court. Notre technique d’énumération des structures de coalitions (CSE), qui com- bine une heuristique originale et une nouvelle représentation de l’espace de recherche, offre une nouvelle façon d’explorer le graphe des partitions en calculant directement les structures de coali- tions. L’analyse des performances de notre approche montre son efficacité en termes de temps et de qualité des solutions trouvées par rapport à l’algorithme exact le plus rapide, à savoir ODP-IP. Nous avons ensuite développé un algorithme imparfait (ADP) basé sur deux observations sur les valeurs des coalitions. Cet algorithme fournit la solution optimale pour plus de 97% des cas avec un gain de temps pouvant atteindre 300 secondes pour 25 agents. Nous avons ensuite présenté un problème négligé des algorithmes existants, à savoir leurs besoins en mémoire, et proposé notre troisième algorithme pour faire face à ce problème majeur. Notre algorithme fournit des solutions de haute qualité avec un gain de temps qui avoisine les 100 % tout en ne nécessitant que moins de 1 % de la mémoire requise par les algorithmes existants (0,02 % pour 26 agents).en_US
dc.language.isofren_US
dc.publisheruniversité Abderrahmane Mira- Bejaiaen_US
dc.subjectGénération de structures de coalitions : Formation de coalition : Programmation dynamique : Algorithme imparfait : Graphe des partitionsen_US
dc.titleMéthodes avancées de génération de structures de coalitions dans les systèmes multi-agents.en_US
dc.typeThesisen_US
Appears in Collections:Mémoires de Master

Files in This Item:
File Description SizeFormat 
Main.pdf901.04 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.