Algoritmos genético e memético de agrupamentos

Algoritmos genético e memético de agrupamentos
Thelma Elita Colanzi1, Wesley Klewerton Guez Assunção2, Aurora Trinidad Ramirez Pozo3
Departamento de Informática (DIN)
Universidade Federal do Paraná (UFPR)
Curitiba, Paraná, Brasil
{thelma.colanzi, wesleyklewerton}@gmail.com, [e-mail]

Carlos Alberto Zorzo4
Departamento de Informática
Universidade Alto Vale do Rio do Peixe (UNIARP)
Caçador, Santa Catarina, Brasil [e-mail] Abstract — Cluster analysis is used in several research areas to classify data sets by their similar caracteristics. Metaheuristic-based techniques, such as genetic algorithms (GAs), have been applied in order to increase the clustering algorithm performance. GA-based clustering algorithms are capable of efficiently and automatically forming natural groups from a pre-defined number of clusters centroids. This paper presents a GA and a memetic algorithm (MA) to clustering. MAs is a GA hybridization technique that uses local search. The results of GA and MA are compared in numeric data bases.
Palavras-chave: algoritmos genéticos, algoritmos meméticos, problema de agrupamentos.

I.

INTRODUÇÃO

Agrupamento (do inglês clustering) consiste da classificação não supervisionada de uma coleção homogênea de pontos de dados em um conjunto natural de grupos (clusters) sem qualquer conhecimento prévio. A classificação resultante deve atender às seguintes propriedades: homogeneidade dentro dos clusters e heterogeneidade entre clusters [1]. Assim, é desejável obter a maior similaridade possível entre os dados de um cluster e a maior diferença possível entre os dados de diferentes clusters.
Uma grande parte dos algoritmos para agrupamentos só considera a homogeneidade entre os dados e resolve o problema a partir de alguns parâmetros de entrada como o número de clusters, formato dos clusters, etc. Em geral, esses algoritmos se baseiam na medida de distância entre os dados para agrupá-los em torno de um centróide