P-TACOS: A Parallel Tabu Search Algorithm for Coalition Structure Generation

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2023

Autores

Sarkar, S (Autor) Outra; Malta, MC (Autor) Outra; Biswas, TK (Autor) Outra; Buchala, DK (Autor) Outra; Dutta, A (Autor) Outra

Ata de Conferência Internacional

Título: 2023 IEEE INTERNATIONAL CONFERENCE ON WEB INTELLIGENCE AND INTELLIGENT AGENT TECHNOLOGY, WI-IAT

Páginas: 367-371

22nd IEEE/WIC International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)

Venice, ITALY, OCT 26-29, 2023

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-00Z-W0P

DOI: 10.1109/wi-iat59888.2023.00060

Abstract (EN): The optimal Coalition Structure Generation (CSG) problem for a given set of agents finds a partition of the agent set that maximises social welfare. The CSG problem is an NP-hard optimisation problem, where the search space grows exponentially. The exact and approximation algorithms focus on finding an optimal solution or a solution within a known bound from the optimum. However, as the number of agents increases linearly, the search space increases exponentially and a practical option here is to use heuristic algorithms. Heuristic algorithms are suitable for solving the optimisation problems because of their less computational complexity. TACOS is a heuristic method for the CSG problem that finds high-quality solutions quickly using a neighbourhood search performed with a memory. However, some of the neighbourhood searches by TACOS can be performed simultaneously. Therefore, this paper proposes a parallel version of the TACOS algorithm (P-TACOS) for the CSG problem, intending to find a better solution than TACOS. We evaluated P-TACOS using eight (8) benchmark data distributions. Results show that P-TACOS achieves better results for all eight (8) data distributions. P-TACOS achieves the highest gain, 74.23%, for the Chisquare distribution and the lowest gain, 0.01%, for the Normal distribution. We also examine how often P-TACOS generates better results than TACOS. In the best case, it generates better results for 92.30% of the time (for the Rayleigh and Agent-based Normal distributions), and in the worst case, 38.46% of the time (for the Weibull distribution).

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 5