NK Hybrid Genetic Algorithm for Clustering

Autor(es)

Tinos, Renato ^[1] ; Zhao, Liang ^[1] ; Chicano, Francisco ^[2] ; Whitley, Darrell ^[3]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Dept Comp & Math, BR-14040110 Ribeirao Preto - Brazil

^[2] Univ Malaga, Dept Lenguajes & Ciencias Comp, E-29071 Malaga - Spain

^[3] Colorado State Univ, Dept Comp Sci, Ft Collins, CO 80524 - USA

• Tipo de documento: Artigo Científico
• Fonte: IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION; v. 22, n. 5, p. 748-761, OCT 2018.
• Citações Web of Science: 5

Resumo

The NK hybrid genetic algorithm (GA) for clustering is proposed in this paper. In order to evaluate the solutions, the hybrid algorithm uses the NK clustering validation criterion 2 (NKCV2). NKCV2 uses information about the disposition of N small groups of objects. Each group is composed of K + 1 objects of the dataset. Experimental results show that density-based regions can be identified by using NKCV2 with fixed small K. In NKCV2, the relationship between decision variables is known, which in turn allows us to apply gray box optimization. Mutation operators, a partition crossover (PX), and a local search strategy are proposed, all using information about the relationship between decision variables. In PX, the evaluation function is decomposed into q independent components; PX then deterministically returns the best among 2(q) possible offspring with computational complexity O(N). The NK hybrid GA allows the detection of clusters with arbitrary shapes and the automatic estimation of the number of clusters. In the experiments, the NK hybrid GA produced very good results when compared to another GA approach and to state-of-art clustering algorithms. (AU)

• Processo FAPESP: 15/06462-1 - Recombinação por decomposição em computação evolutiva
• Beneficiário: Renato Tinós
• Linha de fomento: Auxílio à Pesquisa - Regular
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: José Alberto Cuminato
• Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 15/50122-0 - Fenômenos dinâmicos em redes complexas: fundamentos e aplicações
• Beneficiário: Elbert Einstein Nehrer Macau
• Linha de fomento: Auxílio à Pesquisa - Temático