UM ESTUDO COMPUTACIONAL DO PROBLEMA DE AGRUPAMENTO COM SOMA MÍNIMA DE DISTÂNCIAS
Este artigo traz a proposta de um algoritmo que foi aplicado ao problema de agrupamento com soma mínima de distâncias (PASMD). Dada uma base de dados com n objetos e q variáveis, busca-se distribuir os objetos em k grupos, de modo que a soma total de distâncias entre todos os pares de objetos, dentro de cada um dos grupos, seja mínima. Este problema tem alta complexidade computacional, o que dificulta a aplicação de métodos de enumeração exaustiva ou implícita. Considerando esta questão, foi desenvolvido um algoritmo heurístico baseado nos algoritmos genéticos de chaves aleatórias viciadas (biased random-key genetic algorithm – BRKGA). De forma a avaliar este algoritmo, foram realizados experimentos computacionais, considerando a sua aplicação em um conjunto de 49 bases dados. Os resultados obtidos indicam que esse algoritmo se constitui como uma boa alternativa à resolução do PASMD.
UM ESTUDO COMPUTACIONAL DO PROBLEMA DE AGRUPAMENTO COM SOMA MÍNIMA DE DISTÂNCIAS
-
DOI: 10.22533/at.ed.00118091214
-
Palavras-chave: Análise de Agrupamentos, Soma Mínima e BRKGA.
-
Keywords: Clustering Analysis, Minimum Sum and BRKGA.
-
Abstract:
This article presents the proposal of an algorithm that was applied to the minimum sum of distances clustering problem with (MSDCP). Given a database with n objects and q variables, the objective is to distribute the objects in k groups, so that the total sum of distances between all pairs of objects, within each of the groups, is minimal. This problem have a high computational complexity, which makes it difficult to apply exhaustive or implicit enumeration methods. Considering this question, a heuristic algorithm based on the biased random-key genetic algorithms (BRKGA) was developed. In order to evaluate this algorithm, we perform computational experiments, considering its application in a set of 49 data bases. The results obtained indicate that this algorithm constitutes a good alternative to the resolution of MSDCP.
-
Número de páginas: 15
- Augusto Pizano Vieira Beltrão
