Comparing local search metaheuristics for the maximum diversity problem

Abstract

The Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.

Keywords:

• Maximum Diversity Problem
• Tabu Search
• Scatter Scarch
• Variable Neighbourhood Search
• Random Restart comparisons

Acknowledgements

The authors wish to thank Yari Melzani, Gian Paolo Ghilardi, Alberto Ghilardi, Andrea Beretta and Marco Tadini for their help in the computational experience reported in Aringhieri and Cordone (2006) and Aringhieri et al (2007).