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

• Type: Article in International Conference Proceedings Book
• Date: 2023

Authors

Sarkar, S (Author) Other; Malta, MC (Author) Other; Biswas, TK (Author) Other; Buchala, DK (Author) Other; Dutta, A (Author) Other

Conference proceedings International

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

Pages: 367-371

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

Venice, ITALY, OCT 26-29, 2023

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: 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).

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 5