Multi-agent coalition formation by an efficient genetic algorithm with heuristic initialization and repair strategy

In multi-agent systems (MAS), the coalition formation (CF) is an important problem focusing on allocating agents to different tasks. In this paper, three specific CF problems are considered, including the single-task single-coalition formation, the multi-task single-coalition formation, and the multi-task multi-coalition formation. The mathematical models of these three specific problems are formulated with the objective of minimizing the total cost while satisfying the ability requirement constraint. An efficient genetic algorithm with heuristic initialization and repair strategy (GAHIR) is proposed to solve the CF problem. Multiple initialization and repair methods, which utilize the prior knowledge of the specific problems, are proposed to improve the solution quality. Then, these methods are tested to prove their effectiveness. Finally, a comparison experiment about the proposed algorithm against several advanced algorithms is constructed. The results of statistical analysis by the Wilcoxon rank-sum test demonstrate that the proposed GAHIR can obtain better coalition schemes than its competitors in solving the CF problems. Furthermore, GAHIR has faster convergence speed in most instances.