Abstract:
La 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).
