A simulated annealing algorithm for joint stratification and sample allocation
Section 9. Further work
The perturbation used by
the SAA randomly moves atomic strata,
where mainly from one
stratum to another. This stochastic process is standard in default simulated
annealing algorithms. However, as we are using a starting solution where there
is already similarity within the strata, this random process could easily move
an atomic stratum to a stratum
where it is less suited than the stratum it was in. This suggests the presence
of a certain amount of redundancy in the search for the global minimum.
Lisic et al. (2018) conjecture that the introduction of nonuniform weighting in atomic strata selection could greatly improve performance of (their proposed) simulated annealing method by exchanging atomic strata near stratum boundaries more frequently than more important atomic strata. We agree that, for this algorithm, it would be more beneficial if there was a higher probability that an atomic stratum which was dissimilar to the other atomic strata was selected. We could then search for a more suitable stratum to move this atomic stratum to.
To achieve this we could first randomly select a stratum, and then measure the Euclidean distance of each atomic stratum from that stratum medoid, weighting the chance of selection of the atomic strata in accordance with their distance from the medoid. At this point, an atomic stratum is selected using these weighted probabilities.
The next step would be to use a K-nearest-neighbour algorithm to find the stratum medoid closest to that atomic stratum and move it to that stratum. This simple machine learning algorithm uses distance measures to classify objects based on their nearest neighbours. In this case, so the algorithm in practice is a closest nearest neighbour classifier.
This additional degree of complexity to the algorithm may offset the gains achieved by using delta evaluation, particularly as the problem grows in size, thus reducing the number of solutions evaluated in the same running time. It might be more effective to use the column medians as an equivalent to the medoids. This could assist the algorithm find better quality solutions.
However, the above suggestions may only be effective at an advanced stage of the search, where the atomic strata in each stratum are already quite similar.
Acknowledgements
We wish to acknowledge the editorial staff and reviewers of Survey Methodology for their constructive suggestions in the review process for this journal submission, in particular the suggestion to compare the SAA with the traditional genetic algorithm in Ballin and Barcaroli (2020) in the case of continuous strata. This material is based upon work supported by the Insight Centre for Data Analytics and Science Foundation Ireland under Grant No. 12/RC/2289-P2 which is co-funded under the European Regional Development Fund. Also, this publication has emanated from research supported in part by a grant from Science Foundation Ireland under Grant number 16/RC/3918 which is co-funded under the European Regional Development Fund.
Appendix
Background details on the comparisons in Sections 6 and 7
A.1 Precision constraints
The target upper precision levels for these experiments, i.e. coefficients of variation, for each of the five experiments are provided in Table A.1 below.
| Data set | CV |
|---|---|
| Swiss Municipalities | 0.1 |
| American Community Survey, 2015 | 0.05 |
| US Census, 2000 | 0.05 |
| Kiva Loans | 0.05 |
| UN Commodity Trade Statistics data | 0.05 |
We selected an upper precision level of 0.1 for the Swiss Municipalities data set in keeping with the level set for the experiment in Ballin and Barcaroli (2020). We used an upper precision level of 0.05 for the remaining experiments, given that the upper CV levels generally set by national statistics institutes (NSIs) tend to be between 0.01 and 0.1, and, for this reason, results for CVs in the mid-point of this range are of interest.
A.2 Processing platform
Table A.2 below provides details of the processing platform used for these experiments.
| Specification | Details | Notes |
|---|---|---|
| Processor | AMD Ryzen 9 3950X 16-Core Processor, 3493 Mhz | |
| Cores | 16 Core(s) | |
| Logical processors | 32 Logical Processor(s) | 32 cores in R |
| System model | X570 GAMING X | |
| System type | x64-based PC | |
| Installed physical memory (RAM) | 16.0 GB | |
| Total virtual memory | 35.7 GB | |
| OS name | Microsoft Windows 10 Pro |
In all cases, R version 4.0 or greater was used. We used the foreach (Microsoft Corporation and Weston, 2020a) and doParallel (Microsoft Corporation and Weston, 2020b) packages to run the experiments in parallel. The number of cores used in the experiments was 31 (32 less 1) and this means that in the three experiments with more than 31 domains (American Community Survey 2015, Kiva Loans, UN Commodity Trade Statistics data) the foreach algorithm continued to loop through the available cores until a solution had been found for all domains.
A.3 Hyperparameters for the grouping genetic algorithm and simulated annealing algorithm
Tables A.3 and A.4 below outline the number of domains in each experiment, along with number of iterations and chromosome population size for the grouping genetic algorithm and along with the number of sequences, length of sequence, and starting temperature for the simulated annealing algorithm. Section A.4 provides details on fine-tuning the hyperparameters. For more details on the hyperparameters of the GGA we refer the reader to Ballin and Barcaroli (2013) and O’Luing et al. (2019) and of the SAA to Sections 2.2 and 4.
| Data set | Domains | Number of iterations, I | Chromosome population size, | Mutation chance | Elitism rate, | Add strata factor |
|---|---|---|---|---|---|---|
| Swiss Municipalities | 7 | 4,000 | 50 | 0.0053360 | 0.4 | 0.0037620 |
| American Community Survey, 2015 | 51 | 5,000 | 20 | 0.0008134 | 0.5 | 0.0610529 |
| US Census, 2000 | 9 | 100 | 20 | 0.0000007 | 0.4 | 0.0000472 |
| Kiva Loans | 73 | 3,000 | 20 | 0.0007221 | 0.5 | 0.0685005 |
| UN Commodity Trade Statistics data | 171 | 1,000 | 20 | 0.0004493 | 0.3 | 0.0866266 |
| Data set | Domains | Number of sequences, maxit | Length of sequence, | Temperature, | Decrement constant, | % of L for maximum q value, | Probability of new stratum, |
|---|---|---|---|---|---|---|---|
| Swiss Municipalities | 7 | 10 | 3,000 | 0.0000720 | 0.5083686 | 0.0183356 | 0.0997907 |
| American Community Survey, 2015 | 51 | 3 | 3,000 | 0.0002347 | 0.6873029 | 0.0076477 | 0.0291729 |
| US Census, 2000 | 9 | 2 | 2,000 | 0.0006706 | 0.5457192 | 0.0189395 | 0.0806919 |
| Kiva Loans | 73 | 5 | 2,000 | 0.0009935 | 0.7806557 | 0.0143925 | 0.0317491 |
| UN Commodity Trade Statistics data | 171 | 3 | 3,000 | 0.0007902 | 0.5072737 | 0.0234728 | 0.0013775 |
A.4 Fine-tuning the hyperparameters for the grouping genetic algorithm and simulated annealing algorithm
In order to fine-tune the initial parameters or hyperparameters we used sequential model-based optimization (Hutter, Hoos and Leyton-Brown, 2010). We first generated an initial design of hyperparameters from the value ranges described for the GGA in Table A.5 and in Table A.6 for the SAA below using the latin hypercube design method (McKay, Beckman and Conover, 2000).
| Value type | Iterations | Population size | Mutation chance | Elitism rate, | Add strata factor | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Discrete | Discrete | Numeric | Discrete | Numeric | |||||||||
| Value range | Lower value | Upper value | Increments | Lower value | Upper value | Increments | Lower value | Upper value | Lower value | Upper value | Increments | Lower value | Upper value |
| Swiss Municipalities | 500 | 5,000 | 500 | 10 | 50 | 10 | 0 | 0.10 | 0.1 | 0.5 | 0.1 | 0 | 0.1 |
| American Community Survey, 2015 | 1,000 | 5,000 | 1,000 | 10 | 20 | 10 | 0 | 0.001 | 0.1 | 0.5 | 0.1 | 0 | 0.1 |
| Kiva Loans | 1,000 | 3,000 | 1,000 | 10 | 20 | 10 | 0 | 0.001 | 0.1 | 0.5 | 0.1 | 0 | 0.1 |
| UN Commodity Trade Statistics data | 500 | 1,000 | 500 | 10 | 20 | 10 | 0 | 0.001 | 0.1 | 0.5 | 0.1 | 0 | 0.1 |
| US Census, 2000 | 50 | 100 | 50 | 10 | 20 | 10 | 0 | 0.000001 | 0.1 | 0.5 | 0.1 | 0 | 0.0001 |
| Value type | Number of sequences, maxit | Length of sequence, | Temperature, | Decrement constant, DC | % L for maximum q value, | Probability of new stratum, | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Discrete | Discrete | Numeric | Numeric | Numeric | Numeric | |||||||||
| Value range | Lower value | Upper value | Increments | Lower value | Upper value | Increments | Lower value | Upper value | Lower value | Upper value | Lower value | Upper value | Lower value | Upper value |
| Swiss Municipalities | 10 | 50 | 10 | 1,000 | 3,000 | 1,000 | 0 | 0.001 | 0.5 | 1 | 0.0001 | 0.025 | 0 | 0.1 |
| American Community Survey, 2015 | 1 | 3 | 1 | 1,000 | 3,000 | 1,000 | 0 | 0.001 | 0.5 | 1 | 0.0001 | 0.025 | 0 | 0.1 |
| Kiva Loans | 1 | 5 | 1 | 1,000 | 2,000 | 1,000 | 0 | 0.001 | 0.5 | 1 | 0.0001 | 0.025 | 0 | 0.1 |
| UN Commodity Trade Statistics data | 1 | 3 | 1 | 1,000 | 3,000 | 1,000 | 0 | 0.001 | 0.5 | 1 | 0.0001 | 0.025 | 0 | 0.1 |
| US Census, 2000 | 1 | 2 | 1 | 1,000 | 2,000 | 1,000 | 0 | 0.001 | 0.5 | 1 | 0.0001 | 0.025 | 0 | 0.1 |
As some of the hyperparameter value ranges were discrete, we used a random forest with regression trees to develop a surrogate learner model. After this, a confidence bound using a lambda value, to control the trade-off between exploitation and exploration was used as the acquisition function. The focus search approach (Bischla et al., 2017) was used to optimise the acquisition function which, in turn, was used to propose the hyperparameters which were evaluated using the surrogate function (which is a cheaper alternative to using the GGA or SAA algorithms). From these, the most promising hyperparameters were then evaluated by the GGA or SAA and the hyperparameters and solution costs added to the initial design. The process was then repeated for a set number of iterations and the best performing hyperparameters and solution outcomes were selected. We implemented this using the MBO function with the parameters outlined in Table A.7. These are distinct from the parameters being fine-tuned, which are outlined in Tables A.5 and A.6 above.
| MBO parameters | Value |
|---|---|
| Initial Design size (Latin Hypercube Design method) | 10 |
| Iterations, number of | 10 |
| Number of Trees | 500 |
| Lambda, | 5 |
| Focus Search Points | 1,000 |
As can be seen from the limited scope of the MBO function parameters this was not an exhaustive fine-tuning of the hyperparameters for the GGA and SAA. The aim of these experiments was to consider whether the SAA can attain comparable solution quality with the GGA in less computation time per solution thus resulting in savings in execution times. However, we also compared the total execution times as this is a consequence of the need to train the hyperparameters for both algorithms.
Tables outlining the hyperparameters, in each of the 20 fine-tuning iterations, for each experiment are available from the authors on request. The first 10 sets of hyperparameters were randomly generated from the ranges laid out in Tables A.5 and A.6. The ranges selected were identified using practical knowledge of the algorithms and data. The second 10 sets reflects the MBO function’s attempts to learn the hyperparameters that best lead each algorithm towards the optimal solution using the previous solutions as a guide.
A.5 Hyperparameters for the traditional genetic algorithm and simulated annealing algorithm
Tables A.8 and A.9 outline the hyperparameters for the tradtional genetic algorithm and the simulated annealing algorithm. The add strata factor option is not available for the traditional genetic algorithm and, therefore, is not included in Table A.8. More details on fine-tuning the hyperparameters are provided in Section A.6.
| Data set | Iterations | Population size | Mutation chance | Elitism rate, |
|---|---|---|---|---|
| Swiss Municipalities | 4,000 | 50 | 0.0053360 | 0.4 |
| American Community Survey, 2015 | 1,000 | 20 | 0.0009952 | 0.1 |
| US Census, 2000 | 400 | 20 | 0.0002317 | 0.4 |
| Kiva Loans | 200 | 20 | 0.0817285 | 0.5 |
| UN Commodity Trade Statistics data | 5,000 | 30 | 0.0005599 | 0.2 |
| Data set | Number of sequences, maxit | Length of sequence, | Temperature, | Decrement constant, DC | % for maximum q value, | Probability of new stratum, |
|---|---|---|---|---|---|---|
| Swiss Municipalities | 5 | 5,000 | 0.02311057 | 0.9427609 | 0.3736443 | 0.0229361 |
| American Community Survey, 2015 | 50 | 2,000 | 0.00000005 | 0.9528952 | 0.0001021 | 0.0000008 |
| US Census, 2000 | 1 | 2,000 | 0.00002000 | 0.9665631 | 0.0221147 | 0.0160408 |
| Kiva Loans | 2 | 2,000 | 0.00053839 | 0.8660943 | 0.0014281 | 0.0216320 |
| UN Commodity Trade Statistics data | 2 | 250 | 0.00067481 | 0.9309940 | 0.0203113 | 0.0149499 |
A.6 Fine-tuning the hyperparameters for the traditional genetic algorithm and simulated annealing algorithm
We fine-tuned the hyperparameters for the TGA and SAA using the same methodology described in Section A.4. Tables outlining the hyperparameters, in each of the 20 fine-tuning iterations, for each experiment are available from the authors on request. The first 10 sets were randomly generated using practical knowledge of the algorithms and data to define upper and lower bounds for each hyperparameter. In the second 10 sets the MBO function attempts to optimise the hyperparameters using the previous solutions as a guide.
References
Ballin, M., and Barcaroli, G. (2013). Joint determination of optimal stratification and sample allocation using genetic algorithm. Survey Methodology, 39, 2, 369-393. Paper available at https://www150.statcan.gc.ca/n1/en/pub/12-001-x/2013002/article/11884-eng.pdf.
Ballin, M., and Barcaroli, G. (2020). Optimization of sampling strata with the SamplingStrata package. Accessed 3 May 2021. https://barcaroli.github.io/SamplingStrata/articles/SamplingStrata.html.
Barcaroli, G. (2014). SamplingStrata: An R package for the optimization of stratified sampling. Journal of Statistical Software, 61, 4, 1-24.
Benedetti, R., Espa, G. and Lafratta, G. (2008). A tree-based approach to forming strata in multipurpose business surveys. Survey Methodology, 34, 2, 195-203. Paper available at https://www150.statcan.gc.ca/n1/en/pub/12-001-x/2008002/article/10760-eng.pdf.
Bethel, J.W. (1985). An optimum allocation algorithm for multivariate surveys. Proceedings of the Section on Survey Research Methods, American Statistical Association, 209-212.
Bethel, J. (1989). Sample allocation in multivariate surveys. Survey Methodology, 15, 1, 47-57. Paper available at https://www150.statcan.gc.ca/n1/en/pub/12-001-x/1989001/article/14578-eng.pdf.
Bischla, B., Richterb, J., Bossekc, J., Hornb, D., Thomasa, J. and Langb, M. (2017). mlrmbo: A modular framework for model-based optimization of expensive black-box functions. Gradient Boosting in Automatic Machine Learning: Feature Selection and Hyperparameter Optimization, 36.
ernỳ, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45, 1, 41-51.
Chromy, J.R. (1987). Design optimization with multiple objectives. Proceedings of the Survey Research Methods Section.
Cochran, W.G. (1977). Sampling Techniques. 3rd Edition. New York: John Wiley & Sons, Inc.
Cortez, P. (2014). Modern Optimization with R. Springer.
Falkenauer, E. (1998). Genetic Algorithms and Grouping Problems. New York: John Wiley & Sons, Inc.
Grover, L.K. (1987). Standard cell placement using simulated sintering. In Proceedings of the 24th ACM/IEEE Design Automation Conference, 56-59.
Hartigan, J.A., and Wong, M.A. (1979). Algorithm as 136: A k-means clustering algorithm. Journal of the Royal Statistical Society, Series C (Applied Statistics), 28, 1, 100-108.
Hoos, H.H., and Stützle, T. (2004). Stochastic Local Search: Foundations and Applications. Elsevier.
Hutter, F., Hoos, H.H. and Leyton-Brown, K. (2010). Sequential model-based optimization for general algorithm configuration (extended version). Technical Report TR-201010, University of British Columbia, Computer Science.
Johnson, D.S., Aragon, C.R., McGeoch, L.A. and Schevon, C. (1989). Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning. Operations Research, 37, 6, 865-892.
Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983). Optimization by simulated annealing. Science, 220, 4598, 671-680.
Kiva (2018, Mar). Data Science for Good: Kiva Crowdfunding. https://www.kaggle.com/kiva/data-science-for-good-kiva-crowdfunding.
Lisic, J., Sang, H., Zhu, Z. and Zimmer, S. (2018). Optimal stratification and allocation for the june agricultural survey. Journal of Official Statistics, 34, 1, 121-148.
Luke, S. (2013). Essentials of Metaheuristics (2 Ed.). Lulu. Available for free at http://cs.gmu.edu/~sean/book/metaheuristics/.
McKay, M.D., Beckman, R.J. and Conover, W.J. (2000). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 42, 1, 55-61.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21, 6, 1087-1092.
Microsoft Corporation and Weston, S. (2020a). foreach: Provides Foreach Looping Construct. R package version 1.5.1.
Microsoft Corporation and Weston, S. (2020b). doParallel: Foreach Parallel Adaptor for the ‘Parallel’ Package. R package version 1.0.16.
O’Luing, M., Prestwich, S. and Tarim, S.A. (2019). A grouping genetic algorithm for joint stratification and sample allocation designs. Survey Methodology, 45, 3, 513-531. Paper available at https://www150.statcan.gc.ca/n1/en/pub/12-001-x/2019003/article/00007-eng.pdf.
Rose, J.S., Snelgrove, W.M. and Vranesic, Z.G. (1988). Parallel standard cell placement algorithms with quality equivalent to simulated annealing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 7, 3, 387-396.
Ross, P., Corne, D. and Fang, H.-L. (1994). Improving evolutionary timetabling with delta evaluation and directed mutation. In International Conference on Parallel Problem Solving from Nature, 556-565. Springer.
Ruggles, S., Genadek, K., Goeken, R., Grover, J. and Sobek, M. (2017). Integrated public use microdata series: Version 7.0 [dataset]. Minneapolis: University of Minnesota.
Sörensen, K., and Glover, F. (2013). Metaheuristics. Encyclopedia of Operations Research and Management Science, 62, 960-970.
Takeang, C., and Aurasopon, A. (2019). Multiple of hybrid lambda iteration and simulated annealing algorithm to solve economic dispatch problem with ramp rate limit and prohibited operating zones. Journal of Electrical Engineering & Technology, 14, 1, 111-120.
United Nations (2017, Nov). Global Commodity Trade Statistics. https://www.kaggle.com/unitednations/global-commodity-trade-statistics.
U.S. Census Bureau (2016). 2015 ACS Public Use Microdata Sample (PUMS). Washington, D.C. https://factfinder.census.gov/faces/nav/jsf/pages/searchresults.xhtml?refresh=t#.
Van Laarhoven, P.J., and Aarts, E.H. (1987). Simulated annealing. In Simulated Annealing: Theory and Applications, Springer.
- Date modified: