SCATTER SEARCH WITH STOCHASTIC BEAM SEARCH ON THE COALITION FORMATION PROBLEM

Abstract

The coalition formation problem (CFP) is a crucial component of multi-agent systems (MAS) taking place in various areas in the real world with different variants. This study proposes a parallel metaheuristic algorithm for CFP. Our hybrid method combines two metaheuristic algorithms: the Scatter Search and the Beam Search. While the former ensures that the algorithm thor-oughly explores the search space the latter exploits the visited regions. We re-design Scatter Search's original implementation to perform the time-consuming independent areas of the task in parallel. We employ a perturbation mechanism inside the Beam Search that performs a big jump in the search space when it cannot find any improvement. Moreover we design a problem-specific repre-sentation that stores meta-information to save significant computational time. The proposed method is examined in parallel and sequential configurations and compared with an exact solver recent metaheuristic algorithms and the standard implementation of the Scatter Search. The experimental results show that our solution achieves considerable improvements in both configurations.