Zone clustering using a genetic algorithm and K-means

The zone clustering problem arising from several areas of research such as deciding the optimal location of ambient measuring stations is to divide a 2-dimensional area into several sub-areas in which each included individual zone shows similar properties. In general, the optimal solution of this problem is very hard to obtain. Therefore, instead of finding an optimal solution, the generation of a near optimal solution within a limited time is more meaningful. In this study, the combination of a genetic algorithm and the modified k-means method is used to obtain near optimal solutions. To exploit the genetic algorithm effectively, a representation of chromosomes and appropriate genetic operators are proposed. The k-means method which was originally devised to solve the object clustering problem is modified to improve the solutions obtained from the genetic algorithm. The experiment shows that the proposed method generates the near optimal solution efficiently.