Método híbrido com detecção de regiões promissoras baseado em densidade para o problema de localização de rótulos cartográficos
Arquivos
Data
2016-02-15
Autores
Araujo, Eliseu Junio 
Orientadores
Chaves, Antonio Augusto
Tipo
Dissertação de mestrado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
Metaheuristcs have been the subject of research with the aim to find those having greater efficiency for solving optimization problems. It was noted during this operation, the hybrid metaheuristics are a good choice to accentuate the qualities of these methods. This project is focused on hybrid method Clustering Search (CS), focusing on the improvement and development of a new alternative for him, trying to make it an efficient, robust and flexible method in terms of quality solutions as well as computational time. CS seeks to combine heuristics and meta-heuristics for local search, intensifying the search for regions of space solutions considered promising. In this project we propose a new way to detect promising regions, based on clustering techniques DBSCAN, Label-propagation and NGI. To analyze this approach is proposed to solve a combinatorial optimization problem with many practical applications, the problem of location of map labels. In computational tests are used test problems from the literature. The results were satisfactory for Label-clusters made with propagation and NGI, showing better results than the CS, and showing that they are a good alternative to changing the method.
As metaheurísticas têm sido alvo de pesquisas com o objetivo de encontrar aquelas que possuam maior eficiência para resolver problemas de otimização. Notou-se, durante essa exploração, que as metaheurísticas híbridas são uma boa opção para acentuar as qualidades destes métodos. Este projeto é centrado no método híbrido Clustering Search (CS), tendo como foco o aperfeiçoamento e desenvolvimento de uma nova alternativa para ele, buscando torná-lo um método eficiente, robusto e flexível em termos de qualidade de soluções assim como em tempo computacional. O CS procura combinar meta-heurísticas e heurísticas de busca local, intensificando a busca em regiões do espaço de soluções consideradas promissoras. Neste trabalho é proposta uma nova forma de detectar regiões promissoras, baseado nas técnicas de agrupamento DBScan, Label-propagation e NGI. Para analisar esta abordagem propõe-se resolver um problema de otimização combinatória com diversas aplicações práticas, o problema de localização de rótulos cartográficos. Nos testes computacionais são utilizados problemas testes disponíveis na literatura. Os resultados se mostraram satisfatórios para os agrupamentos feitos com Label-propagation e NGI, mostrando resultados melhores que o CS e demonstrando que são uma boa alternativa de mudança no método.
As metaheurísticas têm sido alvo de pesquisas com o objetivo de encontrar aquelas que possuam maior eficiência para resolver problemas de otimização. Notou-se, durante essa exploração, que as metaheurísticas híbridas são uma boa opção para acentuar as qualidades destes métodos. Este projeto é centrado no método híbrido Clustering Search (CS), tendo como foco o aperfeiçoamento e desenvolvimento de uma nova alternativa para ele, buscando torná-lo um método eficiente, robusto e flexível em termos de qualidade de soluções assim como em tempo computacional. O CS procura combinar meta-heurísticas e heurísticas de busca local, intensificando a busca em regiões do espaço de soluções consideradas promissoras. Neste trabalho é proposta uma nova forma de detectar regiões promissoras, baseado nas técnicas de agrupamento DBScan, Label-propagation e NGI. Para analisar esta abordagem propõe-se resolver um problema de otimização combinatória com diversas aplicações práticas, o problema de localização de rótulos cartográficos. Nos testes computacionais são utilizados problemas testes disponíveis na literatura. Os resultados se mostraram satisfatórios para os agrupamentos feitos com Label-propagation e NGI, mostrando resultados melhores que o CS e demonstrando que são uma boa alternativa de mudança no método.
Descrição
Citação
ARAUJO, Eliseu Junio. Método híbrido com detecção de regiões promissoras baseado em densidade para o problema de localização de rótulos cartográficos. 2016. 84 f. Dissertação (Mestrado) - Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo (UNIFESP), São José dos Campos, 2016.