A simulated annealing algorithm for joint stratification and sample allocation
Section 4. Outline of the simulated annealing algorithm

Table of contents

The SAA with delta evaluation is described in Algorithm 1 below. We then describe the heuristics we have used in the SAA. Delta evaluation is explained in more detail in Section 5.

Figure 4.1

Description of Algorithm 1

Function SIMULATEDANNEALING $(S$ is the starting solution, $f$ is the evaluation function (Bethel-Chromy algorithm), best is the current best solution, BSFSF is the best solution found so far, maxit is the maximum number of sequences, $J$ is the length of sequence, $T_{m a x}$ is the starting temperature, $T_{m i n}$ is the minimum temperature, DC is the Decrement Constant, $L_{m a x %}$ is a % of $L$ (number of atomic strata), $P (H + 1)$ is the probability of a new stratum, $H + 1,$ being added)

$T \leftarrow T_{m a x}$

$b e s t \leftarrow$ S

$C o s t (b e s t) \leftarrow f (b e s t)$

while $i < m a x i t$ && $T > T_{m i n}$ do

if RANDOM $(0, 1)$ $\leq 1 / J$ then

for $l = 1$ to $L$ do

if RANDOM $(0, 1)$ $\leq P (H + 1)$ then

move atomic stratum $l$ to new stratum $H + 1$

end if

end for

end if

for $j = 1$ to $J$ do

if $i = 1$ & $j = 1$ then $q = L \times L_{m a x %}$

else if $i = 1$ & $j > 1$ then $q = c e i l i n g (q \times 0.99)$

else if $i > 1$ then $q = 1$

end if

