Optimizing Coalition Structure in Large Scale Combined SCSGA-MF-TS

Abstract

The key focus of the Simultaneous Coalition Structure Generation and Assignment (SCSGA) problem is to identify a feasible coalition for each task that maximizes the value of the resulting coalition structure.
Incorporating multi-dimensional features on agents and tasks, the SCSGA with Multi-dimensional Features (SCSGA-MF) problem aims to minimize the distance between each coalition and its assigned task, while SCSGA-MF prioritizing Task Satisfaction (SCSGA-MF-TS) additionally focuses on maximizing the total number of satisfied tasks.
In this work, we study and address the SCSGA-MF-TS problem as a combined combinatorial optimization problem, where the two objectives of SCSGA-MF-TS are combined into a single function. For this problem, we adapt a well known evolutionary algorithm and several heuristics to study their performances on large scale problem instances.  Our empirical studies show that the genetic algorithm significantly outperforms other contending methods on the combined SCSGA-MF-TS problem.