Um GRASP com reconexão de caminhos para a solução do problema da maximização da diversidade

• Ano de defesa: 2008
• Autor(a) principal: Andrade, Marcos Ribeiro Quinet de
• 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; Metaheurística GRASP; Heurística; Otimização (Computação); Reconexão de caminhos; Problema da maximização da diversidade; 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/17889

O problema da maximização da diversidade consiste, para uma determinada população, na identificação de um subconjunto de elementos baseando-se na diversidade de suas características, encontrando aqueles que apresentem a maior diversidade possível entre si. A maximização da diversidade pertence à classe dos problemas NP-difíceis, sendo interessante a utilização de metaheurísticas para obtermos soluções ótimas ou próximas das ótimas em um tempo considerado viável. O objetivo principal deste trabalho é aplicar uma versão da heurística GRASP para a resolução do problema acima descrito que empregue a técnica de reconexão de caminhos. A partir de uma versão de um algoritmo GRASP existente na literatura são incorporados diferentes métodos para se realizar a reconexão de caminhos, na busca por soluções de maior qualidade. A partir dos resultados obtidos, verifica-se que é possível a obtenção de soluções superiores às obtidas pela abordagem já desenvolvida. Torna-se possível ainda a obtenção de soluções que apresentem uma determinada qualidade em um menor tempo computacional.