Proposta de melhorias a um algoritmo para agrupamento de padrões via Colônia de Formigas

Resumo

Métodos inspirados em formigas são uma grande promessa para problemas de agrupamento. No algoritmo de Agrupamento baseado em Formigas, proposto por Deneubourg et al. (1991), os padrões são espalhados em uma grade e a cada formiga é atribuído um padrão. As formigas são responsáveis por carregar, transportar e descarregar os padrões na grade. Após a convergência do algoritmo, a recuperação dos grupos é feita, usando-se as posições dos padrões na grade. O objetivo do presente artigo é propor melhorias a este algoritmo, doravante denominado de algoritmo proposto, avaliando o seu desempenho comparativamente ao Método de Ward, aos Mapas de Kohonen Unidimensionais e ao algoritmo ACAM (Ant-based Clustering Algorithm Modified), proposto por Boryczka (2009). No algoritmo proposto, as principais modificações foram: a introdução de uma comparação da probabilidade de descarregar um padrão na posição escolhida aleatoriamente, com a probabilidade de deixar este padrão em sua posição atual; a introdução de uma avaliação da probabilidade de uma posição vizinha, quando a decisão de descarregar um padrão for positiva e a célula em que o padrão deveria ser descarregado estiver ocupada; e a substituição do padrão carregado por uma formiga, caso este padrão não seja descarregado em 100 iterações consecutivas. Para a avaliação do desempenho do algoritmo proposto, foram utilizadas três bases de dados reais e públicas (ÍRIS, WINE e PIMA Indians Diabetes). Os resultados mostraram que houve superioridade no desempenho do algoritmo proposto, em relação ao ACAM para duas das três bases de dados e igualdade, em relação aos outros dois métodos.

Palavras-chave: Mineração de Dados; Metaheurística; Agrupamento Baseado em Formigas.