This paper proposes a real-coded genetic algorithm (GA) with a new flexible gene structure for spatial clustering problems. The basic idea is to improve the solution quality and rate of cluster detection by employing flexible ellipses moving and shifting in all directions. Based on synthetic and real datasets, a performance test is conducted to evaluate the quality of the improvements in the proposed genetic algorithm. The result indicates configuration of the new gene structure and solution representation allows for full exploration of the solution spaces as well as provides better solution quality and cluster detection rates.