We consider the clustering problem in the case where the distances bet
ween elements are metric and both the number of attributes and the num
ber of clusters are large. In this environment the genetic algorithm a
pproach gives high quality clusterings, but at the expense of long run
ning time. Three new and efficient crossover techniques are introduced
here. The hybridization of the genetic algorithm and k-means algorith
m is discussed.