An optimisation algorithm applied to the one-dimensional stratification problem
Section 5. Computational results

• Previous
• Next

In this section, we present the results of application of six methods to solve the stratification problem, namely: Dalenius and Hodges (DH), Geometric (GH), Kozak (KO), Genetic Algorithm of Keskinturk and Er (KE), GRASP (GR) and the new BRKGA method described in Section 4 (BR). All experiments where carried out using R version 3.3.1. The methods DH, GH and KO are available from the R package stratification of Baillargeon and Rivest (2014) (version 2.2-5). With these methods, the Neyman sample allocation method was used. The KE method is available from the R package GA4Stratification of Er, Keskintürk and Daly (2010) (version 1.0). With this method, the maximum number of iterations considered was 10,000 and the values of the other parameters required were the same as those reported by Keskintürk and Er (2007), namely using $p=35$ candidate solutions in each population, a mutation rate of 15% and the sample allocation based also on the Genetic Algorithm. Both the GR and the BR methods were implemented in R by the authors, and the code is provided in package stratbr of de Moura Brito et al. (2017a) (version 1.2) available from CRAN.

For the BR method, $p=100$ candidate solutions were considered in each iteration, with 20% of the solutions being made elite $\left(p_e=20\right)$ and 30% of the solutions being mutant $\left(p_m=30\right)$ in each iteration. The probability of copying a gene from the elite vector was set at $r_c=\text{0}\text{.6}.$ The total number of iterations was set at 1,500. For the sample allocation, both the BR and the GR methods were coupled with the formulation proposed by de Moura Brito et al. (2015) which is available from the R package MultAlloc, also available from CRAN.

To compare the relative efficiency of these methods, they were applied to 27 different populations. Some of these populations are available from the R packages stratification and GA4Stratification, and were previously used in other comparison studies such as Keskintürk and Er (2007), Er (2011), and de Moura Brito et al. (2017b). Appendix A contains brief descriptions of all these populations, including information on which variable was considered as the “ $x$ variable” in each population. Table 5.1 provides some summaries to describe these populations.

The 27 populations considered here form a very diverse set, with total sizes varying from a few hundred (ME84 and P75 with $N=284$ are the smallest) to several thousand (Coffee with $N=\text{18,570}$ is the largest). In the size measure that matters most for efficiency of our optimization algorithm, namely the number $K$ of distinct values of the stratification variable, there’s also large variation (from $K=51$ for Kozak1 to $K=\text{5,453}$ to Kozak3). They also display wide variation in the asymmetry of the $x$ variable’s distributions, ranging from modestly negative (-0,70 for Beta103 to a substantial 40.04 for CensoCO).

All the calculations for the computational experiment were performed using R in a computer with 24 GB RAM, with 8 processors of 3.40 GHz (I7). Taking advantage of the multicore architecture in modern computers, the snowfall R package was used to parallelize the BRKGA algorithm. More specifically, at each iteration, the decoding procedure produces a set of solutions for the boundary points. These boundary points are then supplied to the MultAlloc package for optimum allocation, to obtain the sample sizes in each stratum, and then to compute the objective variance function. Since the computation time for this step is impacted directly by the use of this global optimization formulation, the allocation and calculation of the objective function were parallelized.

All six methods considered in the numerical experiment were applied to each of the 27 populations, for numbers of strata $H$ equal to 3, 4, 5 and 6. These values were used since they are often considered in applications, as well as in similar comparative studies available in the literature, such as Er (2011) and Gunning and Horgan (2004). We did not consider larger values for $H$ since the additional gains in efficiency for $H>6$ are modest. The sample size $n=100$ (i.e., fixed cost) was used, as in the numerical experiments of Er (2011) and Kozak and Verma (2006).

To assess the efficiency of the methods, the CVs of the estimator for the total of the stratification variable $x$ were calculated for each population and number of strata, leading to 27 × 4 = 108 scenarios for each method. CVs were obtained from equation (2.7) and multiplied by 100, to be presented as percentages. Table 5.2 provides the CVs attained by the six methods. The shaded cells indicate methods providing the best solution (minimum CV) for each of 108 scenarios. The NAs in these tables represent cases where solutions could not be obtained due to problems of the specific stratification method or with the corresponding allocation.

Analyzing the results provided in Table 5.2, and in particular, the shaded cells, it is evident that BR has excellent performance when compared to the five competitors considered. This perception is reinforced by the plots in Figure 5.1, where BR was compared with all competitors. Points above the straight line represent scenarios where the method chosen for comparison is outperformed by BR. It is evident from these plots that the three best performing methods are GR, KO and BR.

Table 5.3 provides the percentage of times that each method produced the best solution over the 108 scenarios. Both BR and KO display performance which is superior to that of the other methods and have tied in the number of times that they have achieved the best solution. DH produced the best solution for only three of the 108 scenarios, and GH has never produced a best solution.

The Geometric method GH, besides leading to high CVs, also often provided infeasible solutions, where the stratum limits lead to allocations where sample sizes were larger than the corresponding population sizes. This method also sometimes partitioned the population such that there were very few population elements in some strata. According to Gunning and Horgan (2004), and as noted by Keskintürk and Er (2007), since the interval widths increase geometrically, the GH method will not perform well when the stratification variable has small values, since this will lead to some narrow strata. This method is also not applicable when the smallest value in the stratification variable is zero.

For most populations, the KE method has produced CVs close to those obtained by the KO, GR and BR methods, which are the most efficient in terms of computing time. Large variation on computing time was observed between different methods. The KE method showed the worst results in this criterion, having displayed computing times much larger than those of the competing methods. The KO method, on the other hand, was the fastest in terms of computing time, while at the same time often achieving the best possible precision (lowest CV). The BR method showed computing time in between those of the KO and KE methods.

The graph in Figure 5.2 shows the percentages of times that each of the methods BR, KO, KE and GR produced the best solution, separated by number of strata. It shows a clear advantage of the BR method when compared to the KE and GR methods. When compared to KO, BR performed better for $H=3$ and $H=6,$ while KO was the winner for $H=4$ and $H=5.$ GR performed as well as KO for $H=3$ and $H=6,$ but was outperformed by both BR and KO for $H=4$ and $H=5.$ KE was the clear loser in this analysis, for any number of strata $H.$

We have also searched for associations between performance and other potential drivers, such as the skewness or the size $(N$ or $K)$ of the populations, but have not found any meaningful association within our limited set of populations.

• Previous
• Article main page
• Next