Analysis of GRASP heuristics for the Maximum Diversity Problem

The Maximum Diversity Problem (MDP) consists of selecting elements from some large collection such that the selected elements have the most possible diversity among them. There are many applications that can be solved using the resolution of this problem, such as in human resources, identifying people with less similar characteristics or in biology, when it is desired to identify more diverse species. MDP belongs to the class of NP-hard problem. Thus, the use of approximation or heuristics methods which are capable to get solutions close to the optimum cost becomes quite attractive. In this work we propose construction and local search methods which are used for the implementation of different GRASP (Greedy Randomized Adaptive Search Procedure) heuristics. An experimental study is carried out and the projected alghoritms are compared with two others alghoritms described in literature. Results show that good results are obtained using the proposed heuristics to solve MDP instancesCoordenação de Aperfeiçoamento de Pessoal de Nível SuperiorO Problema de Diversidade Máxima (PDM) corresponde à seleção de elementos a partir de uma coleção maior de forma tal que os elementos selecionados possuam a maior diversidade possível entre eles. Aplicações deste problema podem ser encontradas em várias áreas como, por exemplo, em recursos humanos, identificando indivíduos com características menos similares ou em biologia, quando se deseja obter espécies de maior diversidade. Excluindo-se casos triviais, o PDM é classificado como um problema da classe NP-difícil. Desta forma, o uso de métodos aproximativos ou heurísticos, ou seja, métodos que são capazes de obter soluções não necessariamente ótimas, mas com alguma proximidade do valor ótimo tornam-se bastante atraentes. Neste trabalho são propostos métodos de construção e busca local que, combinados, são usados como base em diferentes propostas de heurísticas GRASP (Greedy Randomized Adaptive Search Procedure). Uma extensa bateria de testes é realizada e os algoritmos propostos são analisados comparando-se com outros dois algoritmos descritos na literatura. Os resultados mostram que as heurísticas propostas fornecem bons resultados na r4solução de instâncias do PD