Proposal and evaluation of heuristics grasp for the maximum diversity problem

The Maximum Diversity Problem (MDP) consists of, given a set N with n elements, selecting a subset M ⊂ N such that the elements of M have the most possible diversity among them. The MDP belongs to the class of NP-Hard problems limiting the exclusive use of exact methods and turning attractive the development of heuristics to solve the problem. In this work we propose constructive and local search heuristics which are used in different versions of GRASP (Greedy Randomized Adaptive Search Procedure). We also analyze the impact of this heuristics in the GRASP performance. Computational results show that the proposed algorithms always find an optimal solution when this one is known and, for larger instances, produce an average performance better than well known versions of GRASP from the literature.