A Task-Oriented Heuristic for Repairing Infeasible Solutions to Overlapping Coalition Structure Generation

作者：Zhang, Guofu; Su, Zhaopin^*; Li, Miqing; Qi, Meibin; Jiang, Jianguo; Yao, Xin

来源：IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2020, 50(3): 785-801.

DOI：10.1109/TSMC.2017.2712624

• Analytical models
• Heuristic algorithms
• Computer science
• Search problems
• Computational complexity
• Maintenance engineering
• Games
• 2-D binary individual
• constrained resources
• heuristic
• overlapping coalition formation (OCF)
• subadditive tasks

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.

• 出版日期2020-3
• 单位合肥工业大学