Por favor, use este identificador para citar o enlazar este ítem: https://repositorio.ufjf.br/jspui/handle/ufjf/10233
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
tatianemartinspacheco.pdf1.88 MBAdobe PDFVista previa
Visualizar/Abrir
Clase: Dissertação
Título : Anthill: otimização heurística por colônia de formigas para resolução do problema de agrupamento automático
Autor(es): Pacheco, Tatiane Martins
Orientador: Menezes, Victor Ströele de Andrade
Miembros Examinadores: Bernardino, Heder Soares
Miembros Examinadores: Arroyo, José Elias Cláudio
Resumo: Métodos aproximativos são amplamente utilizados na resolução de problemas computacionais complexos, uma vez que são capazes de apresentar resultados significativos em relação à qualidade da solução em um tempo satisfatório. Esta dissertação aborda o problema do agrupamento automático, reconhecidamente NP-difícil. Para resolver o problema, o trabalho propõe uma metaheurística baseada em inteligência coletiva, inspirada no comportamento das formigas, denominado Anthill. O índice de silhueta foi utilizado para medir a qualidade dos clusters gerados. Os resultados obtidos pelo Anthill foram comparados com os resultados obtidos na literatura e os experimentos realizados indicam que o algoritmo é capaz de encontrar clusters que representam bem a distribuição original dos dados. Entretanto, durante a avaliação, foi identificado que o tempo de processamento exigido pelo Anthill pode impactar na sua escalabilidade, sendo um impeditivo para o seu uso na resolução de problemas de grande porte. Assim, foi proposta uma versão paralelizada do algoritmo e os experimentos foram reconduzidos. Os resultados finais foram analisados considerando as métricas de Speedup e Eficiência, mantendo os mesmos índices de silhuetas encontrados na versão sequencial.
Resumen : Approximate methods are widely used in solving complex computational problems, since they are capable of presenting significant results regarding the quality of the solution in a satisfactory time. This dissertation addresses the problem of automatic grouping, admittedly NP-difficult. To solve the problem, the work proposes a metaheuristic based on collective intelligence, inspired by the behavior of the ants, called Anthill. The silhouette index was used to measure the quality of the generated clusters. The results obtained by the Anthill were compared with the results obtained in the literature and the experiments carried out indicate that the algorithm is able to find clusters which represent well the original distribution of the data. However, during the evaluation, it was identified that the processing time required by the Anthill can impact its scalability, being an impediment to its use in solving large problems. Thus, a parallel version of the algorithm was proposed and the experiments were carried out. The final results were analyzed considering the Speedup and Efficiency metrics, maintaining the same indexes of silhouettes found in the sequential version.
Palabras clave : Clusterização
Agrupamento automático
Metaheurística
Colônia de formigas
Paralelismo
Clustering
Automatic grouping
Metaheuristic
Ant colony
Parallelism
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editorial : Universidade Federal de Juiz de Fora (UFJF)
Sigla de la Instituición: UFJF
Departamento: ICE – Instituto de Ciências Exatas
Programa: Programa de Pós-graduação em Ciência da Computação
Clase de Acesso: Acesso Aberto
Attribution 3.0 Brazil
Licenças Creative Commons: http://creativecommons.org/licenses/by/3.0/br/
URI : https://repositorio.ufjf.br/jspui/handle/ufjf/10233
Fecha de publicación : 18-mar-2019
Aparece en las colecciones: Mestrado em Ciência da Computação (Dissertações)



Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons