An Adaptive Configuration-Aware Simulated Annealing for the Maximally Diverse Grouping Problem
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36802-36810
DOI: 10.1609/aaai.v40i43.41006 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Baiyu Chen und 5 weiteren Autor:innen.
Abstract (Originalsprache)
The maximally diverse grouping problem (MDGP) seeks to partition the vertices of a complete graph into a fixed number of groups under capacity constraints, maximizing the sum of edge weights within each group. MDGP is an NP-hard combinatorial optimization problem and has wide real-world applications. In this paper, we propose an adaptive configuration-aware simulated annealing (ACSA) algorithm to solve MDGP. First, ACSA adopts a relaxation-based insertion strategy, which temporarily relaxes capacity constraints to expand the neighborhood and allow effective exploration of promising regions. Second, a memory-based swap mechanism is introduced to integrate high-potential suboptimal swap moves into the conventional best-swap operation, thereby achieving a better balance between diversification and intensification of the search. Finally, ACSA employs a vertex-wise sequential coordination strategy to dynamically organize the insertion and swap moves, which enhances the search flexibility. Experiments on 500 benchmark instances demonstrate the strong competitiveness of ACSA, as it improves the best results among the state-of-the-art algorithms on 460 instances and matches them on 39 instances.
Zitieren
APA
Chen, B., Luo, C., Ding, J., Zhang, Q., Su, Z., & Lü, Z. (2026). An Adaptive Configuration-Aware Simulated Annealing for the Maximally Diverse Grouping Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36802-36810. https://doi.org/10.1609/aaai.v40i43.41006
Vancouver
Chen B, Luo C, Ding J, Zhang Q, Su Z, Lü Z. An Adaptive Configuration-Aware Simulated Annealing for the Maximally Diverse Grouping Problem. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36802-36810. doi:10.1609/aaai.v40i43.41006
BibTeX
@article{Chen2026,
author = {Chen, Baiyu and Luo, Canhui and Ding, Junwen and Zhang, Qingyun and Su, Zhouxing and Lü, Zhipeng},
title = {An Adaptive Configuration-Aware Simulated Annealing for the Maximally Diverse Grouping Problem},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36802--36810},
doi = {10.1609/aaai.v40i43.41006}
}
EUVIMED