Anthill: otimização heurística por colônia de formigas para resolução do problema de agrupamento automático

Abstract

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.