A task-oriented heuristic for repairing infeasible solutions to overlapping coalition structure generation

Guofu Zhang, Zhaopin Su, Miqing Li, Meibin Qi, Jianguo Jiang, Xin Yao

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
105 Downloads (Pure)


Overlapping coalition formation (OCF), which provides a natural framework for modeling scenarios where each agent can join and allocate their resources to several completely different coalitions at the same time, has become a very active topic in multiagent systems. For OCF in resource-constrained and subadditive task oriented domains, an agent may not possess sufficient resources to meet the needs of multiple coalitions simultaneously. As a result, there may exist many potential resource conflicts among the rival overlapping coalitions. To tackle such situations, we first present a natural variation of the traditional OCF model and analyze the size of the solution space and the computational complexity of the overlapping coalition structure generation (OCSG) problem. Next, we develop a generic task-oriented heuristic (TOH) for individual repairs that can be used in binary meta-heuristic algorithms to generate overlapping coalitions in a parallel manner. Moreover, we show how the proposed TOH repairs a 2-D individual to resolve resource conflicts and discuss several basic properties. Finally, to evaluate the effectiveness of TOH, we compare it with the existing agent-oriented heuristic for the OCSG problem. The empirical results demonstrate that TOH is of high efficiency and effectiveness in harsh environments with fierce competition over scarce resources.
Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalIEEE Transactions on Systems, Man and Cybernetics: Systems
Early online date26 Jun 2017
Publication statusE-pub ahead of print - 26 Jun 2017


  • Overlapping coalition formation
  • Subadditive tasks
  • Constrained resources
  • Two-dimensional binary individual
  • Heuristic


Dive into the research topics of 'A task-oriented heuristic for repairing infeasible solutions to overlapping coalition structure generation'. Together they form a unique fingerprint.

Cite this