  The NK hybrid genetic algorithm 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, and a local search
strategy are proposed, all using information about the relationship between
decision variables. In partition crossover, the evaluation function is
decomposed into $q$ independent components; partition crossover then
deterministically returns the best among $2^q$ possible offspring with
computational complexity $O(N)$. The NK hybrid genetic algorithm allows the
detection of clusters with arbitrary shapes and the automatic estimation of the
number of clusters. In the experiments, the NK hybrid genetic algorithm
produced very good results when compared to another genetic algorithm approach
and to state-of-art clustering algorithms.
