Anthill: otimização heurística por colônia de formigas para resolução do problema de agrupamento automático - Pacheco, Tatiane Martins (2019)
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.