An optimisation algorithm applied to the one-dimensional stratification problem
Section 3. The one-dimensional stratification problem

• Previous
• Next

Consider the population vector $X_U=\left\{x_1,x_2,\dots ,x_N\right\}$ corresponding to the stratification variable $x.$ Without loss of generality, we assume that the population elements in $U$ are ordered by the stratification variable such that $x_1\le x_2\le \dots \le x_N.$ The stratum boundaries are used to define the $H$ strata according to the rule:

1) $U_1=\left\{i\in U|x_i\le b_1\right\};$

2) $U_h=\left\{i\in U|b_{h-1}<x_i\le b_h\right\}$ for $h=2,3,\dots ,H-1;$

3) $U_H=\left\{i\in U|b_{H-1}<x_i\right\}.$

The stratification problem corresponds to determining the cut-off points, i.e., the stratum boundaries $b_1<b_2<\dots <b_h<\dots <b_{H-1}$ such that the variance (or equivalently the CV) of the estimator of total ${\widehat{Y}}_{\text{SSRS}}$ is minimised. In this section, we consider that the total number of strata $H$ is defined before applying the optimal stratification methods considered.

In practice, the values of the survey variable $y$ are not available and hence the variance in expression (2.3) is not computable. A common approach is to minimise instead the variance (or CV) of the estimator ${\widehat{X}}_{\text{SSRS}}$ for the total of the stratification variable $x.$ Several authors have developed methods that focus on this optimization problem, which from now on we call the one-dimensional “stratification problem”. We adopted the same approach here.

Finding the boundary points that minimize the variance (2.6) or the CV (2.7) corresponds to a hard problem both from analytic and computational points of view. This is so because the integer population and sample sizes $(N_h$ and $n_h,$ respectively) depend in a nonlinear way on the stratum boundaries. According to de Moura Brito, Ochi, Montenegro and Maculan (2010a), depending on $N,$ $H,$ and the number of distinct population $x$ values, the number of possible choices for the boundary points can be very large.

In view of this difficulty, over the past decades, various methods were developed to search for the optimum stratum boundaries, aiming to provide at least solutions which correspond to local minima of good quality.

Dalenius (1951) tackled the problem for the case $H=2$ by approximating the variance in (2.6) by ignoring the finite population correction, which is equivalent to assuming that the sampling within strata would have been simple random sampling with replacement. The approximate variance to be minimised is then given by:

$$\text{Var}\left({\widehat{X}}_{\text{SSRS}}\right)\cong {\displaystyle {\sum }_{h=1}^H{N}_h^2{S}_{hx}^2/n_h}.(3.1)$$

Under the Neyman allocation (Cochran, 1977) using the $x$ variable, and replacing the sample sizes $n_h$ in (3.1) by their theoretical values $n_h=N_h{S}_{hx}/{\displaystyle {\sum }_{k=1}^H{N}_k{S}_{kx}}$ leads to the expression used by Dalenius (1951):

$$\text{Var}\left({\widehat{X}}_{\text{SSRS}}\right)\cong {\left({\displaystyle {\sum }_{h=1}^H{N}_h{S}_{hx}}\right)}^2/n.(3.2)$$

Dalenius and Hodges (1959) considered the case when $H>2,$ and offered an analytic solution which relied on approximating the distribution of the $x$ variable by its histogram with a moderate number of classes. Still considering the approximate variance and assuming Neyman’s allocation, Ekman (1959) provided a solution using a geometric approach to find the stratum boundaries. Hedlin (2000) further extended Ekman’s solution while retaining the original variance (2.6) as the function to be minimised, which he labelled the extended Ekman rule.

Hidiroglou (1986) proposed an approach which pre-specifies the required precision (CV) for the estimator of total, and which divides the population into two strata $\left(H=2\right)$ such that the total sample size $n$ is minimised. In this paper, the second stratum corresponds to a “take-all” or “certainty” stratum, where all elements are included in the sample with probability one $\left(n_2=N_2\right).$ Lavallée and Hidiroglou (1988) generalized the approach to $H>2$ strata, while retaining the idea that the stratum containing the largest population units is to be sampled completely. Their approach relied on adopting a special type of allocation called Power Allocation (Bankier, 1988). More recently, Rivest (2002) further generalised the approach of Lavallée and Hidiroglou (1988) while considering that the target is minimising the variance for the estimator of a total of a model-based prediction of the survey variable $y,$ instead of the stratification variable $x.$

Gunning and Horgan (2004) proposed the so-called Geometric method for defining the stratum boundaries. This method assumes that the CVs of the stratification variable $x$ are approximately constant, and that the distribution of the stratification variable is approximately uniform within each stratum. Under these assumptions, the optimum stratum boundaries would form a Geometric progression, thus leading to a very simple analytic solution.

Keskintürk and Er (2007) proposed an approach based on a global optimisation technique called Genetic Algorithms. Following a similar idea, de Moura Brito et al. (2017b) applied another global optimisation technique called GRASP to the stratification problem. Here we followed a route like Keskintürk and Er (2007), but have adopted an efficient choice of Genetic Algorithm, namely the Biased Random Key Genetic Algorithm (BRKGA), described in Section 4.

Kozak (2004) proposed a method called random search, followed later by Kozak and Verma (2006), where this approach was compared to the Geometric method of Gunning and Horgan (2004). Khan, Nand and Ahmad (2008) used ideas of dynamic programming to develop an algorithm that determines the stratum boundaries considering that the stratification variable has either a Triangular or Normal distribution, and that sampling within strata is with replacement. De Moura Brito, Maculan, Lila and Montenegro (2010b) proposed an exact algorithm based on graph theory, where proportional allocation to the strata is assumed.

Er (2011) compared the efficiency of several methods available in the literature, taking the Geometric approach of Gunning and Horgan (2004) as the initial solution. Kozak (2014) compared his random search with the Genetic Algorithm proposed by Keskintürk and Er (2007). Rao, Khan and Reddy (2014) developed a method that tackles the stratum boundary determination and stratum allocation problems simultaneously. Their algorithm relies on the assumption that the stratification variable follows a Pareto distribution. Our approach is more general and does not assume that the size variable follows a particular distribution.

• Previous
• Article main page
• Next