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: Journal PublicationsJournal Article (refereed)peer-review

3 Citations (Scopus)


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. © 2013 IEEE.
Original languageEnglish
Article number7959090
Pages (from-to)785-801
Number of pages17
JournalIEEE Transactions on Systems, Man, and Cybernetics: Systems
Issue number3
Early online date26 Jun 2017
Publication statusPublished - Mar 2020
Externally publishedYes


  • 2-D binary individual
  • constrained resources
  • heuristic
  • overlapping coalition formation (OCF)
  • subadditive tasks


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