A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem

Xiao Yang, Zonghui Cai, Ting Jin, Zheng Tang and Shangce Gao

European Journal of Operational Research, 2022, vol. 302, issue 3, 925-953

Abstract: The maximally diverse grouping problem (MDGP) aims to assign a given set of elements into a number of groups with size restrictions for the sake of maximizing the sum of diversity in these groups. MDGP is an NP-hard combinatorial optimization problem, possessing widespread application and practical importance. This paper introduces a novel hybrid algorithm, called a three-phase search approach with dynamic population size (TPSDP), for solving the problem. The proposed algorithm devises the search process into three phases with distinct functions which are iterated: (1) an undirected perturbation phase to improve the population diversity, (2) a restructure phase using a distinctive crossover operator to increase the information interaction among solutions, and (3) a directed perturbation phase to discover the adjacent local optima around current solutions. TPSDP also combines a dynamic population size strategy to reserve limited computing resources for potential solutions. The results of experiments and the Friedman test show that the overall performance of the proposed TPSDP is highly competitive with or better than previous state-of-the-art MDGP algorithms on 500 instances taken from five popular benchmark sets. Furthermore, an additional experiment of parameter analysis and a discussion of critical ingredients are presented. The source code of TPSDP is provided at https://toyamaailab.github.io/sourcedata.html.

Keywords: Heuristics; Maximally diverse grouping problem; Local search; Crossover; Dynamic population size (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722000881
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:302:y:2022:i:3:p:925-953

DOI: 10.1016/j.ejor.2022.02.003

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().