A hybrid genetic algorithmic approach to the maximally diverse grouping problem

Abstract

The maximally diverse grouping problem (MDGP) is a NP-complete problem. For such NP-complete problems, heuristics play a major role in searching for solutions. Most of the heuristics for MDGP focus on the equal group-size situation. In this paper, we develop a genetic algorithm (GA)-based hybrid heuristic to solve this problem considering not only the equal group-size situation but also the different group-size situation. The performance of the algorithm is compared with the established Lotfi–Cerveny–Weitz algorithm and the non-hybrid GA. Computational experience indicates that the proposed GA-based hybrid algorithm is a good tool for solving MDGP. Moreover, it can be easily modified to solve other equivalent problems.

Keywords:

• genetic algorithm
• maximally diverse grouping problem
• local neighbourhood search

View correction statement:

Erratum: A hybrid genetic algorithmic approach to the maximally diverse grouping problem

An erratum to this article is available at http://dx.doi.org/10.1057/jors.2010.92.

An erratum to this article is available at http://dx.doi.org/10.1057/jors.2010.92.

Acknowledgements

This work was partly supported by the National Science Fund for Distinguished Young Scholars of China (Project No. 70525002), National Science Fund for Excellent Innovation Research Group of China (Project No. 70721001). Leading Academic Discipline Program, 211 Project for Shanghai University of Finance and Economics (the 3rd phase).