Procedure: Generate a Halton design¶
Description and Background¶
A Halton design is one of a number of non-random space-filling designs suitable for defining a set of points in the simulator input space for creating a training sample.
The \(n\) point Halton design in \(p\) dimensions is generated by a generator set \(g=(g_1,\ldots,g_p)\) of prime numbers. See the “Additional Comments” below for discussion of the choice of generators.
Inputs¶
- Number of dimensions \(p\)
- Number of points desired \(n\)
- Set of prime generators \(g_1,\ldots,g_p\)
Outputs¶
- Halton design \(D = \{x_1, x_2, \ldots, x_n\}\)
Procedure¶
- For each \(i=1,2,\ldots,p\) and \(j=1,2,\ldots,n\), let \(a_{ij}\) be the representation in prime base \(g_i\) of the number \(j\). Let \(n_{ij}\) be the number of digits used for \(a_{ij}\) (i.e. \(n_{ij}\) is the logarithm to base \(g_i\) of \(j\), rounded up to the nearest integer), and let \(R_{ij}\) be the result of reversing the digits of \(a_{ij}\) and evaluating this as a number in base \(g_i\).
- For each \(i=1,2,\ldots,p\) and \(j=1,2,\ldots,n\), let \(x_{ij} = R_{ij} /g_i^{n_{ij}}\).
- For \(j=1,2,\ldots,n\), the j-th design point is \(x_j = (x_{1j}, x_{2j}, \ldots, x_{pj})\).
For example, if \(j=10\) and \(g_i=2\), then \(a_{ij}=1010\), from which we have \(n_{ij}=4\). Then \(R_{ij}\) is the binary number 0101, i.e 5, so that \(x_{ij}=5/2^4=0.3125\).
Additional Comments¶
A potential problem with Halton designs is the difficulty in finding suitable generators. One suggestion is to let \(g_i\) be the \(i\)-th prime, but this may not work well when \(p\) is large.
References¶
The following is a link to the repository for Matlab code for the Halton sequence in up to 11 dimensions: CPHaltonSequence.m (disclaimer).