A simulated annealing algorithm for joint stratification and sample allocation
Section 1. Introduction
In stratified simple random sampling, a population is partitioned into mutually exclusive and collectively exhaustive strata, and then sampling units from each of those strata are randomly selected. The purposes for stratification are discussed in Cochran (1977). If the intra-strata variances were minimized then precision would be improved. It follows that the resulting small samples from each stratum can be combined to give a small sample size.
To this end, we intend to construct strata which are internally homogeneous but which also accommodate outlying measurements. To do so, we adopt an approach which entails searching for the optimum partitioning of atomic strata (however, the methodology can also be applied to continuous strata) created from the Cartesian product of categorical stratification variables, see Benedetti, Espa and Lafratta (2008); Ballin and Barcaroli (2013, 2020).
The Bell number, representing the number of possible partitions (stratifications) of a set of atomic strata, grows very rapidly with the number of atomic strata (Ballin and Barcaroli, 2013). In fact, there comes a point where, even for a moderate number of atomic strata and the most powerful computers, the problem is intractable, i.e. there are no known efficient algorithms to solve the problem.
Many large scale combinatorial optimisation problems of this type cannot be solved to optimality, because the search for an optimum solution requires a prohibitive amount of computation time. This compels one to use approximisation algorithms or heuristics which do not guarantee optimal solutions, but can provide approximate solutions in an acceptable time interval. In this way, one trades off the quality of the final solution against computation time (Van Laarhoven and Aarts, 1987). In other words, heuristic algorithms are developed to find a solution that is “good enough” in a computing time that is “small enough” (Sörensen and Glover, 2013).
A number of heuristic algorithms have been developed to search for optimal or near optimal solutions, for both univariate and multivariate scenarios of this problem. This includes the hierarchichal algorithm proposed by Benedetti et al. (2008), the genetic algorithm proposed by Ballin and Barcaroli (2013) and the grouping genetic algorithm proposed by O’Luing, Prestwich and Tarim (2019). Although effective, the evaluation function in these algorithms can be costly in terms of running time.
We add to this work with a simulated annealing algorithm (SAA) (Kirkpatrick, Gelatt and Vecchi, 1983; ernỳ, 1985). SAAs have been found to work well in problems such as this, where there are many local minima and finding an approximate global solution in a fixed amount of computation time is more desirable than finding a precise local minimum (Takeang and Aurasopon, 2019). We present a SAA to which we have added delta evaluation (see Section 5) to take advantage of the similarity between consecutive solutions and help speed up computation times.
We compared the performance of the SAA on atomic strata with that of the grouping genetic algorithm (GGA) in the SamplingStrata package (Ballin and Barcaroli, 2020). This algorithm implements the grouping operators described by O’Luing et al. (2019). To do this, we used sampling frames of varying sizes containing what we assume to be completely representative details for target and auxiliary variable columns.
Further to the suggestion of a Survey Methodology reviewer, we subsequently compared the SAA with a traditional genetic algorithm (TGA) used by Ballin and Barcaroli (2020) on continuous strata. In both sets of experiments, we used an initial solution created by the k-means algorithm (Hartigan and Wong, 1979) in a two-stage process (see Section 2.3 for more details).
Section 2 provides background information on atomic strata, introduces the SAA and motivates the addition of delta evaluation as a means to improve computation time. Two-stage simulated annealing is also discussed. Section 3 of the paper describes the cost function and evaluation algorithm. Section 4 provides an outline of the SAA. Section 5 presents the improved SAA with delta evaluation. Section 6 provides a comparison of the performance of the SAA with the GGA using an initial solution and fine-tuned hyperparameters. Section 7 then provides details of the comparison of the SAA with the genetic algorithm in Ballin and Barcaroli (2020) on continuous strata. Section 8 presents the conclusions and Section 9 suggests some further work. The Appendix contains background details on precision constraints, the hyperparameters, and the process of fine-tuning the hyperparameters for both comparisons as well as the computer specifications.
- Date modified: