Análise de heurísticas GRASP para o Problema da Diversidade Máxima
Ano de defesa: | 2008 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | |
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 |
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: | |
Link de acesso: | https://app.uff.br/riuff/handle/1/17852 |
Resumo: | 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 |