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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.contributorMartins, Simone de Lima-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5202429302236084-
Autor(es): dc.contributorRibeiro, Celso da Cruz Carneiro-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3614186131432854-
Autor(es): dc.contributorAbreu, Nair Maria Maia de-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4787268Y0-
Autor(es): dc.contributorNetto, Paulo Oswaldo Boaventura-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6042694480342149-
Autor(es): dc.creatorSilva, Geiza Cristina da-
Data de aceite: dc.date.accessioned2024-07-11T18:32:07Z-
Data de disponibilização: dc.date.available2024-07-11T18:32:07Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2008-03-31-
Data de envio: dc.date.issued2021-03-10-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/17852-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/772400-
Descrição: dc.descriptionThe 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-
Descrição: dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior-
Descrição: dc.descriptionO 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 PDM-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectAlgoritmo-
Palavras-chave: dc.subjectMetaheurística GRASP-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectProblema de Diversidade Máxima-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleAnálise de heurísticas GRASP para o Problema da Diversidade Máxima-
Título: dc.titleAnalysis of GRASP heuristics for the Maximum Diversity Problem-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.