NK Hybrid Genetic Algorithm for Clustering

Author(s)

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

Affiliation

^[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

• Document type: Journal article
• Source: IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION; v. 22, n. 5, p. 748-761, OCT 2018.
• Web of Science Citations: 8

Abstract

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)

• FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
• Grantee: Francisco Louzada Neto
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 15/50122-0 - Dynamic phenomena in complex networks: basics and applications
• Grantee: Elbert Einstein Nehrer Macau
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 15/06462-1 - Recombination by decomposition in evolutionary computation
• Grantee: Renato Tinós
• Support Opportunities: Regular Research Grants