A simulated annealing algorithm for joint stratification and sample allocation
Section 5. Improving the performance of the simulated annealing algorithm using delta evaluation

• Previous
• Next

As outlined earlier, the only difference between consecutive solutions is that $q$ atomic strata have been moved from one group into another. As with the other heuristics, $q$ is also tunable, and for the first sequence we have added the option of setting $q>1$ and reducing $q$ for each new solution in the first sequence until $q=1.$ The reason for this is that, where $q>1,$ the increased size of the perturbation can help reduce the number of strata. In this case, we set $q$ as a tunable percentage of the solution size, or of the number of atomic strata, $L,$ to be partitioned. After the first sequence $q=1.$

Furthermore, as the strata are mutually exclusive, this movement of $q$ atomic strata from one stratum to another does not affect the remaining strata in any way. Ross, Corne and Fang (1994) introduce a technique called delta evaluation, where the evaluation of a new solution makes use of previously evaluated similar solutions, to significantly speed up evolutionary algorithms/timetabling experiments. We use the similar properties of two consecutive solutions to apply delta evaluation to the SAA. It follows, therefore, that in the first sequence $q$ should be kept low and the reduction to $q=1$ should be swift.

The Bethel-Chromy algorithm requires the means and variances for each stratum in order to calculate the sample allocation. However, we use the information already calculated for the remaining $H-2$ strata, and simply calculate for the two strata affected by the perturbation. Thus, the computation for the means and variances of the $H$ strata is reduced to a mere subset of that otherwise required.

Now recall that the Bethel-Chromy algorithm starts with a default value for each ${\alpha }_g,$ and uses gradient descent to find a final value for each ${\alpha }_g.$ This search continues up to when the algorithm reaches a minimum step-size threshold, or alternatively exceeds a maximum number of iterations. This minimum threshold is characterised by , which is set as $\text{1}\text{.0}\times {10}^{-11}$ in Ballin and Barcaroli (2020), and the maximum number of iterations is 200. We make the assumption that this search will be substantially reduced if we use the ${\alpha }_g$ values from the evaluation of the current solution as a starting point for the next solution.

The above two implementations of delta evaluation result in a noticeable reduction in computation times as demonstrated in the experiments described below.

• Previous
• Article main page
• Next