Predicting the total cost for the minimised sample size from the optimal partition of constructed strata in multivariate survey design is a problem in cases where the population frame is large. A solution exists that satisfies accuracy constraints, while minimising the sample size and partitioning the starting number of strata iteratively into a smaller number of groups. The optimal stratification for the minimal sample size can be found by testing all possible partitions. However the number of possible partitions grows exponentially with the number of initial strata. There are alternative ways of modelling this problem, one of the most natural is using Genetic Algorithms (GA). These evolutionary algorithms use recombination, mutation and selection to search for optimal solutions. They often converge on optimal or near-optimal solution more quickly than exact methods. We propose a new GA approach to this problem using grouping genetic operators instead of traditional operators. The results show a significant improvement in solution quality for similar computational effort, corresponding to large monetary savings.