A simulated annealing algorithm for joint stratification and sample allocation
Section 6. Comparing the performance of the two algorithms

• Previous
• Next

6.1   Evaluation plan

In this section, we outline the comparison of the performance of the grouping genetic algorithm with the simulated annealing algorithm. We used a number of data sets of varying sizes in these experiments. There are a number of regions in each data set (labelled here as domains). An optimal stratification and minimum sample allocation was selected for each domain.

The sum of the samples for all domains provides the total sample size. The sample size, or cost of the solution, defines the solution quality. For more details on domains refer to Ballin and Barcaroli (2013). 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. More details are available in the Appendix.

We tabulate the results of these experiments in Section 6.4 where for comparison purposes we express the SAA results as a ratio of those for the GGA.

6.2   Comparing the number of solutions generated

After the first iteration the GGA retains the elite solutions, $E,$ from the previous iteration. These are calculated by the product of the elitism rate (the proportion of the chromosome population which are elite solutions), $E_R,$ and the chromosome population size (the number of candidate solutions in each iteration), $N_P.$ As $E$ have already been evaluated they are not evaluated again.

For this reason, we compared the evaluation times for the evaluated solutions in the GGA with all those of the SAA. For the GGA, the total number of evaluated solutions, $N_{\text{GGAsol}},$ is a function of the number of domains, $D,$ the chromosome population size, the non-elite solutions (calculated by the product of $1-E_R$ and $N_P),$ and the number of iterations, $I.$ For more details on the implementation of GGAs (e.g. elite solutions, elitism rate, chromosome population) we refer the reader to (Falkenauer, 1998)

$$N_{\text{GGAsol}}=\left(D\times \left(N_P+\left(N_P\times \left(1-E_R\right)\times \left(I-1\right)\right)\right)\right).$$

For the simulated annealing algorithm, the maximum number of solutions, $N_{\text{SAAsol}},$ is the number of domains, $D,$ by the number of sequences, maxit, by the length of sequence, $J.$ Recall that the SAA also stops if the minimum temperature has been reached ‒ hence we refer to the maximum number of solutions rather than the total. For comparability purposes however, because the temperature is decremented only at the end of each sequence and we have a small number of sequences in the experiments below we assume the full number of solutions has been generated

$$N_{\text{SAAsol}}=D\cdot maxit\cdot J.$$

6.3   Data sets, target and auxiliary variables

Table 6.1 provides a summary by data set of the target and auxiliary variables.

The target and auxiliary variables for the Swiss Municipalities data set were selected based on the experiment described in Ballin and Barcaroli (2020). Accordingly, POPTOT and HApoly were converted into categorical variables using the k-means clustering algorithm. However, we used more domains and iterations in our experiment. More information on this data set is provided by Barcaroli (2014).

For the remaining experiments we selected target and auxiliary variables which we deemed likely to be of interest to survey designers. Further details on the American Community Survey, 2015 (U.S. Census Bureau, 2016), the U.S. Census, 2000 (Ruggles, Genadek, Goeken, Grover and Sobek, 2017), Kiva Loans (Kiva, 2018), and the UN commodity trade statistics data (United Nations, 2017) metadata are available in O’Luing et al. (2019).

A further summary by data set of the number of records and atomic strata, along with a description of the domain variable, is provided in Table 6.2 below.

6.4   Results

As mentioned previously, we used an initial solution in each experiment that is created by the KmeansSolution algorithm (Ballin and Barcaroli, 2020). We then compared the performance of the algorithms in terms of average computation time (in seconds) per solution and solution quality. Table 6.3 provides the sample size, execution times and total execution times for the SAA and GGA.

The total execution time is the sum of the execution times for 20 evaluations of the GGA and SAA algorithms (by the MBO (model-based optimisation) function in the R package mlrMBO (Bischla, Richterb, Bossekc, Hornb, Thomasa and Langb, 2017)) using 20 sets of selected hyperparameters (i.e. one set for each evaluation). Details on the precision constraints and hyperparameters for each experiment can be found in the Appendix. Table 6.4 expresses the SAA results as a ratio of those for the GGA.

As can be seen, the sample sizes are similar, however, the SAA shows significantly lower execution and total execution times. When these experiments are run in parallel, for cases where there is a large number of domains, there may not be enough cores to cover all domains in one run. Indeed, it may take several parallel runs to complete the task, and this will affect mean evaluation time. The computer specifications are provided in Table A.2. Table 6.5 shows the number of solutions evaluated by each algorithm to obtain the results shown in Table 6.3. It also provides a ratio comparison of the average execution time (in seconds) per solution.

The above results indicate that the GGA has evaluated more solutions to find a solution of similar quality to the SAA in all cases, except for the US Census, 2000 experiment. However, we also can see that the SAA takes less time to evaluate each solution in all cases except for the Swiss Municipalities experiment. The average execution time for each experiment can be considered in the context of the size of the data set, parallelisation, and the particular sets of hyperparameters used for the GGA and SAA. In addition to this, there is also memoisation in the evaluation algorithm for the GGA, and the gains obtained by delta evaluation by the SAA.

Gains are more noticeable for larger data sets, because of the size of the solution and number of atomic strata in each stratum. As the strata get larger in size, the movement of $q$ atomic strata from one stratum to another (where $q$ is small) will have a smaller impact on solution quality and, therefore, the delta evaluation will be quicker.

• Previous
• Article main page
• Next