Análise de heurísticas GRASP para o Problema da Diversidade Máxima

• Ano de defesa: 2008
• Autor(a) principal: Silva, Geiza Cristina da
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Ciência da computação; Algoritmo; Metaheurística GRASP; Heurística; Problema de Diversidade Máxima; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/17852

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 instances