A simulated annealing algorithm for joint stratification and sample allocation
Section 2. Background information
2.1 Stratification of atomic strata
Atomic strata are created using categorical auxiliary variable columns such as age group, gender or ethnicity for a survey of people or industry, type of business and employee size for business surveys. The cross-classification of the class-intervals of the auxiliary variable columns form the atomic strata.
Auxiliary variable columns which are correlated to the target variable columns may provide a gain in sample precision or similarity. Each target variable column, contains the value of the survey characteristic of interest, e.g. total income, for each population element in the sample.
Once these are created, we obtain summary statistics, such as the number, mean and standard deviation of the relevant observed values, from the one or more target variable columns that fall within each atomic stratum. The summary information is then aggregated in order to calculate the means and variances for each stratum which in turn are used to calculate the sample allocation for a given stratification.
The partitioning of atomic strata that provides the global minimum sample allocation, i.e. the minimum of all possible sample allocations for the set of possible stratifications, is known as an optimal stratification. There could be a multiple of such partitionings. Although an optimum stratification is the solution to the problem, each stratification represents a solution of varying quality (the lower the cost (minimum or optimal sample allocation) the higher the quality). For each stratification, the cost is estimated by the Bethel-Chromy algorithm (Bethel, 1985, 1989; Chromy, 1987). A more detailed description, and discussion of the methodology for this approach for joint determination of stratification and sample allocation, can be found in Ballin and Barcaroli (2013).
2.2 Simulated annealing algorithms
The basic principle of the SAA (Kirkpatrick et al., 1983; ernỳ, 1985) is that it can accept solutions that are inferior to the current best solution in order to find the global minima (or maxima). It is one of several stochastic local search algorithms, which focus their attention within a local neighbourhood of a given initial solution (Cortez, 2014), and use different stochastic techniques to escape from attractive local minima (Hoos and Stützle, 2004).
Based on physical annealing in metallurgy, the SAA is designed to simulate the controlled cooling process from liquid metal to a solid state (Luke, 2013). This controlled cooling uses the temperature parameter to compute the probability of accepting inferior solutions (Cortez, 2014). This acceptance probability is not only a function of the temperature, but also the difference in cost between the new solution and the current best solution. For the same difference in cost, a higher temperature means a higher probability of accepting inferior solutions.
For a given temperature, solutions are iteratively generated by applying a small, randomly generated, perturbation to the current best solution. Generally, in SAAs, a perturbation is the small displacement of a randomly chosen particle (Van Laarhoven and Aarts, 1987). In the context of our problem, we take perturbation to mean the displacement (or re-positioning) of (generally randomly chosen atomic strata from one randomly chosen stratum to another.
With a perturbation, the current best solution transitions to a new solution. If a perturbation results in a lower cost for the new solution, or if there is no change in cost, then that solution is always selected as the current best solution. If the new solution results in a higher cost, then it is accepted at the above mentioned acceptance probability. This acceptance condition is called the Metropolis criterion (Metropolis, Rosenbluth, Rosenbluth, Teller and Teller, 1953). This process continues until the end of the sequence, at which point the temperature is decremented and a new sequence begins.
If the perturbations are minor, then the current solution and the new solution will be very similar. Indeed, in our SAA we are assuming only a slight difference between consecutive solutions owing to such perturbations (see Section 4.1 for more details). For this reason we have added delta evaluation, which will be discussed further in Section 5, to take advantage of this similarity and help improve computation times.
Accordingly, and as mentioned in the introduction, we present a SAA with delta evaluation and compare it with the GGA when both are combined with an initial solution. We also compare it with a genetic algorithm used by Ballin and Barcaroli (2020) on continuous strata. We provide more background details on initial solutions in Section 2.3 below.
2.3 Two-stage simulated annealing
A two stage simulated annealing process, where an initial solution is generated by a heuristic algorithm in the first stage, has been proposed for problems such as the cell placement problem (Grover, 1987; Rose, Snelgrove and Vranesic, 1988) or the graph partitioning problem (Johnson, Aragon, McGeoch and Schevon, 1989). Lisic, Sang, Zhu and Zimmer (2018) combined an initial solution, generated by the k-means algorithm, with a simulated annealing algorithm, for a problem similar in nature to this problem, but where the sample allocation as well as strata number are fixed, and the algorithm searches for the optimal arrangement of sampling units between strata.
The simulated annealing algorithm used by Lisic et al. (2018) starts with an initial solution (stratification and sample allocation to each stratum) and, for each iteration, generates a new candidate solution by moving one atomic stratum from one stratum to another and adjusting the sample allocation for that stratification. Each candidate solution is then evaluated to measure the coefficient of variation (CV) of the target variables and is accepted, as the new current best solution, if its objective function is less than the preceding solution. Inferior quality solutions are also accepted at a probability, which is a function of a tunable temperature parameter and the change in solution quality between iterations. The temperature cools, at a rate which is also tunable, as the number of iterations increases.
Following this work, Ballin and Barcaroli (2020) recommended combining an initial solution, generated by k-means, with the grouping and traditional genetic algorithms. They demonstrate that the k-means algorithm provides better starting solutions when compared with the starting solution generated by a stochastic approach. We also combine a k-means initial solution with the SAA in the experiments described in Sections 6 and 7.
- Date modified: