Blucher Engineering Proceedings

Dezembro 2020, vol.7, num.3 - VIII Simpósio de Engenharia de Produção
Artigo completo - Open Access Idioma principal | Segundo principal

CLUSTERIZAÇÃO POR MÍNIMA DISTÂNCIA: UMA ABORDAGEM UTILIZANDO ALGORITMO GENÉTICO

CLUSTERIZAÇÃO POR MÍNIMA DISTÂNCIA: UMA ABORDAGEM UTILIZANDO ALGORITMO GENÉTICO

Lopes, Roza Maria Zoellner; Scarpin, Cassius Tadeu; Pécora Júnior, José Eduardo; Sati, Tarek Nasser

Artigo completo:

O problema de clusterização consiste no agrupamento de itens baseado em alguma característica em comum. No presente estudo realizou-se o agrupamento em clusters de pontos gerados aleatoriamente com o objetivo de obter a mínima distância entre eles. Utilizou-se a metaheurística Algoritmo Genético (AG) com soluções iniciais obtidas por heurísticas construtivas e pela metodologia K-means, sendo esta última melhorada pelo algoritmo Local Search. A fim de comprovar a eficiência da abordagem proposta comparouse os dados obtidos com os resultados da solução exata do problema. Os resultados mostram que o Algoritmo Genético obtém soluções para instâncias onde não é possível obter o resultado exato.

O problema de clusterização consiste no agrupamento de itens baseado em alguma característica em comum. No presente estudo realizou-se o agrupamento em clusters de pontos gerados aleatoriamente com o objetivo de obter a mínima distância entre eles. Utilizou-se a metaheurística Algoritmo Genético (AG) com soluções iniciais obtidas por heurísticas construtivas e pela metodologia K-means, sendo esta última melhorada pelo algoritmo Local Search. A fim de comprovar a eficiência da abordagem proposta comparouse os dados obtidos com os resultados da solução exata do problema. Os resultados mostram que o Algoritmo Genético obtém soluções para instâncias onde não é possível obter o resultado exato.

Download (PDF)

Palavras-chave:

DOI: 10.5151/viisimep-315857

Referências bibliográficas
  • [1] BARBOZA, A. O. Simulação e técnicas da computação evolucionária aplicadas a problemas
  • [2] de programação linear inteira mista. 2010.
  • [3] CAO, L. et al. Automatic feature group combination selection method based on GA for the
  • [4] functional regions clustering in DBS. Computer Methods and Programs in Biomedicine, v.
  • [5] 183, 2020.
  • [6] CASTRO, R. E. DE. Otimização de estruturas com multi-objetivos via algoritmos genéticos.
  • [7] PhD, p. 206, 2001.
  • [8] CHAO, C.; ZHIHUI, T.; BAOZHEN, Y. Optimization of two-stage location–routing–
  • [9] inventory problem with time-windows in food distribution network. Annals of Operations
  • [10] Research, v. 273, n. 1–2, p. 111–134, 2019.
  • [11] DEFRYN, C.; SÖRENSEN, K.; CORNELISSENS, T. The selective vehicle routing problem
  • [12] in a collaborative environment. European Journal of Operational Research, 2016.
  • [13] FUENTES, M.; CADARSO, L.; MARÍN, Á. A hybrid model for crew scheduling in rail rapid
  • [14] transit networks. Transportation Research Part B: Methodological, 2019.
  • [15] GATICA, G. et al. Efficient heuristic algorithms for location of charging stations in electric
  • [16] vehicle routing problems. Studies in Informatics and Control, v. 27, n. 1, p. 73–82, 2018.
  • [17] GEREMEW, W. et al. A DC programming approach for solving multicast network design
  • [18] problems via the Nesterov smoothing technique. Journal of Global Optimization, v. 72, n.
  • [19] 4, p. 705–729, 2018.
  • [20] JAIN, A. K. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, v. 31,
  • [21] n. 8, p. 651–666, 2010.
  • [22] LOPES, H. S.; RODRIGUES, L. C. DE A.; ARNS, M. T. S. Meta-Heurísticas em Pesquisa
  • [23] Operacional. Editora Omnipax. 2013.
  • [24] MEILǍ, M. The uniqueness of a good optimum for K-means. ACM International
  • [25] Conference Proceeding Series, v. 148, p. 625–632, 2006.
  • [26] NASCIMENTO, M. C. V.; TOLEDO, F. M. B.; DE CARVALHO, A. C. P. L. F.
  • [27] Investigation of a new GRASP-based clustering algorithm applied to biological data.
  • [28] Computers and Operations Research, v. 37, n. 8, p. 1381–1388, 2010.
  • [29] TALBI, M. E. Metaheuristics : from Design to Implementation Single solution-based
  • [30] metaheuristics. John Wiley & Sons. 2009.
  • [31] TIWARI, A.; CHANG, P. C. A block recombination approach to solve green vehicle routing
  • [32] problem. International Journal of Production Economics, 2015.
  • [33] WANG, Y. et al. Collaborative multi-depot logistics network design with time window
  • [34] assignment. Expert Systems with Applications, v. 140, 2020.
  • [35] WU, Z.; ZHAO, C.; LIU, B. Polygonal Approximation based on Coarse-grained Parallel
  • [36] Genetic Algorithm. Journal of Visual Communication and Image Representation, p.
  • [37] 102717, 2019.
Como citar:

Lopes, Roza Maria Zoellner; Scarpin, Cassius Tadeu; Pécora Júnior, José Eduardo; Sati, Tarek Nasser; "CLUSTERIZAÇÃO POR MÍNIMA DISTÂNCIA: UMA ABORDAGEM UTILIZANDO ALGORITMO GENÉTICO", p-3015-3026. In: Anais do VIII Simpósio de Engenharia de Produção . São Paulo: Blucher, 2020.
ISSN 23577592, DOI 10.5151/viisimep-315857

últimos 30 dias

117
downloads

227
visualizações

816
indexações