While K-means is one of the most well known methods to partition data set into clusters, it still has a problem when clusters are of different size and different density.  K-means converges to one of many local minima. Many methods have been proposed to overcome these limitations of K-means, but most of these methods do not overcome the limitation of both different density and size in the same time. The previous methods success to overcome one of them while fails with the others. In this paper we have used genetic algorithm with k-means to improve its efficiency.