Randomly select $h$ and $h^{'}$

next $\leftarrow$ PERTURBATION(best)

Cost(next) $\leftarrow f (b e s t)$

$Δ E \leftarrow$ COST $(n e x t)$ $-$ COST $(b e s t)$

if $Δ E \leq 0$ then

$b e s t \leftarrow n e x t$

else if RANDOM $(0, 1)$ $< e^{(- \frac{Δ E}{T})}$ then

$b e s t \leftarrow n e x t$

end if

if best $< =$ $B S F S F$ then

$B S F S F \leftarrow b e s t$

end if

end for

$T \leftarrow T * D C$

end while

return $B S F S F$

end function

►using Bethel-Chromy algorithm

►see Section 4.3

►0.99 is not tunable

►Assign $q$ atomic strata from $h$ and $h^{'}$
►using delta evaluation

►Metropolis Criterion

4.1 Perturbation

Consider the following solution represented by the stratification:

${1, 3}, {2}, {4, 5, 6} .$

The integers within each stratum represent atomic strata. In perturbation, the new solution below is created by arbitrarily moving atomic strata, in this example $q = 1,$ from one randomly chosen stratum to another.

${1, 3, 2}, {\emptyset}, {4, 5, 6} .$

The first stratum gains an additional atomic stratum ${2}$ to become ${1, 3, 2},$ whereas the middle or second stratum has been “emptied” (and is deleted), and there remains only two strata. Strata are only emptied when the last remaining atomic stratum has been moved to another stratum.

To clarify how this works in the algorithm: each solution is represented by a vector of integers ‒ atomic strata which have the same integer are in the same stratum. A separate vector of the unique integers in the solution represents the strata. For example, the first solution ${1, 3},$ ${2},$ ${4, 5, 6}$ would be represented by the vector $[1 2 1 3 3 3]$ and the strata would be represented by the vector $[1 2 3] .$ When the new solution is created, the second stratum has been removed and is no longer part of the solution. That is to say, the vector for the new solution is: $[1 1 1 3 3 3]$ and the strata vector is $[1 3] .$ With stratum 2 removed, and for clarity, we rename stratum 3 to 2 so that this solution becomes: $[1 1 1 2 2 2],$ and the strata are now represented by the vector $[1 2] .$ Strata $[1 2]$ will remain in any further solutions unless another stratum is “emptied” or a new stratum is added.

4.2 Evaluation and acceptance

Each new solution is evaluated using the Bethel-Chromy algorithm and the Metropolis acceptance criterion is applied. If accepted, the new solution differs from the previous solution only by the above mentioned perturbation. If it is not accepted, we continue with the previous solution, and again try moving $q$ randomly chosen atomic strata between two randomly selected strata.

4.3 Sequences and new strata

This continues for the tunable length of the sequence, $J .$ This should be long enough to allow the sequence to reach equilibrium. However, there is no rule to determine $J .$ At the commencement of each new sequence, we have $H$ strata in the current best solution. With a fixed probability of $1 / J,$ an additional stratum is added. If a new stratum is to be added, the SAA loops through each atomic stratum and moves it to a new stratum, which is called $H + 1,$ because each stratum is labelled sequentially from 1 to $H$ (see Section 4.1), at a tunable probability, $P (H + 1) .$ The algorithm runs for a tunable number of sequences, maxit.

4.4 Temperature

The temperature is decremented from a starting temperature, $T_{max},$ to a minimum temperature, $T_{min},$ or until maxit has been reached. As we are starting with a near optimal solution, we select $T_{max}$ as no greater than 0.01 and we set $T_{min}$ to be $1 .0 \times 10^{- 11} .$

This is to allow for the advanced nature of the search, and allows the algorithm to focus more on the search for superior solutions, with an ever-reducing probability of accepting inferior solutions. However, a low temperature, $T,$ does not always equate to a low probability of acceptance.

Small positive differences in solution quality (where the new solution has a marginally inferior quality to the current best solution), $Δ E,$ occur often because we are starting with a good quality initial solution. Figure 4.1 demonstrates the probability of such solutions being accepted, $e^{(- \frac{Δ E}{T})},$ increases the smaller this difference becomes for the same $T .$ Nonetheless, Figure 4.1 also demonstrates that for the same changes in solution quality as the $T$ decreases, the probability also decreases (and it behaves increasingly like a hill climbing algorithm).

Figure 4.1

Description of Figure 4.1

Figure illustrating the probability of accepting an inferior solution as a function of the difference in solution quality $(Δ E ),$ according to the three temperatures $(T )$ 0.0001, 0.001 and 0.01. The probability increases the smaller $Δ E$ becomes for the same $T .$ Furthermore, for the same $Δ E,$ as the $T$ decreases, the probability also decreases.

ISSN : 1492-0921

Editorial policy

Survey Methodology publishes articles dealing with various aspects of statistical development relevant to a statistical agency, such as design issues in the context of practical constraints, use of different data sources and collection techniques, total survey error, survey evaluation, research in survey methodology, time series analysis, seasonal adjustment, demographic studies, data integration, estimation and data analysis methods, and general survey systems development. The emphasis is placed on the development and evaluation of specific methodologies as applied to data collection or the data themselves. All papers will be refereed. However, the authors retain full responsibility for the contents of their papers and opinions expressed are not necessarily those of the Editorial Board or of Statistics Canada.

Submission of Manuscripts

Survey Methodology is published twice a year in electronic format. Authors are invited to submit their articles in English or French in electronic form, preferably in Word to the Editor, (statcan.smj-rte.statcan@canada.ca, Statistics Canada, 150 Tunney’s Pasture Driveway, Ottawa, Ontario, Canada, K1A 0T6). For formatting instructions, please see the guidelines provided in the journal and on the web site (www.statcan.gc.ca/SurveyMethodology).

Note of appreciation

Canada owes the success of its statistical system to a long-standing partnership between Statistics Canada, the citizens of Canada, its businesses, governments and other institutions. Accurate and timely statistical information could not be produced without their continued co-operation and goodwill.

Standards of service to the public

Statistics Canada is committed to serving its clients in a prompt, reliable and courteous manner. To this end, the Agency has developed standards of service which its employees observe in serving its clients.

Copyright

Published by authority of the Minister responsible for Statistics Canada.

Use of this publication is governed by the Statistics Canada Open Licence Agreement.

Catalogue No. 12-001-X

Frequency: Semi-annual

Ottawa

Date modified:: 2022-06-21

Language selection

Search and menus

Search

A simulated annealing algorithm for joint stratification and sample allocation
Section 4. Outline of the simulated annealing algorithm

4.1 Perturbation

4.2 Evaluation and acceptance

4.3 Sequences and new strata

4.4 Temperature

A simulated annealing algorithm for joint stratification and sample allocation Section 4. Outline of the simulated annealing algorithm

4.1 Perturbation

4.2 Evaluation and acceptance

4.3 Sequences and new strata

4.4 Temperature

Editorial policy

Submission of Manuscripts

Note of appreciation

Standards of service to the public

Copyright

A simulated annealing algorithm for joint stratification and sample allocation
Section 4. Outline of the simulated annealing algorithm