An optimisation algorithm applied to the one-dimensional stratification problem
Section 1. Introduction
Stratified sampling is a widely used approach to achieve efficiency in sampling designs. The substantial literature on optimal stratification (to be reviewed later in this paper) signals to both the importance of this topic for research and to its wide range of applications. Recently, Hidiroglou and Kozak (2017) compared optimization-based and approximate methods for one-dimensional stratification of skewed populations and concluded that optimization methods are superior and should be used in practice.
In this paper, we propose applying a new optimisation algorithm to determine the stratum boundaries, which we coupled with an approach to obtain the globally optimal sample size allocation to the defined strata. The one-dimensional stratification problem is addressed using a global optimisation technique (a metaheuristic) called Biased Random Key Genetic Algorithm (BRKGA), proposed by Gonçalves and Resende (2011). This technique does not ensure achieving the global optimum for the stratum boundaries, but has been shown to produce good quality solutions for many optimization problems in modest computing times (see Gonçalves and Resende, 2004; Gonçalves, Mendes and Resende, 2005; Festa, 2013 and Oliveira, Chaves and Lorena, 2017).
Our approach for sample allocation given a defined stratification (see de Moura Brito et al., 2015), namely a stratification by a specified variable and given number of strata, is based on an integer programming formulation, and always achieves the global optimum for either minimizing the total sample size given precision constraints or minimizing variance for a fixed total sample size, while providing an exact integer sample allocation, and allowing the specification of minimum and maximum sample sizes per strata, as is often required in practical applications. The approach is implemented in the stratbr R package (see de Moura Brito et al., 2017a), thus providing a practical alternative to existing approximate methods, which it clearly outperforms in terms of efficiency. It also compares favourably with other optimization methods, which are not guaranteed to provide the optimal allocation given the stratification.
We compared this new approach with methods proposed by Dalenius and Hodges (1959), Gunning and Horgan (2004), Kozak (2004, 2006), Keskintürk and Er (2007), and de Moura Brito, Silva Semaan, Fadel and Brito (2017b), using a set comprising 27 real and artificial survey populations. Our empirical study is much larger than that of Hidiroglou and Kozak (2017), who have used only two populations in their comparison. It is also larger than other studies in earlier literature.
We have not considered, as suggested, comparing our approach with classification or regression trees or other machine learning algorithms that synthesise one or more covariates into groupings that can be used for strata. The main reason for this is that such methods do not consider the variance of the target sample estimator or the sample size given precision constraints as the criteria to optimize. Therefore, they cannot be expected to achieve the optimum for the problem we wish to address. In addition, for classification or regression trees the analyst must also specify a “response variable”, in addition to the predictors or auxiliary variables. In many typical sampling situations, the analyst will not have access to data on such a “response variable”, and must aim to minimize variance of the estimator for the total of the size or stratification variable instead (as is the case in most of the literature on this topic).
Although we have addressed only the “one-dimensional stratification problem”, in that a single size measure is used for stratification, one could always use some predictive model or alternative variable reduction technique to summarise auxiliary variables or covariates into a single “ ” or size variable to be used in our proposed approach. Nevertheless, our approach can easily be extended to address multivariate stratification coupled with optimum allocation given the nature of the components of the approach.
The paper is divided as follows: Section 2 contains the key concepts of stratified sampling. Section 3 contains a detailed description of the stratification problem. Section 4 presents the Biased Random Key Genetic Algorithm (BRKGA) and its novel implementation to resolve the stratification problem, in combination with the optimal allocation method proposed by de Moura Brito et al. (2015). Section 5 contains the results of the application of the proposed method compared to those of five other methods available in the literature previously mentioned. Section 6 presents the conclusions of the comparative study.
- Date modified: