A Particle Swarm Optimizer for Solving the Set Partitioning Problem in the Presence of Partitioning Constraints

Gerrit Anders, Florian Siefert, Wolfgang Reif

2015

Abstract

Solving the set partitioning problem (SPP) is at the heart of the formation of several organizational structures in multi-agent systems (MAS). In large-scale MAS, these structures can improve scalability and enable cooperation between agents with (different) limited resources and capabilities. In this paper, we present a discrete Particle Swarm Optimizer, i.e., a metaheuristic, that solves the NP-hard SPP in the context of partitioning constraints – which restrict the structure of valid partitionings in terms of acceptable ranges for the number and the size of partitions – in a general manner. It is applicable to a broad range of applications in which regional or global knowledge is available. For example, our algorithm can be used for coalition structure generation, strict partitioning clustering (with outliers), anticlustering, and, in combination with an additional control loop, even for the creation of hierarchical system structures. Our algorithm relies on basic set operations to come to a solution and, as our evaluation shows, finds high-quality solutions in different scenarios.

Paper Citation

in Harvard Style

Anders G., Siefert F. and Reif W. (2015). A Particle Swarm Optimizer for Solving the Set Partitioning Problem in the Presence of Partitioning Constraints . In Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-758-074-1, pages 151-163. DOI: 10.5220/0005220501510163

in Bibtex Style

@conference{icaart15,
author={Gerrit Anders and Florian Siefert and Wolfgang Reif},
title={A Particle Swarm Optimizer for Solving the Set Partitioning Problem in the Presence of Partitioning Constraints},
booktitle={Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2015},
pages={151-163},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005220501510163},
isbn={978-989-758-074-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - A Particle Swarm Optimizer for Solving the Set Partitioning Problem in the Presence of Partitioning Constraints
SN - 978-989-758-074-1
AU - Anders G.
AU - Siefert F.
AU - Reif W.
PY - 2015
SP - 151
EP - 163
DO - 10.5220/0005220501510163